Stephan Mertens - Research Home | Research | Publications | Teaching | Smorgasbord

Domination in Graphs

Publications

• Domination Polynomial of the Rook Graph
  Journal of Integer Sequences 27 Article 24.3.7 (2024)
• Domination by kings is oddly even (with C. Moore)
  arXiv:2407.19344
• Domination Polynomials of the Grid, the Cylinder, the Torus and the King Graph
  Journal of Integer Sequences 27 Article 24.7.6 (2024)

Data

Domination Polynomials

Stored as list of coefficients, starting with the coefficient for z⁰:

• m x n grid: grid_gf.tgz
• m x n cylinder, m-index periodic: cyl_gf.tgz
• m x n torus: torus_gf.tgz
• m x n king graph: kings_gf.tgz

Total Number of Dominating Subsets

The total number of dominating subsets can be computed from the domination polynomials simply by evaluating them at z=1. But we have computed the total number of dominating subsets with our transfer matrix algorithm directly, which allowed us to solve larger graphs. Hence this extra data files:

• m x n grid totals: grid_total.tgz
• m x n cylinder totals, m-index periodic: cyl_total.tgz
• m x n king graph totals: kings_total.tgz

Updates and new entries in the OEIS

The data produced by the algorithm described in my paper above ("Domination polynomials of the Grid, ...") was used to extend the following sequences in the Online Encyclopedia of Integer Sequences.

• A133515, A133791, A218354, A218663, A286514, A286914, A303334, A347554, A347557, A347632, A350815, A350820

Furthermore these new entries are based on this paper:

• A375566, A375569, A375601, and A375603