The double Hall property and cycle covers in bipartite graphs
The double Hall property and cycle covers in bipartite graphs
In a graph $G$, the $2$-neighborhood of a vertex set $X$ consists of all vertices of $G$ having at least $2$ neighbors in $X$. We say that a bipartite graph $G(A,B)$ satisfies the double Hall property if $|A|\geq2$, and every subset $X \subseteq A$ of size at least $2$ has a $2$-neighborhood of size at least $|X|$. Salia conjectured that any bipartite graph $G(A,B)$ satisfying the double Hall property contains a cycle covering $A$. Here, we prove the existence of a $2$-factor covering $A$ in any bipartite graph $G(A,B)$ satisfying the double Hall property. We also show Salia's conjecture for graphs with restricted degrees of vertices in $B$. Additionally, we prove a lower bound on the number of edges in a graph satisfying the double Hall property, and the bound is sharp up to a constant factor.
D?m?t?r P¨¢lv?lgyi、J¨¢nos Bar¨¢t、Zolt¨¢n L¨?r¨¢nt Nagy、Andrzej Grzesik、Attila Jung
数学
D?m?t?r P¨¢lv?lgyi,J¨¢nos Bar¨¢t,Zolt¨¢n L¨?r¨¢nt Nagy,Andrzej Grzesik,Attila Jung.The double Hall property and cycle covers in bipartite graphs[EB/OL].(2023-10-04)[2025-08-02].https://arxiv.org/abs/2310.02909.点此复制
评论