On a conjecture of Las Vergnas concerning certain spanning trees in graphs
On a conjecture of Las Vergnas concerning certain spanning trees in graphs
复制标题
DOI：
10.1007/bf03322958
复制
发表时间：
1979-03
影响因子：
2.2
通讯作者：
S. Win
中科院分区：
文献类型：
--
作者：
S. Win
Chvatal-Erdos [1]证明了如下定理：如果对一个（有限）图G有f3 o（G）sK（G）+ 1，则G有一条Hamilton路。(Here f3 o（G），K（G）分别表示G的点独立数和连通度。M. Las Vergnas（C.如果f3 o（G）sK（G）+ kl，则G有至多k个端点的生成树。我们称这样的树为k端树。本文将给出Las Vergnas猜想的一个证明。主要的工具将是图G中的顶点、路径和回路的k端系统的概念，这将在下面定义。
Chvatal-Erdos [1] proved the following theorem: If for a (finite) graph G there holds f3o (G) sK (G)+ 1 then G has a Hamiltonian path.(Here f3o (G), K (G) denote the vertex independence number and the connectivity of G, respectively.) A generalization of this result was conjectured by M. Las Vergnas (oral communication by C. Thomassen): If f3o (G) sK (G)+ kl, then G has a spanning tree with at most k endpoints. We shall call such a tree a k-ended tree. In this note a proof of Las Vergnas' conjecture will be given. The main tool will be the notion of a k-ended system of vertices, paths and circuits in a graph G, which will be defined below.