A sufficient condition for a hypergraph to have a Berge-$k$-factor
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_ | 1866917178813448192 |
|---|---|
| author | Gao, Yuping Shan, Songling Yu, Gexin |
| author_facet | Gao, Yuping Shan, Songling Yu, Gexin |
| contents | For any graph (hypergraph) $G$ with vertex set $V$ and edge set $E$, we define its incidence bipartite graph $\mathcal{I}(G)$ as the bipartite graph with bipartition $(E, V)$, where an edge $e \in E$ is adjacent to a vertex $v \in V$ in $\mathcal{I}(G)$ if and only if $e$ is incident to $v$ in $G$. This representation allows all concepts and properties of $G$ to be reformulated in terms of those of $\mathcal{I}(G)$. In this paper, we investigate the notions of graph toughness and $k$-factors in bipartite graphs through this incidence perspective. As an application, our result implies the classic theorem of Enomoto, Jackson, Katerinis, and Saito: for any integer $k \geq 1$, a $k$-tough graph $G$ has a $k$-factor if $k |V(G)|$ is even and $|V(G)| \geq k+1$. Furthermore, we extend this result to hypergraphs, without requiring uniformity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_14172 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A sufficient condition for a hypergraph to have a Berge-$k$-factor Gao, Yuping Shan, Songling Yu, Gexin Combinatorics For any graph (hypergraph) $G$ with vertex set $V$ and edge set $E$, we define its incidence bipartite graph $\mathcal{I}(G)$ as the bipartite graph with bipartition $(E, V)$, where an edge $e \in E$ is adjacent to a vertex $v \in V$ in $\mathcal{I}(G)$ if and only if $e$ is incident to $v$ in $G$. This representation allows all concepts and properties of $G$ to be reformulated in terms of those of $\mathcal{I}(G)$. In this paper, we investigate the notions of graph toughness and $k$-factors in bipartite graphs through this incidence perspective. As an application, our result implies the classic theorem of Enomoto, Jackson, Katerinis, and Saito: for any integer $k \geq 1$, a $k$-tough graph $G$ has a $k$-factor if $k |V(G)|$ is even and $|V(G)| \geq k+1$. Furthermore, we extend this result to hypergraphs, without requiring uniformity. |
| title | A sufficient condition for a hypergraph to have a Berge-$k$-factor |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2304.14172 |