Article in volume
Authors:
Title:
Degree sum condition for the existence of spanning $k$-trees in star-free graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 5-13
Received: 2018-02-12 , Revised: 2019-04-05 , Accepted: 2019-06-10 , Available online: 2021-11-29 , https://doi.org/10.7151/dmgt.2234
Abstract:
For an integer $k \geq 2$, a $k$-tree $T$ is defined as a tree with
maximum degree at most $k$. If a $k$-tree $T$ spans a graph $G$, then $T$ is
called a spanning $k$-tree of $G$. Since a spanning 2-tree is a
Hamiltonian path, a spanning $k$-tree is an extended concept of a Hamiltonian
path. The first result, implying the existence of $k$-trees in star-free graphs,
was by Caro, Krasikov, and Roditty in 1985, and independently, Jackson and
Wormald in 1990, who proved that for any integer $k$ with $k \geq 3$, every
connected $K_{1,k}$-free graph contains a spanning $k$-tree. In this paper,
we focus on a sharp condition that guarantees the existence of a spanning
$k$-tree in $K_{1,k+1}$-free graphs. In particular, we show that every connected
$K_{1,k+1}$-free graph $G$ has a spanning $k$-tree if the degree sum of any
$3k-3$ independent vertices in $G$ is at least $|G|-2$, where $|G|$ is the
order of $G$.
Keywords:
spanning tree, $k$-tree, star-free, degree sum condition
References:
- H. J. Broersma, Hamilton cycles in graphs and related topics (Ph.D-Thesis, University of Twente, 1998).
- Y. Caro, I. Krasikov, and Y. Roditty, Spanning trees and some edge reconstructible graphs, Ars Combin. 20 A (1985) 109–118.
- B. Jackson and N. C. Wormald, $k$-walks of graphs, Australas. J. Combin. 2 (1990) 135–146.
- Y. Liu, F. Tian, and Z. Wu, Some results on longest paths and cycles in $K_{1,3}$-free graphs, J. Changsha Railway Inst. 4 (1986) 105–106.
- O. Ore, Notes on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
- S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math Seminar Univ. Hamburg 43 (1975) 263–267.
Close