DISTANCES IN COCOMPARABILITY GRAPHS AND THEIR POWERS

被引：20

作者：

DAMASCHKE, P

机构：

[1] Mathematische Fakultät, Friedrich-Schiller-Universität Jena, 6900 Jena, Universitätshochhaus, 17. OG, O

来源：

DISCRETE APPLIED MATHEMATICS | 1992年 / 35卷 / 01期

关键词：

D O I：

10.1016/0166-218X(92)90296-M

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let ccp denote the class of cocomparability graphs. We characterize ccp by a distance inequality. As a consequence we show: If G is-an-element-of ccp, then the kth power G(k) also belongs to ccp, for any k greater-than-or-equal-to 1. As a further result we get that such graphs G(k) (G is-an-element-of ccp, k greater-than-or-equal-to 2) have no induced subgraphs isomorphic to K1,4 or K2,3.

引用

页码：67 / 72

页数：6

共 11 条

[1]

Berge C, 1985, GRAPHS

[2] THE K-DOMINATION AND K-STABILITY PROBLEMS ON SUN-FREE CHORDAL GRAPHS [J].

CHANG, GJ ;

NEMHAUSER, GL .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03) :332-345

[3]

DAHLHAUS E, 1987, ARS COMBIN B, V24, P23

[4]

Damaschke P., 1990, TOPICS COMBINATORICS, P219

[5]

DUCHET P, 1979, THESIS U PARIS 6

[6]

Duchet P., 1984, ANN DISCRETE MATH, V88, P67

[7] ON POWERS AND CENTERS OF CHORDAL GRAPHS [J].

LASKAR, R ;

SHIER, D .

DISCRETE APPLIED MATHEMATICS, 1983, 6 (02) :139-147

[8]

Lubiw A., 1982, THESIS U WATERLOO

[9]

Mohring R. H., 1987, COMPUTATIONALLY TRAC

[10]

Raychaudhuri A, 1987, C NUMER, V59, P235

← 1 2 →