CLIQUE GRAPHS OF CHORDAL AND PATH GRAPHS

Authors
SZWARCFITER JL BORNSTEIN CF
Citation
Jl. Szwarcfiter et Cf. Bornstein, CLIQUE GRAPHS OF CHORDAL AND PATH GRAPHS, SIAM journal on discrete mathematics, 7(2), 1994, pp. 331-336
Citations number
10
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
7
Issue
2
Year of publication
1994
Pages
331 - 336
Database
ISI
SICI code
0895-4801(1994)7:2<331:CGOCAP>2.0.ZU;2-M
Abstract
Clique graphs of chordal and path graphs are characterized. A special class of graphs named expanded trees is discussed. It consists of a su bclass of disk-Helly graphs. It is shown that the clique graph of ever y chordal (hence path) graph is an expanded tree. In addition, every e xpanded tree is the clique graph of some path (hence chordal) graph. D ifferent characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing them.