×

On a spanning \(k\)-tree in which specified vertices have degree less than \(k\). (English) Zbl 1307.05052

Summary: 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 \geq 3\) and \(s \geq 0\) be integers, and suppose \(G\) is a connected graph and \(\sigma_k(G) \geq |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.

MSC:

05C05 Trees
05C35 Extremal problems in graph theory
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M.N. Ellingham, Y. Nam and H.-J. Voss, Connected (g, f)-factors, J. Graph Theory 39 (2002) 62-75. doi:10.1002/jgt.10019; · Zbl 0995.05117
[2] H. Enomoto and K. Ozeki, The independence number condition for the existence of a spanning f-tree, J. Graph Theory 65 (2010) 173-184. doi:10.1002/jgt.20471; · Zbl 1222.05023
[3] H. Matsuda and H.Matsumura, On a k-tree containing specified leaves in a graph, Graphs Combin. 22 (2006) 371-381. doi:10.1007/s00373-006-0660-5; · Zbl 1108.05028
[4] H.Matsuda and H.Matsumura, Degree conditions and degree bounded trees, Discrete Math. 309 (2009) 3653-3658. doi:10.1016/j.disc.2007.12.099; · Zbl 1226.05090
[5] V. Neumann-Lara and E. Rivera-Campo, Spanning trees with bounded degrees, Com- binatorica 11 (1991) 55-61. doi:10.1007/BF01375473; · Zbl 0763.05030
[6] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.; · Zbl 0089.39505
[7] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. doi:10.2307/2308928; · Zbl 0106.37103
[8] S. Win, Existenz von ger¨usten mit vorgeschriebenem maximalgrad in graphen, Abh. Math. Seminar Univ. Hamburg 43 (1975) 263-267. doi:10.1007/BF02995957; · Zbl 0309.05122
[9] S. Win, On a connection between the existence of k-trees and the toughness of a graph, Graphs Combin. 5 (1989) 201-205. doi:10.1007/BF01788671; · 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.