Degree Bounded Spanning Trees

Jun Fujisawa, Hajime Matsumura, Tomoki Yamashita

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ⊆ of cardinality n(k-1) + c + 2, there exists a vertex set ⊆ of cardinality k such that the degree sum of vertices in X is at least {pipe}V(G){pipe} - c -1. Then G has a spanning tree T with maximum degree at most k + [c/n] and ∑ν∈V(T) max{dT (ν) - k, 0} ≤ c.

Original languageEnglish
Pages (from-to)695-720
Number of pages26
JournalGraphs and Combinatorics
Issue number5
Publication statusPublished - 2010 Sept
Externally publishedYes


  • Degree bounded tree
  • Degree sum condition
  • Independence number
  • Spanning tree
  • Total excess

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Degree Bounded Spanning Trees'. Together they form a unique fingerprint.

Cite this