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

摘要

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)+7)/2],[(n-1)/2]},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.