Partitioning a graph into two pieces, each isomorphic to the other or to its complement (Q2576840): Difference between revisions

In [J. Graph Theory 44, 1--14 (2003; Zbl 1028.05084)] \textit{A. Bonato} and \textit{R. Nowakowski} defined neighbour-closed-co-neigh\-bour graphs (ncc graphs) as follows: \(G\) is an ncc graph if for all vertices \(x\) of \(G\) the subgraph induced by the set of all neighbours of \(x\) is isomorphic to the subgraph induced by the set of all non-neighbours of \(x\). They characterized the ncc graphs and showed that the ncc graphs can be recognized in polynomial time. In this paper a generalization of the ncc graphs is given. A graph \(G\) is a generalized-neighbour-closed-co-neighbour graph (gncc graph) if for all vertices \(x\) of \(G\) the subgraph induced by the set of all neighbours of \(x\) is isomorphic to the subgraph induced by the set of all non-neighbours of \(x\) or to the complement of the subgraph induced by the set of all non-neighbours of \(x\). It is proved that each gncc graph is an ncc graph and therefore, the seemingly larger family of gncc graphs is equivalent to the family of ncc graphs.