Construction of self-complementary graphs (Q1377771)

Given a fixed graph \(H\) of order \(2p\), a necessary and sufficient condition is presented for the existence of a self-complementary graph \(G\) of order \(4p\) that contains vertex disjoint copies of \(H\) and \(\overline{H}\), the complement of \(H\). It is shown that \(H\) must contain two vertex disjoint subgraphs \(H_1\) and \(H_2\) and an automorphism \(\phi\) such that \(\phi(H_1) = H_2\). An algorithm is presented that generates all such self-complementary graphs \(G\) that are derived from the graph \(H\).