Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929460300742656 |
|---|---|
| author | Mertens, Stephan |
| author_facet | Mertens, Stephan |
| contents | We present an algorithm to compute the domination polynomial of the $m \times n$ grid, cylinder, and torus graphs and the king graph. The time complexity of the algorithm is $O(m^2n^2 λ^{2m})$ for the torus and $O(m^3n^2λ^m)$ for the other graphs, where $λ= 1+\sqrt{2}$. The space complexity is $O(mnλ^m)$ for all of these graphs. We use this algorithm to compute domination polynomials for graphs up to size $24\times 24$ and the total number of dominating sets for even larger graphs. This allows us to give precise estimates of the asymptotic growth rates of the number of dominating sets. We also extend several sequences in the Online Encyclopedia of Integer Sequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08053 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph Mertens, Stephan Combinatorics 05C69, 05A15, 05C30, 11B83 We present an algorithm to compute the domination polynomial of the $m \times n$ grid, cylinder, and torus graphs and the king graph. The time complexity of the algorithm is $O(m^2n^2 λ^{2m})$ for the torus and $O(m^3n^2λ^m)$ for the other graphs, where $λ= 1+\sqrt{2}$. The space complexity is $O(mnλ^m)$ for all of these graphs. We use this algorithm to compute domination polynomials for graphs up to size $24\times 24$ and the total number of dominating sets for even larger graphs. This allows us to give precise estimates of the asymptotic growth rates of the number of dominating sets. We also extend several sequences in the Online Encyclopedia of Integer Sequences. |
| title | Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph |
| topic | Combinatorics 05C69, 05A15, 05C30, 11B83 |
| url | https://arxiv.org/abs/2408.08053 |