Complement of a graph: a generalization (Q1272536): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:56, 31 January 2024
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
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