Complement of a graph: a generalization
type: Item
instance of: scholarly article
title: Complement of a graph: a generalization
zbMATH Open document ID: 0914.05056
DOI: 10.1007/BF02351593
author: E. Sampathkumar
author: L. Pushpalatha
published in: Graphs and Combinatorics
publication date: 1999-06-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1234341
zbMATH Keywords: \(k\)-complement
zbMATH Keywords: partition
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
cites work: Q5572939
cites work: Q3765795
Recommended article: Q4519725
Recommended article: Generalized complements of a graph
Recommended article: The partial complement of graphs
Recommended article: Q5115501
Recommended article: About graph complements
Recommended article: Compositions of complements of graphs
Recommended article: Q3616005
Recommended article: Partial complementation of graphs
Recommended article: Complement of the generalized total graph of Zn
description: scientific article; zbMATH DE number 1234341