**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

**Abstract**:

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 systemof $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 isspanningif 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$-thickprovided $|\{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 isHamiltonian $k$-thickif 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.