# Homeomorphically irreducible spanning tree in hexagulations of surfaces

2019-05-13 11:15

#### 报告内容介绍

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.