IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1149 ISSN 2232-2094 RAINBOW CONNECTION AND GRAPH PRODUCTS Tanja Gologranc Gasper Mekis Iztok Peterin Ljubljana, May 17, 2011 Rainbow connection and graph products IN Tanja Gologranc", GaSper MekiS", Iztok Peterin"'6, o CO CD Jh CD Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia bi 6 University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia Abstract A path in an edge colored graph g is called a rainbow path if all its edges have pairwise different colors. Then g is rainbow connected if there exists a rainbow path between every pair of vertices of g and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained. Key words: (strong) rainbow connection number; direct product; strong product; lexicographic product I 2010 Math. Subj. Class.: 05C15, 05C38, 05C40, 05C76 CO _ 1 Introduction and preliminaries £ Topics related to rainbow problems were first introduced in a classical paper of Erdos, Simonovits, and Sos in 1975 [8] as a counterpart to Ramsey problems. Since then the development went in different directions. For the latest survey see [9]. Probably the latest one was introduced by Chartrand, Johns, McKeon, and Zhang in [6] and it is about "rainbow connection". More precisely, let P be a path of an edge colored graph G. (The coloring is not necessarily a proper coloring.) Then P is called a rainbow path if all of its edges have pairwise different colors. If there exists a rainbow path between each pair of vertices of G, we say that G is rainbow connected and the smallest number of colors needed for G to be rainbow connected is called the rainbow connection number rc(G). Similar concept, also introduced in the same paper [6], is the strong rainbow connection number src(G), i.e., the smallest number of colors needed such that there exist a rainbow colored shortest path (geodesic) between every pair of vertices. Then we also say that, by such a coloring, G is strongly rainbow connected. The motivation for the strong rainbow connection number is that it is clearly the upper bound for rainbow connection number: rc(G) < src(G). The trivial lower bound is obviously diam(G), 0E-mail addresses: tanja.gologranc@gmail.com (T. Gologranc), gasper.mekis@gmail.com (G. Mekis) iztok.peterin@uni-mb.si (I. Peterin). o the diameter of G, i.e., the longest shortest path of G. We will use term "(strongly) rainbow colored" for graph G whenever a coloring of E(G) induces a (strong) rainbow connectedness of G. IN The (strong) rainbow connection number was introduced in [6], where rc(G) and src(G) of some graph classes have been presented. The authors continued with their work in [7] with a similar concept of rainbow connectivity of a graph that has an implication to security networks. The rainbow connection number was bounded from above by minimum degree condition in [3, 16, 21, 22]. The discussion about the algorithmic aspect to the topic can be found in [4]. The vertex version of the rainbow connection number was studied in [16]. More results can be found in survey [18]. The general strategy to approach (strong) rainbow connection number seems to be in finding coloring that is close to the trivial lower bound, since it is hard to raise the lower bound. Here we present a tool that can be useful at least for the strong rainbow connection number. The distance dG(u, v) in a simple undirected graph G between vertices u, v G V(G) is the length of a shortest path between u and v in G. A geodesic interval Ig(u, v) is the set of all vertices of G that are on some shortest u, v-path. A set K C V(G) is geodesic convex if I(u, v) C K for every pair u, v G K. A subgraph H of G is geodesically convex if V(H) forms a geodesic convex set. Hence, geodesic convex subgraphs are closed for all shortest paths, which yields that the strong rainbow connection number is hereditary for geodesic convex sets. 00 Observation 1.1 Let H be a geodesic convex subgraph of a connected graph G. Then src(G) > src(H). C^ Similarly, the rainbow connection number can be observed for some other convexities. Namely, a set A(u, v) is called an all-path interval between u and v if it consists of all vertices that lie on a u, v-path. Then A is an all-path convex set whenever it is closed for all all-path intervals A(u, v), for any u, v G A, and H is an all-path convex subgraph of G when V(H) is an all-path convex set. Again, all-path convex subgraphs are hereditary for rainbow connection number. Unfortunately this gives nothing new, since 2-connected components of G and their (connected) unions form all all-path convex subgraphs. There are also some related concepts as induced path convexity and Steiner convexity. Hence one could define the rainbow connection number with respect to these two convexities and obtain a chain of different invariants. For more about other convexities see [5] and for convexities on graph products see [1, 20]. The second observation is due to the fact that the rainbow connection number is CD ■ i-H J-H CD s reciprocally hereditary for spanning subgraphs. Observation 1.2 Let H be a connected spanning subgraph of a connected graph G. Then rc(H) > rc(G). J-i The standard products (Cartesian, direct, strong, and lexicographic) draw a constant atention of graph reserch comunity, see some recent papers [1, 2, 11, 15, 19, 20, 23, 25]. In this paper we will consider three standard products: the direct, the strong and the lexicographic with respect to the (strong) rainbow connection number. Every of these three products will be treated in one of the forthcoming sections. Some results IN on the Cartesian and the lexicographic product are given in [17, 18]. i—l 2 The direct product The direct product G x H of graphs G and H has the vertex set V(G) x V(H). Two vertices (g, h) and (g', h') are adjacent if the projections on both coordinates are adjacent, i.e., gg' e E(G) and hh' e E(H). It is clearly commutative and associativity also follows quickly. For more general properties we recommend [12]. The direct product is the most natural graph product in the sense of categories. But this also seems to be the reason that it is, in general, also the most elusive product of all standard products. For example, G x H needs not to be connected even when both factors are. To gain connectedness of G x H at least one factor must additionally be nonbipartite as shown by Weichsel [24]. Also, the distance formula dGx h((g, h), (g', h')) = min{max{dO(g, g'), d%(h, h')}, max{dO(g, g'),dH(h, h')}} o for the direct product is far more complicated as it is for other standard products. Here dO(g,g') represents the length of a shortest even walk between g and g' in G, and dO(g, g') the length of a shortest odd walk between g and g' in G. The formula was first shown in [14] and later in [10] in an equivalent version. There is no final solution for the connectivity of the direct product, only some partial results are known (see [2, 11]). In this section we will construct diferent upper bounds for the rainbow connection number of the direct product with respect to some invariants of the factors that are related to the rainbow connection number of the factors. The similar concept as for S the distance formula is used and is due to the rainbow odd and even walks between vertices (and not only rainbow paths) and is thus, in a way, related with the formula. We will show that this bound is tight for some family of graphs, but also that it can be arbitrarily bad. For an edge colored graph G (it needs not to be a proper coloring) we say that G is odd-even rainbow connected if there exists a rainbow colored odd walk and a rainbow colored even walk between every pair of (not necessarily different) vertices of G. Clearly, on such a walk a fixed edge can appear only once. The odd-even rainbow CO CSI CSI CO connection number of a graph G, oerc(G), is the smallest number of colors needed for G to be odd-even rainbow connected and it equals infinity if no such a coloring exists. A bipartite graph has either only even or only odd walks between two fixed vertices, thus there is no odd-even rainbow coloring of such a graph. On the other hand, let G be a graph in which every edge lies on some odd cycle. Then oerc(G) is finite since coloring every edge with its own color produces an odd-even rainbow coloring of G. An odd cycle is an example where this coloring is optimal. In this case, if we would have a two consecutive edges of the same color, then there is no even rainbow walk between the diametrical endvertices of these two edges, and in the case of two nonincident edges IN £ of the same color there is no even rainbow walk between endvertices of any different colored edge. An example with oerc(G) < |E(G)| is on Figure 1 (a). It is also easy to see that oerc(Kn) = 3, n > 3. Namely, if we denote V(Kn) = {0,1,..., n — 1} and for n > 3 and i, j e {0,1,..., n — 1}, i < j we color the edge ij with color j — i(mod 3), we get an odd-even rainbow coloring. It is obvious that for every i e {0,1,..., n — 1} there exists odd rainbow i, i-walk of length three and for every pair of different vertices i, j e {0,1,..., n — 1} there exists rainbow i, j-path of length two. 0 o 1 CO £ co co m CD $H CD m u a CD U (a) (b) (c) Figure 1: (a) A graph with odd-even rainbow connection number less than number of edges; (b) 3-coloring of K2 x K4; (c) 2-coloring of K3 x K3. Let G be a graph. We split G into two spanning subgraphs OG and BG, where the set E(Og) consists of all edges of G that lie on some odd cycle of G, and the set E(BG) = E(G)\E(Og). Clearly, OG and Bg are not always connected. Let OG, OG,..., OG and B k and (go, ho)(gi, hi)... (gi, hi)(gi-i, hi+i)(gi, hi+2)... (gi, hk) is a rainbow (g, h), (g', h')-path in G x H whenever £ < k. Case 2. Let now £ and k have different parity. If there exists a g^gj-subpath of P in OG we can replace this subpath by a rainbow g%,gj-subpath of different parity to obtain a rainbow path P'. If this is the case then |E(P')| and k have the same parity and we can use Case 1. Otherwise, note that P is contained in one component B^. Let gi e P be a vertex that is closest to any component OG of G and let vi e OG be the closest to gi. Let R = gigi+i.. . gi+r, g'+r = vi be a shortest gi, vi-path. From the definition of odd-even rainbow coloring we know that there exists an odd rainbow vi,vi-walk C = viv2 ...vpvi in OG. Now we insert a closed walk that follows RCR O fK)m gi ^^ P ,»bt»n. g,g'-»alk = UoUi . . . Ui+p+2r (W = gogi... gigi+i... gi+r v2v3... vPvigi+r-ig'+r-2... gigi+i... gi of length t = £ + 2r + p. W is clearly not a rainbow walk since some edges appear twice on W. Note that t and £ have different parity since p is an odd number and thus t and k have the same parity. If k > t we can again use the same approach as in Case 1 for W and Q, since every edge of Q has a different color. Similarly, we can use Case 1 if CO t > k > i + 2r + p since then the edges of W with the same color receive a different color of Q. It remains to check the case when t > i + 2r + p > k. As H is not a complete graph, we have rc(H) > diam(H) > 2. Since Q is a shortest rainbow path we obtain three possibilities: Q is a one vertex path, Q is an edge hh', the last two edges of Q have different colors. Let first Q = h = h'. We can find a path hxy or whz that contains two colors. In the case of hxy a path (uo,h)(ui,x)(u2,y)(u3,x) . . . (ui+r+p-i,a)(ui+r+p,b)(ui+r+p+i,c)(ui+r+p+2,d) . . . . . . (ui+2r+p, where a = y, b = x, c = h, d = x if i + r is even and a = x, b = h, c = x, d = h if i + r is odd, is a rainbow path since edges that project on G to a part of W from ui to ui+r (edges of R) have second color cH(xy) and edges that project on G to a part of W from ui+r+p to ui+2r+p (again the edges of R) have second color cH(xh) = cH(xy). Similarly, in the case of whz a path (uo, h)(ui, w)(u2, h) ... (ui+r+p-i, a)(ui+r+p, b)(ui+r+p+i, c)(ui+r+p+2, d) ... (ui+2r+p, h), where a = w, b = h, c = z, d = h if i + r is odd and a = h, b = z, c = h, d = z if i + r is even, is a rainbow path since edges projecting on G to R receive the first time second color cH(hw) and the second time color cH(hz) = cH (hw). IN The second possibility is Q = hh'. Again, there is a path hh'x (or xhh' by sym- metry) in H with cH(hh') = cH(h'x) since H is not a complete graph. We have a path (uo, h)(ui, h')(u2, h) ... (ui+r+p-l, a)(ui+r+p, b)(ui+r+p+l, c)(ui+r+p+2, d) ... (ui+2r+p, h'), where a = h', b = x, c = h', d = x if i + r is odd and a = h, b = h', c = x, d = h' if i + r is even, that is a rainbow path since the first part that projects on G to R receives second color cH (hh') and the second part that projects on G to R receives second color ch (h'x). Finally, let hk-2hk-1hk be the last part of Q. The path o (uo, ho)... (ufc-i, hfc-i)(ufc, hfc-2)(ufc+i, hfc-i)... . . .(ui+r+p- i, a)(ui+r+p, b)(ui+r+p+2, c) ... (ui+2r+p, hfc), where a G {hk-i, hk-2}, b, c G {hk, hk-i} depends on the parity of k and i + r, is again a rainbow path by the same reason as above and the proof is completed. □ C^ Let H be a bipartite graph. Then o(H) = 0 and we can not use the coloring from the proof of Theorem 2.1 with rc(G)(o(H) + b(H)) colors since there is no rainbow path between (g,h) and (g',h), gg' G E(G). However, we can use the symmetric coloring with rc(H)(o(G) + b(G)) colors. Hence we obtain Corollary 2.2 Let G and H be noncomplete connected graphs, where G is nonbipartite CO and H a bipartite. Then rc(G x H) < rc(H)(o(G) + b(G)). It remains to study rc(G x Kn), n > 2, to complete the upper bounds for the direct product. We also skipped (up to here) the strong rainbow connection number for the direct product. The reason for this is that we would need much more detailed information about the factors to construct a strong rainbow coloring. Namely, we need the information which odd cycle is closest to a fixed vertex and has, in addition, the shortest length. In other words, we need to know the shortest closed odd walk from every vertex. To fill a part of that gap we give an exact result for both rc(Kn x Km) and src(Kn x Km). The notation V(Kn) = {0,1,..., n — 1} will be used. CO Theorem 2.3 Let n, m > 3. (i) rc(K„ x Km) = 2 = src(K„ x Km). & (ii) rc(K2 x Km) = 3 = src(K2 x Km). Proof. It is easy to see that diam(K2 x Km) = 3 and diam(Kn x Km) =2, n,m > 3. Hence, rc(K2 x Km) > 3 and rc(Kn x Km) > 2. We also know [6], that for a graph G, rc(G) = 2 if and only if src(G) = 2. IN (i) We distinguish two cases with respect whether both m and n are even or not. Case 1. Suppose first that at least one, say m, is odd. Define a 2-coloring as follows. For every u e V(Kn), an edge (u, v)(u + 1, v') is colored with color 1 if v' = v + 2k — 1(mod m) for some k, 1 < k < m—, otherwise, if v' = v + 2k(mod m) for some k, 1 < k < m—, the edge (u, v)(u + 1, v') is colored with color 2. Every edge of the form (u, v)(u', v') with u' — u > 2 is colored with the same color as the edge (u, v)(u + 1, v') if u' is odd and with different color otherwise. This way all edges are colored. (See Figure 1 (c) for 2-coloring of K3 x K3.) Fix a vertex (u, v) e V(Kn x Km). We need to find a rainbow path of length 2 from (u, v) to every vertex of the form (u, v') or of the form (u',v), as these are exactly the nonadjacent vertices of the vertex (u, v). First, fix a vertex (u, v'). If v and v' are of the same parity, then the edges (u, min{v, v'})(u + 1, min{v, v'} + 1) and (u + 1, min{v, v'} + 1)(u, max{v, v'}) are of different color. If u = n — 1 then take the vertex (u — 1, min{v, v'} + 1). And if v and v' are of different parity, then the path via the vertex (u + 1, max{v, v'} + 1(mod m)) (if u = n — 1, take (u — 1, max{v, v'} + 1(mod m))) is a rainbow path. Second, fix a vertex (u', v). Suppose |u — u'| = 1. If max{u,u'} is odd, then the path via the vertex (max{u, u'} + 1(mod n), v + 1(mod m)) is a rainbow path. And if max{u, u'} is even, then take the path through the vertex (min{u, u'} — 1, v + 1(mod m)). Next, suppose |u — u'| > 1. If max{u,u'} is odd, then the path via the vertex (min{u, u'} + 1, v + 1(mod m)) is a rainbow path, and in the even case take the vertex (max{u, u'} — 1, v + 1(mod m)). Case 2. Both n and m are even. Define a 2-coloring as follows. For every u e V(Kn), an edge (u, v)(u + 1,v') is colored with color 1 if v' = v + 2k — 1(mod m) for some k, 1 < k < m — 1. If v' = v + 2k(mod m) for some k, 1 < k < m — 1, the edge (u, v)(u + 1,v') is colored with color 2. The edges of the remaining matching, where v' = v —1( mod m), are colored with color 2. Similarly as above, every edge of the form (u, v)(u', v') with u' — u > 2 is colored with the same color as the edge (u, v)(u + 1, v') if u' is odd and with different color otherwise. Fix a vertex (u, v). Firstly, find a rainbow path to the vertex (u, v'). Suppose that v and v' are of the same parity. If u < n — 1 then the edge (u, min{v,v'})(u + 1,max{v,v'} — 1) has color 1 and the edge (u + 1,max{v,v'} — 1)(u,max{v, v'}) has color 2. If u = n — 1 then take the path via the vertex (0, min{v,v'} + 1). Suppose next, v and v' are of different parity. Suppose additionally that |v — v'| = 1. If u < n — 1 take the vertex (u + 1, max{v, v'} + 1(mod m)), otherwise take the vertex (u—1, min{v, v'} —1( mod m)). And in the case of |v—v'| > 1, take (u+1, min{v,v'}+1) if u < n — 1, and take (u — 1, max{v, v'} — 1) otherwise. Secondly, find a rainbow path to the vertex (u',v). Suppose |u — u'| = 1. If max{u, u'} is even, then take the vertex (min{u, u'} — 1, v + 1(mod m)). If max{u, u'} a is odd, then the vertex (max{u, u'} + 1, v + 1(mod m)) takes care of the issue unless if max{u, u'} = n — 1, then we can take the vertex (min{u, u'} — 2, v + 1(mod m)). r 00 CSI CSI Last case, suppose |u — u'| > 1. If max{u, u'} is even, take one of the vertices (max{u, u'} — 1, v ± 1) (it may exist only one if v e {0, m — 1}) and we get a rainbow path, otherwise take one of the vertices (min{u, u'} + 1,v ± 1). (ii) First, the graph K2 x K3 is a cycle on six vertices, hence [6] src(K2 x K3) = rc(K2 x K3) = 3. For m > 4 define a 3-coloring of a graph K2 x Km similar as in (i). For every v e V(Km) the edge (0, v)(1, v') is colored with 1 if v' = v + 2k — 1(mod m) for some k, 1 < k < mm 1 — 1, and it is colored with 2 if v' = v + 2k(mod m) for some k, 1 < k < [mJ — 1. The edges of the remaining matching, where v' = v — 1(mod m), get color 3. (See Figure 1 (b) for 2-coloring of K3 x K3.) Fix a vertex (u, v) e V(K2 x Km). Without loss of generality, u = 0. The same arguments as those used in (i) imply that we have a rainbow path (which is a shortest path) on two different colored edges between (0,v) and (0, v') for all v' = v. And for the vertex (1,v), the path (0,v), (1,v + 2(modm)), (0,v + 1(modm)), (1,v) is a rainbow path, which is also a shortest path. Thus, src(K2 x Km) = rc(K2 x Km) = 3. □ o o CSI With respect to the theorem above we would like to note that, already, deciding whether rc(G) = 2 for a given graph G is a NP-Complete problem, the same holds also for checking whether a given coloring is a rainbow coloring [4]. Next we consider a general bound for G x K2. It is easy to see that the coloring of Theorem 2.1 is not a rainbow coloring for G x K2. This is due to the fact that for a 00 bipartite graph B we have two components in B x K2 both isomorphic to B, see [13]. Thus if we wish a path from one component to the other we must visit some Of. Theorem 2.4 Let G be a nonbipartite connected graph. Then rc(G x K2) < o(G) + 2b(G). Proof. Let cf be an optimal odd-even rainbow coloring of the components of OG and let cf be an optimal rainbow coloring of the components of BG (for both cases it holds that no color appears in two different components). We will construct an edge coloring c of G x K2 using cf and cf as follows. Color both component of BG x K2 (which are isomorphic to BG) optimal with 2rc(BG) for every i = 1, 2,... , £. For this we use 2b(G) colors. Both edges of G x K2 that project on G to an edge e of OG receive color cf (e). For the introduced coloring o(G) + 2b(G) colors are used and we need to show that c is a rainbow coloring of G x K2. Let V(K2) = {ki, k2}. Let (g, h) and (g', h') be arbitrary vertices from G x K2. Let P = g0gi.. .ge, g0 = g and ge = g', be a rainbow g,g'-path in the rainbow coloring of G induced by cf and cf. We distinguish two cases. Case 1. Let £ and dK2 (h, h') have the same parity. Without loss of generality we may assume that h = ki. Then h' = ki if £ is even number and h' = k2 otherwise. Thus (g0, ki)(gi, k2)(g2, ki)... (ge, h') is a rainbow (g, h), (g', h')-path in G x K2. Case 2. Let £ and dK2 (h, h') have different parity. Suppose first that P has a nonempty intersection with some O< and let g» be the first and gj the last vertex of P in O<. C/3 CD ■ 1 J-H CD Then we can find a rainbow gi,gj-walk in O< with length of different parity as gi, gj-subpath of P in O<. Replacing this walk with gi,gj-subpath of P in O< we obtain a g,g'-rainbow walk of the same parity as dK2 (h, h') and we continue as in Case 1. IN Suppose now that P has an empty intersection with every O<, p = 1, 2,..., k. Then P is contained in B< for some q and (g, h) and (g', h') are in different components (B<)1 and (bG)2 of B< X K2, respectively. Since G is nonbipartite there exists g'' £ B< n O< for some i. Let {hr, hs} = {k1,k2}. Take a rainbow path from (g,h) to (g'', hr) in (B<)1, a rainbow odd path from (g'',hr) to (g'', hs) in O<, and a rainbow path from (g'', hs) to (g', h') in (B<)2. Then this is a rainbow (g, h), (g', h')-path in G x K2 since we have used different colors for (B<)1, (B<)2, and OG. □ To illustrate the above theorem let G be a graph obtained from an odd cycle C2k+1, k > 1, amalgamated by one endvertex of a path Pn. Then rc(G x K2) = o(G) + 2b(G) = 2k + 1 + 2(n — 1). For this just note that diam(G x K2) = dGxK2((g,k1), (g,k2)) = 2k + 2n — 1, where g is the vertex of G with deg(g) = 1 and V(K2) = {k1, k2}. Even more, if we take 2k + 1 arbitrary trees with an arbitrary fixed vertex and amalgamate one by one of these 2k + 1 vertices by 2k + 1 vertices of C2k+1 to obtain graph G, we have rc(G x K2) = o(G) +2b(G). On the other hand, it is easy to see that we need only 2k + 2^ + 3 < 2k + 2^ + 4 = o(G) + 2b(G) colors for a graph G obtained by connecting C2k+1 and C2^+1 with an edge. In this case we can use only one color for edges that project themselves to the bipartite component of G. Even more, if G has more bipartite components B< "between" two components O< and O< we can lower the upper bound of Theorem 2.4 for each such component B< by 1. The details are left to the reader. It remains to study rc(G x Kn), n > 3, to complete the upper bounds for the direct product. One possibility is to use the coloring from the proof of Theorem 2.1 with rc(G)(o(Kn) + b(Kn)) = rc(G)o(Kn) = 3rc(G) colors whenever G is not complete. £ CO CO w CD 3 The strong product The strong product G ^ H of graphs G and H has the vertex set V(G) x V(H). Two vertices (g,h) and (g',h') are adjacent whenever gg' £ E(G) and h = h' or g = g' and hh' £ E(H) or gg' £ E(G) and hh' £ E(H). Hence there are three types of edges. If an edge of G ^ H belongs to one of the first two types, then we call such edge a Cartesian edge and edge of the last type is called a noncartesian edge. (The name is due to the fact that if we consider only first two types we get a Cartesian product of graphs - a fourth standard product not considered in this work.) The vertex set Gh = {(g, h)|g £ V(G)} for some fixed vertex h of H is called a layer of graph G or simply a G-layer (through h). Similar is gH = {(g,h)|h £ V(H)} an H-layer (through g). It is not hard to see that any G-layer induces a subgraph of G ^ H that is isomorphic to G and any H-layer induces a subgraph of G ^ H that is isomorphic to H. The strong product is connected whenever both factors are and the vertex connectivity of the strong product was solved recently by Spacapan in [23], but we are not aware of any result concerning CD edge connectivity of the strong product. J-l In [17] authors used the fact that the Cartesian product is a spanning subgraph of the strong one and they noted that the strong product has the same upper bound for the rainbow connection number as the Cartesian one. Unfortunately this bound is IN not tight. Even more, for the nontrivial strong product (both factors different from Ki) it is never reached. We will show a much better upper bound, which is tight for many graphs and is, as expected, related to the distance formula for the strong product, which states dc^H((g,h), (g',h')) = max{dG(g,g'),dH(h,h')}. o CSI I CSI 00 CSI CSI CD w Theorem 3.1 Let G and H be connected graphs. Then (i) rc(G B H) < max{rc(G), rc(H)}, (ii) src(G B H) < max{src(G), src(H)}. Proof. Without loss of generality, rc(G) < rc(H). Let cG : E(G) ^ {1,2,..., rc(G)} be a rainbow coloring of G and ch : E(H) ^ {1, 2,..., rc(H)} a rainbow coloring of H. A simple edge coloring of G B H is constructed as follows. Every edge of the form (g, h)(g', h) receives color cG(gg') and any other edge (g, h)(g', h') is colored with ch (hh'). We will show that this coloring is a rainbow coloring of G B H. Let (go,ho) and (gk,hi) be arbitrary vertices of G B H. Let P = gogi.. .gk and Q = hohi... hi be rainbow paths in G and H, respectively. If k < £, the path (go, ho)(gi, hi)... (gk, hk)(gk, hk+i)... (gk, hi) is a rainbow path since no edge on this path lies in any of the G-layers and Q is a rainbow path. Next, let k > £. Denote p = k — £ and suppose that there are r pairwise different colors that appear on both paths P and Q, 0 < r < £. We will construct a rainbow (go, ho), (gk, hi)-path with exactly £ noncartesian edges and p Cartesian edges that lie only in G-layers. Take any £ — r > 0 edges of P with colors that do not appear on Q and add the r edges of P with colors that appear on both paths P and Q. Denote the obtained edges with g^g^+i, gi2gi2+i,... ,gi£gi£+i, where ii < ... < ii. Then fc ^ M^u ho)... (gii, ho)(gil+l, hi Xgi^ hi)... (gi2, M^+b h2)(gi2+2, h2)... ... (gi£, hi-i)(gi£+i, hi)(gi£+2, hi)... (gk, hi) is a rainbow path since every color that appears on both P and Q appears on this path only on a noncartesian edge. (This path, roughly speaking, traverses P in the Ghj-layer from gij+i to gij+1 and then switches with a noncartesian edge (gij+1, hj)(gij+1+i, hj+i) to the Ghj+1 -layer for j = 0,1,..., £ — 1.) The proof of (ii) is analogous, here we take P and Q to be shortest rainbow paths. □ r This upper bound is sharp for many pairs of graphs but it can also be arbitrarily larger than the rainbow connection number of the strong product. Both options will be discussed till the end of this section as well as some particular results. Corollary 3.2 Let G and H be connected graphs with rc(G) < rc(H) = diam(H). Then rc(G K H) = diam(H). IN Proof. Since diam(G) < rc(G), we have diam(G K H) = max{diam(G), diam(H)} = diam(H). Using the trivial lower bound and Theorem 3.1 we have diam(H) < rc(G K H) < max{rc(G), rc(H)} = diam(H) and the equality holds. □ CD U Corollary 3.3 For every connected graph G there exists n0 E N, such that rc(GKPn) = n for every n > n0. Proof. Let n0 = rc(G). For n > n0 we then have rc(G) < rc(Pn) = diam(Pn) and Corollary 3.2 ends the proof. □ 0 Clearly, both corollaries have an analogue version with respect to the strong rainbow connection number. In the remainder of this section we concentrate us on the opposite direction, namely, we present some examples for which the above upper bound is not exact. o Proposition 3.4 For m,n,p,q E N with n,q > 1 we have 2 < rc(Kmn Kl Kpq) < 3. 1 Proof. The lower bound follows from the trivial lower bound. For the upper bound we introduce the following edge coloring of Km,nKKp, q using three colors. All noncartesian edges get color 1, all edges that belong to some Km,n-layer get color 2, and all edges that belong to a Kp,q-layer get color 3. To show that this is a rainbow coloring we split KmnKKpq into four parts AC, AD, BC and BD that correspond to Cartesian product CO of their bipartition sets. So suppose that V(Km n) = A U B and V(Kp q) = C U D, CO where A = {ai, a2,..., am} and B = {bi, b2,..., bn} form a bipartition of Km,n, and C = {ci,c2,... ,cp} and D = {di,d2,... ,dq} a bipartition of Kp,q. Every vertex of AC is adjacent to every vertex of BD, the same holds for AD and BC. Hence, we have to find a rainbow path between any two vertices of BD as well as between any vertex of BD and BC (or AD). All other paths can be found symmetrically. The path (bi,dj)(ai,dj)(ai,ci)(bk,df) is a rainbow path between two arbitrary vertices of BD. The path (bi,dj)(ai,dj)(bk,q) is a rainbow path between vertices from BD and BC. The last case, the path (bi, dj)(bi, ci)(ak, de) is a rainbow path from a vertex from BD to a vertex from AD. □ • i Jh In [6] it is shown that rc(Km,n) = min{[ mn~| , 4} for 2 < m < n. Hence, the Proposition 3.4 is no surprise. Combining the latter result with Theorem 3.1 we get: Corollary 3.5 Let 2 < m < n < 2m and 2 < p < q < 2p. Then rc(Km,n K Kp,q) = 2. Jh However, Proposition 3.4 also allows that m and p are equal to 1. If this is the case, then we are dealing with stars Ki,n, Ki,q, and their rainbow connection number equals n and q, respectively. Hence, the upper bound of Theorem 3.1 equals max{n, q}, but we have a rainbow 3-coloring by Proposition 3.4. Thus, the difference between the upper bound of Theorem 3.1 and the rainbow connection number of the strong product IN can be arbitrarily large. It seems that, in general, this upper bound behaves good if the graph for which the bound max{rc(G), rc(H)} is obtained has diameter close to its rainbow connection number. We end this section with the exact result for stars. For this recall that rc(G) = 2 is equivalent to src(G) = 2 [6]. co u a CD Corollary 3.6 Let n, q > 3. Then rc(Ki,n K K\,q) = 3 and src(Ki,n K K,n) = n. Proof. We will use the same notation as in the proof of Proposition 3.4. Note that there is only one vertex (a1,c1) in AC, but there are at least 9 vertices in BD. If we would have a 2-rainbow coloring of K1,nKlK1,q, then this coloring would also be a strong rainbow coloring. It is not hard to see that the set {(a1,c1), (b1,d1), (b2,d2), (b3,d3)} is convex in K1,n K K1,q and this set induces a K1,3. By Observation 1.1 we have src(K1,n K K1,q) > src(K1,3) = 3. Hence, rc(K,n K K1,q) > 3 and by Proposition 3.4 the equality holds. For the second part, the set {(a1 ,c1)} U {(6j,dj)|i G {1,2, ...,n}} is convex in K1. n K K1 n. Moreover, it induces a convex subgraph K1 n and by Observation 1.1 we O otata src(K,„ K K1J > n. Theorem 31 concludes rte proof. □ 4 The lexicographic product The lexicographic product G o H of graphs G and H is the graph with V(G o H) = V(G) x V(H). Two vertices (g,h), (g',h') are adjacent if gg' G E(G) or if g = g' and hh' G E(H). The lexicographic product is not commutative and is connected whenever G is connected. Again G- and H-layers are isomorphic to G and H, respectively. In [17] authors proved that the upper bound for the rainbow connection number of G o H is the rainbow connection number of G if H is complete and one more otherwise. It is easy to see that the rainbow connection number of G is a good upper bound for all graphs G, with rc(G) > 2 and every H with at least three vertices. Theorem 4.1 Let G and H be graphs with |V(G)| > 2, |V(H)| > 3, and let G be connected. Then m rc(G o H) < max {rc(G), 2} and src(G o H) < max {src(G), 2}. "J- Proof. First note that we need two colors in the case when G is complete and H is not. Suppose now that G is not complete and that G is rainbow connected with colors 0,1,..., rc(G) — 1. For every h G H color the G-layer Gh the same as G. By this way, any two vertices (g, h)(g', h) G V(G o H) are connected by a rainbow path. Every edge of the form (g,h)(g',h') gets color k + 1(modrc(G)), where gg' G E(G), h = h', and k is the color of the edge gg' in G. Finally, color edges from H layers arbitrarily. Let (g,h), (g',h') G V(G o H) and h = h'. Suppose first g = g'. Then (g, h)(g1, h')(g, h') is a rainbow (g, h), (g, h')-path in G o H for ggi G E(G). Suppose now that g = g'. Let gg1... gkg' be a rainbow g, g'-path in G and let h1 be an arbitrary vertex in H different from h and h'. Then (g, h)(g1, h1)(g2, h)(g3, h1)... (gk , u)(g',h') is a rainbow IN (g, h), (g', h')-path, where u = h if k is even and u = h1 otherwise. Note that the same arguments hold if we start with a strong rainbow coloring of G. In the case g = g' the above path works only when h and h' are not adjacent. But if they are adjacent there is nothing to prove. □ There are many examples which show that this upper bound is not the best possible. For instance, if H is connected with at least two vertices then rc(K1,n o H) < 3. The coloring that realizes the latter upper bound is obtainable as follows. The edges (g^, h)(gj, h) get color 1, color 2 is given to edges of the form (g^, h)(gj, h'), where g^ G E(K1,n) and h = h'. Every edge inside an H-layer gets color 3. It is straightforward to check the rainbow connectedness. (Note that this is not a strong rainbow coloring.) This case shows that the difference between the upper bound from Theorem 4.1 and the rainbow connection number of lexicographic product can be arbitrarily large. However, this coloring provides a surprising relation with some other invariant. Denote with /0(G) the minimum cardinality of a vertex cover S C V(G), i.e., S contains at least one endvertex of every edge. Theorem 4.2 Let G be a connected graph and H a graph without isolated vertices with |V(H)| > 2. Then rc(G o H) < 20(G) + 1. C^ Proof. Let S be a vertex cover of minimum cardinality. We can cover V(G) with {NG[si]|si G S}. Color the edges in H-layers with color 1. We color edges in (NG[s1^o H with color 2 if they belong to a G-layer and with color 3 if they do not belong to a G-layer nor to a H-layer (as the latter ones are already colored). Inductively, we continue with (NG[sjj) o H, i > 1, where all yet uncolored edges that belong to a G-layer receive color 2i and other uncolored edges not in an H-layer get color 2i + 1. Finally, set color 1 to all edges from an H-layer. Hence all edges are colored and we have used 20(G) + 1 colors. Clearly, (g, h)(g', h)(g, h') is a rainbow (g, h), (g, h')-path. For go = gk let P = gog1... gk be a shortest g0, gk-path in G. Then a path in GoH that projects to P and follows the sequence of edges Cartesian-noncartesian-Cartesian-... or vice versa with possible last edge in a H-layer is a rainbow (g0,h), (gk,h')-path as can be easily seen. □ Our next goal is to prove that rc(T o H) < diam(T) + 1, where T is a tree and the graph H has enough vertices. We need to order the vertices in G. For this we use breadth-first search (BFS), a graph search algorithm that begins at the arbitrary vertex and explores all the neighboring vertices. Then for each of those nearest vertices, it explores their unexplored neighbors, and so on, until there are no vertices left to explore. J-i Lemma 4.3 Let i G {0,1,..., n}. Then i can be written as a sum of n different numbers from {0,1,..., n} with respect to module n + 1. £ CO CO CD CO Proof. Let j G {0,1,..., n} be such that j = 0 + 1 + ... + (n - 1) (mod n + 1). (1) If i = j we are done. If i > j, then we replace n — (i — j) in (1) with n (adding i — j on both sides of (1)), that is i = 0 + ... + (n — (i — j) — 1) + n + (n — (i — j) + 1) + ... + n — 1 (mod n + 1). If i < j, then we replace j — i — 1 in (1) with n, that is i = 0 + ... + (j — i — 2) + n + (j — i) + ... + (n — 1) (mod n + 1). Corollary 4.4 Let i G {0,1,...,n}. Then i can be written as a sum of k different numbers from {0,1,..., n} with respect to module n + 1, where 1 < k < n. CO u a CD Theorem 4.5 Let T be a tree with diam(T) > 2 and H a graph with |V(H)| > diam(T)" 2 Then diam(T) < rc(T o H) < diam(T) + 1. Proof. Note first that diam(T) is the trivial lower bound for rc(To H), since diam(To H) = diam(T) > 2. Let g1,g2,... , g|V(T)| and 0,1,..., | V(H)|—1 be the vertices of T and H, respectively, ordered by BFS. Let n = diam(T) and let c : E(ToH) ^ {0,1,..., n} denote a coloring CO of T o H with n + 1 colors defined as follows. For i < j let c((gi, k)(gj, k')) = k' — k (mod n + 1), where gigj G E(T). The remaining edges can be colored arbitrarily as they will play diam(T)" 2 We no role later. Note that we have exactely n + 1 colors since |V(H)| > need to prove that any two vertices of T o H are connected by a rainbow path. Let (gi, k), (gj, k') G V(T o H) and (gi, k) = (gj, k'). If i = j, there exists a (gi, k), (gi, k')-path of length four, colored with colors 0, n, 1, 2 for an arbitrary neighbor g^ of gi if k = k' (mod n + 1), and, otherwise, a (gi,k), (gi,k')-path of length two, colored with colors k' — k (mod n + 1) and 0. Hence we can assume, without loss of generality, that i < j. If |k — k'| > n, then there is a rainbow (gi, k), (gj, k')-path containing the same colors as a rainbow (gi, k), (gj, k'')-path, where |k — k''| < n and k'' = k' (mod n + 1)., thus we may assume that |k — k'| < n. We distinguish two cases. Case 1. For every vertex gk from the gi,gj-path (which is unique as we are dealing with a tree) holds i < k < j with respect to the ordering of T. Let h be a number from {0,1,..., n} such that h = k' — k (modn + 1). From Corollary 4.4 it follows that h can be written as a sum of dT(gi,gj) different numbers from {0,1,..., n} with respect to the module n + 1. The definition of the coloring c assures that these numbers are exactly the different colors of a (g, k), (gj, k')-path in T o H (the order of the colors is not important, with any permutation of these colors we can come from the start to the end). Case 2. Next, there exists a vertex gk on the §i, gj-path with k < i < j with respect to the ordering of T. Let gk be chosen such that k is as small as possible. Suppose first that dT(gi,gj) = 2. Clearly, then gk is the common neighbor of gi and gj. We would like to find a rainbow (gi,k), (gj,k')-path. If k = k'(mod n + 1) then (gi,k), (gk,k), (gj,k') is a (gi, k), (gj, k')-path colored with colors 0, k! — k (mod n + 1). If k = k! (mod n + 1) we distinguish three possible cases with respect to the position of another vertex gp e V(T) different from gk,gi,gj, which does exist as diam(T) > 3. i—l (i) If gk has a neighbor gp different from gi, gj then (gi, k), (gk, k), (gp, k + 1), (gk, k + 2), (gj,k') is a rainbow path with colors 0,n, 1,n — 1 if gp < gk and with colors 0.1,n,n — 1 if gk < gp. £ (ii) If gi has a neighbor gp different from gk then i < p, otherwise T is not a tree. The path (gi, k), (gp,k + 1), (gj,, k + 2), (gk, k), (gj, k') is a rainbow path with colors 1,n, 2,0. o CSI (iii) If gj has a neighbor gp different from gk then j < p and (gi,k), (gk,k), (gj,k + 1), (gp, k + 3), (gj ,k') is a (gi,, k), (gj, k')-path colored with colors 0,1,2,3. (N Now let dT(gi,gj) > 2. For start, we search for a (gi,k), (gj,k')-path colored with different colors, where k = k'(modn + 1). We distinguish three cases with respect to the parity of dr (gk ,gi) and dr (gk ,gj). (i) Let dr (gk ,gi)and dr (gk ,gj) be odd. If dr (gk ,gj) = 1 then we have a (gi, k), (gk ,k+ 1)-path with colors 0,1, n — 1 and pairs of colors i,n + 1 — i. The edge (gk, k + 1), (gj,k') has color n. If dr(gk,gj) > 1 then there is a (gi,k), (gk,k + n)-path with colors 1, 3, n — 2,4, n — 3,... It remains to show that there exists a (gk, k + n), (gj, k')-path colored with colors that did not appear on the (gi,, k), (gk, k + n)-path. That is clear, since we can use colors 0, 2, n and pairs of colors £,n + 1 — £, which have not been used on the (gi, k), (gk,k + n)-path. (ii) Let dr(gk,gi) be odd and let dr(gk,gj) be even. Then there is a (gi,k), (gk,k)- path with colors 0,1,n, 2,n — 1,____ It remains to show that there exists a (gk,k), (gj, k')-path with colors that did not appear on the (gi,k), (gk,k)-path. This is not a problem, since we can use the pairs of colors £,n + 1 — £, which have not been used in the (gi,, k), (gk, k)-path. CD ■ i J-H CD W (iii) Let dr(gk, gi,) be even. Then there is a (gi, k), (gk, k)-path with colors 1, n, 2, (n — 1), 3, (n — 2),... It remains to show that there exists a (gk, k), (gj, k')-path colored with colors that did not appear on the (gi, k), (gk, k)-path. This is true, since we can use color 0 and pairs of colors £,n + 1 — £, which have not appeared on the (gi, k), (gk, k)-path. Of course, the color 0 is used just in the case when dr(gk,gj) is odd. It remains to prove that there exists a rainbow (g^k), (gj,k')-path, where k ^ k'(mod n +1). We will do only the case where dT(gk,g») and dT(gk, gj) are even, other three possibilities are similar. Since module is n + 1, without loss of generality, we can IN assume that 1 < k' — k < n. We will transform the rainbow (gi, k), (gj, k)-path P into a rainbow (gi, k), (gj, k')-path. The aim is to increase the sum of the colors on gk, gj-path for £ and decrease the sum of the colors on gk,gi-path for £', where £ + £' = k' — k. Of course, if we are able to do that for dT(gi,gj) = n, then we are also able to do it for smaller distances between gi and gj. Therefore we can assume that P has n edges. The coloring of P is the following. Let i = dT(g2fe. Colors used in coloring of gk ,gi-path of P are 1, 2,..., i, (n + 1 — i), (n + 2 — i),..., (n — 1), n and those that are used in the coloring of gk,gj-path of P are (i + 1), (i + 2),..., n, n+t2,..., (n — i — 1), (n — i). i—l 1. If j = k'—k < i then we use colors 0,1,..., j—1, j+1,..., i instead of 1,2,..., j, j+ 1,...,i in P. o 2. If j = k' — k < 3i we can switch n — £ for some £ G {0,1,..., i} in coloring of gk ,gi-path in P with n — i in coloring of gk ,gj-path in P and use 1. if it is necessary. It remains to study the case when j = k' — k > 3i. It is obvious that dT(g2k,gi) = i < n — 2i = dT(gk,gj). Hence, for 1 < £ < i we can switch n — i + £ in coloring of gk,gi-path in P with i + £ in coloring of gk,gj-path in P and use 1. if it is necessary. Since 2i(n — 2i + 1) > n, we solve every j = k' — k, where 3i < j < diam(T). □ Altogether, under the assumptions of Theorem 4.5 we have diam(T) < rc(T o H) < diam(T) + 1, since diam(T o H) = diam(T). The ideas from the above proof give us also a motivation for another general result. £ CO CO m a CD U Corollary 4.6 Let G and H be graphs with diam(G) > 2 and |V(H)| > diam(G) and let G be connected. Then rc(G o H) < 2diam(G) + 1. Proof. Order the vertices of G and H with BFS and use the coloring of G o H from the proof of Theorem 4.5 with module 2diam(G) + 1, instead of diam(G) + 1. Let L1, L2,..., Lk be the levels of BFS ordering of G. Every pair of vertices gi G La,gj G Lb, i < j satisfies one of the following properties. 1. There exists gk from gi,gj--path with gk G Lc for c < a, b and k < i < j (we can CD choose the smallest k) and d(gk,gi),d(gk,gj) < diam(G). I ' 2. If gk is on gi,gj-path with d(gi,gk) + d(gk,gj) = d(gi,gj) then gi < gk < gj. ■ i Thus we can use the arguments from the proof of the Theorem 4.5 to complete the proof. □ References [1] B. S. Anand, M. Changat, S. KlavZar, I. Peterin, Convex sets in lexicographic products of graphs, Graphs Combin. DOI 10.1007/s00373-011-1031-4. £ CO CD CO [2] B. Bresar, S. Spacapan, On the connectivity of the direct product of graphs, Aus-tralas. J. Combin. 41 (2008) 45-56. [3] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57. [4] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and Algorithms for Rainbow Connection, J. Comb. Optim. 3 (2011) 330-347. [5] M. Changat, H. M. Mulder, G. Sierksma, Convexities related to path properties on graphs, Discrete Math. 290 (2005) 117-131. [6] G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. [7] G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81. [8] P. Erdos, M. Simonovits, V. T. Sos, Anti-Ramsey theorems, Colloq. Math. Soc. Janos Bolyai 10 (1975) 633-643. [9] S. Fujita, C. Magnant, K. Ozeki, Rainbow generalization of Ramsey theory: a survey, Graphs Combin. 26 (2010) 1-30. [10] A. A. Ghidewon, R. Hammack, Centers of tensor product of graphs, Ars Combin. 74 (2005) 201-211. HH [11] R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360-1363. [12] W. Imrich, S. Klavzar, Product Graphs: Structure and Recognition, John Wiley & Sons, New York, 2000. [13] P. K. Jha, S. Klavzar, B. Zmazek, Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Teory 17 (1997) 301-309. [14] S. R. Kim, Centers of a tensor composite graph, Congr. Numer. 81 (1991) 193-203. [15] S. Klavzar, S. Spacapan, On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008) 93-98. [16] M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2009) 185-191. CD [17] X. Li, Y. Sun, Characterize graphs with rainbow connection number m — 2 and rainbow connection numbers of some graph operations, submitted. [18] X. Li, Y. Sun, Rainbow Connection of Graphs - A Survey, Arxiv preprint arXiv:1101.5747v1 [math.CO] (2011). [19] R.J. Nowakowski, K. Seyffarth, Small cycle double covers of products. I. Lexicographic product with paths and cycles. J. Graph Theory 57 (2008), 99-123. [20] I. Peterin, Intervals and convex sets in strong product of graphs, submitted. [21] I. Schiermeyer, Rainbow connection in graphs with minimum degre three, IWOCA 2009, LNCS 5874 (2009) 435-437. [22] I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Teory 31 (2011) 387-395. [23] S. Spacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010) 457-467. [24] P. M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc., 13 (1962) 47-52. o m CD $H CD m u a CD U [25] X.Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59 (2008), 261-278.