On spanning connected graphs

Cheng-Kuan Lin, Hua-Min Huang, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.
Original languageEnglish
Pages (from-to)1330-1333
Number of pages4
JournalDiscrete Mathematics
Issue number7
StatePublished - 6 Apr 2008


  • Hamiltonian connected; Hamiltonian; Ore theorem; Menger theorem

Fingerprint Dive into the research topics of 'On spanning connected graphs'. Together they form a unique fingerprint.

Cite this