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

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 \left\{\min \left\{\lfloor \frac{n-p(T)+7}{2}\rfloor ,\lfloor \frac{n-1}{2}\rfloor \right\},2\right\}$ 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].