Yulai Ma, Pairwise disjoint perfect matchings in regular graphs

An $r$-graph is an $r$-regular graph in which every odd set of vertices is connected to its complement by at least $r$ edges. A central question regarding $r$-graphs is determining the maximum number of pairwise disjoint perfect matchings they can contain. This talk explores how edge connectivity influences this parameter.

For ${0 \leq \lambda \leq r}$, let $m(\lambda,r)$ denote the maximum number $s$ such that every $\lambda$-edge-connected $r$-graph contains $s$ pairwise disjoint perfect matchings. The values of $m(\lambda,r)$ are known only in limited cases; for example, $m(3,3)=m(4,r)=1$, and $m(r,r) \leq r-2$ for all $r \not = 5$, with $m(r,r) \leq r-3$ when $r$ is a multiple of $4$. In this talk, we present new upper bounds for $m(\lambda,r)$ and examine connections between $m(5,5)$ and several well-known conjectures for cubic graphs.

This is joint work with Davide Mattiolo, Eckhard Steffen, and Isaak H. Wolf.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.