Diameters of iterated clique graphs of chordal graphs. (English) Zbl 0726.05059

Chen, Bor-Liang; Lih, Ko-Wei

J. Graph Theory 14, No. 3, 391-396 (1990).

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

Reviewer: E.Prisner (Hamburg)

MSC:

05C99	Graph theory
05C38	Paths and cycles

Keywords:

clique graph; intersection graph; chordal graphs

References:

[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)