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

08/03/2018
by   Ratko Darda, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset