×

zbMATH — the first resource for mathematics

Intersection number and edge clique graphs of chordal and strongly chordal graphs. (English) Zbl 0668.05057
Combinatorics, graph theory, and computing, Proc. 19th Southeast. Conf., Boca Raton/Fla. 1988, Congr. Numerantium 67, 197-204 (1988).
[For the entire collection see Zbl 0665.00002.]
The edge clique graph C(G) of a graph G has the edges of G as vertices. Two such vertices are adjacent in C(G) if some clique of G contains both corresponding edges. The author gives another proof of the theorem of M. O. Albertson and K. L. Collins [J. Comb. Theory, Ser. B 36, 298-309 (1984; Zbl 0527.05032)] that the edge clique graph of any chordal graph is chordal. Then F. Gavril’s [SIAM J. Comp. 1, 180- 187 (1972; Zbl 0227.05116)] minimum clique-vertex cover algorithm can be applied to find minimum clique-edge covers of chordal graphs. Finally he shows that the edge clique graph of any strongly chordal graph remains strongly chordal.
Reviewer: E.Prisner

MSC:
05C99 Graph theory
05C35 Extremal problems in graph theory
05C38 Paths and cycles