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
    0 references

    Identifiers