Eigenvalues and parity factors in graphs

Abstract

Let $G$ be a graph and let $g,f$ be nonnegative integer-valued functions defined on $V(G)$ such that $g(v)\le f(v)$ and $g(v)\equiv f(v)(\mathrm{mod}2)$ for all $v\in V(G)$. A $(g,f)$-parity factor of $G$ is a spanning subgraph $H$ such that for each vertex $v\in V(G)$, $g(v)\le d_H(v)\le f(v)$ and $f(v)\equiv d_H(v)(\mathrm{mod}2)$. We prove sharp upper bounds for certain eigenvalues in an $h$-edge-connected graph $G$ with given minimum degree to guarantee the existence of a $(g,f)$-parity factor; we provide graphs showing that the bounds are optimal. This result extends the recent one of the second author (2022), extending the one of Gu (2014), Lu (2010), Bollb{á}s, Saito, and Wormald (1985), and Gallai (1950).

arXiv comment16 pages, 1 figure