IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1151
ISSN 2232-2094
ON THE RAINBOW CONNECTION OF CARTESIAN PRODUCTS AND THEIR SUBGRAPHS
Sandi Klavzar Gasper Mekis
Ljubljana, June 7, 2011
On the rainbow connection of Cartesian products and
their subgraphs
Sandi Klavzar*	Gasper MekiST
io
0 o
1
CO
CO
Abstract
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above with the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number smaller as much as possible than the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow coloring is introduced. In particular it is proved that the so-called ©-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow coloring.
Key words: rainbow connection; strong rainbow connection; Cartesian product of graphs; isometric subgraph; hypercube
AMS subject classification (2010): 05C15, 05C76, 05C12
CO
1 Introduction
The concept of rainbow connection was introduced just a few years ago by Char-trand, Johns, McKeon, and Zhang [4] but it already received an amazing attention. For instance, the recent survey [11] of Li and Sun on the topic contains a list of 56 references. Let us briefly mention a sample of the related research directions.
In the seminar paper [4], the rainbow connection number rc(G) as well as the strong rainbow connection number src(G) of a connected graph G were introduced. Among other results, these two graphs invariants were determined for cycles, wheels,
'u
*Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia; Faculty of Natural Sciences and Mathematics, University of Maribor, Koroska 160, 2000 Maribor, Slovenia; Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana. E-mail: sandi.klavzar@fmf.uni-lj.si.
^Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana. E-mail: gasper.mekis@gmail.com.
a
^	1
cu
o
complete bipartite graphs, and complete multipartite graphs. As a consequence, the difference src(G) —rc(G) can be arbitrarily large. In [3] it is proved that the invariants are intrinsically difficult, in fact even deciding whether rc(G) = 2 holds for a graph G is an NP-complete problem. On a positive side, Kemnitz and Schiermeyer [8] proved that most of graphs of order n, diameter two and clique number at least n — 3 have rainbow connection number two, and list all the exceptions. Some more bad news: to find out whether a given edge coloring is a rainbow coloring is also an NP-complete problem [3]. Bounds on the rainbow connection number of graphs in terms of minimum degree and other graph parameters are given in [2, 9, 12].
Very recently, two groups of authors independently considered the rainbow connection of graph products [1, 5]. More precisely, the first of these papers deals with Cartesian, lexicographic and strong products, while the latter treats direct, strong and lexicographic products. So all standard graph products (see [6] for the theory of these products) have been addresses by now. Additional results on graph operations, including graph products, were reported in [10].
In this paper we are interested in the rainbow connection number of Cartesian products of graphs with the emphasize on the question what can be said about their subgraphs. In Section 3 we present and compare known upper bounds and demonstrate that there is no hope for some general bounds on the rainbow connection number of (isometric) subgraphs of Cartesian products. On the other hand, for the simplest products—hypercubes—the situation is different. We treat hypercubes in Section 4 where it is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above with the rainbow connection number of the hypercube. Using bipartite wheels we show that there exist isometric subgraphs of hypercubes with the rainbow connection number arbitrarily smaller than the rainbow connection number of the hypercube. In the final section the concept of CO c-strong rainbow coloring is introduced and studied. This is in part motivated by CO the fact that the c-strong rainbow connection number of an isometric subgraph of an arbitrary Cartesian product graph is bounded above with the one of the product.
2 Preliminaries
In this section we collect definitions and concepts needed in the rest of the paper. All the graphs considered will be simple, finite, and connected.
An edge coloring of a connected graph G is a rainbow coloring if for any two vertices of G there is a path between them whose edges have pairwise different colors.
i
CSI 00 CSI CSI
CD
■ i-H J-H
CD CO
Such paths are called rainbow paths and G is called rainbow connected. The least number of colors needed to make G rainbow connected is the rainbow connection number rc(G) of G. If in the above definitions the paths considered are shortest paths, we speak of the strong rainbow coloring, strong rainbow connected graphs, and the strong rainbow connection number src(G) of G.
U
a
CD U
o
The Cartesian product G □ H of graphs G and H has the vertex set V(G) x V(H). Vertices (g,h) and (g',h') of G □ H are adjacent whenever gg' £ E(G) and h = h', or g = g' and hh' £ E(H). The subgraph of G□ H induced on vertices {(g, h) | g £ V(G)} is a is a G-layer (through h). H-layers are defined analogously. Clearly, G-layers and H-layers are isomorphic to G and H, respectively. The Cartesian product operation is commutative and associative, hence the Cartesian product of more factors is well-defined. The simplest multiple Cartesian products □	are
known as hypercubes Qd. The Cartesian product of graphs is connected if and only if all of its factors are connected.
Recall that the k-wheel Wk, k > 3, is the graph obtained from Ck by adding a vertex and connecting it to every vertex of Ck. For k > 3, the bipartite wheel BWk is the graph obtained from the k-wheel Wk by subdividing each of the edges of the outer cycle of Wk with one vertex. In particular, BW3 is the graph obtained from Q3 be removing one of its vertices and BW4 = P3 □ P3.
The graph distance considered is the standard shortest paths distance. By ecc(v) = max{dG(u, v) | u £ V(G)} we denote the eccentricity of a vertex v £ V(G). The diameter of G, diam(G), is the length of a longest shortest path, in other words, diam(G) = max{ecc(v) | v £ V(G)}. Note that
diam(G) < rc(G) < src(G).
i
The radius of G is defined as r(G) = min{ecc(v) | v £ V(G)}.
A subgraph H of connected graph G is isometric if dH(u, v) = dG(u, v) holds for all u, v £ V(H). If additionally every shortest u, v-path lies completely in H, we say that H is a convex subgraph of G. G is a partial cube if for some integer d, G is an isometric subgraph of Qd. Edges uv and u'v' of G are in relation © if d(u, u') + d(v,v') = d(u, v') + d(u',v). Relation © is reflexive, symmetric, but generally not transitive. Winkler [13] proved that a (connected) graph G is a partial cube if and only G is a bipartite graph with transitive relation ©. Hence for partial cubes G, relation © partitions E(G) into equivalence classes that will be referred as ©-classes. The least number d needed for a partial cube G to isometrically embed into Qd is the isometric dimension idim(G) of G. Finally, a graph is a median graph if for any triple of its vertices u, v, w there exists a unique vertex that lies on a shortest u, v-path, on a shortest u, w-path and on a shortest v, w-path. It is well-known that median graphs are partial cubes.
• Sh
3 Cartesian products and their subgraphs
In this section we present two known upper bounds for the rainbow connection number of Cartesian products, compare the two bounds, and address the problem if there is a relation between the rainbow connection number of a Cartesian product and its subgraphs. We state all results for two factors since generalizations to more
factors are straightforward due to the associativity of the Cartesian product and since the distance in a product is just the sum of distances between the projections onto factors.
Let £g and £H be edge colorings of graphs G and H. Then the coloring £q □ H defined with £G □ H ((g, h)(g', h)) = £o(gg') if gg' e E(G) and £G □ h ((g, h)(g, h')) = £H (hh') if hh' e E(H) will be called a product coloring (of G □ H with respect to £g and £H). In other words, a product coloring inherits colorings of layers from the colorings of the corresponding factors.
Given graphs G and H equipped with disjoint optimal rainbow colorings, Li and Sun [10] noticed that the product coloring of G □ H gives
10
rc(G □ H) < rc(G) + rc(H).	(1)
i—l
They also observed that the bound is tight, we state this fact for the later reference.
Proposition 3.1 ([10]) Let G and H be graphs with rc(G) = diam(G) and rc(H) = diam(H). Then rc(G □ H) = rc(G) + rc(H).
Proof. Using (1) and the fact that diam(G □ H) = diam(G) + diam(H) we have: diam(G) + diam(H) = diam(G □ H) < rc(G □ H) < rc(G) + rc(H)
= diam(G) + diam(H), hence the assertion.	□
On the other hand, Basavaraju et al. [1] proved the following upper bound:
rc(G □ H) < 2r(G □ H).	(2)
CO
To prove (2) a construction more involved than the one to obtain (1) is required. The next result demonstrates tightness of (2):
Proposition 3.2 ([1]) Let G and H be graphs with diam(G) = 2r(G) and diam(H) = 2r(H). Then rc(G □ H) = 2r(G □ H).
Proof. Similarly as in the proof of Proposition 3.1, the fact r(G □ H) = r(G) + r(H) and (2) yield:
diam(G) + diam(H) = diam(G □ H) < rc(G □ H) < 2r(G □ H) = 2r(G) + 2r(H) = diam(G) + diam(H),
CD
and we are done.	□
Proposition 3.2 in particular implies that for any n, m > 2,
rc(Ki,ra □ Ki,m) = 4 .
^	4
CU
lO
0 fi
o
1
CO
£ CO CO
This example shows that (2) can be arbitrarily better than (1). Indeed, inequality (1) asserts that rc(Ki,n □ K1,m) < n + m.
On the other hand, (2) can also be worse than (1). To see this, consider any graphs G and H with diam(G) = r(G) = rc(G) and diam(H) = r(H) = rc(H). Then Proposition 3.1 implies that (1) gives the exact result rc(G □ H) = r(G)+r(H), while (2) asserts rc(G □ H) < 2r(G)+2r(H). For a simple concrete example consider products of complete graphs for which rc(Kn □ Km) = 2.
We turn now our attention to subgraphs of Cartesian products and pose a question whether we can bound rc(X) in terms of rc(G □ H), provided X is a subgraph of G □ H. Clearly, rc(X) can be arbitrarily smaller than rc(G □ H). But it can also be arbitrarily bigger, as the example of Figure 1 shows. There P20 is a subgraph of P5 □ P4, rc(P2o) = 19, and rc(P5 □ P4) = rc(P5) + rc(P0 = 7 by Proposition 3.1. Of course, the example easily generalizes to Pn □ Pm for any n and m.
0 C^^D-C^^O-0
o o-0-0-0-o
o-o-o-o-o
Figure 1: The product P5 □ P4
Hence not much can be said about general subgraphs of Cartesian products. But what if X is an isometric subgraph of G □ H? Also in this case, rc(X) can be arbitrarily bigger than rc(G □ H), we will demonstrate this in the next section. Finally, note that considering convex subgraphs gives no new information because convex subgraphs of Cartesian products are precisely subproducts that project onto convex subgraphs of the factors [7].
m
CD CD
m
u
a
CD U
4 Isometric subgraphs of hypercubes
The message of the previous section was that not much can be said in general about the rainbow connection number of (isometric) subgraphs of Cartesian products. For the simplest Cartesian products—hypercubes—the situation is different:
Proposition 4.1 Let G be an isometric subgraph of Qn. Then rc(G) < rc(Qn) = n.
Proof. Clearly, rc(Q1) = 1. For n > 2 the assertion rc(Qn) = n follows by an inductive use of Proposition 3.1.
Let now G be an isometric subgraph of Qn. Color Qn by the product coloring, where each of its factors K2 is colored with a private color and let G be equipped with the induced coloring. Let u, v G V(G). Then, as G is isometric in Qn, there exists a shortest u, v-path in G, say P, that lies completely in Qn. As P is a geodesic, the product coloring of Qn assigns different colors to its edges. Hence G is rainbow connected and we have used at most n colors.	□
CD
lO
i
CSI 00 CSI
Corollary 4.2 Let G be a partial cube with idim(G) = diam(G). Then rc(G) = idim(G).
Proof. Combine the fact that rc(G) > diam(G) with Proposition 4.1.	□
We continue with a specific class of partial cubes that will enable us to answer a question raised in Section 3.
fi
Lemma 4.3 For any k > 4, rc(BWk) = 4.
Proof. Denote the central vertex of BWk with x. For i = 1,..., k let yi be a neighbor of x (in ordered way through the cycle), and zi the vertex of degree 2 between yi and yi+i, where i + 1 is meant cyclically. It is easy to see, that diam(BWk) = 4 for k > 4. To complete the proof we thus need to construct a rainbow coloring of BWk using four colors.
Suppose first k is even. Color the edges xyi with color 3 if i is odd, and with color 4 otherwise. Edges yizi and yizi-1 get color 1 for odd i, for even i they get color 2. Any of the non-neighbors (zi) of x can be reached from x using either colors 4 and 2 or colors 3 and 1. Let 1 < i < j < k. Now find a rainbow path between yi
CO
and yj. If i and j are of different parity, then we can take a path via x using colors
CO 3 and 4. Otherwise, take the path yi,x,yj-i,zj-i,yj (a path of colors 3,4, 2,1 or 4,3,1,2). Next, take zi and zj. Then zi,yi+1,x,yj+1, zj is a rainbow path if i and j are of different parity, otherwise we can take the path zi,yi+1,x,yj-,zj. The only case left is when we take yi and zj, where 1 < i, j < k. Then the path yi,x,yt, zj is a rainbow path, where yt is the neighbor of zj with t of different parity as i.
Let now k be odd. As above, edges yizi and yiz^ 1 get color 1 for odd i, for even i they get color 2. For 1 < i < k, edge xyi gets color 3 if i is odd, and color 4 otherwise. We color the remaining edge xyk with color 2. With the same arguments as in (i) follows that we have a rainbow path between any two vertices in BWk — {zk-1 , yk, zk}. The path zk-1, yk-1, x, y1, zk is a rainbow path. Hence it remains to see, that there exists a rainbow path between any vertex from BWk — {zk-1, yk, zk} and any vertex from {zk-1,yk, }. Clearly, from y^ we can achieve any vertex in BWk — {zk-1,yk,zk} by going to x (color 2) and then using the colors 3,1 or 4. From zk-1 (resp. zk) we can reach yi with colors 1, 2, 3 or 1, 2, 4 and we can reach zi with colors 2, 4, 3,1 (resp. 1, 3, 4, 2).	□
ft
lO
0 fi
o
1
CO
£ CO CO
Consider products BWk □ BWk, k > 4. Then Lemma 4.3 and Proposition 3.1 imply that rc(BWk □ ) = 8. On the other hand, K1;k is an isometric subgraph of BWk □ BWk with rc(K1;fc) = k, which demonstrates that in general Cartesian products the rainbow connection number of an isometric subgraph can be arbitrarily bigger than the one of the product.
In view of Proposition 4.1 we now ask, how big can the difference between rc(G) and rc(Qn) be, where G is isometric in Qn and idim(G) = n. (The answer is trivial if we would not require idim(G) = n.) We have:
Theorem 4.4 For every d > 4 and for every k > d, there exists a median graph G with diam(G) = d = rc(G) and idim(G) = k.
Proof. Lemma 4.3 gives rc(BWfc-(d-4}) = 4. Connect an endvertex of a path on d—4 vertices with one of the vertices of degree two in BWk-(d-4) to construct a graph G. By this operation G is still a median graph with idim(G) = idim(BWk-(d-4)) + d — 4 = k and diam(G) = d. Now take any 4-coloring of BWk-(d-4) that makes BWk-(d-4) rainbow connected and color the remaining edges in G each with its own (new) color. By this way G obviously gets rainbow connected where d colors are used.	□
The assumption d > 4 in Theorem 4.4 is unavoidable. First note that the only median graphs with diam(G) = 2 are C4 and K1,n and that rc(K1>n) = idim(K1>n) = n — 1. For d = 3, it can be shown that all median graphs G of diameter 3 can be constructed as follows. Either G = Q3 or G can be obtained from one of the left three graphs from Figure 2 by attaching to the black vertices an arbitrary number of pendant vertices and by attaching to adjacent black vertices an arbitrary number
of pendant squares.
Q
O O
O-O
O-
-O
O O-
-O
m
CD CD
m
Figure 2: Generators of median graphs of diameter 3
It is straightforward to see that by attaching pendant vertices and pendant squares the rainbow connection number rises. So there is no infinite family (in the sense that we can move isometric dimension arbitrary far away from diameter) of median graphs with diameter and with rainbow connection number equal to 3.
u
a
CD U
lO
0 fi
o
1
CO
£ CO CO
m
CD
$H
CD
m
u
a
CD U
5 Strong rainbow colorings
We now turn to strong rainbow colorings and consider the example from Figure 3. The factors C4 and K2 are equipped with strong rainbow colorings, however the product coloring produces an isometric subgraph of C4 □ K2 that is not (strong) rainbow colored.
0 3 0
Figure 3: The product C4 □ K2
This example motivates us to introduce the following concepts. A coloring of the edges of a graph G is a complete strong rainbow coloring, c-strong rainbow coloring for short, if every shortest path is a rainbow path. Having a c-strong rainbow coloring of G we say that G is c-strong rainbow connected. The smallest number of colors needed to make G c-strong rainbow connected is the c-strong rainbow connection number src(G) of G. Note that defining an analogous concept for the rainbow connection is not interesting, as then only the coloring where every edge has its own color would make a graph completely rainbow connected. Clearly,
diam(G) < rc(G) < src(G) < src(G).
The appropriateness of the c-strong rainbow colorings for Cartesian product is demonstrated with the following:
Proposition 5.1 For any (connected) graphs G and H and any isometric subgraph X of G □ H,
src(X) < src(G □ H) < src(G) + src(H).
Proof. Let G and H be c-strong rainbow colored with r and s disjoint colors, respectively. Then the product coloring is a c-strong rainbow coloring of G □ H using r + s colors. Indeed, this follows from the fact that a shortest path in G □ H projects (under the projection on G) onto a shortest path in G and projects (under the projection on H) onto a shortest path in H, cf. [7]. Moreover, the same argument also implies that src(X) < src(G □ H) because the induced coloring of X (being
embedded into G □ H) is also a c-strong rainbow coloring using at most r + s colors. □
Just as for rainbow connection, we can also say more about c-strong rainbow colorings for isometric subgraph of hypercubes. Before we state the result, let us introduce some related notation.
For an edge ab of a partial cube G we will denote with ©(ab) the ©-class of G containing ab. Removing the edges ©(ab) from G, two connected components Wab (containing the vertices that are closer to a than to b) and Wba (containing the vertices that are closer to b than to a) are obtained. The subgraphs of Wab and Wba containing the vertices that have a neighbor in Wba and Wab are denoted with Uab and Uba, respectively. Given a partial cube G, the ©-coloring is the coloring of the edges of G with ©-classes.
Theorem 5.2 Let G be a partial cube. Then src(G) = idim(G). Moreover, the ©-coloring is a unique optimal c-strong rainbow coloring of G.
o
CSI
I
Proof. Since no two edges on a shortest path belong to the same ©-class of G, the ©-coloring yields src(G) < idim(G).
Let c be an arbitrary c-strong rainbow coloring of G using src(G) colors. Fix ab G E(G). Let xy be an arbitrary edge in Wab. The latter graph is a convex subgraph in G, hence every shortest x, a-path (y, a-path, resp.) lies completely in Wab (it may happen that, for instance, x = a). The equality d(x, a) = d(y, a) is not possible, as then we would have an odd cycle in G which cannot happen in a partial
CSI
cube. Thus, without loss of generality, we may assume d(x, a) < d(y, a). Denote with P a shortest x, a-path. Then y,x,P, b is a shortest y,b-path since Uab = Uba, Uab (Uba, resp.) is a convex subgraph in Wab (Wba, resp.) and the edges between Uab and Uba form a perfect matching representing exactly the edges of ©(ab). It follows that c(xy) = c(ab). The case when xy is an edge in Wba is analogous. Therefore, no two edges of different ©-classes can have the same color in any c-strong rainbow coloring. Hence, src(G) > idim(G).
For the uniqueness just observe that if we would have used in some ©-class more than one color, then we would need for the whole graph strictly more than idim(G) colors.	□
As already mentioned, the difference between diam(G) and rc(G) can be arbi-
(D
$H
CD W
trarily large. We now show that the same is true for src(G) and src(G).
Proposition 5.3 For any n > 4, src(Wn) = [n/2].
Proof. Denote the central vertex of Wn with x and the vertices of the outer cycle consecutively with yi, y2,..., yn. Any two nonadjacent vertices y^ and yj are at distance 2 (which is the diameter of Wn), hence in this case the edges xy^ and xyj
ft
must have different colors. In other words, the only pairs of edges incident to x that can have the same color are of the form xyi and xyj, where yi is adjacent to yj. Thus, src(Wn) > [n/2]. Now we need to find a coloring that attains this bound.
The edge yiyi+1 gets color 1 for odd i < n, for even i < n it gets color 2 and the remaining edge yny1 gets color 3. For all i, the edge xyi gets color |~i/2~|. Checking that this is a c-strong rainbow coloring is straightforward.	□
2 _
Recall from [4] that src(Wn) = |n/3|. Hence the difference src(Wn) — src(Wn)
can be arbitrarily large. In fact, the same is true also in the class of partial cubes.
To see this, consider again the bipartite wheels. Then
lO
CO CO
src(BWn) = idim(BWn) = n and |"n/2] < src(BWn) < |~n/2] + 2
The first inequality follows from the proof of Proposition 5.3. For the second one consider the following coloring. Using the notations from Lemma 4.3, color xyi with |i/2| and color the edges around the cycle alternatively with the remaining two colors. Checking the rainbow connectedness is easy.
References
[1]	M. Basavaraju, L. S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number of graph power and graph products, manuscript, (2011) arXiv:1104.4190 [math.CO].
[2]	Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) R57.
[3]	S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 3 (2011) 330-347.
[4]	G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohemica 133 (2008) 85-98.
fc
[5]	T. Gologranc, G. Mekis, I. Peterin, Rainbow connection and graph products, manuscript, IMFM Preprint Series 49 (2011) #1149.
[6]	R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
"Jh
[7]	W. Imrich, S. KlavZar, D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Products, A K Peters, Wellesley, 2008.
[8]	A. Kemnitz, I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313-320.
a
[9] M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191.
[10]	X. Li, Y. Sun, Characterize graphs with rainbow connection number m — 2 and rainbow connection numbers of some graph operations, manuscript (2010).
CD
[11]	X. Li, Y. Sun, Rainbow connection of graphs - A survey, manuscript (2011) arXiv:1101.5747v1 [math.CO].
i-H
lO
0 o
1
CO
£ CO CO
[12]	I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31 (2011) 387-395.
[13]	P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225.
m
CD
$H
CD
m
u
a
CD
fr 11 cu