Complement of a graph: a generalization (Q1272536)

From MaRDI portal
Revision as of 21:06, 17 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Complement of a graph: a generalization
scientific article

    Statements

    Complement of a graph: a generalization (English)
    0 references
    0 references
    0 references
    6 June 1999
    0 references
    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.
    0 references
    \(k\)-complement
    0 references
    partition
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references