×

Progress on sufficient conditions for a graph to have a spanning \(k\)-ended tree. (English) Zbl 1530.05029

Summary: Let \(G\) be a connected graph with vertex set \(V (G)\), we define \[\sigma_2 (G)=\min \{d(u)+d(v) \text{ for all non-adjacent vertices } u, v \in V (G)\}.\] Let \(K_{m, m+k}\) be a complete bipartite graph with bipartition \(V (K_{m, m+k}) = A \cup B\), \(|A| = m\), \(|B| = m + k\). Denote by \(H\) the graph obtained from \(K_{m, m+k}\) by adding (or not adding) some edges with two end vertices in \(A\). Let \(\mathcal{H}\) be the set of all connected graphs \(H\). In this paper, we prove that if \(G\) is a connected graph satisfying \(\sigma_2 (G) \geq |G| - k\) then \(G\) has a spanning \(k\)-ended tree except for the case \(G\) is isomorphic to a graph \(H \in \mathcal{H}\). This result is a generalization of the result by H. Broersma and H. Tuinstra [J. Graph Theory 29, No. 4, 227–237 (1998; Zbl 0919.05017)]. On the other hand, we also give a sufficient condition for a graph to have a few branch vertices as a corollary of our main result.

MSC:

05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 0919.05017

References:

[1] Broersma, H.; Tuinstra, H., Independence trees and Hamilton cycles, J. Graph Theory, 29, 227-237 (1998) · Zbl 0919.05017 · doi:10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W
[2] Diestel, R., Graph Theory, 3rd edn (2005), Berlin: Springer, Berlin · Zbl 1074.05001
[3] Ore, O., Note on hamiltonian circuits, Amer. Math. Mon., 67, 55 (1960) · Zbl 0089.39505 · doi:10.2307/2308928
[4] Ozeki, K.; Yamashita, T., Spanning trees: A survey, Graphs Combin., 27, 1-26 (2011) · Zbl 1232.05055 · doi:10.1007/s00373-010-0973-2
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.