Iterated clique graphs with increasing diameters

✍ Scribed by Bornstein, Claudson F.; Szwarcfiter, Jayme L.

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 73 KB
• Volume: 28
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199807)28:3<147::aid-jgt4>3.0.co;2-k

✦ Synopsis

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(K i (G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(K i (G)) = diam(G) + i.