zbMATH — the first resource for mathematics

Diameters of iterated clique graphs of chordal graphs. (English) Zbl 0726.05059
The clique graph K(G) of a graph G is the intersection graph of the cliques (i.e. the maximal complete subgraphs) of G. Iterated clique graphs \(K^ n(G)\) are defined as usual by \(K(K^{n-1}(G))\) for \(n\geq 2\), where \(K^ 1(G):=K(G)\). B. Hedman [J. Comb. Theory, Ser. B 37, 270-278 (1984; Zbl 0547.05056)] had shown that the difference of the diameters of K(G) and \(K^ n(G)\) equals n if G is a connected unit interval graph of diameter at least n. The main result of the present paper states this being true for connected chordal graphs also. Recall that a graph is chordal if every induced cycle is a triangle. A tool, but interesting for its own sake, is the following result: \(K^ 2(G)\), but not necessarily K(G), is chordal for any chordal graph G. Independently these results were also obtained by H. J. Bandelt and E. Prisner [J. Comb. Theory, Ser. B 51, No.1, 34-45 (1991; see following review)].

05C99 Graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Buneman, Discrete Math. 9 pp 205– (1974)
[2] Gavril, J. Combinat. Theory Ser. B 16 pp 47– (1974)
[3] Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054
[4] Hedman, J. Combinat. Theory Ser. B 37 pp 270– (1984)
[5] Walter, J. Graph Theory 2 pp 265– (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.