Combinatorics Seminar 2015

Speaker: Yinfeng Zhu (祝隐峰), Shanghai Jiao Tong University

Date: Tue, Dec 08, 2015

Time: 15:40 - 16:20

Venue: Middle Meeting Room

Title: Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs


Let $G$ be a graph and $R = \{(s_1, t_1), \dots, (s_k, t_k)\}$ be a set of $k$ pairs of vertices of $G$. A path system of $G$ rooted at $R$ is a family of $k$ paths on $G$ such that the $i$-th path is an $s_i, t_i$-path and every two paths in the family intersect only at their possible common endpoints. A path system of $G$ is spanning if the union of the vertices of the paths in it is the whole vertex set of $G.$

In this talk, we use the concept of Hamiltonian thickness to discuss when $G$ has a spanning path system rooted at $R$. We also suggest a simple algorithm to find spanning rooted path system.

This is joint work with Yaokun Wu and Ziqing Xiang.

Slides: View slides