کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647147 | 1342330 | 2015 | 5 صفحه PDF | دانلود رایگان |
Liu and Xu (1998) and Ellingham, Nam and Voss (2002) independently showed that every kk-edge-connected simple graph GG has a spanning tree TT such that for each vertex vv, dT(v)≤⌈d(v)k⌉+2. In this paper we show that every kk-edge-connected graph GG has a spanning tree TT such that for each vertex vv, dT(v)≤⌈d(v)−2k⌉+2; also if GG has kk edge-disjoint spanning trees, then TT can be found such that for each vertex vv, dT(v)≤⌈d(v)−1k⌉+1. This result implies that every (r−1)(r−1)-edge-connected rr-regular graph (with r≥4r≥4) has a spanning Eulerian subgraph whose degrees lie in the set {2,4,6}{2,4,6}; also reduces the edge-connectivity needed for some theorems due to Barát and Gerbner (2014) and Thomassen (2008, 2013). Moreover these bounds for finding spanning trees are sharp.
Journal: Discrete Mathematics - Volume 338, Issue 8, 6 August 2015, Pages 1317–1321