- Tytuł:
- On a Spanning $k$-Tree in which Specified Vertices Have Degree Less Than $k$
- Autorzy:
- Matsumura, Hajime
- Powiązania:
- https://bibliotekanauki.pl/articles/31339152.pdf
- Data publikacji:
- 2015-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
spanning tree
degree bounded tree
degree sum condition - Opis:
- 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 $\sigma_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 $\sigma_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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 191-196
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł