Homeomorphically irreducible spanning trees in hexangulations of surfaces
Homeomorphically irreducible spanning trees in hexangulations of surfaces
复制标题
DOI：
10.1016/j.disc.2019.01.032
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Shaohui Zhai;Erling Wei;Jinghua He;D. Ye
中科院分区：
文献类型：
--
作者：
Shaohui Zhai;Erling Wei;Jinghua He;D. Ye
连通图的同胚不可约生成树(HIST)是不含二次顶点的生成树。平面三次图中同胚不可约生成树的存在性问题的判定是NP完全的。曲面的六角形是嵌入在曲面上的三次图，使得每个面都以六边形为边界。Hoffmann-Ostenhof和Ozeki提出的问题是：环面是否存在有限或无限多个具有同胚不可约支撑树的六角形。本文证明了H(m，n)表示的曲面六角化族有同胚不可约生成树当且仅当它有奇数个面，从而回答了Hoffmann-Ostenhof和Ozeki关于曲面六角化的问题。
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 hexangulation 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 hexangulations of torus with homeomorphically irreducible spanning trees. In this paper, we show that a family of hexangulations of surfaces, denoted by H (m, n), have a homeomorphically irreducible spanning tree if and only if it has an odd number of faces, which answers the problem of Hoffmann-Ostenhof and Ozeki for hexangulations of surfaces.