TY - JOUR
T1 - Closure and Spanning k-Trees
AU - Matsubara, Ryota
AU - Tsugaki, Masao
AU - Yamashita, Tomoki
PY - 2014/6
Y1 - 2014/6
N2 - In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that (Formula presented) for every independent set S in G of order k with u, v ∈ S. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win's result (Abh Math Sem Univ Hamburg, 43:263-267, 1975) and Kano and Kishimoto's result (Graph Comb, 2013) as corollaries.
AB - In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that (Formula presented) for every independent set S in G of order k with u, v ∈ S. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win's result (Abh Math Sem Univ Hamburg, 43:263-267, 1975) and Kano and Kishimoto's result (Graph Comb, 2013) as corollaries.
KW - Closure
KW - Spanning tree
KW - k-tree
UR - http://www.scopus.com/inward/record.url?scp=84903200626&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84903200626&partnerID=8YFLogxK
U2 - 10.1007/s00373-013-1314-z
DO - 10.1007/s00373-013-1314-z
M3 - Article
AN - SCOPUS:84903200626
SN - 0911-0119
VL - 30
SP - 957
EP - 962
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 4
ER -