Construction of self-complementary graphs (Q1377771)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Construction of self-complementary graphs |
scientific article |
Statements
Construction of self-complementary graphs (English)
0 references
22 June 1998
0 references
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\).
0 references
self-complementary
0 references
graph automorphism
0 references