Meyniel weakly triangulated graphs .2. A theorem of Dirac

被引：5

作者：

Hayward, RB

机构：

[1] Dept. of Math. and Computer Science, University of Lethbridge, Lethbridge, AB T1K 3M4

来源：

DISCRETE APPLIED MATHEMATICS | 1997年 / 78卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

weakly triangulated graph; Meyniel graph; handle;

D O I：

10.1016/S0166-218X(97)00058-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We generalize a theorem due to Dirac and show that every Meyniel weakly trianylated graph has some vertex which is not the middle vertex of any P-5. Our main tool is a separating set notion known as a handle. (C) 1997 Elsevier Science B.V.

引用

页码：283 / 289

页数：7

共 12 条

[1] CHARACTERIZATIONS OF TOTALLY BALANCED MATRICES [J].

ANSTEE, RP ;

FARBER, M .

JOURNAL OF ALGORITHMS, 1984, 5 (02) :215-230

[2]

BROUWER AE, 1980, 14680 ZW MATH CENTR

[3]

CHVTAL V, 1993, IN PRESS P 1993 WORK

[4]

DATRI A, 1984, 3RD P ACM S PODS, P1

[5]

Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI DOI 10.1007/BF02992776

[6] A CHARACTERIZATION OF SOME GRAPH CLASSES WITH NO LONG HOLES [J].

ESCHEN, E ;

SRITHARAN, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 65 (01) :156-162

[7] WEAKLY TRIANGULATED GRAPHS [J].

HAYWARD, RB .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (03) :200-209

[8]

HAYWARD RB, DMCSTRCS0294 U LETHB

[9] ON BRITTLE GRAPHS [J].

HOANG, CT ;

KHOUZAM, N .

JOURNAL OF GRAPH THEORY, 1988, 12 (03) :391-404

[10] A CHARMING CLASS OF PERFECTLY ORDERABLE GRAPHS [J].

HOANG, CT ;

MAFFRAY, F ;

OLARIU, S ;

PREISSMANN, M .

DISCRETE MATHEMATICS, 1992, 102 (01) :67-74

← 1 2 →