2025/04/03 by Leandro F. Aurichi, Paulo Magalhães Júnior, Aurichi, Leandro +3 · 1 citation
Computer Science · Mathematics · #05C05 05C38 05C63 54H99 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #General Topology (math.GN) #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2504.02816
openalex publication_date 2025/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G and a subset X of vertices of G with size at least two, we denote by N2G(X) the set of vertices of G that have at least two neighbors in X. We say that a bipartite graph G with sides A and B satisfies the double Hall property if for every subset X of vertices of A with size at least 2, \vert N2G(X)\vert ≥ \vert X\vert. Salia conjectured that if G is a bipartite graph that satisfies the double Hall property, then there exists a cycle in G that covers all vertices of A. In this work, we study this conjecture restricted to infinite graphs. For this, we use the definition of ends and infinite cycles. It is simple to see that Salia's conjecture is false for infinite graphs in general. Consequently, all our results are partial. Under certain hypothesis it is possible to obtain a collection of pairwise disjoint 2-regular subgraphs that covers A. We show that if side B is locally finite and side A is countable, then the conjecture is true. Furthermore, assuming the conjecture holds for finite graphs, we show that it holds for infinite graphs with a restriction on the degree of the vertices of B. This result is inspired by the result obtained by Barát, Grzesik, Jung, Nagy and Pálvölgyi for finite graphs. Finally, we also show that if Salia's conjecture holds for some cases of infinite graphs, then the conjecture about finite graphs presented by Lavrov and Vandenbussche is true.