HAMILTONICITY IN GRAPHS WITH FEW P-4S

被引：13

作者：

HOCHSTATTLER, W ^{[1
]}

TINHOFER, G ^{[1
]}

机构：

[1] TECH UNIV MUNICH,D-80290 MUNICH,GERMANY

来源：

COMPUTING | 1995年 / 54卷 / 03期

关键词：

HAMILTONICITY; P-4-CONNECTEDNESS; P-4-STRUCTURE; PATH COVER NUMBER; SCATTERING NUMBER;

D O I：

10.1007/BF02253613

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In a recent series of articles R. Jamison and S. Olariu developed, starting from an extension of the notion of a cograph, a theory of the decomposition of graphs into P-4-connected components. It turned out in their work that the algorithmic idea to exploit the unique tree structure of cographs can be generalized to graphs with simple P-4-structure. In this paper we will show that deciding hamiltonicity and computing the path covering number are easy tasks for P-4-sparse and P-4-extendible graphs. We thereby generalize a result of H. A. Jung [8] concerning cographs.

引用

页码：213 / 225

页数：13

共 8 条

[1]

Chvatal V., Tough graphs and Hamiltonian circuits, Discrete Mathematics, 5, pp. 215-228, (1973)

[2]

Corneil D.G., Lerch H., Stewart L., Complement reducible graphs, Discr. Appl. Math., 3, pp. 163-185, (1981)

[3]

Golumbic, Algorithmic graph theory and perfect graphs, (1980)

[4]

Jamison R., Olariu S., P4-reducible graphs—a class of uniquely tree-representable graphs, Stud. Appl. Math., 81, pp. 79-87, (1989)

[5]

Jamison R., Olariu S., On a unique tree representation for P4-extendible graphs, Discr. Appl. Math., 34, pp. 151-164, (1991)

[6]

Jamison R., Olariu S., A unique tree representation for P4-sparse graphs, Discr. Appl. Math., 35, pp. 115-129, (1992)

[7]

Jamison R., Olariu S., P-components and the homogeneous decomposition of graphs, (1994)

[8]

Jung H.A., On a class of posets and the corresponding comparability graphs, Journal of Comb. Theor. Ser. B, 24, pp. 125-133, (1978)

← 1 →