报告题目:Disjoint perfect matchings in semi-regular graphs
报告人:鲁红亮,西安交通大学
报告时间:12月4号下午 4:30-5:30
地点:1518
摘要:
Let $n/ge 34$ be an even integer, and $D_n=2/lceil n/4 /rceil-1$. In this paper, we prove that every $/{D_n,/,D_n+1/}$-regular graph of order $n$ contains $/lceil n/4 /rceil$ disjoint perfect matchings. This result is sharp in the sense that (i) there exists a $/{D_n,/,D_n+1/}$-regular graph containing exactly $/lceil n/4 /rceil$ disjoint perfect matchings, and that (ii) there exists a $/{D_n-1,/,D_n/}$-regular graph without perfect matchings for each $n$. As a consequence, for any integer $D/ge D_n$, every $/{D,/,D+1/}$-regular graph of order $n$ contains $/lceil (D+1)/2 /rceil$ disjoint perfect matchings. This extends Csaba et~al.'s breathtaking result that every $D$-regular graph of sufficiently large order is $1$-factorizable, generalizes Zhang and Zhu's result that every $D_n$-regular graph of order $n$ contains $/lceil n/4 /rceil$ disjoint perfect matchings, and improves Hou's result that for all $k/ge n/2$, every $/{k,/,k+1/}$-regular graph of order $n$ contains $(/lfloor n/3/rfloor+1+k-n/2)$ disjoint perfect matchings.
欢迎感兴趣的师生前来参加!