Bipartite graphs with the double Hall property

Abstract

The super-neighborhood of a vertex set $A$ in a graph $G$, denoted by $\hat{I}{›}^2(A)$, is the set of vertices adjacent to at least two vertices in $A$. We say that a bipartite graph $G=(X,Y)$ with $|X|\ge 2$ satisfies the double Hall property (with respect to $X$) if $|\hat{I}{›}^2(A)|\ge |A|$ for any subset $A\subseteq X$ with $|A|\ge 2$. Kostochka et al. first conjectured that if a bipartite graph $G=(X,Y)$ satisfies a slightly weaker version of the double Hall property, then $G$ contains a cycle that covers all vertices of $X$. They verified their conjecture for $|X|\le 6$. In this paper, we extend their result to $|X|=7$. Later, Salia conjectured that every bipartite graph satisfying the double Hall property has a cycle covering all vertices of $X$. We show that Salia's conjecture is almost equivalent to a much weaker conjecture requiring vertices in $Y$ to have high degrees. By extending a result of Barát et al., we also show that Salia's conjecture holds for some graphs where the vertices of $Y$ have degree either $2$ or very high. Finally, we establish a lower bound for the maximum degree of graphs satisfying the double Hall property and present deterministic and probabilistic constructions of such graphs that approach this bound.

20 pages, 2 figures