SUSTech Discrete Mathematics Seminar

Logo

This is the homepage of the SUSTech Discrete Mathematics Seminar at the Department of Mathematics at SUSTech.

Past Talks

2025-11-06

Speaker: Weigen Yan (Jimei University)
Room: College of Science M1001
Time: 10:00 - 11:00
Tencent Meeting: 501 211 106

Let $G$ be a connected $k$-regular graph of order $n$, and let $p(G)$ and $h(G)$ denote the number of disjoint perfect matchings and disjoint Hamilton cycles of $G$, respectively. The 1-factorization (resp., Hamilton decomposition) conjecture states that $p(G)=k$ if $n\leq2k$ and $n$ is even (resp., $h(G)=\lfloor k/2\rfloor$ if $n\leq2k+1$). Zhang and Zhu (J. Combin. Theory Ser. B, 56 (1992) 74-89) proved that $p(G)\geq \lfloor k/2\rfloor$ if $n\leq2k$ and $n$ is even, and Jackson (J. London Math. Soc. 19 (1979) 13-16) proved that $h(G)\geq \lfloor(3k-n+1)/6\rfloor$ if $14\leq n\leq 2k+1$.

In this paper, we mainly obtain the following two results, which extend the above results by Zhang and Zhu and by Jackson.

  1. If $n\leq 3k+3$ and $n$ is even, then $p(G)\geq \min{\lambda_0(G), k-\lceil n/4\rceil}$, where $\lambda_0(G)$ is the odd-edge-connectivity of $G$.

  2. If $G$ is 2-connected and $n\leq 3k$, then $h(G)\geq\min {\lambda(G)-\lfloor k/2\rfloor, \lfloor(3k-n+1)/6\rfloor}$, where $\lambda(G)$ is the edge-connectivity of $G$.

As an application, we prove that if a $k$-regular graph $G$ satisfies: $\lambda_1(G)\geq k-2$, $3n\leq 8k$, $k$ is odd, and $k=k_1+k_2+\cdots+k_m$ is any partition of $k$ with each part $k_i\geq2$, then $G$ has a $(G_1,G_2,\ldots,G_m)$-factorization, where $\lambda_1(G)$ is the size of smallest odd edge-cut of $G$, and $G_i$ is a $k_i$-factor of $G$ for $i=1,2,\ldots,m$, which partially confirms a conjecture posed by Thomassen (J. Combin. Theory Ser. B, 141 (2020) 343-351).

This is joint work with Jingchao Lai and Xing Feng

tags: