Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph

2024/08/15 by Stephan Mertens, Mertens, Stephan
Computer Science · Mathematics · #05A15 #05C30 #05C69 #11B83 #Advanced Differential Equations and Dynamical Systems #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Cylinder #FOS: Mathematics #Geometry #Graph #Graph theory and applications #Grid #Mathematics #Torus

paper · pdf · doi:10.48550/arxiv.2408.08053

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2024/08/15 · openalex created_date 2025/01/03 · openalex updated_date 2026/07/28

Abstract

We present an algorithm to compute the domination polynomial of the m × n grid, cylinder, and torus graphs and the king graph. The time complexity of the algorithm is O(m²n² λ^2m) for the torus and O(m³n²λ^m) for the other graphs, where λ= 1+√(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× 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.

Related

• An atlas of domination polynomials of graphs of order at most six
• The domination polynomial of powers of paths and cycles
• A New Lower Bound for the Domination Number of Complete Cylindrical Grid Graphs
• Introduction to Domination Polynomial of a Graph
• Domination by kings is oddly even