Antifactors in bipartite multigraphs

arXiv2205.14904MaRDI QIDQ6400514FDOQ6400514

L. Esperet

Publication date: 30 May 2022

Abstract: Let $G$ be a $q$-regular bipartite graph with bipartition $(U,V)$. It was proved by Lu, Wang, and Yan in 2020 that $G$ has a spanning subgraph $H$ such that each vertex of $U$ has degree 1 in $H$, and each vertex of $V$ has degree distinct from 1 in $H$. We extend the result to multigraphs, under the condition that $q$ is a prime power and the number of perfect matchings of $G$ is not divisible by $q$. The condition on the number of perfect matchings is necessary for multigraphs. We conclude with a conjecture on the limiting distribution of the number of perfect matchings modulo $q$ in a random bipartite $q$-regular graph.

This page was built for publication: Antifactors in bipartite multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400514)