报告人:
魏二玲
报告人单位:
中国人民大学
时间:
2019-05-15 15:30-16:30
地点:
卫津路校区14-202
开始时间:
2019-05-15 15:30-16:30
报告人简介:
年:
日月:
报告人简介
魏二玲,现为中国人民大学副教授,硕士生导师。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.