Complement of a graph: a generalization (Q1272536): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: L. Pushpa Latha / rank | |||
Property / reviewed by | |||
Property / reviewed by: Sergei L. Bezrukov / rank | |||
Property / author | |||
Property / author: L. Pushpa Latha / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sergei L. Bezrukov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3765795 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:43, 28 May 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