Combinatorics Seminar 2014

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

Date: Fri, Apr 4, 2014

Time: 17:05 - 17:35

Venue: Middle Meeting Room

Title: Fault-tolerant spanning path systems and forward degrees of graphs


Let $G$ be a graph. For any family $R = R_k$ consisting of $k$ pairs of vertices $(s_1, t_1), \dots, (s_k, t_k) \in V(G) \times V(G)$, a path system of $G$ rooted at $R$ is a family $P_1, \dots, P_k$ of $k$ paths such that $P_i$ is an $s_i, t_i$-path for each $i \in \{1, \dots, k\}$, and $V(P_i) \cap V(P_j) = \{s_i, t_i\} \cap \{s_j, t_j\}$ holds for any two distinct indices $i, j \in \{1, \dots, k\}$. When all $(s_i, t_i)$ coincide with $(s, t)$, the path system is termed as an $s,t$-$k$-rail. A path system is spanning if every vertex of $G$ appears in at least one path in the system. A vertex ordering $v_1, \dots, v_n$ of $G$ is $k$-thick provided $|\{j : v_j v_i \in E(G), i \lt j \leq n\}| \geq \min (k, n - i)$ holds for each $i \in \{1, \dots, n\}$ and is Hamiltonian $k$-thick if it is $k$-thick and even corresponds to a Hamiltonian path of $G$. Peng Li and Yaokun Wu recently initiated the study of the relationship between thick orderings and spanning path systems.

The purpose of this talk is to show that the existence of a (Hamiltonian) $k$-thick ordering in a graph guarantees that, even when "some" nodes are faulty, the surviving graph still has a spanning path system with various given roots of a size comparable to $k$.

Here is one specific result stated in more precise language. Take two nonnegative integers $t$ and $s$ with $s + t \leq k$ and $t \geq 2$. Let $v_1, \dots, v_n$ be a Hamiltonian $k$-thick ordering of $G$. Then for every $S \in {V(G) \setminus \{v_1, v_n\} \choose s}$, $G - S$ contains a spanning $v_1, v_n$-$t$-rail and such a $t$-rail can be found in linear time.

This is joint work with Yaokun Wu and Ziqing Xiang.