Dept. of Mathematical and Statistical Sciences Fall 2021 Seminar Series Presents

Dr. James Shook

Security Components and Mechanisms Group, NIST

WHEN: Monday January 31st, 2022, from 11:00am to noon

TITLE: On a conjecture that strengthens the $k$-factor case of Kundu's $k$-factor Theorem

ABSTRACT: An non-negative sequence of integers $\pi=(d_{1},\ldots,d_{n})$ is said to be
graphic if there exists a graph $G=(V,E)$, called a realization of $\pi$, with
$V=\{v_{1},\ldots, v_{n}\}$  such that $v_{i}\in V$ has $d_{i}$ neighbors in
$G$. In 1974, Kundu showed that for even $n$ if $\pi=(d_{1},\ldots,d_{n})$ is a
non-increasing graphic sequence such that $(d_{1}-k,\ldots,d_{n}-k)$ is graphic,
then some realization of $\pi$ has a $k$-factor. In 1978, Brualdi and then Busch
et al.\, in 2012, conjectured that not only is there a $k$-factor, but there is
$k$-factor that can be partitioned into $k$ edge-disjoint $1$-factors. We will
discuss this conjecture and present some new supporting results.