Bety Hayat Susanti¹a^b , A.N.M. Salman^a , Rinovia Simanjuntak^a

^aCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia ^bSekolah Tinggi Sandi Negara, Jl. Raya H. Usa, Putat Nutug, Ciseeng, Bogor, Indonesia

bety.hayat@stsn-nci.ac.id, msalman@math.itb.ac.id, rino@math.itb.ac.id

An edge-colored graph G is rainbow k-connected, if there are k-internally disjoint rainbow paths connecting every pair of vertices of G. The rainbow k-connection number of G, denoted by rck(G), is the minimum number of colors needed for which there exists a rainbow k-connected coloring for G. In this paper, we are able to find sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products of some graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.

Keywords: Cartesian product, 2-connected graph, rainbow 2-connectivity, rainbow path Mathematics Subject Classification: 05C15, 05C40

DOI: 10.5614/ejgta.2020.8.1.11

1. Introduction

All graphs considered in this paper are undirected, simple, and finite. Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , `}, ` ∈ N, where adjacent edges may receive the same color. An edge-colored path P in G is rainbow if no two edges of P are colored the same. An edge-colored graph G is rainbow connected, if for any two distinct vertices of G, there exists a rainbow path which connects them. An edge-coloring under which G is rainbow

Received: 11 March 2019, Revised: 15 June 2019, Accepted: 5 January 2020.

¹Corresponding author

connected is called a rainbow coloring. The minimum number of colors for which there exists a rainbow coloring of G is called the rainbow connection number of G, and denoted by rc(G). These concepts were introduced by Chartrand et al. in [3].

Chakraborty et al. [2] investigated the computational complexity and algorithms for the rainbow connection number and they showed that finding the rainbow connection number of a graph is NP-hard. Numerous authors have investigated bounds, algorithms, and computational complexity of the rainbow connection number of some graphs. Some results about rainbow connection number of certain graphs have been determined by some researchers, such as, complete graphs, trees, complete bipartite graphs, and complete multipartite graphs [3], rocket graphs [21], pencil graphs [24], flower graphs [14], origami graphs and pizza graphs [27], stellar graphs [23], and some subdivided roof graphs [26]. In 2018, Septyanto and Sugeng [22] generalized the notion of "color codes" that was originally used by Chartrand et al. [3] in their study of the rc of complete bipartite graphs, so that it can be applied to any connected graph. Meanwhile, some results about rainbow connection number of graphs resulted from graph operations were also investigated by some researchers, such as Cartesian product [16, 1], strong product [1, 10], lexicographic product [16, 1, 10], direct product [10], corona product [6], and amalgamation [8]. Interested readers can see [17, 19] for details on this topic.

In 2009, the concept of rainbow k-connectivity was introduced by Chartrand et al. in [4] as follows. Recall that a graph G is called k − connected if |V (G)| > k and G − X is connected for every set X ⊆ V (G) with |X| < k [7]. It follows from Whitney's Theorem [5], a graph G is k-connected if and only if for every two distinct vertices x and y of G, the graph G contains k internally disjoint x − y paths. An edge-coloring of G is called rainbow k-connected if, for any two distinct vertices x and y of G, the graph contains k internally disjoint rainbow x−y paths. The minimum number of colors for which there exists a rainbow k-connected coloring of G is called the rainbow k-connection number of G, denoted by rck(G). In this case, the function rck(G) is only defined for k-connected graphs.

The rainbow k-connection number for some basic graphs have been known, such as for complete graphs, regular complete bipartite graphs [4], and complete multipartite graphs [15]. Some upper bounds have also been derived for the rainbow k-connection number of dense graphs [9] and random graphs [9, 12]. The concept of rainbow k-connectivity can also be applied in transferring classified information in secured communication networks [4].

In particular, the exact values of rainbow 2-connection number of graphs have also investigated by some researchers, i.e., complete graphs and regular complete bipartite graphs [4]. Some other researchers also gave upper bounds for the rainbow 2-connection number for some graph classes, i.e., 2-connected graphs [18] and Cayley graphs [20]. Moreover, Li and Liu [18] showed that if G is a 2-connected graph, then rc² ≤ order(G) with equality holds if and only if G is a cycle. In [25], we derived upper bounds for the rainbow 2-connection number of the Cartesian product of paths and cycles.

In this paper, we generalize our previous result by deriving sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products between complete graphs, fans, wheels, and cycles, with paths.

2. Main results

The following definition of the Cartesian product of two graphs is taken from Hammack et al. [11]. The Cartesian product of G and H is a graph, denoted by \(G \square H\), whose vertex set is \(V(G) \times V(H)\) and two vertices (x,y) and (x',y') are adjacent if x=x' and \(yy' \in E(H)\), or \(xx' \in E(G)\) and y=y'. Thus, \(V(G \square H)=\{(x,y)|x\in V(G) \text{ and } y\in V(H)\}\) and \(E(G \square H)=\{(x,y)(x',y')|x=x' \text{ and } yy'\in E(H), \text{ or } xx'\in E(G) \text{ and } y=y'\}\). The vertex set \(G^h=\{(g,h):g\in V(G)\}\) for some fixed vertex h of H is called the layer of graph G or simply a G-layer through G. Similarly, G-layer and G-layer induces a subgraph of G-layer that is isomorphic to G and G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G and G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer that is isomorphic to G-layer through G-layer through G-layer induces a subgraph of G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer through G-layer thro

We use the following definition of k-distance and k-diameter of a graph G from Hsu and Łuczak [13] as follows.

Definition 1. [13] Let G be a k-connected graph and x, y be any two distinct vertices of G. Let \(P_k(x, y)\) be a family of k disjoint paths between x and y, where

\[\mathcal{P}_k(x,y) = \{P_1, P_2, \dots, P_k\}\]

with \(|P_1| \leq |P_2| \leq \ldots \leq |P_k|\) and \(|P_i|\) denotes the number of edges in \(P_i\) for \(1 \leq i \leq k\). The k-distance between vertices x and y, denoted by \(d_k(x,y)\), is defined as the minimum integer \(d_k(x,y)\) for which there are k internally disjoint paths of length at most \(d_k(x,y)\) between x and y in G. The k-diameter of G, denoted by \(diam_k(G)\), is defined as \(max\{d_k(x,y)|x,y\in V(G)\}\).

Fact 2.1. [13] If G is k-connected, then

\[diam_k(G) \ge diam_{k-1}(G) \ge \ldots \ge diam_1(G) = diam(G).\]

In [3], Chartrand et al. stated that the rainbow connection number of a non trivial connected graph G is at least the diameter of G. By using Fact 2.1, we obtain lower bounds of the rainbow k-connection number of G as follows.

Proposition 2.1. Let k be a positive integer. If G is a k-connected graph, then

\[diam(G) \le diam_k(G) \le rc_k(G)\].

Proof. The first inequality follows from Fact 2.1.

Now, we want to prove for the second inequality. Suppose that \(diam_k(G) = s\) and x, y are two arbitrary vertices in G. If \(d_k(x,y) = s\), then we need at least s different colors to color k paths to be rainbow paths. If \(d_k(x,y) < s\), then we can color all the k internally disjoint paths with some other additional colors. Both cases show that \(rc_k(G) \ge s\).

For simplicity, we define \[[a,b] = \{x \in \mathbb{Z} | a \le x \le b\}\] and \(a \mod^* b = \begin{cases} a \mod b, & \text{if } a \ne kb \text{ for any } k \in \mathbb{Z}; \\ b, & \text{if } a = kb \text{ for some } k \in \mathbb{Z}. \end{cases}\)

In the main theorems, we shall follow the following notations: \(P_n\) is a path on n vertices, \(C_n\)is a cycle on n vertices, \(K_n\) is a complete graph on n vertices, \(W_n = C_n + K_1\) is a wheel on n + 1vertices, and \(F_n = P_n + K_1\) is a fan on n + 1 vertices.

The following theorem provides lower and upper bounds for rainbow 2-connection number of Cartesian products of 2-connected graphs and paths.

Theorem 2.1. Let m be a positive integer at least 2. If G is a 2-connected graph, then

\[diam_2(G \square P_m) \le rc_2(G \square P_m) \le \lceil \frac{m}{rc_2(G)} \rceil (rc_2(G)) + m - 1.\]

Proof. It is obvious that \(diam_2(G \square P_m) \leq rc_2(G \square P_m)\).

Let \(V(G \square P_m) = \{g_i^{h_j} | g_i \in V(G), h_j \in V(P_m), i \in [1, |V(G)|], j \in [1, m]\}\). Let \(E(G) = \{e_i | i \in P_m\}\)[1,k]}. For \(j \in [1,m]\), let \(G^{h_j}\) be a G-layer through \(h_j\) and let \(e_i^{h_j}\) be an edge in \(G^{h_j}\) with \(i \in [1,k]\). Let c be a rainbow \(rc_2(G)\)-coloring of G. Let \(rc_2(G) = d\).

We define a coloring \[c': E(G \square P_m) \to [1, \lceil \frac{m}{d} \rceil (d) + m - 1]\] as follows. \[c'(e_i^{h_j}) = \begin{cases} c(e_i), & \text{for } j = 1 \text{ and } i \in [1, k]; \\ (c'(e_i^{h_1}) + j - 1) \mod^* d, & \text{for } j \in [2, d] \text{ and } i \in [1, k]; \\ c'(e_i^{h_1}) + \ell d, & \text{for } j \in \ell d + 1 \text{ and } \ell \in [1, \lceil \frac{m}{d} \rceil - 1]; \\ (c'(e_i^{\ell d + 1}) + j - 1) \mod^* d + \ell d, & \text{for } j \in \bigcup_{k = 1}^{\lfloor \frac{m}{d} \rceil - 1} [kd + 2, (k + 1)d] \\ & \text{and } \ell \in [1, \lceil \frac{m}{d} \rceil - 1]. \end{cases}\] \[c(g_i^{h_j} g_i^{h_{j+1}}) = \lceil \frac{m}{d} \rceil d + j, \text{ for } j \in [1, m - 1] \text{ and } i \in [1, |V(G^{h_j})].\] We consider any two vertices \(x, y \in V(G \square P_m)\). Clearly, there exist two internally disjoint \(x - y\) rainbow paths by coloring \(c'\) which connections.

Clearly, there exist two internally disjoint x-y rainbow paths by coloring c' which connect x and

Case 2. \(x \in V(G^{h_j})\) and \(y \in V(G^{h_r})\) for \(j, r \in [1, m]\) with \(j \neq r\). Subcase 2.1. If \(x = g_l^{h_j} \in V(G^{h_j})\) and \(y = g_l^{h_r} \in V(G^{h_r})\) with j < r, then there exist two internally disjoint x - y rainbow paths, i.e. \(g_l^{h_j}, g_l^{h_{j+1}}, \ldots, g_l^{h_r}\) and \(g_l^{h_j}, g_s^{h_j}, g_s^{h_{j+1}}, \ldots, g_s^{h_r}, g_l^{h_r}\) where \(g_l^{h_j}g_s^{h_j} \in E(G^{h_j})\) which connect \(g_l^{h_j}\) and \(g_l^{h_r}\).

Subcase 2.2. If \(x = g_l^{h_j} \in V(G^{h_j})\) and \(y = g_s^{h_r} \in V(G^{h_r})\) with j < r, then there exist two internally disjoint x-y rainbow paths, i.e. \(g_l^{h_j}, g_l^{h_{j+1}}, \dots, g_l^{h_r}, \dots, g_s^{h_r}\) and \(g_l^{h_j}, \dots, g_s^{h_j}, g_s^{h_{j+1}}, \dots, g_s^{h_{r-1}}, \dots\)\(g_s^{h_r}\).

Hence, \(rc_2(G \square P_m) \leq \lceil \frac{m}{rc_2(G)} \rceil (rc_2(G)) + m - 1\). Thus, we complete the proof.

Since \(diam_2(F_n \square P_m) = n + m - 2\) for \(m \ge 2, n \ge 4\) and \(rc_2(F_n) = n - 1\) for \(n \ge 4\), we obtain that for \(m \leq (n-1)\), the lower and upper bounds of \(rc_2(F_n \square P_m)\) as written in Theorem 2.1 coincide. Hence, we get the following corollary.

Corollary 2.1. Let m and n be two positive integers with \(n \ge 4\), \(m \ge 2\), and \(m \le (n-1)\). Then

\[rc_2(F_n \square P_m) = \lceil \frac{m}{(n-1)} \rceil (n-1) + m - 1.\]

Figure 1. A rainbow 2-connected coloring on \(F_5 \square P_3\).

As shown in Figure 1, we present a rainbow 2-connected coloring on \(F_n \square P_m\) for n=5 and m = 3.

Although we could not extend the proof of Corollary 2.1 for m > n-1, we raised the following conjecture.

Conjecture 1. Let m and n be two positive integers with \(n \ge 4\), \(m \ge 2\), and m > (n-1). Then

\[rc_2(F_n \square P_m) = \lceil \frac{m}{(n-1)} \rceil (n-1) + m - 1.\]

The following theorem gives an example of Cartesian products of 2-connected graphs and paths whose rainbow 2-connection number achieves the lower bound of Theorem 2.1.

Theorem 2.2. If \(n \ge 4\) and \(m \ge 2\), then

\[rc_2(K_n \square P_m) = m + 1 = diam_2(K_n \square P_m).\]

Proof. Since \(diam_2(K_n \square P_m) = m+1\), it is clear that \(rc_2(K_n \square P_m) \ge diam_2(K_n \square P_m) = m+1\). Let \(V(K_n \square P_m) = \{u_i^j | 1 \le i \le n, 1 \le j \le m\}\) and \(E(K_n \square P_m) = \{u_i^j u_{i+1}^j, u_i^j u_k^j, u_i^j u_i^{j+1} | 1 \le j \le m\}\)\(i, k \le n, 1 \le j \le m-1\) where \(i \ne k, k \ne i+1\), and \(u_n^j u_{n+1}^j = u_n^j u_1^j\).

Next, we shall consider a proof of the upper bound. We define an edge-coloring \(c: E(K_n \square P_m) \to \mathbb{R}\)[1, m+1] as follows.

\[c(u_i^j u_{i+1}^j) = \begin{cases} 1, & \text{for } i \in [1, n] \text{ and } j = 1; \\ j, & \text{for } i \in [1, n] \text{ and } j \in [2, m]. \end{cases}\]

For \[i \neq k\] and \(i \neq k-1\), we define the following colors to the coloring \(c\). \[c(u_i^j u_k^j) = \begin{cases} 2, & \text{for } i \in [1, n] \text{ and } j = 1; \\ 1, & \text{for } i \in [1, n] \text{ and } j \in [2, m]. \end{cases}\]\[c(u_i^j u_i^{j+1}) = 2 + j, \text{ for } i \in [1, n] \text{ and } j \in [1, m-1].\]

We shall show that the above coloring is a rainbow 2-connected (m+1)-coloring of \(K_n \square P_m\). Consider any two distinct vertices \(x, y \in V(K_n \square P_m)\), we divided the proof into two cases.

Case 1. For \(x=u_i^j\) and \(y=u_k^j, x,y\in V(K_n^j), i\in [1,n], i\neq k,j\in [1,m]\), then, there exist two internally disjoint x-y rainbow paths which connect them, i.e., \(u_i^j, u_k^j\) and \(u_i^j, u_{k+1}^j, u_k^j\).

Case 2. For \(x \in V(K_n^j)\) and \(y \in V(K_n^l)\), \(j \neq l, j, l \in [1, m]\), we divide into two subcases. For \(x = u_i^j \in V(K_n^j)\) and \(y = u_i^l \in V(K_n^l)\), \(i \in [1, n]\), there exist two internally disjoint rainbow paths which connect x and y, i.e., \(u_i^j, u_i^{j+1}, \ldots, u_i^{l-1}, u_i^l\) and \(u_i^j, u_{i+2}^j, u_{i+2}^{j+1}, \ldots, u_{i+2}^l, u_i^l\). For \(x = u_i^j \in V(K_n^j)\) and \(y = u_k^l \in V(K_n^l)\), \(i \neq k, i, k \in [1, n]\), there exist two internally disjoint rainbow paths which connect x and y, i.e., \(u_i^j, u_i^{j+1}, \ldots, u_i^l u_k^l\) and \(u_i^j, u_j^j, u_i^{j+1}, \ldots, u_k^l\) for \(k \neq i+1\) or \(u_i^j, u_{i+1}^j, u_{i+1}^{j+1}, \ldots, u_{i+1}^l\) and \(u_i^j, u_{i+3 \mod n}^j, u_{i+3 \mod n}^j, \ldots, u_{i+3 \mod n}^l\), \(u_i^l\) for \(k \neq i+1\). So, this completes the proof.

We present a rainbow 2-connected coloring on \(K_n \square P_m\) for n=5 and m=3, as shown in Figure 2.

Figure 2. A rainbow 2-connected coloring on \(K_5 \square P_3\).

In the next theorem, we give an example of Cartesian products of 2-connected graphs and paths whose rainbow 2-connection number achieves the upper bound of Theorem 2.1.

Theorem 2.3. If \(n \ge 4\) and \(m \ge 2\), then

\[rc_2(W_n \square P_m) \le \lceil \frac{m}{\lceil \frac{n}{2} \rceil} \rceil \lceil \frac{n}{2} \rceil + m - 1,\]

and equality holds for \(n \in [4, 6]\) and \(m \leq \lceil \frac{n}{2} \rceil\).

Proof. Since, \(rc_2(W_n) = \lceil \frac{n}{2} \rceil\), the upper bound is a direct consequence of Theorem 2.1. Let \(V(W_n \Box P_m) = \{u_i^j | 0 \le i \le n, 1 \le j \le m\}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\) and \(E(W_n \Box P_m) = \{u_i^j u_{i+1}^j | i \in [1, n-1] \}\)

\(j \in [1, m-1]\).

For n=4, the lower bound is exactly the same with the upper bound since \(diam_2(W_4 \square P_2)=3\). For \(n \in [5,6]\), assume to the contrary that \(rc_2(W_n \square P_m) \leq \lceil \frac{n}{2} \rceil + m-2\).

Let c' be a rainbow 2-connectivity of \(W_n \square P_m\) using \(\lceil \frac{n}{2} \rceil + m - 2\) colors. Consider two vertices \(u_1^1\) and \(u_3^3\), then there exist three internally disjoint paths with length 4 which connect them, i.e. \(u_1^{\hat{1}}, u_1^2, u_1^3, u_0^3, u_3^3; u_1^1, u_0^1, u_3^1, u_3^2, u_3^3;\) and \(u_1^1, u_2^1, u_2^2, u_2^3, u_3^3.\) There are three combinations of paths that need to be reviewed, but they all lead to a contradiction. First, we consider \(u_1^1, u_1^2, u_1^3, u_0^3, u_3^3\) and \(u_1^1, u_0^1, u_3^1, u_3^2, u_3^3\) paths. Without loss of generality, color \(c'(u_1^1u_1^2) = 1, c'(u_1^2u_1^3) = 2, c'(u_1^3u_0^3) = 3,\)and \(c'(u_0^3u_3^3) = 4\). Hereafter, color \(c'(u_1^1u_0^1) = 4\), \(c'(u_0^1u_3^1) = 3\), \(c'(u_3^1u_3^2) = 2\), and \(c'(u_3^2u_3^3) = 4\). 1. Next, consider vertices \(u_2^1\) and \(u_4^3\), then there exist three internally disjoint paths with length 4, i.e. \(u_2^1, u_2^2, u_3^3, u_4^3; u_2^1, u_3^1, u_4^1, u_4^2, u_4^3;\) and \(u_2^1, u_0^1, u_0^2, u_0^3, u_4^3.\) Consider paths \(u_2^1, u_2^2, u_2^3, u_3^3, u_4^3\) and \(u_2^1, u_3^1, u_4^1, u_4^2, u_4^3.\) Without loss of generality, color \(c'(u_2^1u_2^2) = 1, c'(u_2^2u_2^3) = 2, c'(u_2^3u_3^3) = 1\)3, and \(c'(u_3^3u_4^3) = 4\). Then, color \(c'(u_4^2u_4^3) = 1\), \(c'(u_4^1u_4^2) = 2\), \(c'(u_4^1u_3^1) = 3\), and \(c'(u_3^1u_2^1) = 3\)4. Consider vertices \(u_1^1\) and \(u_4^3\), then there exist two internally disjoint paths with length 4, i.e. \(u_1^1, u_1^2, u_1^3, u_0^3, u_4^3\) and \(u_1^1, u_0^1, u_4^1, u_4^2, u_4^3\). Since we have already colored \(u_1^1, u_1^2, u_1^3, u_0^3\) path, it forces us to color \(c'(u_0^3u_4^3)=4\) and \(c'(u_0^1u_4^1)=3\). Consider vertices \(u_3^1\) and \(u_5^1\), then there exist two internally disjoint paths with length 4, i.e. \(u_3^1, u_3^2, u_3^3, u_0^3, u_5^3\) and \(u_3^1, u_4^1, u_4^2, u_4^3, u_5^3\). The left edges that have not colored yet are \(u_4^3u_5^3\) and \(u_0^3u_5^3\). It forces us to color \(c'(u_4^3u_5^3)=4\) and \(c'(u_0^3u_5^3)=3\). But, there are no two internally disjoint rainbow paths which connect \(u_3^3\) and \(u_4^3\). Thus, we have a contradiction. By using a similar process with previous two paths, whatever two internally disjoint paths that we choose, we get a contradiction.

As shown in Figure 3, we present a rainbow 2-connected coloring on \(W_n \square P_m\) for n = 5 and m = 3.

Figure 3. A rainbow 2-connected coloring on \(W_5 \square P_3\).

Despite the fact that we could not extend the proof of Theorem 2.3 for \(n \in [4, 6]\) and \(m > \lceil \frac{n}{2} \rceil\) or \(n \ge 7\), we raised the following conjecture.

Conjecture 2. If \(n \in [4, 6]\) and \(m > \lceil \frac{n}{2} \rceil\) or \(n \ge 7\), then

\[rc_2(W_n \square P_m) = \lceil \frac{m}{\lceil \frac{n}{2} \rceil} \rceil \lceil \frac{n}{2} \rceil + m - 1.\]

Next, we consider the Cartesian products of cycles and paths, which is an improvement of our result in [25]. Previously, \(rc_2(Cn\Box P_m) \leq \lceil \frac{m}{2} \rceil n\), a product of n and m, instead of a sum of n and m. The upper bound in the next theorem is also much less than the general upper bound in Theorem 2.1.

Theorem 2.4. If \(n \geq 3\) and \(m \geq 2\), then

\[rc_2(C_n\square P_m) \le n+m-2,\]

where equality holds for \(n \in [3, 5]\).

Proof. Let \(V(C_n \Box P_m) = \{u_i^j | 1 \le i \le n, 1 \le j \le m\}\) and \(E(C_n \Box P_m) = \{u_i^j u_{i+1}^j, u_i^j u_i^{j+1} | 1 \le i \le n, 1 \le j \le m \text{ where } u_{n+i} = u_i\}.\)

First, we shall consider a proof of the upper bound. We define an edge-coloring \(c: E(C_n \square P_m) \to [1, n+m-2]\) as follows.

\[c(u_i^j u_{i+1}^j) \ = \begin{cases} i, & \text{for } i \in [1, n] \text{ and } j = 1; \\ c(u_{i+1}^1 u_{i+2}^1), & \text{for } i \in [1, n], j \in [2, n] \text{ and } n = 3; \\ c(u_{i+1}^1 u_{i+2}^1), & \text{for } i \in [1, n], \text{j is even, } j \geq 2 \text{ and } n \geq 4; \\ (c(u_i^2 u_{i+1}^2) + 2) \ mod^*n, & \text{for } i \in [1, n], \text{j is odd, } j \geq 3 \text{ and } n \geq 4. \end{cases}\] \[c(u_i^j u_i^{j+1}) \ = \begin{cases} (i+1) \ mod^*n, & \text{for } i \in [1, n] \text{ and } j = 1; \\ j+n-1, & \text{for } i \in [1, n] \text{ and } j \in [2, m-1]. \end{cases}\]

We shall show that the above coloring is a rainbow 2-connected (n+m-2)-coloring of \(C_n \square P_m\). Consider two distinct vertices \(x, y \in V(C_n \square P_m)\), we divide the proof into two cases.

Case 1. For \(x,y\in V(C_n^j), j\in [1,m]\), there exist two internally disjoint x-y rainbow paths which connect them, i.e., \(u_i^j, u_{i+1}^j, \ldots, u_k^j\) and \(u_i^j, u_{i-1}^j, \ldots, u_1^j, u_n^j, u_{n-1}^j, \ldots, u_k^j\).

Case 2. For \(x \in V(C_n^j)\) and \(y \in V(C_n^l), j \neq l, j, l \in [1, m]\), we divide into two subcases. For \(x = u_i^j \in V(C_n^j)\) and \(y = u_i^l \in V(C_n^l), i \in [1, n]\), there exist two internally disjoint rainbow paths which connect x and y, i.e., \(u_i^j, u_i^{j+1}, \ldots, u_i^{l-1}, u_i^l\) and \(u_i^j, u_{i+1}^j, u_{i+1}^{j+1}, \ldots, u_{i+1}^l, u_i^l\). For \(x = u_i^j \in V(C_n^j)\) and \(y = u_k^l \in V(C_n^l), i, k \in [1, n], i \neq k\), there exist two internally disjoint rainbow paths which connect x and y, i.e., \(u_i^j, u_{i+1}^j, \ldots, u_k^j, u_k^{j+1}, \ldots, u_k^l\) and \(u_i^j, u_i^{j+1}, \ldots, u_i^l, u_{i-1}^l, \ldots, u_1^l, u_n^l, \ldots, u_k^l\). Thus, \(rc_2(C_n \Box P_m) \leq n + m - 2\).

Now, we consider a proof of lower bound. We divide the proof into two cases.

Case 1. For n=3, it is a direct consequence of Theorem 2.1, since \(diam_2(C_3 \square P_m) = m+1\).

Case 2. For \(n \in [4, 5]\), we want to show that \(rc_2(C_n \Box P_m) \ge n + m - 2\). Without loss of generality, assume to the contrary that \(rc_2(C_n \Box P_m) \le n + m - 3\). Let c' be a rainbow 2-connectivity of \(C_n \Box P_m\) using n + m - 3 colors.

For n=4, consider two vertices \(u_1^m\) and \(u_3^1\), then there exist three internally disjoint pathswith length at most n+m-3 which connect \(u_1^m\) and \(u_3^1\), i.e, \(u_1^m, u_1^{m-1}, \ldots, u_1^1, u_2^1, u_3^1; u_1^m, u_4^m, u_4^{m-1}, \ldots,\)

\(u_4^1, u_3^1\); and \(u_1^m, u_2^m, u_3^m, u_3^{m-1}, \dots, u_3^1\). There are three combinations of paths that need to be reviewed, but they all lead to a contradiction.

First, we consider \(u_1^m, u_1^{m-1}, \ldots, u_1^1, u_2^1, u_3^1\) and \(u_1^m, u_4^m, u_4^{m-1}, \ldots, u_4^1, u_3^1\) paths. Without loss of generality, we color \(c'(u_1^m u_1^{m-1}) = 1\), \(c'(u_1^{m-1} u_1^{m-2}) = 2, \ldots, c'(u_1^2 u_1^1) = n+m-5\), \(c'(u_1^1 u_2^1) = n+m-4\), and \(c'(u_2^1 u_3^1) = n+m-3\). Then, color \(c'(u_1^m u_4^m) = n+m-3\), \(c'(u_4^m u_4^{m-1}) = n+m-4, \ldots, c'(u_4^2 u_4^1) = 2\), and \(c'(u_4^1 u_3^1) = 1\). Next, consider two vertices \(u_2^m\) and \(u_4^n\), then there exist two internally disjoint paths with length n+m-3, i.e., \(u_2^m, u_1^m, u_4^m, u_4^m, u_4^{m-1}, \ldots, u_4^1\) and \(u_2^m, u_2^{m-1}, \ldots, u_2^1, u_3^1, u_4^1\). Since we have already colored \(u_1^m, u_4^m, u_4^m, u_4^{m-1}, \ldots, u_4^1\), it forces us to color \(c'(u_1^m u_2^m) = 1\). We also already colored \(u_4^1 u_3^1\) and \(u_3^1 u_2^1\), then without loss of generality, color \(c'(u_2^1 u_2^2) = 2\), \(c'(u_2^2 u_3^2) = 3\), \(\ldots\), \(c'(u_2^{m-1} u_2^m) = n+m-4\). But, there are no two internally disjoint rainbow paths which connect \(u_1^1\) and \(u_2^4\). So, we have a contradiction. By using a similar process with previous two paths, whatever two internally disjoint paths that we choose, we get a contradiction.

For n=5, consider two vertices \(u_1^m\) and \(u_4^1\), then there exist three internally disjoint paths with length at most n+m-3 which connect \(u_1^m\) and \(u_4^1\), i.e., \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(\dots, u_4^1\); and \(u_1^m, u_5^m, u_5^{m-1}, \dots, u_5^1, u_4^1\). There are three combinations of paths that need to be reviewed, but they all lead to a contradiction. First, we consider \(u_1^m, u_1^{m-1}, \dots, u_1^1, \dots, u_4^1\) and \(u_1^m, \ldots, u_4^m, u_4^{m-1}, \ldots, u_4^1\). Without loss of generality, we color \(c'(u_1^m u_1^{m-1}) = 1, c'(u_1^{m-1} u_1^{m-2}) = 1\)\(2, \ldots, c'(u_1^2 u_1^1) = n + m - 6, c'(u_1^1 u_2^1) = n + m - 5, \ldots, c'(u_3^1 u_4^1) = n + m - 3.\) Then, we color \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)n+m-3. Next, consider two vertices \(u_5^1\) and \(u_2^m\), then there exist three disjoint paths with length at most n+m-3 which connect \(u_5^1\) and \(u_2^m\), i.e., \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)and \(u_5^1, u_1^1, u_1^2, \dots, u_1^m, u_2^m\). Consider the first path, since we have already colored edges \(u_2^1 u_3^1\) and \(u_3^1u_4^1\), we can not color one of edges of \(u_2^1u_2^2, u_2^2u_2^3, \dots, u_2^{m-1}u_2^m\) with n+m-5 that already used on edge \(u_1^1u_2^1\). Because if we consider two vertices \(u_1^1\) and \(u_2^4\), then there are no two internally disjoint rainbow paths which connect them. Thus, it forces us to color \(c'(u_4^1u_5^1) = n + m - 5\). We also can not color \(c'(u_2^1u_2^2)=1\), because if we consider two vertices \(u_2^1\) and \(u_4^1\), then there are no two internally disjoint rainbow paths which connect them. So, we color \(c'(u_2^1u_2^2)=n+m-7, c'(u_2^2u_2^3)=1\)\(n+m-6,\ldots,c'(u_2^{m-1}u_2^m)=1.\)

Next, consider two vertices \(u_2^1\) and \(u_5^m\), then there exist two internally disjoint paths with length n+m-3 which connect them, i.e., \(u_2^1, u_3^1, \ldots, u_5^1, \ldots, u_5^m\) and \(u_2^1, u_2^2, \ldots, u_2^m, \ldots, u_5^m\), it forces us to color \(c'(u_5^{m-1}u_5^m) = n+m-6, c'(u_5^{m-2}u_5^{m-1}) = n+m-5, \ldots, c'(u_5^1u_5^2) = 1\). Consider two vertices \(u_3^1\) and \(u_4^1\), then there exist two possible internally disjoint paths which connect them, i.e., \(u_3^1, u_3^2, \ldots, u_3^m, u_2^m, u_1^m\) and \(u_3^1, u_2^1, u_1^1, u_1^2, \ldots, u_1^m\), it forces us to color \(c'(u_3^1u_3^2) = n+m-7, c'(u_3^2u_3^3) = n+m-6, \ldots, c'(u_3^{m-1}u_3^m) = 1\). But, there are no two internally disjoint rainbow paths which connect \(u_2^1\) and \(u_3^1\). Thus, we have a contradiction. By using a similar process with previous two paths, whatever two internally disjoint paths that we choose, we always get a contradiction. Hence, we complete the proof.

We present a rainbow 2-connected coloring on \(C_n \square P_m\) for n=5 and m=3, as shown in Figure 4.

Although we could not generalize the proof of Theorem 2.4 for \(n \ge 6\), we raised the following conjecture.

Figure 4. A rainbow 2-connected coloring on C5✷P3.

Conjecture 3. If n ≥ 6 and m ≥ 2, then

\[rc_2(C_n \square P_m) = n + m - 2.\]

3. Conclusion

The rainbow k-connection number is a concept for measuring connectivity of a graph. In this paper, we were able to derive sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We provided the rainbow 2 connection number of Cartesian products of some 2-connected graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.

We also conjectured that for m > n−1, the rainbow 2-connection number of Fn✷P^m is exactly the same as the upper bound in Theorem 2.1; for n ∈ [4, 6] and m > d n 2 e or n ≥ 7, the rainbow 2-connection number of Wn✷P^m is exactly the same as the upper bound in Theorem 2.3; and for n ≥ 6, the rainbow 2-connection number of Cn✷P^m is exactly the same as the upper bound in Theorem 2.4.

Acknowledgement

This research is partially supported by Indonesian Directorate General of Higher Education. The authors are very grateful to the referees whose valuable comments and suggestions resulted in a better organized and improved paper.

References

• [1] M. Basavaraju, L. S. Chandran, D. Rajendraprasad, and A. Ramaswamy, Rainbow connection number of graph power and graph products, Graphs Combin. 30 (6) (2014), 1363–1382.
• [2] S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Combin. Optim. 21 (2011), 330–347.
• [3] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, Rainbow connection in graphs, Mathematica Bohemica 133 (2008), 85–98.
• [4] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2) (2009), 75–81.
• [5] G. Chartrand and P. Zhang, A First Course in Graph Theory (Dover Publications, 2012).
• [6] R. Deniawanty and A. N. M. Salman, The rainbow connection number of an n-crossed prism graph and its corona product with a trivial graph, Procedia Computer Science 74 (2015), 143–150.
• [7] R. Diestel, Graph Theory 5ed. (Springer, 2017).
• [8] D. Fitriani and A. N. M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb. 13 (1) (2016), 90–99.
• [9] S. Fujita, H. Liu, and C. Magnant, Rainbow k-connection in dense graphs, Electron. Notes Discrete Math. 38 (2011), 361–366.
• [10] T. Gologranc, G. Mekis, and I. Peterin, Rainbow connection and graph products, ˇ Graphs Combin. 30 (3) (2014), 591–607.
• [11] R. Hammack, W. Imrich, and S. Klavzar, ˇ Handbook of Product Graphs 2ed. (Taylor and Francis Group, 2011).
• [12] J. He and H. Liang, On rainbow k-connectivity of random graphs, Inform. Process. Lett. 112 (10) (2014), 406–410.
• [13] D. F. Hsu and T. Łuczak, Note on the k-diameter of k-regular k-connected graphs, Discrete Math. 133 (1994), 291–296.
• [14] I. S. Kusuma and A. N. M. Salman, The rainbow connection number of a flower graph (Cm, Kn) graph and a flower (C3, Fn) graph, Procedia Computer Science 74 (2015), 168– 172.
• [15] X. Li and Y. Sun, On the rainbow k-connectivity of complete graphs, Australas. J. Combin. 49 (2011), 217–226.

• [16] X. Li and Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, preprint.
• [17] X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29 (2013), 1–38.
• [18] X. Li and S. Liu, A sharp upper bound for the rainbow 2-connection number of a 2-connected graph, Discrete Math. 313 (2013), 755–759.
• [19] X. Li and Y. Sun, An updated survey on rainbow connections of graphs a dynamic survey, Theory and Applications of Graphs 0:1 (2017) article 3.
• [20] Z. Lu and Y. Ma, Rainbow 2-connection numbers of Cayley graphs, Inform. Process. Lett. 115 (2015), 486–491.
• [21] S. Nurdin and A. N. M. Salman, The rainbow connection number of rocket graphs, AIP Conference Proceedings of The 5 th International Conference on Mathematics and Natural Sciences 1677 (030012-1-030012-3) (2015).
• [22] F. Septyanto and K. A. Sugeng, Color code techniques in rainbow connection, Electron. J. Graph Theory Appl. 6 (2) (2018), 347–361.
• [23] A. Shulhany and A. N. M. Salman, The (strong) rainbow connection number of stellar graphs, AIP Conference Proceedings of Mathematics, Science, and Computer Science Education International Seminar 1708 (2016), 060007.
• [24] D. N. S. Simamora and A. N. M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Computer Science 74 (2015), 138–142.
• [25] B. H. Susanti, A. N. M. Salman, and R. Simanjuntak, Upper bounds for rainbow 2-connetivity of the Cartesian product of a path and a cycle, Procedia Computer Science 74 (2015), 151– 154.
• [26] B. H. Susanti, A. N. M. Salman, and R. Simanjuntak, The rainbow connection number of some subdivided roof graphs, AIP Conference Proceedings of The 7 th SEAMS-UGM International Conference on Mathematics and Its Applications 1707 (2016), 020021.
• [27] N. Syahidah and A. N. M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Computer Science 74 (2015), 162–167.