CLIQUE GRAPHS OF CHORDAL AND PATH GRAPHS

被引：32
作者：
SZWARCFITER, JL
BORNSTEIN, CF
机构：
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 02期
关键词：
ALGORITHMS; CHORDAL GRAPHS; CLIQUE GRAPHS; PATH GRAPHS;
D O I：
10.1137/S0895480191223191
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Clique graphs of chordal and path graphs are characterized. A special class of graphs named expanded trees is discussed. It consists of a subclass of disk-Helly graphs. It is shown that the clique graph of every chordal (hence path) graph is an expanded tree. In addition, every expanded tree is the clique graph of some path (hence chordal) graph. Different characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing them.
引用
收藏
页码：331 / 336
页数：6
相关论文
共 10 条
[1]   CLIQUE GRAPHS AND HELLY GRAPHS [J].
BANDELT, HJ ;
PRISNER, E .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 51 (01) :34-45
[2]   DISMANTLING ABSOLUTE RETRACTS OF REFLEXIVE GRAPHS [J].
BANDELT, HJ ;
PESCH, E .
EUROPEAN JOURNAL OF COMBINATORICS, 1989, 10 (03) :211-220
[3]  
Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8
[4]   DIAMETERS OF ITERATED CLIQUE GRAPHS OF CHORDAL GRAPHS [J].
CHEN, BL ;
LIH, KW .
JOURNAL OF GRAPH THEORY, 1990, 14 (03) :391-396
[5]  
Gavril F., 1974, Journal of Combinatorial Theory, Series B, V16, P47, DOI 10.1016/0095-8956(74)90094-X
[6]   INTERSECTION GRAPHS OF PATHS IN A TREE [J].
MONMA, CL ;
WEI, VK .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :141-181
[7]   VERTEX-TO-VERTEX PURSUIT IN A GRAPH [J].
NOWAKOWSKI, R ;
WINKLER, P .
DISCRETE MATHEMATICS, 1983, 43 (2-3) :235-239
[8]   THE SMALLEST GRAPH VARIETY CONTAINING ALL PATHS [J].
NOWAKOWSKI, R ;
RIVAL, I .
DISCRETE MATHEMATICS, 1983, 43 (2-3) :223-234
[9]   CONVERGENCE OF ITERATED CLIQUE GRAPHS [J].
PRISNER, E .
DISCRETE MATHEMATICS, 1992, 103 (02) :199-207
[10]  
QUILLIOT A, 1985, J COMB THEORY A, P186
1