The double Hall property and cycle covers in bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929353010446336 |
|---|---|
| author | Barát, János Grzesik, Andrzej Jung, Attila Nagy, Zoltán Lóránt Pálvölgyi, Dömötör |
| author_facet | Barát, János Grzesik, Andrzej Jung, Attila Nagy, Zoltán Lóránt Pálvölgyi, Dömötör |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02909 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The double Hall property and cycle covers in bipartite graphs Barát, János Grzesik, Andrzej Jung, Attila Nagy, Zoltán Lóránt Pálvölgyi, Dömötör Combinatorics 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. |
| title | The double Hall property and cycle covers in bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.02909 |