A generalization of an ear decomposition and k-trees in highly connected star-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912527100674048 |
|---|---|
| author | Maezawa, Shun-ichi Ozeki, Kenta Yamamoto, Masaki Yashima, Takamasa |
| author_facet | Maezawa, Shun-ichi Ozeki, Kenta Yamamoto, Masaki Yashima, Takamasa |
| contents | In this paper, we introduce a generalized version of an ear decomposition, called a $j$-spider decomposition, for $j$-connected star-free graphs with $j \geq 2$. Its application enables us to improve a previousely known sufficient condition for the existence of a $k$-tree in highly connected star-free graphs, where a $k$-tree is a spanning tree in which every vertex is of degree at most $k$. More precisely, we show that every $j$-connected $K_{1,j(k-2)+2}$-free graph has a $k$-tree for $k\ge j$, thereby improving a classical result of Jackson and Wormald for $k\ge j$. Our approach differs from previous studies based on toughness-type arguments and instead relies on both a~$j$-spider decomposition and a factor theorem related to Hall's marriage theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05962 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A generalization of an ear decomposition and k-trees in highly connected star-free graphs Maezawa, Shun-ichi Ozeki, Kenta Yamamoto, Masaki Yashima, Takamasa Combinatorics 05C05, 05C35, 05C40 In this paper, we introduce a generalized version of an ear decomposition, called a $j$-spider decomposition, for $j$-connected star-free graphs with $j \geq 2$. Its application enables us to improve a previousely known sufficient condition for the existence of a $k$-tree in highly connected star-free graphs, where a $k$-tree is a spanning tree in which every vertex is of degree at most $k$. More precisely, we show that every $j$-connected $K_{1,j(k-2)+2}$-free graph has a $k$-tree for $k\ge j$, thereby improving a classical result of Jackson and Wormald for $k\ge j$. Our approach differs from previous studies based on toughness-type arguments and instead relies on both a~$j$-spider decomposition and a factor theorem related to Hall's marriage theorem. |
| title | A generalization of an ear decomposition and k-trees in highly connected star-free graphs |
| topic | Combinatorics 05C05, 05C35, 05C40 |
| url | https://arxiv.org/abs/2508.05962 |