Title：On the Path Cover Number of Connected Quasi-Claw-Free Graphs

Abstract：Detecting vertex disjoint paths is one of the central issues in designing and evaluating an interconnection network. It is naturally related to routing among nodes and fault tolerance of the network. A path cover of a graph $G$ is a spanning subgraph of $G$ consisting of vertex disjoint paths, and a path cover number of $G$ denoted by $p(G)=\min\{|\mathcal{P}|:$ $\mathcal{P}$ is a path cover of $G\}$. In this paper, we show that if the minimum degree sum of an independent set with $k+1$ vertices in a connected quasi-claw-free graph $G$ of order $n$ is no less than $n-k$, then $p(G)\leq k-1$, where $k\geq 2$. Examples illustrate that the degree sum condition in our result is sharp. This is a joint work with Huiqing Liu, Jian Lu and Xiuyu Zhong.

Speaker：Shunzhe Zhang, Ph.D., Hubei University. His research interests include interconnection networks, and graph theory and its application.

Date：10:00am-11:00am 2021-12-04（Saturday）.

Tencent Meeting ID：555 731 600

Organizer：School of Mathematical Science

Students and teachers who are interested in graph theory are welcome.