Geodetic Number and Geo-Chromatic Number of 2-Cartesian Product of Some Graphs

Medha Itagi Huilgol^1*, B. Divya²

¹Department of Mathematics, Bengaluru City University, Central College Campus, Bengaluru, India.
²Department of Mathematics, Bangalore University, Bengaluru, India.

DOI: 10.4236/ojdm.2022.121001                

Abstract

A set S ⊆ V (G) is called a geodetic set if every vertex of G lies on a shortest u-v path for some u, v ∈ S, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by . A set C ⊆ V (G) is called a chromatic set if C contains all vertices of different colors in G, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by . A geo-chromatic set S_c ⊆ V (G) is both a geodetic set and a chromatic set. The geo-chromatic number  of G is the minimum cardinality among all geo-chromatic sets of G. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.

Keywords

Cartesian Product, Grid Graphs, Geodetic Set, Geodetic Number, Chromatic Set, Chromatic Number, Geo-Chromatic Set, Geo-Chromatic Number

1. Introduction

Products of structures are a fundamental construction in mathematics, for which theorems abound in set theory, category theory, universal algebra etc. Product in graphs is a natural extension of concepts of graphs involved in the product. The most famous, well studied graph product is the cartesian product. It not only extends many properties, but also carries metric space structure with it. Combining the usual vertex distance as a metric, the cartesian product is generalized to give multidimensional aspect to the underlying graphs. A special case of this was studied as 2-cartesian product by Acharya [1] [2]. These papers throw light on 2-cartesian product of some special graphs. Inspired by these, in this paper we consider finding geodetic number of 2-cartesian product of graphs and then extend them to find geochromatic number. Geodetic number primarily deals with distance convexity which is studied by many researchers [3] [4] [5], etc. The depth of convexity theory enables study of geodeticity in graphs to further heights. Another interesting concept in graphs that finds numerous applications is that of coloring. Recently these two concepts are combined to give geochromatic number, which acts as a double layered measure that covers all vertices in a graph containing all color class representations. The geochromatic number of a graph was defined by Samli et al. [6], which was further studied by Mary [7], Huilgol et al. [8]. In this paper we determine the geodetic number of 2-cartesian product of some graphs and extend them to find geochromatic number.

First of all, we list some important preliminaries.

2. Definitions and Preliminary Results

All the terms undefined here are in the sense of Buckley and Harary [9]. Here we consider a finite graph without loops and multiple edges. For any graph G the set of vertices is denoted by $V\left(G\right)$ and the edge set by $E\left(G\right)$. The order and size of G are denoted by p and q respectively.

Let u and v be vertices of a connected graph G. A shortest $u-v$ path is called a $u\mathrm{,}v$ -geodesic. The distance between two vertices u and v is defined as the length of a $u\mathrm{,}v$ geodesic in G and is denoted by $d_G\left(u\mathrm{,}v\right)$ or $d\left(u\mathrm{,}v\right)$ if G is clear from the context.

The eccentricity of vertex v of a graph G denoted by $ecc\left(v\right)$ is maximum distance from v to any other vertex of G. Diameter of G, denoted by $diam\left(G\right)$ is the maximum eccentricity of vertices in G, and radius is the minimum such eccentricity denoted by $rad\left(G\right)$.

Definition 2.1. [9] A vertex v of G is a peripheral vertex if $ecc\left(v\right)=diam\left(G\right)$ .

Definition 2.2. [9] The set of all peripheral vertices of G is called periphery, denoted by $P\left(G\right)$ . That is, $P\left(G\right)=\left\{v\in V\left(G\right)\mathrm{<mo>\; :\; </mo>}ecc\left(v\right)=diam\left(G\right)\right\}$ .

Definition 2.3. [9] A graph G is said to be self-centered if $diam\left(G\right)=rad\left(G\right)$ .

Definition 2.4. [9] If each vertex of a graph G has exactly one eccentric vertex, then G is called a unique eccentric vertex graph.

Definition 2.5. [9] The (geodesic) interval $I\left(u\mathrm{,}v\right)$ between u and v is the set of all vertices on all shortest $u-v$ paths. Given a set $S\subseteq V\left(G\right)$ , its geodetic closure $I\left[S\right]$ is the set of all vertices lying on some shortest path joining two vertices of S. Thus, $I\left[S\right]=\left\{v\in V\left(G\right)\mathrm{<mo>\; :\; </mo>}v\in I\left(x\mathrm{,}y\right)\mathrm{,}x\mathrm{,}y\in S\right\}={\displaystyle {\cup }_{x\mathrm{,}y}}I\left\{x\mathrm{,}y\right\}$.

A set $S\subseteq V\left(G\right)$ is called a geodetic set in G if $I\left[S\right]=V\left(G\right)$ ; that is every vertex in G lies on some geodesic between two vertices from S. The geodetic number $g_n\left(G\right)$ of a graph G is the minimum cardinality of a geodetic set in G.

Definition 2.6. [10] A n-vertex coloring of G is an assignment of n colors 1, 2, 3, ..., n to the vertices of G. The coloring is proper if no two adjacent vertices have the same color.

Definition 2.7. [10] A set $C\subseteq V\left(G\right)$ is called chromatic set if C contains all vertices belonging to each color class. Chromatic number of G is the minimum cardinality among all chromatic sets of G, that is, $\chi \left(G\right)=\left\{\min \left|C_i\right|\mathrm{<mo>\; /\; </mo>}{C}_{i}isachromaticsetofG\right\}$.

Definition 2.8. [6] A set $S_c$ of vertices in G is said to be geochromatic set, if $S_c$ is both a geodetic set and a chromatic set. The minimum cardinality of a geochromatic set of G is its geochromatic number (GCN) and is denoted by ${\chi }_{gc}\left(G\right)$ . A geochromatic set of size ${\chi }_{gc}\left(G\right)$ is said to be ${\chi }_{gc}$ -set.

Definition 2.9. [4] A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete.

Definition 2.10. [5] Let G be a graph and let $S=\left\{x_1,x_2,\cdots ,x_k\right\}$ be a geodetic set of G, then S is a linear geodetic set if for any $x\in V\left(G\right)$ there exists an index i, $1<i<k$ such that $x\in I\left[x_i\mathrm{,}{x}_{i+1}\right]$ .

Definition 2.11. [5] Let G be a graph, If S is a geodetic set of G such that, for all $u\in V\left(G\right)\backslash S$ , for all $v\mathrm{,}w\in S\mathrm{<mo>\; :\; </mo>}u\in I\left[v\mathrm{,}w\right]$ then S is a complete geodetic set of G.

The following results are helpful in proving our results.

Theorem 1. [11] Every geodetic set of a graph contains its extreme vertices.

Theorem 2. [5] If G is a non trivial connected graph of order p and diameter d, then $g_n\left(G\right)\le p-d+1$ .

Theorem 3. [9] If every chromatic set of a graph G contains k vertices, then G has k vertices of degree at least $k-1$ .

Theorem 4. [10] Every minimum chromatic set of a graph G contains at most $\left(\Delta \left(G\right)+1\right)$ vertices.

Theorem 5. [10] If $G=K_t$ , a complete graph on t vertices, then $V\left(G\right)$ is the unique chromatic set of G.

3. Geodetic Number and Geochromatic Number of 2-Cartesian Product of Some Graphs

We establish the geodetic number of graphs resulting from 2-cartesian product of two graphs. We first give some definitions and preliminary results pertaining to 2-cartesian products, geodeticity, chromaticity and geochromaticity with respect to 2-cartesian product in paths, cycles and complete bipartite graphs.

Definition 3.1. [12] The cartesian product $G\square H$ of graphs G and H is the graph with vertex set $V\left(G\right)\times V\left(H\right)$ in which vertices $\left(g\mathrm{,}h\right)$ and $\left(g^{\prime }\mathrm{,}{h}^{\prime }\right)$ are adjacent whenever $g{g}^{\prime }\in E\left(G\right)$ and $h=h^{\prime }$ or $g=g^{\prime }$ and $h{h}^{\prime }\in E\left(H\right)$ .

By [12] most important metric property of the cartesian product operation is written as follows $d_{G\square H}\left(\left(g\mathrm{,}h\right)\mathrm{,}\left(g^{\prime }\mathrm{,}{h}^{\prime }\right)\right)=d_G\left(g\mathrm{,}{g}^{\prime }\right)+d_H\left(h\mathrm{,}{h}^{\prime }\right)$, for any two graphs G and H.

Theorem 6. [12] For any two graphs G and H, $\chi \left(G\square H\right)=\max \left\{\chi \left(G\right)\mathrm{,}\chi \left(H\right)\right\}$.

Remark 1. In the cartesian product color assignment is given as follows: Whenever $\chi \left(G\right)\ge \chi \left(H\right)$, let $g\mathrm{<mo>\; :\; </mo>}V\left(G\right)\to \left\{\mathrm{0,1,}\cdots \mathrm{,}\chi \left(G\right)-1\right\}$ be a coloring of G and $h\mathrm{<mo>\; :\; </mo>}V\left(H\right)\to \left\{\mathrm{0,1,}\cdots \mathrm{,}\chi \left(H\right)-1\right\}$ be a coloring of H.A color assignment f is $f\mathrm{<mo>\; :\; </mo>}V\left(G\square H\right)\to \left\{\mathrm{0,1,}\cdots \mathrm{,}\chi \left(G\right)-1\right\}$ , defined by $f\left(a,x\right)=g\left(a\right)+h\left(x\right)\left(\mathrm{mod}\chi \left(G\right)\right)$.

Theorem 7. [13] Let $X=G\square H$ be the cartesian product of connected graphs G and H and let $\left(g\mathrm{,}h\right)$ , $\left(g^{\prime }\mathrm{,}{h}^{\prime }\right)$ be vertices of X then, $I_X\left[\left(g\mathrm{,}h\right)\mathrm{,}\left(g^{\prime }\mathrm{,}{h}^{\prime }\right)\right]=I_G\left[\left(g\mathrm{,}{g}^{\prime }\right)\right]\times I_H\left[\left(h\mathrm{,}{h}^{\prime }\right)\right]$. Moreover, $I_X\left[\left(g\mathrm{,}h\right)\mathrm{,}\left(g^{\prime }\mathrm{,}{h}^{\prime }\right)\right]=I_X\left[\left(g^{\prime }\mathrm{,}h\right)\mathrm{,}\left(g\mathrm{,}{h}^{\prime }\right)\right]$.

Theorem 8. [11] For any graphs G and H, $g_n\left(G\right)=m\ge g_n\left(H\right)=n\ge 2$ , then $m\le g_n\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\square H\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le mn-n\mathrm{.}$

Theorem 9. [11] Let G and H be graphs on at least two vertices with

$g_n\left(G\right)=m$ and let $g_n\left(H\right)=n$ . Suppose that both G and H contain linear

minimum geodetic sets, then $g_n\left(G\square H\right)\le \lfloor \frac{mn}{2}\rfloor$ .

Theorem 10. [5] Let G be a graph on at least two vertices that admits a linear minimum geodetic set and let H be a graph with $g_n\left(H\right)=2$ , then $g_n\left(G\square H\right)=g_n\left(G\right)$.

Theorem 11. [11] Let G and H be non trivial graphs, both being non trivial graphs having complete minimum geodetic sets. Let H be a graph with $g_n\left(H\right)=2$ then $g_n\left(G\square H\right)=\max \left\{g_n\left(G\right)\mathrm{,}{g}_n\left(H\right)\right\}$ .

Theorem 12. [8] For the cartesian product of two paths, that is, the grid graphs, the geochromatic number is given by,

$\begin{array}{l}{\chi }_{gc}\left(P_m\square P_n\right)\\ =\{\begin{array}{l}2,form\ne n\mathrm{,}andoneofmorniseven\mathrm{,}\\ 3,form=n\mathrm{,}andform\ne n,withbothmandnoddorbotheven.\end{array}\end{array}$

Theorem 13. [8] For the cartesian product of cycle $C_m$ with path $P_n$ , the geo-chromatic number is given by, ${\chi }_{gc}\left(C_m\square P_n\right)=2$ or 3.

Theorem 14. [8] For the cartesian product of cycle $C_m$ with cycle $C_n$ the geo-chromatic number is given by, ${\chi }_{gc}\left(C_m\square C_n\right)=\mathrm{2,3}$ or 5.

Theorem 15. [8] For the cartesian product of complete graph $K_m$ with path $P_n$ the geochromatic number is given by,

${\chi }_{gc}\left(K_m\square P_n\right)\mathrm{<mo>\; =\; </mo>}\{\begin{array}{l}m\mathrm{,}fornodd\mathrm{,}\\ m+\mathrm{1,}forneven\mathrm{.}\end{array}$

Theorem 16. [8] For the cartesian product of complete graph $K_m$ with cycle $C_n$ the geochromatic number is given by,

${\chi }_{gc}\left(K_m\square C_n\right)=\{\begin{array}{l}m,fornoddandn/2even,\\ m+1,fornevenandn/2odd,\\ 2m-1,fornodd.\end{array}$

Definition 3.2. [2] The 2-cartesian product of graphs $G_1=\left(V_1\mathrm{,}{E}_1\right)$ and $G_1=\left(V_2\mathrm{,}{E}_2\right)$ is the graph $G=\left(V\mathrm{,}E\right)$ with the vertex set $V\mathrm{<mo>\; =\; </mo>}{V}_1\times V_2$ and the edge set E defined as follows:

Two vertices $\left(u\mathrm{,}v\right)$ and $\left(u^{\prime }\mathrm{,}{v}^{\prime }\right)$ are adjacent in G if one of the conditions is satisfied:

1) $d_{G_1}\left(u,u^{\prime }\right)=2$ and $d_{G_2}\left(v\mathrm{,}{v}^{\prime }\right)=0$,

2) $d_{G_1}\left(u,u^{\prime }\right)=0$ and $d_{G_2}\left(v\mathrm{,}{v}^{\prime }\right)=2$ .

We denote this graph G by $G_1{\times }_2{G}_2$.

It is clear that if we replace 2by 1in the definition,then we get usual cartesian product $G_1\square G_2$ .

Note that, if diameter of each graph $G_1$ and $G_2$ is less than 2, then $G_1{\times }_2{G}_2$ is a null graph.To avoid this,we consider all graphs with diameter at least 2.

Definition 3.3. [2] The grid graph $G=G_{m,n}$ is defined as the graph with the vertex set $V=\left\{\left(u_i,v_j\right):i=1,2,3,\cdots ,mandj=1,2,\cdots ,n\right\}$ and egde set $E={\displaystyle {\cup }_{j=1}^m\left\{\left(u_i,v_j\right)\leftrightarrow \left(u_i,v_{j+1}\right):1\le j\le n-1\right\}}{\displaystyle {\cup }_{j=1}^m\left\{\left(u_i,v_j\right)\leftrightarrow \left(u_{i+1},v_j\right):1\le i\le m-1\right\}}$.

Definition 3.4. [2] The semi tied grid graph $G_{\left(m\right)\mathrm{,}\left(n^0\right)}$ is a grid graph with the vertex set $V\left(G\right)$ and the edge set consisting of following edges:

1)Each edge of $G_{m\mathrm{,}n}$ ;

2) The edges $\left(u_i\mathrm{,}{v}_1\right)\leftrightarrow \left(u_i\mathrm{,}{v}_n\right)$ ,for every $i=1,2,\cdots ,m$ .

In place of (2), if we consider (2)' then we get another semi tied grid graph denoted by $G_{\left(m^0\right)\mathrm{,}\left(n\right)}$, where (2)': The edges $\left(u_i\mathrm{,}{v}_j\right)\leftrightarrow \left(u_m\mathrm{,}{v}_j\right)$ , for every $j=1,2,3,\cdots ,n$.

A graph containing all the above types of edges is called a tied graph, denoted by $G_{\left(m^0\right)\mathrm{,}\left(n^0\right)}$.

Proposition 3.1. [2] For $m\mathrm{,}n\ge 3$ ,

1) If both m and n are even integers then,

$P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left(\frac{m}{2}\right),\left(\frac{n}{2}\right)}\right)}^{\left(i\right)}\right]$.

2)If m is odd and n is even, then,

$P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m+1}{2}\right),\left(\frac{n}{2}\right)}\right)}^{\left(i\right)}\right]\cup \left[{\displaystyle {\cup }_{j=1}^2}{\left(G_{\left(\frac{m-1}{2}\right),\left(\frac{n}{2}\right)}\right)}^{\left(j\right)}\right]$.

3) If m is even and n is odd, then,

$P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m}{2}\right),\left(\frac{n+1}{2}\right)}\right)}^{\left(i\right)}\right]\cup \left[{\displaystyle {\cup }_{j=1}^2}{\left(G_{\left(\frac{m}{2}\right),\left(\frac{n-1}{2}\right)}\right)}^{\left(j\right)}\right]$.

4)If both m and n are odd integers, then,

$\begin{array}{l}{P}_m{\times }_2{P}_n\\ =\left[\left(G_{\left(\frac{m+1}{2}\right),\left(\frac{n+1}{2}\right)}\right)\right]\cup \left[\left(G_{\left(\frac{m+1}{2}\right),\left(\frac{n-1}{2}\right)}\right)\right]\cup \left[\left(G_{\left(\frac{m-1}{2}\right),\left(\frac{n+1}{2}\right)}\right)\right]\cup \left[\left(G_{\left(\frac{m-1}{2}\right),\left(\frac{n-1}{2}\right)}\right)\right]\end{array}$.

Proposition 3.2. [2] Let $P_m$ and $C_n$ be path graph and cycle graph with m and n vertices respectively.

1) If n is an even integer,then $P_m{\times }_2{C}_n$ has four components which are semi tied graphs.

a) if m is even,we have 4isomorphic components ${\left(G_{\left(\frac{m}{2}\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}$ .Hence,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left(\frac{m}{2}\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$.

b) if m is odd,we have 2pairs of isomorphic components ${\left(G_{\left(\frac{m+1}{2}\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}$ and ${\left(G_{\left(\frac{m-1}{2}\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(j\right)}$ .Hence,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m+1}{2}\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]\cup \left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m-1}{2}\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(j\right)}\right]$.

2) If n is an odd integer,then $P_m{\times }_2{C}_n$ has two components which are semi tied graphs.

a) if m is even,we have 2isomorphic components ${\left(G_{\left(\frac{m}{2}\right)\mathrm{,}\left({\left(n\right)}^0\right)}\right)}^{\left(i\right)}$ to give

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m}{2}\right),\left({\left(n\right)}^0\right)}\right)}^{\left(i\right)}\right]$.

b) if m is odd,we have 2non-isomorphic components $\left(G_{\left(\frac{m+1}{2}\right)\mathrm{,}\left({\left(n\right)}^0\right)}\right)$ and $\left(G_{\left(\frac{m-1}{2}\right)\mathrm{,}\left({\left(n\right)}^0\right)}\right)$ to give

$P_m{\times }_2{C}_n=\left(G_{\left(\frac{m+1}{2}\right)\mathrm{,}\left({\left(n\right)}^0\right)}\right)\cup \left(G_{\left(\frac{m-1}{2}\right)\mathrm{,}\left({\left(n\right)}^0\right)}\right)$.

Proposition 3.3. [2] Let $C_m$ and $C_n$ be cycle graphs with m and n vertices respectively.

1) If both m and n are even integers,then $C_m{\times }_2{C}_n$ has four isomorphic tied grid graph components are $\left(G_{\left({\left(\frac{m}{2}\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)$ .Hence

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left({\left(\frac{m}{2}\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$.

2) If m is odd and n is even,then $C_m{\times }_2{C}_n$ has two tied grid graph components $\left(G_{\left({\left(m\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)$ to have

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left({\left(m\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$.

3) If both m and n are odd integers,then $C_m{\times }_2{C}_n$ is a connected graph which is a tied grid graph.

Proposition 3.4. [2] Let $K_{s\mathrm{,}t}$ be a complete biartite graph and $P_m$ be a path graph with m vertices. Then $K_{s\mathrm{,}t}{\times }_2{P}_m$ has exactly four components.

1) If m is an even integer then $K_{s\mathrm{,}t}{\times }_2{P}_m$ has four components two components each isomorphic to $K_s\square P_{\left(\frac{m}{2}\right)}$ and $K_t\square P_{\left(\frac{m}{2}\right)}$ and

2)If m is an odd integer then $K_{s\mathrm{,}t}{\times }_2{P}_m$ has four components viz., $K_s\square P_{\left(\frac{m+1}{2}\right)}$ , $K_s\square P_{\left(\frac{m-1}{2}\right)}$ , $K_t\square P_{\left(\frac{m+1}{2}\right)}$ ,and $K_t\square P_{\left(\frac{m-1}{2}\right)}$ .

Proposition 3.5. [2] Let $K_{s\mathrm{,}t}$ be a complete bipartite graph and $C_m$ be a cycle graph with m vertices.

1)If m is an even integer then $K_{s\mathrm{,}t}{\times }_2{C}_m$ has four components two components each isomorphic to $K_s\square C_{\left(\frac{m}{2}\right)}$ and $K_t\square C_{(\; m\; 2\; )}$

2)If m is an odd integer then $K_{s\mathrm{,}t}{\times }_2{C}_m$ has two components $K_s\square C_m$ and $K_t\square C_m$ .

Remark 2. By [14] [15] the geodetic number of disconnected graph is the sum of geodetic number of each component.

Theorem 17. The geodetic number of 2-cartesian product of two paths is given by, $g_n\left(P_m{\times }_2{P}_n\right)=8$ , for $m\mathrm{,}n\ge 3$ .

Proof. Let $P_m$ and $P_n$ be two path graphs with $V\left(P_m\right)=\left\{u_1,u_2,u_3,\cdots ,u_m\right\}$ and $E\left(P_m\right)=\left\{\left(u_1{u}_2\right)\mathrm{,}\left(u_2{u}_3\right)\mathrm{,}\left(u_3{u}_4\right)\mathrm{,}\cdots \mathrm{,}\left(u_{m-1}{u}_m\right)\right\}$ and $V\left(P_n\right)=\left\{v_1,v_2,v_3,\cdots ,v_n\right\}$ and $E\left(P_m\right)=\left\{\left(v_1{v}_2\right)\mathrm{,}\left(v_2{v}_3\right)\mathrm{,}\left(v_3{v}_4\right)\mathrm{,}\cdots \mathrm{,}\left(v_{n-1}{v}_n\right)\right\}$. By Proposition 3.1 [2], $\left(P_m{\times }_2{P}_n\right)$ has four components with each component being a grid graph isomorphic to $\left(P_m\square P_n\right)$ with identity map as the bijection. From Theorem 11 [11], paths contain complete minimum geodetic sets, hence, we have $g_n\left(P_m\square P_n\right)=\max \left\{g_n\left(P_m\right),g_n\left(P_n\right)\right\}=\left\{\left(2,2\right)\right\}=2$.

In $\left(P_m{\times }_2{P}_n\right)$ a geodetic set can be formed as follows depending on the values of m and n.

1) If both m and n are even integers then, $P_m{\times }_2{P}_n$ has four isomorphic

components by Proposition 3.1 [2], that is, $P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\frac{m}{2},\frac{n}{2}}\right)}^i\right]$. As each

component is isomorphic to $\left(P_m\square P_n\right)$, a geodetic set is of the form, $\left\{\left(u_1\mathrm{,}{v}_1\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_2\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_n\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_2\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_1\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_2\right)\mathrm{,}\left(u_m\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_n\right)\mathrm{,}\left(u_m\mathrm{,}{v}_2\right)\right\}$.

2) If m is odd and n is even, then $P_m{\times }_2{P}_n$ has two pairs of isomorphic components by Proposition 3.1 [2]. Hence,

$P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\frac{m+1}{2},\frac{n}{2}}\right)}^i\right]\cup \left[{\displaystyle {\cup }_{j=1}^2}{\left(G_{\frac{m-1}{2},\frac{n}{2}}\right)}^j\right]$. Here a geodetic set is of the form,

$\left\{\left(u_1\mathrm{,}{v}_1\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_n\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_1\right)\mathrm{,}\left(u_m\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_n\right)\mathrm{,}\left(u_m\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_2\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_2\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_2\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_2\right)\right\}$.

3) If m is even and n is odd, then $P_m{\times }_2{P}_n$ has two pairs of isomorphic components by Proposition 3.1 [2]. Hence,

$P_m{\times }_2{P}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\frac{m}{2},\frac{n+1}{2}}\right)}^i\right]\cup \left[{\displaystyle {\cup }_{j=1}^2}{\left(G_{\frac{m}{2},\frac{n-1}{2}}\right)}^j\right]$. Here a geodetic set is of the form,

$\left\{\left(u_1\mathrm{,}{v}_1\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_2\right)\mathrm{,}\left(u_m\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_n\right)\mathrm{,}\left(u_m\mathrm{,}{v}_2\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_1\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_2\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_n\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_2\right)\right\}$.

4) If both m and n are odd integers, then $P_m{\times }_2{P}_n$ has four non-isomorphic components by Proposition 3.1 [2]. Therefore,

$P_m{\times }_2{P}_n=\left[\left(G_{\frac{m+1}{2}\mathrm{,}\frac{n+1}{2}}\right)\right]\cup \left[\left(G_{\frac{m+1}{2}\mathrm{,}\frac{n-1}{2}}\right)\right]\cup \left[\left(G_{\frac{m-1}{2}\mathrm{,}\frac{n+1}{2}}\right)\right]\cup \left[\left(G_{\frac{m-1}{2}\mathrm{,}\frac{n-1}{2}}\right)\right]$. A geodetic

set is of the form, $\left\{\left(u_1\mathrm{,}{v}_1\right)\mathrm{,}\left(u_m\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_n\right)\mathrm{,}\left(u_m\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_2\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_n\right)\mathrm{,}\left(u_m\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_1\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_n\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_n\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_1\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_2\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{n-1}\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_{n-1}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_2\right)\right\}$.

By [14] [15] each component has geodetic number 2. Hence $g_n\left(P_m{\times }_2{P}_n\right)=8$, for $m\mathrm{,}n\ge 3$. □

Corollary 3.1. The geochromatic number of 2-cartesian product of two paths is given by, ${\chi }_{gc}\left(P_m{\times }_2{P}_n\right)=8$ , for $m\mathrm{,}n\ge 3$ .

Proof. By Theorem 6 [12], we have $\chi \left(P_m\square P_n\right)=2$. Hence, geodetic set of each component of $P_m{\times }_2{P}_n$ is bicolorable. By the above theorem, each component has geodetic number 2. Since $P_m{\times }_2{P}_n$ has four components isomorphic to $P_m\square P_n$, by Theorem 12 [8] the result follows. □

Theorem 18. The geodetic number number of 2-cartesian product of path $P_m$ with cycle $C_n$ is given by, $g_n\left(P_m{\times }_2{C}_n\right)=\{\begin{array}{l}6,fornodd,\\ 12,forn\equiv 2\left(\mathrm{mod}4\right),\\ 8,forn\equiv 0\left(\mathrm{mod}4\right).\end{array}$

Proof. Let $P_m$ be a path with m vertices and $C_n$ be a cycle with n vertice. Let the vertices abd edges be labelled as $V\left(P_m\right)=\left\{u_1,u_2,u_3,\cdots ,u_m\right\}$ and $E\left(P_m\right)=\left\{\left(u_1{u}_2\right)\mathrm{,}\left(u_2{u}_3\right)\mathrm{,}\left(u_3{u}_4\right)\mathrm{,}\cdots \mathrm{,}\left(u_{m-1}{u}_m\right)\right\}$. Similarly, let $V\left(C_n\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ and $E\left(C_n\right)=\left\{\left(v_1{v}_2\right)\mathrm{,}\left(v_2{v}_3\right)\mathrm{,}\left(v_3{v}_4\right)\mathrm{,}\cdots \mathrm{,}\left(v_{n-1}{v}_n\right)\mathrm{,}\left(v_n{v}_1\right)\right\}$. Hence, we have $V\left(P_m{\times }_2{C}_n\right)=\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{<mo>\; /\; </mo>}{u}_i\in V\left(P_m\right)\text{and}{v}_j\in V\left(C_n\right)\right\}$. As given in the statement, we have three cases as follows:

Case 1: Let n be an odd interger of the form, say, $n=2k+1$ and $k\ge 1$ with $m\ge 3$.

Here we consider two subcases, depending on whether m is odd or even.

Subcase (1a): Let m be odd.

By Proposition 3.2 [2], we get two non-isomorphic components, that is, $P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m+1}{2}\right),\left({\left(n\right)}^0\right)}\right)\right]\cup \left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m-1}{2}\right),\left({\left(n\right)}^0\right)}\right)\right]$. We see that

$\left(G_{\left(\frac{m+1}{2}\right),\left({\left(n\right)}^0\right)}\right)\cong P_{\left(\frac{m+1}{2}\right)}\square C_{\left({\left(n\right)}^0\right)}$ and $\left(G_{\left(\frac{m-1}{2}\right),\left({\left(n\right)}^0\right)}\right)\cong P_{\left(\frac{m-1}{2}\right)}\square C_{\left({\left(n\right)}^0\right)}$ with the identity map as the bijection. As paths contain complete minimum geodetic sets and

cycles contain linear geodetic sets, by Theorem 10 [5], we have $g_n\left(P_m\square C_n\right)=\max \left\{g_n\left(P_m\right)\mathrm{,}{g}_n\left(C_n\right)\right\}=\max \left\{\left(\mathrm{2,3}\right)\right\}=3$. The geodetic set is of the

form $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k+1}\right)\right\}$ or $\left\{\left(u_m\mathrm{,}{v}_j\right),\left(u_1\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+k+1}\right)\right\}$, for

$1\le j\le n$. Similarly, for other component the geodetic set is of the form

$\left\{\left(u_2\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{j+k+1}\right)\right\}$ or $\left\{\left(u_{m-1}\mathrm{,}{v}_j\right)\mathrm{,}\left(u_2\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_2\mathrm{,}{v}_{j+k+1}\right)\right\}$. Hence the geodetic set is given by $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k+1}\right)\right\}$ or

$\left\{\left(u_m\mathrm{,}{v}_j\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+k+1}\right)\right\}$ or $\left\{\left(u_2\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_{m-1}\mathrm{,}{v}_{j+k+1}\right)\right\}$ or

$\left\{\left(u_{m-1}\mathrm{,}{v}_j\right)\mathrm{,}\left(u_2\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_2\mathrm{,}{v}_{j+k+1}\right)\right\}$. By [14] [15] each component has geodetic number 3. Therefore $g_n\left(P_m{\times }_2{C}_n\right)=6$.

Subcase (1b): Let m be even.

By Proposition 3.2 [2], we get two isomorphic components, that is, $P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left(\frac{m}{2}\right),\left({\left(n\right)}^0\right)}\right)}^{\left(i\right)}\right]$. We have $\left(G_{\left(\frac{m}{2}\right),\left({\left(n\right)}^0\right)}\right)\cong P_{\frac{m}{2}}{\times }_2{C}_{\left({\left(n\right)}^0\right)}$ with identity map as the bijection. Similar to the above case we get by Theorem 10 [5], we have $g_n\left(P_{\frac{m}{2}}\square C_n\right)=3$. The geodetic set is of the form

$\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+k+1}\right)\right\}$ or $\left\{\left(u_m\mathrm{,}{v}_j\right),\left(u_1\mathrm{,}{v}_{j+k}\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+k+1}\right)\right\}$, for $1\le j\le n$. By [14] [15] each component has geodetic number 3, to give $g_n\left(P_m{\times }_2{C}_n\right)=6$.

Case 2: Let n be even of the form $n=2l$, $l\ge 1$ and l odd.

Here we consider two subcases, depending on whether m is even or odd.

Subcase (2a): Let m be even.

By Propsition 3.2 [2], we get four isomorphic components, that is,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\frac{m}{2},\left(\frac{n}{2}\right)}\right)}^i\right]$ and we see that $G_{\left(\frac{m}{2}\right)\mathrm{,}\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m}{2}\right)}\square C_l$ with identity map as the bijection. Hence by Theorem 10 [5], $g_n\left(P_{\frac{m}{2}}\square C_l\right)=3$. The geodetic

set is of the form $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l+1}\right)\right\}$ or

$\left\{\left(u_m\mathrm{,}{v}_j\right),\left(u_1\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+l+1}\right)\right\}$ for $1\le j\le n$. By [14] [15] each component has geodetic number 3. Therefore, $g_n\left(P_m{\times }_2{C}_l\right)=12$.

Subcase (2b): Let m be odd.

By Propsition 3.2 [2], we have 2 pairs of isomorphic components, that is,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m+1}{2}\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)\right]\cup \left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m-1}{2}\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)\right]$. We see that

$G_{\left(\frac{m+1}{2}\right),\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m+1}{2}\right)}\square C_l$ and $G_{\left(\frac{m-1}{2}\right)\mathrm{,}\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m-1}{2}\right)}\square C_l$ with identity map as the bijection. Hence by Theorem 3.5 [5], we have $g_n\left(P_{\left(\frac{m+1}{2}\right)}\square C_l\right)=g_n\left(P_{\left(\frac{m-1}{2}\right)}\square C_l\right)=3$.

The geodetic set is of the form $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l+1}\right)\right\}$ or $\left\{\left(u_m\mathrm{,}{v}_j\right),\left(u_1\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+l+1}\right)\right\}$ for $1\le j\le n$. By [14] [15] each component has geodetic number 3. Therefore $g_n\left(P_m{\times }_2{C}_l\right)=12$.

Case 3: Let n be even of the form $n=2l$, $l\ge 1$ and l even.

Here we consider two subcases, depending on whether m is odd or even.

Subcase (3a): Let m be even.

By Proposition 3.2 [2], we have four isomorphic components, that is,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}\left(G_{\left(\frac{m}{2}\right),\left(\frac{n}{2}\right)}^{\left(i\right)}\right)\right]$ and we see that $G_{\left(\frac{m}{2}\right),\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m}{2}\right)}\square C_l$ with identity

map as the bijection. Similar to the above case, by Theorem 3.5 [5], we have

$g_n\left(P_{\left(\frac{m}{2}\right)}\square C_l\right)=\max \left\{g_n\left(P_{\left(\frac{m}{2}\right)}\right)\mathrm{,}{g}_n\left(C_l\right)\right\}=2$. The geodetic set is of the form

$\left\{\left(u_m\mathrm{,}{v}_j\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+l}\right)\right\}$ or $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l}\right)\right\}$ for $1\le j\le n$. By [14] [15] each component has geodetic number 2. Therefore $g_n\left(P_m{\times }_2{C}_l\right)=8$.

Subcase (3b): Let m be odd.

By Proposition 3.2 [2], we have 2 pairs of isomorphic components, that is,

$P_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m+1}{2}\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)\right]\cup \left[{\displaystyle {\cup }_{}}\left(G_{\left(\frac{m-1}{2}\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)\right]$ and we see that $G_{\left(\frac{m+1}{2}\right),\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m+1}{2}\right)}\square C_l$ and $G_{\left(\frac{m-1}{2}\right),\left(\frac{n}{2}\right)}\cong P_{\left(\frac{m-1}{2}\right)}\square C_l$ with identity map as the bijection. Similar to above cases, by Theorem 10 [5], we have $g_n\left(P_{\left(\frac{m+1}{2}\right)}\square C_l\right)$ and $g_n\left(P_{\left(\frac{m-1}{2}\right)}\square C_l\right)=3$. The geodetic set is of the form $\left\{\left(u_1\mathrm{,}{v}_j\right)\mathrm{,}\left(u_m\mathrm{,}{v}_{j+l}\right)\right\}$ or

$\left\{\left(u_m\mathrm{,}{v}_j\right)\mathrm{,}\left(u_1\mathrm{,}{v}_{j+l}\right)\right\}$ for $1\le j\le n$. By [14] [15] each component has geodetic number 2. Therefore $g_n\left(P_m{\times }_2{C}_l\right)=8$. □

Corollary 3.2. The geochromatic number of 2-cartesian product of path $P_n$ cycle $C_n$ is given by, ${\chi }_{gc}\left(P_m{\times }_2{C}_n\right)=\{\begin{array}{l}6,fornodd,\\ 12,forn\equiv 2\left(\mathrm{mod}4\right),\\ 8,forn\equiv 0\left(\mathrm{mod}4\right).\end{array}$

Proof. By Theorem 6 [12], we have $\chi \left(P_m\square C_n\right)=\max \left\{\left(\mathrm{2,3}\right)\right\}=3$ if n is odd and $\chi \left(P_m\square C_n\right)=\max \left\{\left(\mathrm{2,2}\right)\right\}=2$ if n is even. By the above theorem, each component has geodetic number 2 or 3, and $P_m{\times }_2{C}_n$ has either two or four components isomorphic to $P_m\square C_n$. A geodetic set can be found using union from each component, and hence we can permute the vertices of such a geodetic set to have all color class representation, to give a geochromatic set. By Theorem 13 [8], the result follows. □

Theorem 19. For the 2-cartesian product of cycle $C_m$ with cycle graph $C_n$ the geodetic number is given by,

$\begin{array}{l}{g}_n\left(C_m{\times }_2{C}_n\right)\\ =\{\begin{array}{l}5,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 1\left(\mathrm{mod}2\right),\\ 8,form\equiv 0\left(\mathrm{mod}4\right),n\equiv 0\left(\mathrm{mod}4\right),\\ 6,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 0\left(\mathrm{mod}4\right);m\equiv 0\left(\mathrm{mod}2\right),n\equiv 1\left(\mathrm{mod}2\right),\\ 10,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 2\left(\mathrm{mod}4\right),\\ 12,form\equiv 1\left(\mathrm{mod}4\right),n\equiv 0\left(\mathrm{mod}4\right),\\ 20,form\equiv 2\left(\mathrm{mod}4\right),n\equiv 2\left(\mathrm{mod}4\right).\end{array}\end{array}$

Proof. Let $C_m$ be a cycle with m vertices and $C_n$ be a cycle with n vertices, labelled as $V\left(C_m\right)=\left\{u_1\mathrm{,}{u}_2\mathrm{,}{u}_3\mathrm{,}\cdots \mathrm{,}{u}_m\right\}$ and $E\left(C_m\right)=\left\{\left(u_1{u}_2\right),\left(u_2{u}_3\right),\left(u_3{u}_4\right),\cdots ,\left(u_{m-1}{u}_m\right),\left(u_m{u}_1\right)\right\}$ and $V\left(C_n\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ and $E\left(C_n\right)=\left\{\left(v_1{v}_2\right)\mathrm{,}\left(v_2{v}_3\right)\mathrm{,}\left(v_3{v}_4\right)\mathrm{,}\cdots \mathrm{,}\left(v_{n-1}{v}_n\right)\mathrm{,}\left(v_n{v}_1\right)\right\}$. Then we have $V\left(C_m{\times }_2{C}_n\right)=\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{<mo>\; /\; </mo>}{u}_i\in V\left(P_m\right)\text{and}{v}_j\in V\left(C_n\right)\right\}$. As given in the statement we have the following cases:

Case 1: Let $m\mathrm{,}n$ be odd of the form, $m=2k+1,n=2l+1$.

By Proposition 3.3 [2], $C_m{\times }_2{C}_n$ is a connected graph isomorphic to $G_{\left(m^0\right)\mathrm{,}\left(n^0\right)}$, a tied grid graph. Further, $G_{\left(m^0\right)\mathrm{,}\left(n^0\right)}\cong C_m\square C_n$. By Theorem 14 [8], we get

$g_n\left(C_m{\times }_2{C}_n\right)=5$ and the geodetic set is of the form $\left\{\left(u_i,v_j\right),\left(u_{i+k},v_{j+l}\right),\left(u_{i+k},v_{j+l+1}\right),\left(u_{i+k+1},v_{j+l+1}\right),\left(u_{i+k+1},v_{j+l+1}\right)\right\}$, for $1\le i\le m$ and $1\le j\le n$. Hence $g_n\left(C_m{\times }_2{C}_n\right)=5$

Case 2: For $m=2k$, $k\ge 2$, $n=2l$, $l\ge 2$ with $k\mathrm{,}l$ even.

By Proposition 3.3 [2] we have four isomorphic components, that is,

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left({\left(\frac{m}{2}\right)}^0\right)\mathrm{,}\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$ and $G_{{\left(\frac{m}{2}\right)}^0\mathrm{,}{\left(\frac{n}{2}\right)}^0}\cong C_k\square C_l$ with identity map

as the bijection. By Theorem 11 [11], we have $g_n\left(C_k\square C_l\right)=2$. The geodetic sets are of the form $\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_{j+l}\right)\right\}$ or $\left\{\left(u_i\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_j\right)\right\}$ for $1\le i\le m$ and $1\le j\le n$. By [14] [15] each component has geodetic number 2. Hence geodetic set of $g_n\left(C_k{\times }_2{C}_l\right)=8$.

Case 3: For $m=2k+1$, $n=2l$, with l even and $m=2k$, $n=2l+1$ with k even.

By Proposition 3.3 [2], we get two pairs of isomorphic components, that is,

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left({\left(m\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$ and $G_{{\left(m\right)}^0\mathrm{,}{\left(\frac{n}{2}\right)}^0}\cong C_{2k+1}\square C_l$ with identity map

as the bijection. Similar to the above case by Theorem 11 [11], we get

$g_n\left(C_{2k+1}\square C_l\right)=3$. The geodetic set is given by $\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_{j+l}\right)\right\}$

or $\left\{\left(u_i\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_j\right)\right\}$ for $1\le i\le m$ and $1\le j\le n$. By [14] [15] each component has geodetic number 3. Hence geodetic set of $g_n\left(C_{2k+1}{\times }_2{C}_l\right)=6$.

Case 4: For $m=2k+1$, $n=2l$ with l odd and $m=2k$, n with k odd.

By Proposition 3.3 [2], we get two pairs of isomorphic components, that is,

$C_{2k+1}{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^2}{\left(G_{\left({\left(m\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$ and $G_{{\left(m\right)}^0,{\left(\frac{n}{2}\right)}^0}\cong C_{2k+1}\square C_l$ with identity

map as the bijection. Similar to the above case by Theorem 11 [11], we have $g_n\left(C_{2k+1}\square C_{2l}\right)=3$. The geodetic set is given by $\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_{j+l}\right)\right\}$ or $\left\{\left(u_i\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_j\right)\right\}$. By [14] [15] each component has geodetic number 3. Hence geodetic set of $g_n\left(C_{2k+1}{\times }_2{C}_l\right)=6$.

Case 5: For $m=2k$, $n=2l$ and k odd, l even.

By Proposition 3.3 [2], we get four isomorphic components, that is,

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left({\left(\frac{m}{2}\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$ and $G_{{\left(\frac{m}{2}\right)}^0\mathrm{,}{\left(\frac{n}{2}\right)}^0}\cong C_k\square C_l$ with identity map

as the bijection. Using Theorem 11 [11], we get $g_n\left(C_k\square C_l\right)=3$. The geodetic set is given by $\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_{j+l}\right)\right\}$ or

$\left\{\left(u_i\mathrm{,}{v}_{j+l}\right)\mathrm{,}\left(u_{i+k}\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i+k+1}\mathrm{,}{v}_j\right)\right\}$. By [14] [15] each component has geodetic number 3, hence geodetic number of $g_n\left(C_k{\times }_2{C}_l\right)=12$.

Case 6: For $m=2k$, $n=2l$ and $k\mathrm{,}l$ odd.

By Proposition 3.3 [2], we get four isomorphic components, that is,

$C_m{\times }_2{C}_n=\left[{\displaystyle {\cup }_{i=1}^4}{\left(G_{\left({\left(\frac{m}{2}\right)}^0\right),\left({\left(\frac{n}{2}\right)}^0\right)}\right)}^{\left(i\right)}\right]$ and $G_{{\left(\frac{m}{2}\right)}^0\mathrm{,}{\left(\frac{n}{2}\right)}^0}\cong C_k\square C_l$ with identity map

as the bijection. By Theorem 14 [8] we get $g_n\left(C_k\square C_l\right)=5$. The geodetic sets are of the form $\left\{\left(u_i,v_j\right),\left(u_{i+k},v_{j+l}\right),\left(u_{i+k},v_{j+l+1}\right),\left(u_{i+k+1},v_{j+l+1}\right),\left(u_{i+k+1},v_{j+l+1}\right)\right\}$.

By [14] [15] each component has geodetic number 5. Hence $g_n\left(C_k{\times }_2{C}_l\right)=20$.

□

Corollary 3.3. The geochromatic number of 2-cartesian product of cycle $C_m$ with cycle $C_n$ is given by,

$\begin{array}{l}{\chi }_{gc}\left(C_m{\times }_2{C}_n\right)\\ =\{\begin{array}{l}5,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 1\left(\mathrm{mod}2\right),\\ 8,form\equiv 0\left(\mathrm{mod}4\right),n\equiv 0\left(\mathrm{mod}4\right),\\ 6,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 0\left(\mathrm{mod}4\right);m\equiv 0\left(\mathrm{mod}2\right),n\equiv 1\left(\mathrm{mod}2\right),\\ 10,form\equiv 1\left(\mathrm{mod}2\right),n\equiv 2\left(\mathrm{mod}4\right),\\ 12,form\equiv 1\left(\mathrm{mod}4\right),n\equiv 0\left(\mathrm{mod}4\right),\\ 20,form\equiv 2\left(\mathrm{mod}4\right),n\equiv 2\left(\mathrm{mod}4\right).\end{array}\end{array}$

Proof. By Theorem 6 [12], $\chi \left(C_m\square C_n\right)=\max \left\{\left(\mathrm{2,3}\right)\right\}=3$, if n is odd and

$\chi \left(C_m\square C_n\right)=\max \left\{\left(\mathrm{2,2}\right)\right\}=2$, if n is even. By the above theorem, each component has geodetic number 2, 3 or 5. A geodetic set can be found using union from each component, and hence we can permute the vertices of such a geodetic set to have all color class representation, to give a geochromatic set. By Theorem 14 [8] result follows. □

Theorem 20. The geodetic number of 2-cartesian product of complete bipartite graph $K_{s\mathrm{,}t}$ with path $P_m$ is given by,

$g_n\left(K_{s\mathrm{,}t}{\times }_2{P}_m\right)=\{\begin{array}{l}4s\mathrm{,}fors=tandmeven,\\ 2s+2t\mathrm{,}fors\ne t,otherwise.\end{array}$

Proof. Let $K_{s\mathrm{,}t}$ be a complete bipartite graph with $U_1$ and $U_2$ as two partite sets. Let $V\left(P_m\right)=\left\{v_1,v_2,v_3,\cdots ,v_m\right\}$. $K_t\mathrm{,}{K}_s$ and $P_m$ contain complete minimum geodetic sets. As given in the statement we have the following cases depending on $s\mathrm{,}t$ and m.

Case 1: Let m be even.

Using Proposition 3.4 [2], we get two pairs of isomorphic components of the

form $K_s\square P_{\left(\frac{m}{2}\right)}$ or $K_t\square P_{\left(\frac{m}{2}\right)}$ with identity mapping as the bijection. We know

that each component is isomorphic to cartesian product of a complete graph and a path. Hence, we get the geodetic number to be s or t. By Theorem 11 [11],

$g_n\left(K_s\square P_{\left(\frac{m}{2}\right)}\right)\mathrm{<mo>\; =\; </mo>}\max \left\{g_n\left(K_s\right),g_n\left(P_{\frac{m}{2}}\right)\right\}=\max \left\{\left(s,2\right)\right\}=s$, for $s\ge 2$ and $g_n\left(K_t\square P_{\left(\frac{m}{2}\right)}\right)\mathrm{<mo>\; =\; </mo>}\max \left\{g_n\left(K_t\right),g_n\left(P_{\frac{m}{2}}\right)\right\}=\max \left\{\left(t,2\right)\right\}=t$, for $t\ge 2$. Hence a geodetic set is of the form $\left\{\left(u_i\mathrm{,}{v}_1\right)\mathrm{,}\left(u_j\mathrm{,}{v}_{\left(\frac{m}{2}\right)}\right)\right\}$ or $\left\{\left(u_i\mathrm{,}{v}_{\left(\frac{m}{2}\right)}\right)\mathrm{,}\left(u_j\mathrm{,}{v}_1\right)\right\}$ for

( $1\le i\le s$ or t), ( $1\le j\le s$ or t) and $i\ne j$. By [14] [15] each component has geodetic number is s and t. Hence $g_n\left(K_{s\mathrm{,}t}{\times }_2{P}_n\right)=4s$ or 4t, if $s=t$ and $g_n\left(K_{s\mathrm{,}t}{\times }_2{P}_n\right)=2s+2t$, if $s\ne t$.

Case 2: Let m be odd.

Using Proposition 3.4 [2], we have four non isomorphic components, that is,

$K_s\times P_{\left(\frac{m+1}{2}\right)}$, $K_s\times P_{\left(\frac{m-1}{2}\right)}$, $K_t\times P_{\left(\frac{m+1}{2}\right)}$, $K_t\times P_{\left(\frac{m-1}{2}\right)}$ with identity mapping as the

bijection and each being isomorphic to the cartesian product of a complete graph and a path. Similar to the above case, we get the geodetic number equal to s or t, in each case by [14] [15]. Hence $g_n\left(K_{s,t}{\times }_2{P}_n\right)=2\left(s+t\right)$. □

Corollary 3.4. The geochromatic number of 2-cartesian product of complete bipartite graph $K_{s\mathrm{,}t}$ with path $P_m$ is given by,

${\chi }_{gc}\left(K_{s\mathrm{,}t}{\times }_2{P}_m\right)=\{\begin{array}{l}4s\mathrm{,}fors=t,\\ 2s+2t\mathrm{,}fors\ne t.\end{array}$

Proof. By Theorem 6 [12], $\chi \left(K_m\square P_n\right)=\max \left\{\left(m\mathrm{,2}\right)\right\}=m$, we have $K_s$ is s colorable and $K_t$ is t colorabe. By the above theorem, each component has geodetic number s or t. Since $K_{s\mathrm{,}t}{\times }_2{P}_n$ has four components isomorphic to $K_m\square P_n$ each of them being s and t colorable. A geodetic set can be found using union for each component and hence we can permute the vertices of such geodetic set to have all color class representation, to give a geochromatic set. By Theorem 15 [8], the result follows. □

Theorem 21. The geodetic number of 2-cartesian product of complete bipartite graph $K_{s\mathrm{,}t}$ with cycle $C_m$ is given by,

$g_n\left(K_{s\mathrm{,}t}{\times }_2{C}_m\right)=\{\begin{array}{l}4s\mathrm{,}fors=tandmeven,\\ 2s+2t\mathrm{,}fors\ne tandmeven,\\ 2\left(s+t-1\right)\mathrm{,}formodd.\end{array}$

Proof. Let $K_{s\mathrm{,}t}$ be a complete bipartite graph with $U_1$ and $U_2$ partite sets. Let $V\left(C_m\right)=\left\{v_1,v_2,v_3,\cdots ,v_m\right\}$. As given in the statement, we have the following cases depending on $s\mathrm{,}t$ and m.

Case 1: Let m be even.

Using Proposition 3.5 [2], we have four components, two components each

isomorphic to $K_s\square C_{\left(\frac{m}{2}\right)}$ and $K_t\square C_{\left(\frac{m}{2}\right)}$ with identity mapping as the bijection

and each being isomorphic to cartesian product of a complete graph and a cycle.

Hence, by Theorem 11 [11] we have $g_n\left(K_s\times C_{\left(\frac{m}{2}\right)}\right)=\max \left\{s\mathrm{,2}\right\}=s$ and $g_n\left(K_t\times C_{\left(\frac{m}{2}\right)}\right)=\max \left\{t\mathrm{,2}\right\}=t$, we get the geodetic number equal to s or t, by [14]

[15] for each component. Hence geodetic set is of the form $\left\{\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i^{\prime }}\mathrm{,}{v}_{j^{\prime }}\right)\right\}$, for $i\ne i^{\prime }$, $1\le i\mathrm{,}{i}^{\prime }\le m$. Hence $g_n\left(K_{s\mathrm{,}t}{\times }_2{C}_n\right)=4t$ or 4s, if $s=t$ and $g_n\left(K_{s\mathrm{,}t}{\times }_2{P}_n\right)=2s+2t$ if $s\ne t$.

Case 2: Let m be odd.

Using Proposition 3.5 [2], we get two components isomrphic to $K_s\square C_m$, $K_t\square C_m$. By Theorem 16 [8], we get $g_n\left(K_s\square C_m\right)=2s-1$ and $g_n\left(K_t\square C_m\right)=2t-1$ and a geodetic set is of the form $\left(\left(u_i\mathrm{,}{v}_j\right)\mathrm{,}\left(u_{i^{\prime }}\mathrm{,}{v}_{j^{\prime }}\right)\left(u_{i^{\prime }}\mathrm{,}{v}_{j^{\prime }+1}\right)\right)$ for ( $1\le i\le s$ or t), ( $1\le j\le s$ or t) and $i\ne j$. By [14] [15] each component has geodetic number is $2s-1$ and $2t-1$. Hence $g_n\left(K_{s\mathrm{,}t}{\times }_2{C}_n\right)=2s+2t-2$. □

Corollary 3.5. The geochromatic number of 2-cartesian product of complete bipartite graph $K_{s\mathrm{,}t}$ with cycle $C_n$ is given by,

${\chi }_{gc}\left(K_{s\mathrm{,}t}{\times }_2{C}_n\right)=\{\begin{array}{l}4s\mathrm{,}fors=tandmeven,\\ 2s+2t\mathrm{,}fors\ne tandmeven,\\ 2\left(s+t-1\right)\mathrm{,}formodd.\end{array}$

Proof. By Theorem 6 [12], $\chi \left(K_m\square C_n\right)=\max \left\{\left(m\mathrm{,2}\right)\right\}=m$. By the above theorem, each component has geodetic number $s,t$. Since $K_{s\mathrm{,}t}{\times }_2{C}_n$ has two or four components isomorphic to $K_m\square C_n$. A geodetic set can be found using union from each component and hence we can permute the vertices of such a geodetic set to have all color class representation, to get a geochromatic set. By Theorem 16 [8] result follows. □

4. Conclusion

Here we have determined geodetic number and geochromatic number of 2-cartesian product of some special class of graphs like complete graphs, cycles and paths. This procedure can be extended to find the geodetic number and geo-chromatic number of r-cartesian products, in general for graphs.

Acknowledgements

We highly appreciate suggestions given by unknown referees that have improved overall presentation of the paper.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Acharya, U.P. and Mehta, H.S. (2015) Generalized Cartesian Product of Graphs. International Journal of Mathematics and Scientific Computing, 5, 4-7.
[2]	Acharya, U.P. and Mehta, H.S. (2014) 2-Cartesian Product of Special Graphs. International Journal of Mathematics and Soft Computing, 4, 139-144.
[3]	Harary, F., Loukakis, E. and Tsouros, C. (1993) The Geodetic Number of a Graph. Mathematical and Computer Modelling, 17, 89-95.
[4]	Chartrand, G., Harary, F. and Zhang, P. (2002) On the Geodetic Number of a Graph. Networks, 39, 1-6. https://doi.org/10.1002/net.10007
[5]	Chartrand, G., Harary, F. and Zhang, P. (2000) Geodetic Sets in Graphs. Discussiones Mathematicae Graph Theory, 20, 129-138. https://doi.org/10.7151/dmgt.1112
[6]	Samli, B.S. and Chellathurai, R.S. (2018) Geochromatic Number of a Graph. International Journal of Scientific Research in Mathematical and Statistical Sciences, 5, 259-264.
[7]	Stanis Arul Mary, S.A. (2020) Geo Chromatic Number for Certain Cartesian Product of Graphs. International Journal of Mathematics Trends and Technology, 66, 40-43. https://doi.org/10.14445/22315373/IJMTT-V66I1P507
[8]	Huilgol, M.I. and Divya, B. (2021) Geochromatic Number of Cartesian Product of Some Graphs. Journal of Mathematics and Computer Science, 11, 3866-3886.
[9]	Buckley, F. and Harary, F. (1990) Distance in Graphs. Addison-Wesley Publishing Company, Redwood City.
[10]	Khayoom, M.M.A., Arul, P. and Sudhahar, P. (2017) Monophonic Chromatic Parameter in a Connected Graph. International Journal of Mathematical Analysis, 11, 911-920. https://doi.org/10.12988/ijma.2017.78114
[11]	Breser, B., Klavžar, S. and Horvat, S.T. (2008) On the Geodetic Number and Related Metric Sets in Cartesian Product Graphs. Discrete Mathematics, 308, 5555-5561.
[12]	Hammack, R., Imrich, W. and Klavzar, S. (2011) Handbook of Product of Graphs. CRC Press, New York.
[13]	Mulder, H.M. (1980) The Interval Function of a Graph. Vol. 132, Mathematisch Centrum, Amsterdam.
[14]	Xaviour, X.L. and Chellathurai, R.S. (2020) Geodetic Global Domination in the Join of Two Graphs. International Journal of Recent Technology and Engineering, 8, 4579-4583. https://doi.org/10.35940/ijrte.E6770.018520
[15]	Xaviour, X.L. and Prakash, S.V.A. (2018) Isolate Geodetic Number of a Graph. Journal of Applied Science and Computations, 5, 755-765.