Complement of a graph: a generalization (Q1272536)

Let \(P=\{V_1,\dots,V_p\}\) be a partition of the vertex set of a graph \(G=(V,E)\) with \(| V| =p\) into singleton sets. Removing the edge between \(V_i\) and \(V_j\) (if it exists) and adding this edge elsewhere results in the well-known complement of \(G\). The authors study a similar operation for a partition of arbitrary order \(k\) with \(2\leq k\leq p\). In this case all edges of \(G\) between \(V_i\) and \(V_j\) must be removed and all nonexisting edges between \(V_i\) and \(V_j\) must be added to \(G\). The resulting graph is called \(k\)-complement of \(G\) with respect to the partition \(P\). The graph \(G\) is called \(k\)-self complementary, if it is isomorphic to its \(k\)-complement with respect to some partition \(P\). Examples of \(k\)-self complementary graphs include complete binary trees, stars, double-stars, cycles \(C_4\), \(C_6\), and \(C_8\). The authors provide a complete characterization of \(k\)-self complementary trees, forests and connected unicyclic graphs.