TY - JOUR

T1 - On spanning connected graphs

AU - Lin, Cheng-Kuan

AU - Huang, Hua-Min

AU - Tan, Jiann-Mean

AU - Hsu, Lih-Hsing

PY - 2008/4/6

Y1 - 2008/4/6

N2 - A k-container C(u, v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u, v) of G is a k*-container if the set of the vertices of all the paths in C(u, v) contains all the vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k*-connected graphs. (c) 2007 Published by Elsevier B.V.

AB - A k-container C(u, v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u, v) of G is a k*-container if the set of the vertices of all the paths in C(u, v) contains all the vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k*-connected graphs. (c) 2007 Published by Elsevier B.V.

KW - Hamiltonian connected; Hamiltonian; Ore theorem; Menger theorem

U2 - 10.1016/j.disc.2007.03.072

DO - 10.1016/j.disc.2007.03.072

M3 - Article

VL - 308

SP - 1330

EP - 1333

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 7

ER -