On the honesty of graph complements
type: Item
instance of: scholarly article
title: On the honesty of graph complements
zbMATH Open document ID: 0796.05060
DOI: 10.1016/0012-365X(93)90282-X
author: K. S. Bagga
author: L. W. Beineke
author: Marc J. Lipman
author: Raymond E. Pippert
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: The focus here is on honest graphs (see the previous review for definitions) with the main result being that if \(G \neq P_ 4\) then \(G\) or \(\overline G\) is honest. As a corollary it follows that every self- complementary graph of order at least 5 is honest thus answering the closing question cited in the previous review. Note that almost all graphs are honest since, as the authors showed earlier [Congr. Numerantium 60, 141-144 (1987; Zbl 0664.05039)]: if \(G\) has diameter 2 then \(G\) is honest. Also, Theorem 8 quoted in the previous review is improved by showing that the conclusion still holds even though the order of \(G\) is 2 unless \(G=K_ 2\) and \(H=K_ 3\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 500624
zbMATH Keywords: integrity
zbMATH Keywords: honest graphs
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q3815334
cites work: Edge-integrity: A survey
cites work: Q3789603
cites work: On the edge-integrity of some graphs and their complements
Recommended article: Q3472139
Recommended article: Q3490019
Recommended article: On the edge-integrity of some graphs and their complements
Recommended article: Q3571793
Recommended article: On Integrity of Harary Graphs
Recommended article: Q5115501
Recommended article: Q3815334
Recommended article: Q4871150
Recommended article: Validity up to complementation in graph theory
Recommended article: On the weak-integrity of graphs
description: scientific article; zbMATH DE number 500624