Suil O, Finding a spanning Halin subgraph in 3-connected {K_{1,3},P_5}-free graphs

Finding a spanning Halin subgraph in 3-connected $\{K_{1,3},P_5\}$ -free graphs

Suil O
Georgia State University, USA

2014/08/28 *Thursday* 4PM-5PM
Room 1409

A Halin graph is constructed from a plane embedding of a tree whose non-leaf vertices have degree at least 3 by adding a cycle through its leaves in the natural order determined by the embedding. In this talk, we prove that every 3-connected $\{K_{1,3},P_5\}$ -free graph has a spanning Halin subgraph. This result is best possible in the sense that the statement fails if $K_{1,3}$ is replaced by $K_{1,4}$ or $P_5$ is replaced by $P_6$ . This is a joint work with Guantao Chen, Jie Han, Songling Shan, and Shoichi Tsuchiya.

Tags: 오수일

This entry was posted on Friday, August 22nd, 2014 at 10:44 am and is filed under 2014, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.