学术活动

Homeomorphically irreducible spanning tree in hexagulations of surfaces

2019-05-15 15:30

报告人: 魏二玲

报告人单位: 中国人民大学

时间: 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.


Contact us

Add:bat·365(中国)唯一官方网站 -Mobile Lgoin Center,

        No. 135, Ya Guan Road, Jinnan District, Tianjin, PRC 

Tel:022-60787827   Mail:math@tju.edu.cn