On regular 2-connected 2-path Hamiltonian graphs

Authors

Abstract: A graph

G

is

l

-path Hamiltonian if every path of length not exceeding

l

is contained in a Hamiltonian cycle. It is well known that a 2-connected,

k

-regular graph

G

on at most

3 k - 1

vertices is edge-Hamiltonian if for every edge

u v

of

G

,

u, v

is not a cut-set. Thus

G

is 1-path Hamiltonian if

G s e t m i n u s u, v

is connected for every edge

u v

of

G

. Let

P = u v z

be a 2-path of a 2-connected,

k

-regular graph

G

on at most

2 k

vertices. In this paper, we show that there is a Hamiltonian cycle containing the 2-path

P

if

G s e t m i n u s V (P)

is connected. Therefore, the work implies a condition for a 2-connected,

k

-regular graph to be 2-path Hamiltonian. An example shows that the

2 k

is almost sharp, i.e., the number is at most

2 k + 1

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: On regular 2-connected 2-path Hamiltonian graphs