Hamiltonicity in connected regular graphs

被引：5

作者：

Cranston, Daniel W. ^{[1
]}

Suil, O. ^{[2
]}

机构：

[1] Virginia Commonwealth Univ, Dept Math & Appl Math, Richmond, VA 23284 USA

[2] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 22-24期

关键词：

Combinatorial problems; Hamiltonicity; Regular graphs; CYCLES;

D O I：

10.1016/j.ipl.2013.08.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle. Published by Elsevier B.V.

引用

页码：858 / 860

页数：3

共 6 条

[1]

[Anonymous], 2001, Introduction to Graph Theory

[2]

HILBIG F, 1986, THESIS TU BERLIN

[3] HAMILTON CYCLES IN REGULAR 2-CONNECTED GRAPHS [J].

JACKSON, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 29 (01) :27-46

[4] CYCLES THROUGH VERTICES OF LARGE MAXIMUM DEGREE [J].

JACKSON, B .

JOURNAL OF GRAPH THEORY, 1995, 19 (02) :157-168

[5] Matching and edge-connectivity in regular graphs [J].

O, Suil ;

West, Douglas B. .

EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (02) :324-329

[6] Balloons, Cut-Edges, Matchings, and Total Domination in Regular Graphs of Odd Degree [J].

Suil, O. ;

West, Douglas B. .

JOURNAL OF GRAPH THEORY, 2010, 64 (02) :116-131

← 1 →