Rooted HIST Property on Planar Triangulations

Abstract

A spanning tree with no vertices of degree two of a graph is called a homeomorphically irreducible spanning tree (or HIST) of the graph. It has been proved that every planar triangulation \(G\) with at least four vertices has a HIST \(H\) [1]. However, the previous result asserts nothing whether the degree of a fixed vertex \(v\) of \(G\) is at least three or not in \(H\). In this paper, we prove that if a planar triangulation \(G\) has \(2n\) (\(n \geq 2\)) vertices, then, for any vertex \(v\), \(G\) has a HIST \(H\) such that the degree of \(v\) is at least three in \(H\). We call such a spanning tree a rooted HIST of \(G\) with root \(v\).