On spanning connected graphs |
| |
Authors: | Cheng-Kuan Lin Hua-Min Huang Lih-Hsing Hsu |
| |
Institution: | a Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30010, ROC b Department of Mathematics, National Central University, Chungli, Taiwan 32001, ROC c Department of Computer Science and Information Engineering, Providence University, Taichung, Taiwan 43301, ROC |
| |
Abstract: | A k-containerC(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. |
| |
Keywords: | Hamiltonian connected Hamiltonian Ore Theorem Menger Theorem |
本文献已被 ScienceDirect 等数据库收录! |
|