Premium
Spanning Trees with Vertices Having Large Degrees
Author(s) -
Egawa Yoshimi,
Ozeki Kenta
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21824
Subject(s) - combinatorics , mathematics , spanning tree , minimum degree spanning tree , vertex (graph theory) , connectivity , shortest path tree , graph , simple graph , degree (music) , minimum spanning tree , connected dominating set , discrete mathematics , physics , acoustics
Let G be a connected simple graph, and let f be a mapping from V ( G ) to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex v has degree at least f ( v ) . We show that if | Γ G ( S ) | − f ( S ) + | S | ≥ 1 for any nonempty subset S ⊆ L , then a connected graph G has a spanning tree such thatd T ( x ) ≥ f ( x )for all x ∈ V ( G ) , whereΓ G ( S )is the set of neighbors v of vertices in S with v ∉ S , L = { x ∈ V ( G ) : f ( x ) ≥ 2 } , andd T ( x )is the degree of x in T . This is an improvement of several results, and the condition is best possible.