On k-E nded Spanning and Dominating Trees


  • Zhora G. Nikoghosyan Institute for Informatics and Automation Problems of NAS RA


Hamilton cycle, Hamilton path, Dominating cycle, Dominating path, Longest path, k-ended tree


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.


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.




How to Cite

Nikoghosyan, Z. G. . (2021). On k-E nded Spanning and Dominating Trees. Mathematical Problems of Computer Science, 43, 26–31. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/204