The existence of biregular spanning subgraphs in bipartite graphs via spectral radius
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914993804410880 |
|---|---|
| author | Fan, Dandan Gu, Xiaofeng Lin, Huiqiu |
| author_facet | Fan, Dandan Gu, Xiaofeng Lin, Huiqiu |
| contents | Biregular bipartite graphs have been proven to have similar edge distributions to random bipartite graphs and thus have nice pseudorandomness and expansion properties. Thus it is quite desirable to find a biregular bipartite spanning subgraph in a given bipartite graph. In fact, a theorem of Ore implies a structural characterization of such subgraphs in bipartite graphs. In this paper, we demonstrate the existence of biregular bipartite spanning subgraphs in bipartite graphs by employing spectral radius. We also study the existence of spanning trees with restricted degrees and edge-disjoint spanning trees in bipartite graphs via spectral radius. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21116 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The existence of biregular spanning subgraphs in bipartite graphs via spectral radius Fan, Dandan Gu, Xiaofeng Lin, Huiqiu Combinatorics Biregular bipartite graphs have been proven to have similar edge distributions to random bipartite graphs and thus have nice pseudorandomness and expansion properties. Thus it is quite desirable to find a biregular bipartite spanning subgraph in a given bipartite graph. In fact, a theorem of Ore implies a structural characterization of such subgraphs in bipartite graphs. In this paper, we demonstrate the existence of biregular bipartite spanning subgraphs in bipartite graphs by employing spectral radius. We also study the existence of spanning trees with restricted degrees and edge-disjoint spanning trees in bipartite graphs via spectral radius. |
| title | The existence of biregular spanning subgraphs in bipartite graphs via spectral radius |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.21116 |