Spanning Trees with few Branch and end Vertices
Keywords:
Spanning tree, End vertex, k-ended tree, Branch vertex, Degree sum of the branch vertices, Ore-type conditionAbstract
For a graph G, let σ2 be the minimum degree sum of two nonadjacent vertices in G. A vertex of degree one in a tree is called an end vertex and a vertex of degree at least three is called a branch vertex. We consider: (*) connected graphs on n vertices such that σ2 ≥ n - k + 1 for some positive integer k. In 1976, it was proved (by the author) that every graph satisfying (*), has a spanning tree with at most k end vertices. In this paper we first show that every graph satisfying (*), has a spanning tree with at most k +1 branch and end vertices altogether. The next result states that every graph satisfying (*), has a spanning tree with at most 1/2 (k - 1) branch vertices. The third result states that every graph satisfying (*), has a spanning tree with at most 3/2 (k -1) degree sum of branch vertices. 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", Proc. London, Math. Soc., vol.2, pp. 69-81, 1952.
O. Ore, “A note on hamiltonian circuits", Am. Math. Month., vol. 67, page 55, 1960.
V. Chvátal and P. Erdös, “A noe on hamiltonian circuits", Discrete Math., vol. 2, pp. 111-113, 1972.
M. Las Vergnas, “Sur une propriété des arbres maximaux dans un graphe", 1972 C.R. Acad.Sci.Paris Ser. A, vol. 272, pp. 1297-1300, 1971.
Zh.G. Nikoghosyan, “Two theorems on spanning trees", Uchenie Zapiski E GU (Scientific Transactions of the Yerevan State University), Ser. Matematika, (in Russian), no. 3, pp. 36, 1976.
H. Broersma and H. Tuinstra, “Independence trees and Hamilton cycles", J. Graph Theory, vol. 29, pp. 227-237, 1998.
S. Win, “On a conjecture of Las Vergnas concerning certain spanning trees in graphs", Resultate Math., vol. 2, pp. 215-224, 1979.
L. Gargano, P. Hell, L. Stacho and U. Vaccaro, “Spanning trees with bounded number of branch vertices", Lecture notes in Comput. Sci., vol. 2380, pp. 355-365, 2002.
E. Flandrin, T. Kaiser, R. Kuzel, H. Li and Z. Ryjácek, “Neighborhood unions and extremal spanning trees", Discrete Math., vol. 308, pp. 2343-2350, 2008.
H. Matsuda, K. Ozeki and T. Yamashita, “Spanning trees with a bounded number of branch vertices in a claw-free graph", Graphs and Combin. vol. 30, pp. 429-437, 2014.
Zh.Nikoghosyan, On spanning tree problems arising in optical and terminal networks", CSIT Conference 2015, Yerevan, Armenia, September 28 - October 2, pp. 94-95, 2015.
A. Saito and K. Sano, “Spanning trees homeomorphic to a small tree", Discrete Math., vol. 339, pp. 677-681, 2016.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
