×

Spanning trees and spanning Eulerian subgraphs with small degrees. (English) Zbl 1310.05058

Summary: Z. Liu and B. Xu [J. Graph Theory 28, No. 2, 87–95 (1998; Zbl 0923.05015)] and M. N. Ellingham et al. [ibid. 39, No. 1, 62–75 (2002; Zbl 0995.05117)] independently showed that every \(k\)-edge-connected simple graph \(G\) has a spanning tree \(T\) such that for each vertex \(v\), \(d_T(v) \leq \lceil \frac{d(v)}{k} \rceil + 2\). In this paper we show that every \(k\)-edge-connected graph \(G\) has a spanning tree \(T\) such that for each vertex \(v\), \(d_T(v) \leq \lceil \frac{d(v) - 2}{k} \rceil + 2\); also if \(G\) has \(k\) edge-disjoint spanning trees, then \(T\) can be found such that for each vertex \(v\), \(d_T(v) \leq \lceil \frac{d(v) - 1}{k} \rceil + 1\). This result implies that every \((r - 1)\)-edge-connected \(r\)-regular graph (with \(r \geq 4\)) has a spanning Eulerian subgraph whose degrees lie in the set \(\{2, 4, 6 \}\); also reduces the edge-connectivity needed for some theorems due to J. Barát and D. Gerbner [Electron. J. Comb. 21, No. 1, Research Paper P1.55, 11 p. (2014; Zbl 1300.05243)] and C. Thomassen [J. Graph Theory 58, No. 4, 286–292 (2008; Zbl 1214.05134); Combinatorica 33, No. 1, 97–123 (2013; Zbl 1299.05270)]. Moreover these bounds for finding spanning trees are sharp.

MSC:

05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, Jørgen; Thomassé, Stéphan; Yeo, Anders, Small degree out-branchings, J. Graph Theory, 42, 4, 297-307 (2003) · Zbl 1018.05041
[2] Barát, János; Gerbner, Dániel, Edge-decomposition of graphs into copies of a tree with four edges, Electron. J. Combin., 21, 1, 11 (2014), Paper 1.55 · Zbl 1300.05243
[3] Barát, János; Thomassen, Carsten, Claw-decompositions and Tutte-orientations, J. Graph Theory, 52, 2, 135-146 (2006) · Zbl 1117.05088
[4] Broersma, H. J.; Kriesell, M.; Ryjác˘ek, Z., On factors of 4-connected claw-free graphs, J. Graph Theory, 37, 2, 125-136 (2001) · Zbl 0984.05067
[5] Catlin, Paul A., A reduction method to find spanning Eulerian subgraphs, J. Graph Theory, 12, 1, 29-44 (1988) · Zbl 0659.05073
[6] Czumaj, Artur; Strothmann, Willy-B., Bounded degree spanning trees (extended abstract), (Algorithms—ESA’97 (Graz). Algorithms—ESA’97 (Graz), Lecture Notes in Comput. Sci., vol. 1284 (1997), Springer: Springer Berlin), 104-117 · Zbl 1477.68215
[7] Ellingham, M. N., Yunsun Nam, and Heinz-Jürgen Voss. Connected \((g, f)\)-factors, J. Graph Theory, 39, 1, 62-75 (2002)
[8] Ellingham, M. N.; Zha, Xiaoya, Toughness, trees, and walks, J. Graph Theory, 33, 3, 125-137 (2000) · Zbl 0951.05068
[9] Fürer, Martin; Raghavachari, Balaji, Approximating the minimum-degree Steiner tree to within one of optimal, Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, 1992. Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, 1992, J. Algorithms, 17, 3, 409-423 (1994) · Zbl 1321.05262
[10] Jaeger, F., A note on sub-Eulerian graphs, J. Graph Theory, 3, 1, 91-93 (1979) · Zbl 0396.05034
[11] Liu, Zhenhong; Xu, Baoguang, On low bound of degree sequences of spanning trees in \(K\)-edge-connected graphs, J. Graph Theory, 28, 2, 87-95 (1998) · Zbl 0923.05015
[12] Meredith, G. H.J., Regular \(n\)-valent \(n\)-connected nonHamiltonian non-\(n\)-edge-colorable graphs, J. Combinatorial Theory Ser. B, 14, 55-60 (1973) · Zbl 0237.05106
[13] Nash-Williams, C. St. J.A., Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805
[14] Thomassen, Carsten, Decompositions of highly connected graphs into paths of length 3, J. Graph Theory, 58, 4, 286-292 (2008) · Zbl 1214.05134
[15] Thomassen, Carsten, Decomposing graphs into paths of fixed length, Combinatorica, 33, 1, 97-123 (2013) · Zbl 1299.05270
[16] Tutte, W. T., On the problem of decomposing a graph into \(n\) connected factors, J. Lond. Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001
[17] Win, Sein, On a connection between the existence of \(k\)-trees and the toughness of a graph, Graphs Combin., 5, 2, 201-205 (1989) · Zbl 0673.05054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.