On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k

Hajime Matsumura. "On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k." Discussiones Mathematicae Graph Theory 35.1 (2015): 191-196. <http://eudml.org/doc/271232>.

@article{HajimeMatsumura2015,
abstract = {A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than k. The degree condition is sharp.},
author = {Hajime Matsumura},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {spanning tree; degree bounded tree; degree sum condition},
language = {eng},
number = {1},
pages = {191-196},
title = {On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k},
url = {http://eudml.org/doc/271232},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Hajime Matsumura
TI - On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 191
EP - 196
AB - A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than k. The degree condition is sharp.
LA - eng
KW - spanning tree; degree bounded tree; degree sum condition
UR - http://eudml.org/doc/271232
ER -