Searching for square-complementary graphs: non-existence results and complexity of recognition

Ratko Darda, Martin Milanič, Miguel Pizaña

A graph is square-complementary (squco, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is…