DEGREE SUM CONDITION FOR THE EXISTENCE OF SPANNING k-TREES IN STAR-FREE GRAPHS

Michitaka Furuya, Shun Ichi Maezawa, Ryota Matsubara, Haruhide Matsuda, Shoichi Tsuchiya, Takamasa Yashima

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

For an integer k ≥ 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 ≥ 3, every connected K1,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 K1,k+1-free graphs. In particular, we show that every connected K1,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.

Original languageEnglish
Pages (from-to)5-13
Number of pages9
JournalDiscussiones Mathematicae - Graph Theory
Volume42
Issue number1
DOIs
Publication statusPublished - 2022

Keywords

  • degree sum condition
  • k-tree
  • spanning tree
  • star-free

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'DEGREE SUM CONDITION FOR THE EXISTENCE OF SPANNING k-TREES IN STAR-FREE GRAPHS'. Together they form a unique fingerprint.

Cite this