Two Characterizations of Hypercubes

  • Juhani Nieminen
  • Matti Peltola
  • Pasi Ruotsalainen
DOI: https://doi.org/10.37236/584

Abstract

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.

Published
2011-04-29
Issue
Volume 18, Issue 1 (2011)
Article Number
P97