Neighborhood union condition for the existence of spanning k-trees in star-free graphs
Zhenzhen Ma, Tao Tian
Source record
Source: Crossref
Published: Oct 17, 2025
DOI: 10.1142/s179383092550137x
Open original source ↗Source abstract
For an integer [Formula: see text], a [Formula: see text]-tree [Formula: see text] is defined to be a tree [Formula: see text] with maximum degree at most [Formula: see text]. If a [Formula: see text]-tree [Formula: see text] spans a graph [Formula: see text], then [Formula: see text] is called a spanning [Formula: see text]-tree of [Formula: see text]. Since a spanning [Formula: see text]-tree is a Hamiltonian path, a spanning [Formula: see text]-tree is an extended concept of a Hamiltonian path. In this paper, we focus on a sharp condition that guarantees the existence of a spanning [Formula: see text]-tree in [Formula: see text]-free graphs. We show that every connected [Formula: see text]-free graph [Formula: see text] has a spanning [Formula: see text]-tree if the cardinality of the neighborhood union of any [Formula: see text] independent vertices in [Formula: see text] is at least [Formula: see text], where [Formula: see text] is the order of [Formula: see text].
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.