Dominion on Grids

Abstract

The domination (number) of a graph G=(V,E), denoted by γ(G), is the size of the minimum dominating sets of V(G), also known as γ-sets. As such, the dominion of G, denoted by ζ(G), counts all its γ-sets. We proved a conjecture from one of the authors on the dominion of cycles C3k−1 and C3k−2, k≥2. Further, we found the formulae and recurrence relations for the dominions of several grids, Gm,n, with 2≤m≤4 and other results when m≤9 and n≤20. In general, domination and dominion play important roles in assessing certain vulnerabilities of any given network system.