Exploring signed domination number for the cartesian product of two path graphs

Abstract

Let 𝐺 = (𝑉, 𝐸) be a graph with the vertex set 𝑉(𝐺) and consider a function 𝑓: 𝑉(𝐺) → {-1, +1}. If the closed neighborhood of 𝑣 contains +1′s more than -1′s for every 𝑣 ∈ 𝑉(𝐺). Then 𝑓 is the signed domination function for the graph 𝐺 (1). 𝛾𝑠(𝐺) denotes the minimum weight of a signed domination function of 𝐺. The Cartesian product of two path graphs forms a grid graph. Specially, the Cartesian product of 𝑃𝑚 and 𝑃𝑛 gives 𝑚 × 𝑛 grid graph (𝑚 rows and 𝑛 columns) with 𝑚𝑛 number of vertices. In this study, we review existing methods for determining the signed domination number of the Cartesian product of two path graphs 𝛾𝑠(𝑃𝑚 × 𝑃𝑛). We then include definitions of open and closed neighborhoods of a graph, the signed domination function and the signed domination number. The theorems which are used to determine 𝛾𝑠(𝑃𝑚 × 𝑃𝑛) when 𝑚 = 3,4,5,6 and 7 were also presented. In exploring the 𝛾𝑠(𝑃𝑚 × 𝑃𝑛) where 𝑚 = 8, we draw upon existing literature which has focused on determining signed domination number for 𝛾𝑠(𝑃𝑚 × 𝑃𝑛) ranging from 𝑚 = 3 to 𝑚 = 7. This foundational knowledge guides our approach as we compile graphical illustrations that depict both trivial and general configurations of signed domination in grid graphs. These illustrations help us identify and categorize specific cases, defining sub-cases essential for the proof of the theorem. Through this process, we establish relationships among these graphical representations and develop a localized function, denoted as |𝐵𝑗|, to capture the relationships within each identified case. Building on these insights, we suggest theoretically valid approaches to completing the calculation for the 𝛾𝑠(𝑃𝑚 × 𝑃𝑛) when 𝑚 = 8, evaluating and refining our results based on the findings obtained from these methodical investigations. Our finding leads to a upper bound for the signed domination number of the grid graph 𝑃8 × 𝑃𝑛. The theorem is, for 𝑛 ≥ 1, if 𝑛 ≡ 0(𝑚𝑜𝑑 4) then 𝛾𝑠(𝑃8 × 𝑃𝑛) ≤ 4𝑛. We also propose a conjecture for the 𝑛 ≡ 1(𝑚𝑜𝑑 4), 𝛾𝑠(𝑃8 × 𝑃𝑛) ≤ 4𝑛 + 2.