Title：Spanning trees with bounded number of leaves and branches

Abstract：For a graph $G$, take one vertex $v$ of $G$, and add $k-2$ pendant edges to $v$, and denote the resulting graph by $G'$. Then $G'$ has a spanning $k$-ended tree if and only if $G$ has a hamiltonian path. Hence the problem of determining whether a graph has a spanning $k$-ended tree or not is also NP-complete. Therefore, it is widely believed that it is impossible to find a good necessary and sufficient condition for a graph to have a spanning $k$-ended tree. Thus we mainly deal with sufficient conditions for a graph to have such spanning trees.

Speaker：Cai Junqing obtained his Ph. D. from Lanzhou University. Her research interests include graph theory, Network and Combinatorics. Many of her results published on《 Discrete Mathematics》et..

Date：2:00pm-3:00pm 2021-7-24（Saturday）.

Tencent Meeting ID： 802 979 938

Organizer：School of Mathematical Science

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