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 an induced subgraph of a squco bipartite graph, that the problem of recognizing squco graphs is graph isomorphism complete, and that no nontrivial squco graph is both bipartite and planar. These results resolve three of the open problems posed in Discrete Math. 327 (2014) 62-75.

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment