5 CYCLE DOUBLE COVERS OF SOME CUBIC GRAPHS

被引：42

作者：

HUCK, A ^{[1
]}

KOCHOL, M ^{[1
]}

机构：

[1] SLOVAK ACAD SCI,INST INFORMAT,BRATISLAVA 84000,SLOVAKIA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1995年 / 64卷 / 01期

关键词：

D O I：

10.1006/jctb.1995.1029

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The main result of this paper can be roughly described as follows. Any bridgeless cubic graph G having a 2-factor with at most two odd components has a 5-cycle double cover, ie., there exists a collection L of five Eulerian subgraphs of G such that every edge of G is an edge of exactly two subgraphs in L. This generalizes and improves several known results. For instance, we can show that any graph with a Hamilton path has a 5-cycle double cover. (C) 1995 Academic Press, Inc.

引用

页码：119 / 125

页数：7

共 12 条

[1] CYCLE COVERS OF CUBIC MULTIGRAPHS [J].

ALSPACH, B ;

ZHANG, CQ .

DISCRETE MATHEMATICS, 1993, 111 (1-3) :11-17

[2]

ALSPACH BR, IN PRESS T AM MATH S

[3]

BONDY JA, 1976, GRAPH THEORY APPLICA

[4]

Celmins U., 1984, THESIS U WATERLOO WA

[5] CYCLE DOUBLE COVERS OF GRAPHS WITH HAMILTON PATHS [J].

GODDYN, LA .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :253-254

[6] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[7]

JAEGER F, 1985, ANN DISCRETE MATH, V27, P1, DOI DOI 10.1016/S0304-0208(08)72993-1

[8]

Seymour P.D., 1979, GRAPH THEORY RELATED, P341

[9]

Szekeres G., 1973, B AUST MATH SOC, V8, P367

[10] SEMI-DUALITY AND THE CYCLE DOUBLE COVER CONJECTURE [J].

TARSI, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (03) :332-340

← 1 2 →