2023/10/04 by Barát, János, Grzesik, Andrzej, Jung, Attila +2 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.02909
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|≥2, and every subset X ⊆ 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.