Homeomorphically irreducible spanning tree in hexagulations of surfaces

Erling Wei, an associate professor at Renmin University of China. Before that, She received her doctor degree from Beijing Jiaotong University in 2002. 

A homeomorphically irreducible spanning tree (HIST) of a connected graph is a spanning tree without vertices of degree two. The determination of the existence problem of a homeomorphically irreducible spanning tree in a plane cubic graph is NP-complete. A hexagulation of a surface is a cubic graph embedded on a surface such that every face is bounded by a hexagon. It is a  problem asked by Hoffmann-Ostenhof and Ozeki that whether there are finitely or infinitely many hexagulations of torus with homeomorphically irreducible spanning trees. In this paper, we show that a family of hexagulations of the surface, denoted by $H(m,n)$ with $m\ge 4$ being even and $n\ge 2$, have a homeomorphically irreducible spanning tree if and only if $m\equiv 2\pmod 4$, which settles the problem of Hoffmann-Ostenhof and Ozeki.