Spanning trees with minimum number of leaves in the square graph of a tree

Article type: Research Article

Authors: Wu, Qiuxin

Affiliations: College of Science, Beijing Information Science and Technology University, Beijing 100196, China. E-mail: [email protected]

Abstract: A 3-tree is a tree with the maximum degree at most three. Let T be a tree of order n and p(T). In this paper, we prove that the square of T has a spanning tree F in which every leave of T has degree one or two and F has at most max{min{⌊n−p(T)+72⌋,⌊n−12⌋},2} leaves; This implies that the square graph of a connected graph G has the same conclusion above as a tree. These bounds are all sharp in same sense. We also give a shorter proof of a result in [10].

Keywords: Square graph, 3-tree, spanning tree, factor

DOI: 10.3233/JCM-160598

Journal: Journal of Computational Methods in Sciences and Engineering, vol. 16, no. 1, pp. 21-27, 2016