On k-E nded Spanning and Dominating Trees
Keywords:
Hamilton cycle, Hamilton path, Dominating cycle, Dominating path, Longest path, k-ended treeAbstract
A tree with at most k leaves is called a k-ended tree. Let tk be the order of a largest k-ended tree in a graph. A tree T of a graph G is said to be dominating if V (G - T) is an independent set of vertices. The minimum degree sum of any pair (triple) of nonadjacent vertices in G will be denoted by σ2 (σ 3). The earliest result concerning spanning trees with few leaves (by the author, 1976) states: (*) if G is a connected graph of order n with σ2 ≥ n-k +1 for some positive integer k, then G has a spanning k-ended tree. In this paper we show: (i) the connectivity condition in (*) can be removed; (ii) the condition σ2 ≥ n - k + 1 in (*) can be relaxed by replacing n with tk+1; (iii) if G is a connected graph with σ3 ≥ tk+1 - 2k + 4 for some integer k ≥ 2, then G has a dominating k-ended tree. All results are sharp.
References
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.
G. A. Dirac, “Some theorems on abstract graphs", Proceedings of the London Mathematical Society, vol. 2, no. 3, pp. 69-81, 1952.
O. Ore, “A note on hamiltonian circuits", American Mathematical Monthly, vol. 67, p. 55, 1960.
M. Las Vergnas, “Sur une propriete des arbres maximaux dans un graphe", Comptes Rendus de l'Academie des sciences Paris Ser. A 272, pp. 1297-1300, 1971.
H. Broersma and H. Tuinstra, “Independence trees and Hamilton cycles", J. Graph Theory, vol. 29, no. 4, pp. 227-237, 1998.
Zh.G. Nikoghosyan, “Two theorems on spanning trees", Uchenie Zapiski EGU (Scientific Transactions of the Yerevan State University), Ser. Matematika, (in Russian), no. 3, pp. 3-6, 1976.
Zh. G. Nikoghosyan, “Theorems on Hamilton cycles and spanning trees",Molodoi nauchnii rabotnik, Ser. Natural Sciences, Yerevan State University, (in Russian), vol. 24, no. 2, pp. 15-20, 1976.
N . Chie, “On sufficient conditions for a graph to be hamiltonian", Natural Science, Ochanomizu University, vol. 31, no. 2, pp. 75-80, 1980.
K. Ozeki and T. Yamashita, “Spanning trees - A survey", Graphs Combinatorics, vol. 27, no. 1, pp. 1-26, 2011.
Zh. G. Nikoghosyan, “Spanning trees on 3-polytopes", Kibernetika, (in Russian), no. 4, pp. 35-42, 1982.
Zh. G. Nikoghosyan, “n-spanning and hypo-n-spanning graphs", Tanulmanyok, Budapest, (in Russian), no. 135, pp. 153-167, 1982.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
