Two Characterizations of Hypercubes

Juhani Nieminen, Matti Peltola, Pasi Ruotsalainen


Two characterizations of hypercubes are given: 1) A graph is a hypercube if and only if it is antipodal and bipartite $(0,2)$-graph. 2) A graph is an $n$-hypercube if and only if there are $n$ pairs of prime convexes, the graph is a prime convex intersection graph, and each intersection of $n$ prime convexes (no one of which is from the same pair) is a vertex.

Full Text: PDF