Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650753 | Discrete Mathematics | 2008 | 4 Pages |
Abstract
A k-container C(u,v)C(u,v) of G between uu and vv is a set of k internally disjoint paths between uu and vv. A k -container C(u,v)C(u,v) of G is a k*k*-container if the set of the vertices of all the paths in C(u,v)C(u,v) contains all the vertices of G. A graph G is k*k*-connected if there exists a k*k*-container between any two distinct vertices. Therefore, a graph is 1*1*-connected (respectively, 2*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*k*-connected graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Cheng-Kuan Lin, Hua-Min Huang, Jimmy J.M. Tan, Lih-Hsing Hsu,