On 2-Connected Spanning Subgraphs with Bounded Degree in K
1,r
-Free Graphs |
| |
| Authors: | Roman Ku?el Jakub Teska |
| |
| Institution: | 1. Department of Mathematics, University of West Bohemia, Univerzitn?? 8, 306 14, Plze??, Czech Republic
2. Institute for Theoretical Computer Science, Charles University, Univerzitn?? 8, 306 14, Plze??, Czech Republic
|
| |
| Abstract: | For any integer r > 1, an r-trestle of a graph G is a 2-connected spanning subgraph F with maximum degree Δ(F) ≤ r. A graph G is called K
1,r
-free if G has no K
1,r
as an induced subgraph. Inspired by the work of Ryjáček and Tkáč, we show that every 2-connected K
1,r
-free graph has an r-trestle. The paper concludes with a corollary of this result for the existence of k-walks. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
