Raziskovalni matematični seminar

We study square-complementary graphs, that is, graphs whose complement and square are isomorphic.

We prove several necessary conditions for a graph to be square-complementary, describe ways of building new square-complementary graphs from existing ones, construct infinite families of square-complementary graphs, give a characterization of natural numbers n for which there exists a square-complementary graph of order n, and characterize square-complementary graphs within various graph classes. The bipartite case turns out to be of particular interest.

Joint work with Anders Sune Pedersen, Daniel Pellicer and Gabriel Verret.