Sumin Huang: The sparse sequences of graphs

Abstract:

For a graph $G$ of order $n$ and an integer $k$ with $1\leq k\leq n$, let $\pi(G,k)$ denote the minimum
number of edges spanned by $k$ vertices and call $(\pi(G,1),\pi(G,2),\ldots,\pi(G,n))$ the sparse sequence
of $G$. We give a sufficient condition for a sequence to be the sparse sequences of a general graph and
a tree, respectively. For any tree $T$ and $1\leq k\leq n-2$, we find that $\pi(T,k+2)-\pi(T,k+1)\geq \pi(T,k+1)-\pi(T,k)-1$.
We also establish a recursive relation, based on which we give a recursive algorithm for determining a
sequence to be the sparse sequences of a tree.

The lecture can be followed by zoom if necessary:

• Zoom link: https://us06web.zoom.us/j/82771257270?pwd=rZyB2cHe3PJokSnoWDgdN6fZMhfzGl.1
• Passcode: 095714
• Its number: 827 7125 7270