Monday, January 31 2022

11:00am - 12:00pm

11:00am - 12:00pm

Department Seminar

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

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.

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.

Speaker: | James Shook |

Affiliation: | NIST |

Location: |

Done