On the honesty of graph complements (Q1313844): Difference between revisions

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\).