On spanning connected graphs

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

Research output: Contribution to journalArticle

20 Scopus citations

Abstract

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
Volume308
Issue number7
DOIs
StatePublished - 6 Apr 2008

Keywords

  • 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

    Lin, C-K., Huang, H-M., Tan, J-M., & Hsu, L-H. (2008). On spanning connected graphs. Discrete Mathematics, 308(7), 1330-1333. https://doi.org/10.1016/j.disc.2007.03.072