On Domination and Total Domination Numbers on Strong Product of Two Path Graphs

Researchers show a lot of interest in the probe of graph invariants with respect to graph products as it poses challenging questions and provides interesting insights. The graph invariants considered here are domination, total domination and captive domination numbers. Let G = (V, E) be a simple undirected graph. A set D⊆V(G) is called a dominating set if any v ∈ V(G) – D is adjacent to at least one element in D and the size of a minimum dominating set of G is called the domination number of G denoted by γ(G).D is called a total dominating set if any v ∈V(G) is adjacent to at least one element in D and the size of a minimum total dominating set of G is called the total domination number of G denoted by γt(G).The graph product taken up for investigation is the strong product of two path graphs. A motivation for this stems from the conjecture: Let Γ = CNN [n, m] be the (n, m)- dimensional CNN such that m, n ≥ 2. Then γΓ = n3m3raised in [1]. Here the CNN denotes cellular neural networks. In the language of graph theory, the Γ is isomorphic to the strong product of two path graphs denoted byPn⊠ Pm. In this paper, while disproving this conjecture for certain cases we also found the exact values of γΓ for all n and m by carefully analyzing the underlying structures for connection pattern. While doing so, we also end up with the exact values of γtPn⊠Pm and a few other results.