|国家预印本平台
首页|The double Hall property and cycle covers in bipartite graphs

The double Hall property and cycle covers in bipartite graphs

The double Hall property and cycle covers in bipartite graphs

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论