z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here