Comparing the numbers of subforests and subgraph-degree-tuples
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918179648831488 |
|---|---|
| author | Shteiner, Sergei Shteyner, Pavel |
| author_facet | Shteiner, Sergei Shteyner, Pavel |
| contents | We enumerate the row-column-sums of all square tridiagonal $(0,1)$-matrices and prove that their count coincides with OEIS A022026 $-$ the number of acyclic subgraphs of the complete $2\times n$ grid graph. We then extend this correspondence in two independent directions: 1. admitting larger sets of matrix entries, and 2. relaxing the tridiagonal support to broader prescribed sparsity patterns. The latter leads us to conjecture that, for any bipartite graph $G$, the number of its acyclic subgraphs equals the number of degree sequences realized by subgraphs of $G$. Moreover, for any non-bipartite graph, the former should be strictly smaller than the latter. We discuss several general approaches and prove these hypotheses for cactus graphs and generalized book graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26936 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Comparing the numbers of subforests and subgraph-degree-tuples Shteiner, Sergei Shteyner, Pavel Combinatorics 05B20 (Primary) 05A19, 05C30, 05C07, 05C15 (Secondary) We enumerate the row-column-sums of all square tridiagonal $(0,1)$-matrices and prove that their count coincides with OEIS A022026 $-$ the number of acyclic subgraphs of the complete $2\times n$ grid graph. We then extend this correspondence in two independent directions: 1. admitting larger sets of matrix entries, and 2. relaxing the tridiagonal support to broader prescribed sparsity patterns. The latter leads us to conjecture that, for any bipartite graph $G$, the number of its acyclic subgraphs equals the number of degree sequences realized by subgraphs of $G$. Moreover, for any non-bipartite graph, the former should be strictly smaller than the latter. We discuss several general approaches and prove these hypotheses for cactus graphs and generalized book graphs. |
| title | Comparing the numbers of subforests and subgraph-degree-tuples |
| topic | Combinatorics 05B20 (Primary) 05A19, 05C30, 05C07, 05C15 (Secondary) |
| url | https://arxiv.org/abs/2510.26936 |