×

Degree conditions and degree bounded trees. (English) Zbl 1226.05090

Summary: We give sufficient conditions for a graph to have degree bounded trees. Let \(G\) be a connected graph and \(A\) a vertex subset of \(G\). We denote by \(\sigma _k(A)\) the minimum value of the degree sum in \(G\) of any \(k\) independent vertices in \(A\) and by \(w(G - A)\) the number of components in the induced subgraph \(G - A\). Our main results are the following: (i) If \(\sigma _k(A)\geq |V(G)| - 1\), then \(G\) contains a tree \(T\) with maximum degree at most \(k\) and \(A \subseteq V(T)\). (ii) If \(\sigma _{k-w(G-A)}(A)\geq |A| - 1\), then \(G\) contains a spanning tree \(T\) such that \(d_T(x)\leq k\) for every \(x \in A\).
These are generalizations of the result achieved by S. Win [“Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen,” Abh. Math. Semin. Univ. Hamb. 43, 263–267 (1975; Zbl 0309.05122)] and the degree conditions are sharp.

MSC:

05C07 Vertex degrees
05C05 Trees

Citations:

Zbl 0309.05122
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B.; Brightwell, G., Cycles through specified vertices, Combinatorica, 13, 147-155 (1993) · Zbl 0780.05033
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan, Elsevier: Macmillan, Elsevier London · Zbl 1134.05001
[3] Broersma, H.; Li, H.; Li, J.; Tian, F.; Veldman, H. J., Cycles through subsets with large degree sums, Discrete Math., 171, 43-54 (1997) · Zbl 0883.05089
[4] Čada, R.; Flandrin, E.; Li, H.; Ryjáček, Z., Cycles through given vertices and closures, Discrete Math., 276, 65-80 (2004) · Zbl 1031.05072
[5] Favaron, O.; Flandrin, E.; Li, H.; Liu, Y.; Tian, F.; Wu, Z., Sequences, claws and cyclability of graphs, J. Graph Theory, 21, 357-369 (1996) · Zbl 0849.05045
[6] Ore, O., Note on Hamilton circuits, Amer. Math. Monthly, 67, 55 (1960) · Zbl 0089.39505
[7] Ota, K., Cycles through prescribed vertices with large degree sum, Discrete Math., 145, 201-210 (1995) · Zbl 0838.05071
[8] Shi, R., 2-neighborhoods and Hamiltonian conditions, J. Graph Theory, 16, 267-271 (1992) · Zbl 0761.05066
[9] Win, S., Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg, 43, 263-267 (1975) · Zbl 0309.05122
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.