Number of vertices of degree three in spanning 3-trees in square graphs

摘要

In this paper, we show that the square graph of a tree T has a spanning tree of maximum degree at most three and with at most max{0,∑x∈W≥3(T)(tT(x)−2)−2} vertices of degree three, where W≥3(T)={x∈V(T): there are at least three edge-disjoint paths of length at least two that start x} and tT(x) is the number of edge-disjoint paths with length at least two that start at a vertex x.