Graphs whose complement and cube are isomorphic

摘要

We study cube-complementary graphs, that is, graphs whose complement and cube are isomorphic. We prove several necessary conditions for a graph to be cube-complementary, describe ways of building new cube-complementary graphs from existing ones, and construct infinite families of cube-complementary graphs.