The domination number of the king’s graph

Abstract

For a graph Γ , a subset S⊆ VΓ is known to be a dominating set, if every x∈ VΓ S has at least one neighbor in D. The domination number γ(Γ) is merely the size of a smallest dominating set in Γ . The strong product Pr⊠ Ps of two paths Pr and Ps is known as the king’s graph. Interestingly, the king’s graph is isomorphic to the two-parametric family of cellular neural network (CNNs). In Asad et al. (Alex Eng J 66:957–977, 2023), the authors retrieved certain structural characteristics of CNNs from their minimal dominating sets. They conjectured in Problem 8.3 that the domination number of Pr⊠ Ps is ⌈r3⌉⌈s3⌉ . This paper solves Problem 8.3 by providing a proof to the conjecture. This result, in turn, reveals interesting topological properties such as an optimal routing for this class of neural networks.