当前位置: 首页 > 科学研究 > 学术交流 >
学术交流

Homeomorphically irreducible spanning tree in hexagulations of surfaces

2019-05-13 11:15

报告人:魏二玲 【中国人民大学】

时间:2019-05-15 15:30-16:30

地点:卫津路校区14-202


报告人简介

魏二玲,现为中国人民大学副教授,硕士生导师。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.

联系我们

地址:天津市海河教育园区雅观路135号32号教学楼,300350
邮箱:maths@tju.edu.cn
电话:+86 (0)22 27402850
传真:+86 (0)22 27402850

Copyright@2017 拉菲2娱乐 版权所有

扫码关注娱乐最新动态