Disconnected 2-factors in planar cubic bridgeless graphs

被引：18

作者：

Diwan, AA ^{[1
]}

机构：

[1] Indian Inst Technol, Dept Comp Sci & Engn, Bombay 400076, Maharashtra, India

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2002年 / 84卷 / 02期

关键词：

2-factor; Cubic; Disconnected; Planar;

D O I：

10.1006/jctb.2001.2079

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every planar cubic bridgeless graph with at least six vertices has a disconnected 2-ractor, that is a 2-factor which is not a Hamilton cycle. This is in contrast to the fact that there exist arbitrarily large cubic bridgeless graphs in which every 2-factor is a Hamilton cycle. (C) 2002 Elsevier Science (USA).

引用

页码：249 / 259

页数：11

共 9 条

[1]

[Anonymous], 1891, Acta Mathematica, DOI DOI 10.1007/BF02392606

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

Diestel R., 1997, Graduate Texts in Mathematics, V173

[4] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[5]

Garey M. R., 1976, SIAM Journal on Computing, V5, P704, DOI 10.1137/0205049

[6]

Hall P, 1935, J. Lond. Math. Soc., Vs1-10, P26, DOI [10.1112/jlms/s1-10.37.26, DOI 10.1112/JLMS/S1-10.37.26]

[7]

Hell P., 1988, SIAM J DISCRETE MATH, V1, P472

[8]

Tutte W.T., 1947, J. London Math. Soc., V22, P107, DOI DOI 10.1112/JLMS/S1-22.2.107

[9] THE FACTORS OF GRAPHS [J].

TUTTE, WT .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1952, 4 (03) :314-328

← 1 →