Graphs and Combinatorics (2013) 29:1–38

DOI 10.1007/s00373-012-1243-2

SURVEY

Rainbow Connections of Graphs: A Survey

Xueliang Li · Yongtang Shi · Yuefang Sun

Received: 30 January 2011 / Revised: 7 September 2012 / Published online: 16 October 2012
© Springer Japan 2012

Abstract The concept of rainbow connection was introduced by Chartrand et al. [14]
in 2008. It is interesting and recently quite a lot papers have been published about it.
In this survey we attempt to bring together most of the results and papers that dealt
with it. We begin with an introduction, and then try to organize the work into five
categories, including (strong) rainbow connection number, rainbow k-connectivity,
k-rainbow index, rainbow vertex-connection number, algorithms and computational
complexity. This survey also contains some conjectures, open problems and questions.

Keywords Rainbow path · (Strong) rainbow connection number · Rainbow

k-connectivity · k-rainbow index · Rainbow vertex-connection number · Algorithm ·
Computational complexity

Mathematics Subject Classification (2010) 05C15 · 05C35 · 05C40 · 05D40 ·

68Q25 · 68R10

This study was supported by NSFC No.11071130.

X. Li (B) · Y. Shi · Y. Sun

Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071,
People’s Republic of China
e-mail: lxl@nankai.edu.cn
Y. Shi
e-mail: shi@nankai.edu.cn
Y. Sun
e-mail: bruceseun@gmail.com

123
2 Graphs and Combinatorics (2013) 29:1–38

1 Introduction

1.1 Motivation and Definitions

Connectivity is perhaps the most fundamental graph-theoretic subject, both in a com-

binatorial sense and an algorithmic sense. There are many elegant and powerful results
on connectivity in graph theory. There are also many ways to strengthen the connec-
tivity concept, such as requiring hamiltonicity, k-connectivity and imposing bounds
on the diameter, and so on. An interesting way to strengthen the connectivity require-
ment, the rainbow connection, was introduced by Chartrand et al. [14] in 2008, which
is restated as follows:
This new concept comes from the communication of information between agencies
of government. The Department of Homeland Security of USA was created in 2003
in response to the weaknesses discovered in the transfer of classified information after
the September 11, 2001 terrorist attacks. Ericksen [35] made the following observa-
tion: An unanticipated aftermath of those deadly attacks was the realization that law
enforcement and intelligence agencies couldn’t communicate with each other through
their regular channels, from radio systems to databases. The technologies utilized
were separate entities and prohibited shared access, meaning that there was no way
for officers and agents to cross check information between various organizations.
While the information needs to be protected since it relates to national security, there
must also be procedures that permit access between appropriate parties. This two-fold
issue can be addressed by assigning information transfer paths between agencies which
may have other agencies as intermediaries while requiring a large enough number of
passwords and firewalls that is prohibitive to intruders, yet small enough to manage
(that is, enough so that one or more paths between every pair of agencies have no
password repeated). An immediate question arises: What is the minimum number of
passwords or firewalls needed that allows one or more secure paths between every two
agencies so that the passwords along each path are distinct?
This situation can be modeled by graph-theoretic model. Let G be a nontrivial con-
nected graph on which an edge-coloring c : E(G) → {1, 2, . . . , n}, n ∈ N, is defined,
where adjacent edges may be colored the same. A path is rainbow if no two edges of
it are colored the same. An edge-coloring graph G is rainbow connected if every two
vertices are connected by a rainbow path. An edge-coloring under which G is rainbow
connected is called a rainbow coloring. Clearly, if a graph is rainbow connected, it
must be connected. Conversely, any connected graph has a trivial edge-coloring that
makes it rainbow connected, namely, color the edges with distinct colors. As intro-
duced in [14], the rainbow connection number of a connected graph G, denoted by
r c(G), is the smallest number of colors that are needed in order to make G rainbow
connected. A rainbow coloring using r c(G) colors is called a minimum rainbow col-
oring. So the question mentioned above can be modeled by means of computing the
value of the rainbow connection number. By definition, if H is a connected spanning
subgraph of G, then r c(G) ≤ r c(H ). For a basic introduction to the topic, we refer
the readers to Chapter 11 in [19].
In addition to regarding it as a natural combinatorial measure and its application to
the secure transfer of classified information between agencies, the rainbow connection

123
Graphs and Combinatorics (2013) 29:1–38 3

number can also be motivated by its interesting interpretation in the area of networking
[12]: Suppose that G represents a network (e.g., a cellular network). We wish to route
messages between any two vertices in a pipeline, and require that each link on the
route between the vertices (namely, each edge on the path) is assigned a distinct chan-
nel (e.g. a distinct frequency). Clearly, we want to minimize the number of distinct
channels that we use in our network. This number is precisely r c(G).
Let c be a rainbow coloring of a connected graph G. For any two vertices u and
v of G, a rainbow u − v geodesic in G is a rainbow u − v path of length d(u, v),
where d(u, v) is the distance between u and v in G. A graph G is strongly rainbow
connected if there exists a rainbow u − v geodesic for any two vertices u and v in G. In
this case, the coloring c is called a strong rainbow coloring of G. Similarly, we define
the strong rainbow connection number of a connected graph G, denoted sr c(G), as
the smallest number of colors that are needed in order to make G strong rainbow
connected [14]. Note that this number is also called the rainbow diameter number in
[12]. A strong rainbow coloring of G using sr c(G) colors is called a minimum strong
rainbow coloring of G. Clearly, we have diam(G) ≤ r c(G) ≤ sr c(G) ≤ m, where
diam(G) denotes the diameter of G and m is the size of G.
In a rainbow coloring, we need only find one rainbow path connecting evey two
vertices. There is a natural generalizaiton: the number of rainbow paths between any
two vertices is at least an integer k with k ≥ 1 in some edge-coloring. A well-known
theorem of Whitney [83] shows that in every κ-connected graph G with κ ≥ 1, there
are k internally disjoint u − v paths connecting any two distinct vertices u and v for
every integer k with 1 ≤ k ≤ κ. Similar to rainbow coloring, we call an edge-coloring
a rainbow k-coloring if there are at least k internally disjoint u − v paths connecting
any two distinct vertices u and v. Chartrand et al. [17] defined the rainbow k-connec-
tivity r ck (G) of G to be the minimum integer j such that there exists a j-edge-coloring
which is a rainbow k-coloring. A rainbow k-coloring using r ck (G) colors is called a
minimum rainbow k-coloring. By definition, r ck (G) is the generalization of r c(G)
and r c1 (G) = r c(G) is the rainbow connection number of G. By coloring the edges
of G with distinct colors, we see that every two vertices of G are connected by k inter-
nally disjoint rainbow paths and that r ck (G) is defined for every k with 1 ≤ k ≤ κ.
So r ck (G) is well-defined. Furthermore, r ck (G) ≤ r c j (G) for 1 ≤ k ≤ j ≤ κ.
Note that this newly defined rainbow k-connectivity computes the number of colors,
which is distinct from connectivity (edge-connectivity) which computes the number
of internally disjoint (edge-disjoint) paths. We can also call it rainbow k-connection
number.
Now we introduce another generalization of rainbow connection number by Char-
trand et al. [18]. Let G be an edge-colored nontrivial connected graph of order n. A
tree T in G is a rainbow tree if no two edges of T are colored the same. Let k be a
fixed integer with 2 ≤ k ≤ n. An edge coloring of G is called a k-rainbow coloring
if for every set S of k vertices of G, there exists a rainbow tree in G containing the
vertices of S. The k-rainbow index r xk (G) of G is the minimum number of colors
needed in a k-rainbow coloring of G. A k-rainbow coloring using r xk (G) colors is
called a minimum k-rainbow coloring. Thus r x2 (G) is the rainbow connection num-
ber r c(G) of G. It follows, for every nontrivial connected graph G of order n, that
r x2 (G) ≤ r x3 (G) ≤ · · · ≤ r xn (G).

123
4 Graphs and Combinatorics (2013) 29:1–38

The above four new graph-parameters are defined for all edge-colored graphs.
Krivelevich and Yuster [53] naturally introduced a new parameter corresponding to
rainbow connection number which is defined on vertex-colored graphs. A vertex-
colored graph G is rainbow vertex-connected if any two vertices are connected by a
path whose internal vertices have distinct colors. A vertex-coloring under which G
is rainbow vertex-connected is called a rainbow vertex-coloring. The rainbow ver-
tex-connection number of a connected graph G, denoted by r vc(G), is the smallest
number of colors that are needed in order to make G rainbow vertex-connected. The
minimum rainbow vertex-coloring is defined similarly. Obviously, we always have
r vc(G) ≤ n − 2 (except for the trivial graph), and r vc(G) = 0 if and only if G is
a clique. Also clearly, r vc(G) ≥ diam(G) − 1 with equality if the diameter of G is
1 or 2.
Note that r vc(G) may be much smaller than r c(G) for some graph G. For example,
r vc(K 1,n−1 ) = 1 while r c(K 1,n−1 ) = n − 1. r vc(G) may also be much larger than
r c(G) for some graph G. For example, take n vertex-disjoint triangles and, by desig-
nating a vertex from each of them, add a complete graph on the designated vertices.
This graph has n cut-vertices and hence r vc(G) ≥ n. In fact, r vc(G) = n by coloring
only the cut-vertices with distinct colors. On the other hand, it is not difficult to see
that r c(G) ≤ 4. Just color the edges of the K n with, say, color 1, and color the edges
of each triangle with the colors 2, 3, 4.
For more details on various rainbow connections, we refer the reader to our new
book [74].
In Sect. 2, we will focus on the rainbow connection number and strong rainbow
connection number. We collect many upper bounds for these two parameters. From
Sects. 3 to 5, we survey on the other three parameters: rainbow k-connectivity, k-rain-
bow index, rainbow vertex-connection number, respectively. In the last section, we
sum up the results on algorithms and computational complexity.

1.2 Terminology and Notation

All graphs considered in this survey are finite, simple and undirected. We follow the
notation and terminology of [9] for all those not defined here. We use V (G) and E(G)
to denote the set of vertices and the set of edges of G, respectively. For any subset
X of V (G), let G[X ] denote the subgraph induced by X ; similarly, for any subset F
of E(G), let G[F] denote the subgraph
 induced by F. Let G be a set of graphs, then
V (G) = G∈G V (G), E(G) = G∈G E(G). We define a clique in a graph G to be a
complete subgraph of G, and a maximal clique is a clique that is not contained in any
larger clique of G. For a set S, |S| denotes the cardinality of S. An edge in a connected
graph is called a bridge, if its removal disconnects the graph. A graph with no bridges
is called a bridgeless graph. A vertex is called pendant if its degree is 1. We call a path
of G with length k a pendant k-length path if one of its end vertex has degree 1 and
all inner vertices have degree 2 in G. By definition, a pendant k-length path contains
a pendant -length path (1 ≤  ≤ k). A pendant 1-length path is a pendant edge. We
denote Cn a cycle with n vertices. For n ≥ 3, the wheel Wn is constructed by joining

123
Graphs and Combinatorics (2013) 29:1–38 5

a new vertex to every vertex of Cn . We use g(G) to denote the girth of G, that is, the
length of a shortest cycle of G.
Let G be a connected graph. Recall that the distance between two vertices u and
v in G, denoted by d(u, v), is the length of a shortest path between them in G. The
eccentricity of a vertex v is ecc(v) := max x∈V (G) d(v, x). The diameter of G is
diam(G) := max x∈V (G) ecc(x). The radius of G is rad(G) := min x∈V (G) ecc(x).
Distance between a vertex v and a set S ⊆ V (G) is d(v, S) := min x∈S d(v, x). The
k-step open neighbourhood of a set S ⊆ V (G) is N k (S) := {x ∈ V (G)|d(x, S) = k},
k ∈ {0, 1, 2, . . .}. A set D ⊆ V (G) is called a k-step dominating set of G, if every
vertex in G is at a distance at most k from D. Further, if D induces a connected
subgraph of G, it is called a connected k-step dominating set of G. The cardinality
of a minimum connected k-step dominating set in G is called its connected k-step
domination number, denoted by γck (G). We call a two-step dominating set k-strong
[53] if every vertex that is not dominated by it has at least k neighbors that are dom-
inated by it. Chandran et al. [13] made two new definitions which will be useful in
the sequel. A dominating set D in a graph G is called a two-way dominating set if
every pendant vertex of G is included in D. In addition, if G[D] is connected, we call
D a connected two-way dominating set. A (connected) two-step dominating set D of
vertices in a graph G is called a (connected) two-way two-step dominating set if (i)
every pendant vertex of G is included in D and (ii) every vertex in N 2 (D) has at least
two neighbours in N 1 (D). Note that if δ(G) ≥ 2, then every (connected) dominating
set in G is a (connected) two-way dominating set.
A subgraph H of a graph G is called isometric if distance between any pair of
vertices in H is the same as their distance in G. The size of a largest isometric cycle
in G is denoted by iso(G). A graph is called chordal if it contains no induced cycles
of length greater than 3. The chordality of a graph G is the length of a largest induced
cycle in G. Note that every isometric cycle is induced and hence iso(G) is at most
the chordality of G. For k ≤ α(G), we use σk (G) to denote the minimum degree sum
that is taken over all independent sets of k vertices of G, where α(G) is the number
of elements of an maximum independent set of G.

2 (Strong) Rainbow Connection Number

2.1 Basic Results

Chartrand et al. [14] did some basic research on the (strong) rainbow connection num-
bers of graphs. They determined the precise (strong) rainbow connection numbers of
several special graph classes including trees, complete graphs, cycles, wheel graphs,
complete bipartite graphs and complete multipartite graphs.
Proposition 2.1 [14] Let G be a nontrivial connected graph of size m. Then
(a) r c(G) = 1 if and only if G is complete, sr c(G) = 1 if and only if G is complete;
(b) r c(G) = 2 if and only if sr c(G) = 2;
(c) r c(G) = m if and only if G is a tree, sr c(G) = m if and only if G is a tree.
Proposition 2.2 [14] For each integer n ≥ 4, r c(Cn ) = sr c(Cn ) =  n2 .

123
6 Graphs and Combinatorics (2013) 29:1–38

Proposition 2.3 [14] For each integer n ≥ 3, we have

⎧
⎨ 1 if n = 3,
r c(Wn ) = 2 if 4 ≤ n ≤ 6,
⎩
3 if n ≥ 7.

and sr c(Wn ) =  n3 .
√
Proposition 2.4 [14] For integers s and t with 2 ≤ s ≤ √ t, r c(K s,t ) = min{ s t, 4},
and for integers s and t with 1 ≤ s ≤ t, sr c(K s,t ) =  s t.
Proposition 2.5 [14] Let G = K n 1 ,n 2 ,...,n k be a complete k-partite graph, where k ≥ 3
k−1
and n 1 ≤ n 2 ≤ · · · ≤ n k such that s = i=1 n i and t = n k . Then
⎧
⎨1 if n k = 1,
r c(G) = 2 √ if n k ≥ 2 and s > t,
⎩
min{ s t, 3} if s ≤ t.

and
⎧
⎨1 if n k = 1,
sr c(G) = 2√ if n k ≥ 2 and s > t,
⎩ s
 t if s ≤ t.

By Proposition 2.1, it follows that for every positive integer a and for every tree
T of size a, r c(T ) = sr c(T ) = a. Furthermore, for a ∈ {1, 2}, r c(G) = a if and
only if sr c(G) = a. If a = 3, b ≥ 4, then by Proposition 2.3, r c(W3b ) = 3 and
sr c(W3b ) = b. For a ≥ 4, we have the following.
Theorem 2.6 [14] Let a and b be positive integers with a ≥ 4 and b ≥ 5a−6
3 . Then
there exists a connected graph G such that r c(G) = a and sr c(G) = b.
Then, combining Propositions 2.1 and 2.3 with Theorem 2.6, they got the following
result.
Corollary 2.7 [14] Let a and b be positive integers. If a = b or 3 ≤ a < b and
b ≥ 5a−6
3 , then there exists a connected graph G such that r c(G) = a and sr c(G) = b.

Finally, they thought the question that whether the condition b ≥ 5a−6
3 can be
deleted and raised the following conjecture:
Conjecture 2.8 [14] Let a and b be positive integers. Then there exists a connected
graph G such that r c(G) = a and sr c(G) = b if and only if a = b ∈ {1, 2} or
3 ≤ a ≤ b.
Chen and Li [23] gave an affirmative solution to this conjecture by displaying a
class of graphs with rainbow connection number a and strong rainbow connection
number b.
From the above several propositions, we know r c(G) = sr c(G) holds for some
special graph classes. The following problem appears to be difficult:

123
Graphs and Combinatorics (2013) 29:1–38 7

Fig. 1 A counterexample to
Conjecture 2.10

Problem 2.9 Characterize those graphs G for which r c(G) = sr c(G), or, give some
sufficient conditions to guarantee that r c(G) = sr c(G).

Recall the fact that if H is a connected spanning subgraph of a nontrivial (con-

nected) graph G, then r c(G) ≤ r c(H ). This fact is very useful to bounding the value
of r c(G) by giving bounds for its connected spanning subgraphs. We have noted that
if, in addition, diam(H ) = 2, then sr c(G) ≤ sr c(H ). The authors of [14] naturally
raised the following conjecture:

Conjecture 2.10 [14] If H is a connected spanning subgraph of a nontrivial (con-

nected) graph G, then sr c(G) ≤ sr c(H ).

Recently, this conjecture was disproved by Chakraborty et al. [12]. They showed
the following example: see Fig. 1, where G is obtained from H by adding the edge
e = uv, then H is a connected spanning subgraph of G. It is easy to show that there
is a strong rainbow coloring of H which uses six colors, but the graph G requires at
least seven colors to ensure its strong rainbow connection.
Suppose that G contains two bridges e = uv and f = x y. Then G − e − f
contains three components G i (1 ≤ i ≤ 3), where two of these components contain
one of u, v, x and y and the third component contains two of these four vertices, say
u ∈ V (G 1 ), x ∈ V (G 2 ) and v, y ∈ V (G 3 ). If S is a set of k vertices containing u and
x, then every tree whose vertex set contains S must also contain the edges e and f .
This gives us a necessary condition for an edge-colored graph to be k-rainbow colored.

Observation 2.11 [18] Let G be a connected graph of order n containing two bridges
e and f . For each integer k with 2 ≤ k ≤ n, every k-rainbow coloring of G must
assign distinct colors to e and f .

From Observation 2.11, we know that if G is rainbow connected under some edge-
coloring, then any two bridges obtain distinct colors.

2.2 Upper Bounds for the Rainbow Connection Number

While it appears unlikely that one can determine the rainbow connection number of
an arbitrary graph (actually, it is NP-hard, see Sect. 6), we will provide some useful
bounds for this parameter, especially sharp upper bounds.

123
8 Graphs and Combinatorics (2013) 29:1–38

2.2.1 In Terms of Minimum Degree

Caro et al. [11] investigated the extremal graph-theoretic behavior of the rainbow con-
nection number. Motivated by the fact that there are graphs with minimum degree 2
and with r c(G) = n − 3 (just take two vertex-disjoint triangles and connect them
by a path of length n − 5), it is interesting to study the rainbow connection number
of graphs with minimum degree at least 3. They asked the following question: Is it
true that minimum degree at least 3 guarantees that r c(G) ≤ αn where α < 1 is
independent of n? This turns out to be true, and they proved:

Theorem 2.12 [11] If G is a connected graph with n vertices and δ(G) ≥ 3, then
r c(G) < 56 n.

In the proof of Theorem 2.12, they first gave an upper bound for the rainbow con-
nection number of 2-connected graphs (see Theorem 2.24), then from it, they next
derived an upper bound for the rainbow connection number of connected bridgeless
graphs (see Theorem 2.27).
The constant 5/6 appearing in Theorem 2.12 is not optimal, but it probably cannot
be replaced with a constant smaller than 43 , since there are 3-regular connected graphs
with r c(G) = diam(G) = 3n−10 4 , and one such graph can be constructed as follows
[80]: Take two vertex disjoint copies of the graph K 5 − P3 and label the two vertices
of degree 2 with w1 and w2k+2 , where k ≥ 1 is an integer. Next join w1 and w2k+2
by a path of length 2k + 1 and label the vertices with w1 , w2 , . . . , w2k+2 . Now for
1 ≤ i ≤ k every edge w2i w2i+1 is replaced by a K 4 −e and we identify the two vertices
of degree 2 in K 4 − e with w2i and w2i+1 . The resulting graph G 4k+10 is 3-regular,
has order n = 4k + 10 and r c(G 4k+10 ) = diam(G 4k+10 ) = 3k + 5 = 3n−10 4 . Then
Caro et al. conjectured:

Conjecture 2.13 [11] If G is a connected graph with n vertices and δ(G) ≥ 3, then
r c(G) < 43 n.

Schiermeyer proved the conjecture in [80] by showing the following result:

Theorem 2.14 [80] If G is a connected graph with n vertices and δ(G) ≥ 3, then
r c(G) < 3n−1
4 .

For 2-connected graphs, Theorem 2.14 is true by Theorem 2.24. Hence it remains to
prove it for graphs with connectivity 1. Schiermeyer extended the concept of rainbow
connection number as follows: Additionally we require that any two edges of G have
different colors whenever they belong to different blocks of G. The corresponding
rainbow connection number will be denoted by r c∗ (G). Then they derived Theorem
2.14 by first proving the following result: let G be a connected graph with n vertices,
connectivity 1, and δ ≥ 3, then r c∗ (G) ≤ 3n−104 .
Not surprisingly, as the minimum degree increases, the graph would become more
dense and therefore the rainbow connection number would decrease. Specifically,
Caro et al. also proved the following upper bounds in term of minimum degree.

123
Graphs and Combinatorics (2013) 29:1–38 9

Theorem 2.15 [11] If G is a connected graph with n vertices and minimum degree δ,
then
 
ln δ 4 ln δ + 3
r c(G) ≤ min n (1 + oδ (1)), n .
δ δ

In the proof, they used the concept of a connected two-dominating set (A set of
vertices S of G is called a connected two-dominating set if S induces a connected
subgraph of G and, furthermore, each vertex outside of S has at least two neighbours
in S) and the probabilistic method. They showed that in any case it cannot be improved
below δ+13n
− δ+7
δ+1 as they constructed a connected n-vertex graph with minimum degree
δ and this diameter: Take m copies of K δ+1 , denoted by X 1 , . . . , X m and label the
vertices of X i with xi,1 , . . . , xi,δ+1 . Take two copies of K δ+2 , denoted by X 0 , X m+1
and similarly label their vertices. Now, connect xi,2 with xi+1,1 for i = 0, . . . , m with
an edge, and delete the edges (xi,1 , xi,2 ) for i = 0, . . . , m + 1. The obtained graph
has n = (m + 2)(δ + 1) + 2 vertices, and minimum degree δ (and maximum degree
δ + 1). It is straightforward to verify that a shortest path from x0,1 to xm+1,2 has length
3m + 5 = δ+1 3n
− δ+7
δ+1 .
This, naturally, raised the open problem of determining the true behavior of r c(G)
as a function of δ.
Chakraborty et al. [12] proved that any connected n-vertex graph with minimum
degree (n) has a bounded rainbow connection.
Theorem 2.16 [12] For every > 0 there is a constant C = C( ) such that if G is a
connected graph with n vertices and minimum degree at least n, then r c(G) ≤ C.
The proof of Theorem 2.16 is based upon a modified degree-form version of the
Szemerédi Regularity Lemma (see [52] for a good survey on the Regularity Lemma)
that they proved.
The above lower bound construction suggests that the logarithmic factor in their
upper bound may not be necessary and that, in fact r c(G) ≤ Cn/δ where C is a
universal constant. If true, notice that for graphs with a linear minimum degree n,
this implies that r c(G) is at most C/ . However, Theorem 2.16 does not even guaran-
tee the weaker claim that r c(G) is a constant. The constant C = C( ) they obtained
is a tower f unction in 1/ and in particular extremely far from being reciprocal to
1/ .
Finally, Krivelevich and Yuster in [53] determined the behavior of r c(G) as a
function of δ(G) and resolved the above-mentioned open problem.
Theorem 2.17 [53] A connected graph G with n vertices has r c(G) < 20n
δ(G) .

The proof of Theorem 2.17 uses the concept of a connected two-step dominating set.
Krivelevich and Yuster first proved that for a connected graph H with minimum degree
n
k and n vertices, there exists a two-step dominating set S whose size is at most k+1 and
 
there is a connected two-step dominating set S containing S with |S | ≤ 5|S|−4. They
found two edge-disjoint spanning subgraphs in a graph G with minimum degree at
least  δ−1
2 . Then they derived a rainbow coloring for G by giving a rainbow coloring
to each subgraphs according to its connected two-step dominating set.

123
10 Graphs and Combinatorics (2013) 29:1–38

The authors noted that the constant 20 obtained by their proof is not optimal and
can be slightly improved with additional effort. However, from the example below
Theorem 2.15, one cannot expect to replace C by a constant smaller than 3.
Motivated by the results of Theorems 2.14, 2.15 and 2.17, Schiermeyer raised the
following open problem in [80].

Problem 2.18 [80] For every k ≥ 2 find a minimum constant ck with 0 < ck ≤ 1
such that r c(G) ≤ ck n for all graphs G with minimum degree δ(G) ≥ k. Is it true that
ck = k+1
3
for all k ≥ 2?

This is true for k = 2, 3 as shown before (c2 = 1 and c3 = 43 ). Recently, Chandran

et al. [13] nearly settled the above problem. They used the concept of a connected
two-way two-step dominating set in the argument and they first proved the following
result.

Theorem 2.19 [13] If D is a connected two-way two-step dominating set in a graph

G, then r c(G) ≤ r c(G[D]) + 6.

Furthermore, they gave a nearly sharp bound for the size of D by showing that every
connected graph G of order n ≥ 4 and minimum degree δ has a connected two-way
3n
two-step dominating set D of size at most δ+1 − 2; moreover, for every δ ≥ 2, there
exist infinitely many connected graphs G such that γc2 (G) ≥ 3(n−2)
δ+1 − 4. Then the
following result is easy.

Theorem 2.20 [13] For every connected graph G of order n and minimum degree δ,

3n
r c(G) ≤ + 3.
δ+1

Moreover, for every δ ≥ 2, there exist infinitely many connected graphs G such that
r c(G) ≥ 3(n−2)
δ+1 − 1.

Theorem 2.20 answers Problem 2.18 in the affirmative but up to an additive constant
of 3. Moreover, this bound is seen to be tight up to additive factors by the construction
mentioned in [11] (see the example below Theorem 2.15) and [33]. Therefore, for
graphs with linear minimum degree n, the rainbow connection number is bounded
by a constant. It is still interesting to work out a sharp upper bound, i.e., to determine
the constant term in the above upper bound.
Recently, Dong and Li [26] derived an upper bound on the rainbow connection
numbers of graphs under given minimum degree sum condition σ2 . Recall that for a
graph G, σ2 (G) = min{d(u) + d(v)|u, v are independent in G}. Clearly, the degree
sum condition σ2 is weaker than the minimum degree condition.

Theorem 2.21 [26] For a connected graph G of order n, r c(G) ≤ 6n

σ2 +2 + 8.

Similar to the method of Theorem 2.20, they derived that every connected graph G
of order n with at most one pendant vertex has a connected two-way two-step dom-
inating set D of size at most σ26n+2 + 3. Then by using Theorem 2.19, they got the

123
Graphs and Combinatorics (2013) 29:1–38 11

theorem. From the example below Theorem 2.15, we know that their bounds are seen
to be tight up to additive factors. Using a method similar to that of Theorem 2.20,
Dong and Li [28] further got the following result for a general k:

Theorem 2.22 [28] If G is a connected graph of order with k independent vertices,

then r c(G) ≤ σ3kn
k +k
+ 6k − 3.

They also gave examples to show that the bound in terms of the minimum degree
sum is much better than the one in terms of the minimum degree, i.e., when δ is very
small but σk is very large, the bound is r c(G) < 9k − 3, which means that r c(G) can
be bounded above by a constant from the bound in terms of the minimum degree sum,
but linear in n from the bound in terms of the minimum degree.

2.2.2 In Terms of Connectivity

With respect to the the relation between r c(G) and the connectivity κ(G), mentioned
in [80], Broersma asked a question at the IWOCA workshop:

Problem 2.23 [80] What happens with the value r c(G) for graphs with higher con-
nectivity?

For κ(G) = 1, Theorem 2.14 means that if G is a graph of order n, connectivity

κ(G) = 1 and δ ≥ 3. Then r c(G) ≤ 3n−1 4 . For κ(G) = 2, in the proof of Theorem
2.12, as we mentioned above, Caro et al. derived the following:

Theorem 2.24 [11] If G is a 2-connected graph with n vertices then r c(G) ≤ 2n

3 .

That is, if G is a graph of order n, connectivity κ(G) = 2. Then r c(G) ≤ 2n

3 .
From Theorem 2.20, we can easily obtain an upper bound of the rainbow connection
number according to the connectivity:

3n 3n
r c(G) ≤ +3≤ + 3.
δ+1 κ +1

Therefore, for κ(G) = 3, r c(G) ≤ 3n 4 + 3; for κ(G) = 4, r c(G) ≤ 5 + 3. Motivated

3n

by the results in [11], Li and Shi [66] improved this bound by using the Fan Lemma.
3(n+1)
Theorem 2.25 [66] If G is a 3-connected graph with n vertices, then r c(G) ≤ 5 .

However, for general connectivity, there is no upper bound which is superior to

3n
κ+1 + 3. Recently, Li and Liu got a best possible upper bound in [60] for 2-connected
graphs.

Theorem 2.26 [60,63] Let G be a 2-connected graph of order n (n ≥ 3). Then

r c(G) ≤  n2  and the upper bound is tight for n ≥ 4.

Ekstein et al. [31] rediscovered this result. One could think of generalizing Theo-
rem 2.26 to the case of higher connectivity. Li and Liu [60,63] raised the following
stronger conjecture that for every κ ≥ 1, if G is a κ-connected graph of order n, then

123
12 Graphs and Combinatorics (2013) 29:1–38

r c(G) ≤  κn . Unfortunately, Ekstein et al. in [31] found examples showing that for
every κ there are κ-connected graphs G of order n with r c(G) ≥ n−2 κ + 1, which is
slightly bigger than  κn  when κ (≥ 3) divides n.
The following result is an important ingredient in the proof of Theorem 2.12 in
[11].
Theorem 2.27 [11] If G is a connected bridgeless graph with n vertices, then r c(G) ≤
5 − 1.
4n

From Theorem 2.20, we can also easily obtain an upper bound of the rainbow
connection number according to the edge-connectivity λ:

3n 3n
r c(G) ≤ +3≤ + 3.
δ+1 λ+1
In [63], the authors showed that the above bound is tight up to additive factors by
constructing a family of λ-edge-connected graphs for infinitely many values of λ and
order n with diameter d = λ+1 3n
− 3. Since diameter is a lower bound on the rainbow
connection number, the construction suffices for our purpose. Let d ≥ 1 be a natural
number, and λ a natural number such that λ + 1 is a multiple of 3 and λ ≥ 8. Set
k := λ+13 , and set V (G) the disjoint union of V0 , V1 , . . . , Vd , where |Vi | is 2k for
i = 0 and i = d, and k for 1 ≤ i < d. Two distinct vertices u ∈ Vi and v ∈ V j are
adjacent in G if and only if |i − j| ≤ 1. It is easy to see that the diameter of G is d,
n = |V (G)| = k(d + 3) and hence d = nk − 3 = λ+1 3n
− 3. By considering all pairs
of vertices, it can be seen that G is λ-edge-connected.

2.2.3 In Terms of Radius

Note that all the above upper bounds are determined by n and other parameters such as
(edge)-connectivity, minimum degree. The diameter of a graph, and hence its radius,
are obvious lower bounds for rainbow connection number. Hence it is interesting to
see if there is an upper bound which is a function of the radius r or diameter alone.
Such upper bounds were shown for some special graph classes in [13] which we will
introduce in the sequel. But, for a general graph, the rainbow connection number can-
not be bounded above by a function of r alone. For instance, the star K 1,n has a radius 1
but rainbow connection number n. Still, the question of whether such an upper bound
exists for graphs with higher connectivity remains. Basavaraju et al. [5] answered this
question in the affirmative. The key of their argument is the following lemma, and in
the proof of this lemma, we can obtain a connected (k − 1)-step dominating set from
a connected k-step dominating set.
Lemma 2.28 [5] If G is a bridgeless graph, then for every connected k-step dom-
inating set D k of G, k ≥ 1, there exists a connected (k − 1)-step dominating set
D k−1 ⊃ D k such that

r c(G[D k−1 ]) ≤ r c(G[D k ]) + min{2k + 1, ζ },

where ζ = iso(G).

123
Graphs and Combinatorics (2013) 29:1–38 13

Given a graph G and a set D ⊂ V (G), A D-ear is a path P = (x0 , x1 , . . . , x p )

in G such that P ∩ D = {x0 , x p }. P may be a closed path, in which case x0 = x p .
Further, P is called an acceptable D-ear if either P is a shortest D-ear containing
(x0 , x1 ) or P is a shortest D-ear containing (x p−1 , x p ). Let A = {a1 , a2 , . . .} and
B = {b1 , b2 , . . .} be two pools of colors, none of which are used to color G[D k ].
A D k -ear P = (x0 , x1 , . . . , x p ) will be called evenlycolor ed if its edges are col-
ored a1 , a2 , . . . , a p  , b p , . . . , b2 , b1 in that order. Basavaraju, Chandran, Rajen-
2 2
draprasad and Ramaswamy proved this lemma by constructing a sequence of sets
D k = D0 ⊂ D1 ⊂ · · · ⊂ Dt = D k−1 and coloring the new edges in every induced
graph G[Di ] such that the following property is maintained for all 0 ≤ i ≤ t: every
x ∈ Di \D k lies in an evenly colored acceptable D k -ear in G[Di ].
The following theorem can be derived from Lemma 2.28 easily.

Theorem 2.29 [5] For every connected bridgeless graph G,

r
r c(G) ≤ min{2i + 1, ζ } ≤ r ζ,
i=1

where r is the radius of G.

Let η(G) be the smallest integer such that every edge of G belongs to a cycle of
length at most η(G). It is not hard to show that η(G) ≤ iso(G) = ζ for any graph G.
Huang et al. [46] generalized Theorem
 2.29 in the following result: for every bridgeless
graph G with radius r , r c(G) ≤ ri=1 min{2i + 1, η(G)} ≤ r η(G). They also gave
upper bounds of the rainbow connection numbers for plane graphs, edge-transitive
graphs and bipartite graphs. Theorem 2.29 has the following two corollaries.

Corollary 2.30 [5] For every connected bridgeless graph G with radius r ,

r c(G) ≤ r (r + 2).

Moreover, for every integer r ≥ 1, there exists a bridgeless graph with radius r and
r c(G) = r (r + 2).

Corollary 2.31 [5] For every connected bridgeless graph G with radius r and chor-
dality k,

r
r c(G) ≤ min{2i + 1, k} ≤ r k.
i=1

Moreover, for every two integers r ≥ 1 and 3 ≤ k ≤ 2r + 1,there exists a bridgeless

graph G with radius r and chordality k such that r c(G) = ri=1 min{2i + 1, k}.

Corollary 2.30 answered the above question in the affirmative, the bound is sharp
and is a function of the radius r alone. Basavaraju et al. also demonstrated that the
bound cannot be improved even if we assume stronger connectivity by constructing

123
14 Graphs and Combinatorics (2013) 29:1–38

a κ-connected graph of radius r whose rainbow connectionnumber is r (r + 2) for

−i+1
any two given integers κ, r ≥ 1: Let s(0) := 0, s(i) := 2 rj=r j for 1 ≤ i ≤ r
and t := s(r ) = r (r + 1). Let V be the disjoint union of V0 , V1 , . . . , Vt , where
Vi = {xi,0 , xi,1 , . . . , xi,κ−1 } for 0 ≤ i ≤ t − 1 and Vt = {xt,0 }. Construct a graph
X r,κ on V by adding the following edges. E(X ) = {{xi, j , xi  , j  } : |i − i  | ≤ 1} ∪
{{xs(i),0 , xs(i+1),0 } : 0 ≤ i ≤ r − 1}.
Corollary 2.31 generalises a result from [13] that the rainbow connection number
of any bridgeless chordal graph is at most three times its radius as the chordality of a
chordal graph is three.
Basavaraju et al. showed that for every bridgeless graph G with radius r , r c(G) ≤
r (r + 2), as shown in Corollary 2.30. As one can see, they did not consider graphs
with bridges. Since bridges are important objects in a rainbow coloring (any two dif-
ferent bridges must receive distinct colors), Dong and Li [27] considered graphs with
bridges. They bounded r c(G) above by the number of bridges and radius of a graph G.

Theorem 2.32 [27] Let G be a connected graph with radius r and center vertex u. If we
let Dr = {u}, then G has r − 1 connected dominating sets Dr −1 , Dr −2 ,r . . . , D such
1

that D ⊂ D
r r −1 ⊂D r −2 ⊂ · · · ⊂ D ⊂ D = V (G) and r c(G) ≤ i=1 max{2i +
1 0

1, bi }, where bi is the number of bridges

r in E[D i , N (D i )] for 1 ≤ i ≤ r , and the
number of bridges in G is equal to i=1 bi .

Note that if bi ≤ 2i + 1 for all 1 ≤ i ≤ r , then r c(G) ≤ ri=1 (2i + 1) = r (r + 2),
which is independent of the number of bridges in G, whereas if bi > 2i + 1 for all
1 ≤ i ≤ r , then r c(G) = ri=1 bi, the number of bridges of G. So, this generalizes
Corollary 2.30.

2.2.4 Miscellaneous Bounds

Caro et al. [11] also derived a result which gives an upper bound for rainbow con-
nection number according to the order and the number of vertex-disjoint cycles. Here
χ  (G) is the chromatic index of G.

Theorem 2.33 [11] Suppose G is a connected graph with n vertices, and assume
that there is a set of vertex-disjoint cycles that cover all but s vertices of G. Then
r c(G) < 3n/4 + s/4 − 1/2. In particular:
(i). If G has a 2-factor then r c(G) < 3n/4.
(ii). If G is k-regular and k is even then r c(G) < 3n/4.
(iii). If G is k-regular and χ  (G) = k then r c(G) < 3n/4.

Another approach for achieving upper bounds is based on the size (number of
edges) m of the graph. Those type of sufficient conditions are known as Erdős-Gallai
type results. Research on the following Erdős-Gallai type problem has been started in
[50].

Problem 2.34 [50] For every k with 1 ≤ k ≤ n − 1, compute and minimize the
function f (n, k) with the following property: If |E(G)| ≥ f (n, k), then r c(G) ≤ k.

123
Graphs and Combinatorics (2013) 29:1–38 15

Kemnitz and Schiermeyer [50] investigated the lower bound for f (n, k). Kemnitz
and Schiermeyer [50], Li et al. [59] and Kemnitz et al. [51] showed the following
result.

n−k+1 2.35 [50,51,59] Let k and n be natural numbers with k ≤ n. Then f (n, k) ≥
Theorem
2 + (k − 1), where equality holds for k = 1, 2, 3, 4, n − 6, n − 5, n − 4, n −
3, n − 2, n − 1.

Li and Sun [73] provided a new approach to investigate the rainbow connection
number of a graph G according to some constraints to its complement graph G. They
gave two sufficient conditions to guarantee that r c(G) is bounded by a constant. By
using the fact that r c(G) ≤ r c(H ) where H is a connected spanning subgraph of
a connected graph G, and the structure of its complement graph as well as Proposi-
tions 2.4 and 2.5, they derived the following result.

Theorem 2.36 [73] If G is a connected graph G for which G does not belong to
the following two cases: (i) diam(G) = 2, 3, (ii)G contains exactly two connected
components and one of them is trivial, then r c(G) ≤ 4. Furthermore, this bound is
best possible.

For the remaining cases, r c(G) can be very large as discussed in [73]. So they add a
constraint. If G is triangle-free, then G is claw-free. They derived the following result.
In their argument, Theorem 2.44 is useful.

Theorem 2.37 [73] For a connected graph G, if G is triangle-free, then r c(G) ≤ 6.

Chen et al. [20] investigated Nordhaus-Gaddum-type results. A Nordhaus-Gad-

dum-type result is a (sharp) lower or upper bound on the sum or product of the values
of a parameter for a graph and its complement. The name “Nordhaus-Gaddum-type”
is so given because it is Nordhaus and Gaddum [76] who first established the following
type of inequalities for the chromatic number of graphs in 1956.

Theorem 2.38 [20] Let G and G be connected with n ≥ 4, then

4 ≤ r c(G) + r c(G) ≤ n + 2.

Furthermore, the upper bound is sharp for n ≥ 4 and the low bound is sharp for
n ≥ 8.

They also proved that r c(G) + r c(G) ≥ 6 for n = 4, 5; and r c(G) + r c(G) ≥ 5
for n = 6, 7 and these bounds are best possible.

2.3 Rainbow Connection Numbers for Some Graph Classes

Some graph classes, such as line graphs, have many special properties, and by these
properties we can get some interesting results on their rainbow connection numbers in
terms of some graph parameters. For example, in [11], Caro et al. derived Theorem 2.24

123
16 Graphs and Combinatorics (2013) 29:1–38

Fig. 2 A clique-forest-structure
with size 6 and 2 components

according to the ear-decomposition of a 2-connected graph. In this subsection,

we will introduce some results on rainbow connection numbers of line graphs,
etc.
Li and Sun [67,68] studied the rainbow connection numbers of line graphs in terms
of particular properties of line graphs shown in [44] and [45]. They gave two sharp
upper bounds for the rainbow connection number of a line graph and one sharp upper
bound for the rainbow connection number of an iterated line graph.
Recall that the line graph L(G) of a graph G is the graph whose vertex set is
V (L(G)) = E(G) and two vertices e1 , e2 of L(G) are adjacent if and only if these
edges are adjacent in G. The iterated line graph of a graph G, denoted by L 2 (G), is
the line graph of the graph L(G). More generally, the k-iterated line graph L k (G)
is the line graph of L k−1 (G) (k ≥ 2). We write L 1 (G) for L(G). We also need the
following new terminology.
For a connected graph G, we call G a clique-tree-structure, if it satisfies the follow-
ing condition: each block is a maximal clique. We call a graph H a clique-forest-struc-
ture, if H is a disjoint union of some clique-tree-structures, that is, each component of
a clique-forest-structure is a clique-tree-structure. By the above condition, we know
that any two maximal cliques of G have at most one common vertex. Furthermore,
G is formed by its maximal cliques. The si ze of a clique-tree(forest)-structure is the
number of its maximal cliques. An example of clique-forest-structure is shown in
Fig. 2.
If each block of a clique-tree-structure is a triangle, we call it a triangle-tree-struc-
ture. Let  be the size of a triangle-tree-structure. Then, by definition, it is easy to
show that there are 2 + 1 vertices in it. Similarly, we can give the definition of a
triangle-forest-structure and there are 2 + c vertices in a triangle-forest-structure
with size  and c components. We denote n 2 the number of inner vertices (degrees at
least 2) of a graph.

Theorem 2.39 [68] For any set T of t edge-disjoint triangles of a connected graph
G, if the subgraph induced by the edge set E(T ) is a triangle-forest-structure, then

r c(L(G)) ≤ n 2 − t.

Moreover, the bound is sharp.

123
Graphs and Combinatorics (2013) 29:1–38 17

Theorem 2.40 [68] If G is a connected graph, T is a set of t edge-disjoint triangles

that cover all but n 2 inner vertices of G and c is the number of components of the
subgraph G[E(T )], then

r c(L(G)) ≤ t + n 2 + c.

Moreover, the bound is sharp.

Theorem 2.41 [68] Let G be a connected graph with m edges and m 1 pendant 2-
length paths. Then

r c(L 2 (G)) ≤ m − m 1 .

The equality holds if and only if G is a path of length at least 3.

In the proofs of the above three theorems, Li and Sun used the particular structure of
line graphs and the observation: If G is a connected graph and {E i }i∈[t] is
a partition of
t
the edge set of G into connected subgraphs G i = G[E i ], then r c(G) ≤ i=1 r c(G i )
(see [67]). The above three theorems give upper bounds for rainbow connection num-
ber of L k (G)(k = 1, 2) according to some parameters of G. One may consider the
relation between r c(G) and r c(L(G)).

Problem 2.42 Determine the relationship between r c(G) and r c(L(G)), is there an
upper bound for one of these parameters in terms of the other?

One also can consider the rainbow connection number of the general iterated line
graph L k (G) when k is sufficiently large.

Problem 2.43 Consider the value of r c(L k (G)) as k → ∞. Is it bounded by a con-

stant or does it convergence to a function of some graph parameters, such as the order
n of G?

For Problem 2.43, we know if G is a cycle Cn (n ≥ 4), then L k (G) = G, so

r c(L k (G)) =  n2 . But for many graphs, we know, as k grows, L k (G) will become
more dense, and r c(L k (G)) may decrease.
An intersection graph of a family of sets F, is a graph whose vertices can be mapped
to the sets in F such that there is an edge between two vertices in the graph if and
only if the corresponding two sets in F have a non-empty intersection. An interval
graph is an intersection graph of intervals on the real line. A unit interval graph is
an intersection graph of unit length intervals on the real line. A circular arc graph is
an intersection graph of arcs on a circle. An independant triple of vertices x, y, z in
a graph G is an asteroidal triple (AT), if between every pair of vertices in the triple,
there is a path that does not contain any neighbour of the third. A graph without aster-
oidal triples is called an AT -free graph [24]. A graph G is a threshold graph, if there
exists a weight function w : V (G) → R and a real constant t such that two vertices
u, v ∈ V (G) are adjacent if and only if w(u) + w(v) ≥ t. A bipartite graph G(A, B)
is called a chain graph if the vertices of A can be ordered as A = (a1 , a2 , . . . , ak )

123
18 Graphs and Combinatorics (2013) 29:1–38

such that N (a1 ) ⊆ N (a2 ) ⊆ · · · ⊆ N (ak ) [84]. Chandran et al. [13] investigated the
rainbow connection numbers of these special graph classes. They first showed a result
concerning the connected two-way dominating sets.

Theorem 2.44 [13] If D is a connected two-way dominating set in a graph G, then

r c(G) ≤ r c(G[D]) + 3.

They also proved that every connected graph G of order n and minimum degree δ
2 (D)|)
has a connected two-step dominating set D of size at most 3(n−|N
δ+1 − 2.
From Theorem 2.44, the following result can be derived.

Theorem 2.45 [13] Let G be a connected graph with δ(G) ≥ 2. Then

(i) if G is an interval graph, diam(G) ≤ r c(G) ≤ diam(G) + 1, in particular, if
G is a unit interval graph, then r c(G) = diam(G);
(ii) if G is AT -free, diam(G) ≤ r c(G) ≤ diam(G) + 3;
(iii) if G is a threshold graph, diam(G) ≤ r c(G) ≤ 3;
(iv) if G is a chain graph, diam(G) ≤ r c(G) ≤ 4;
(v) if G is a circular arc graph, diam(G) ≤ r c(G) ≤ diam(G) + 4.
Moreover, there exist threshold graphs and chain graphs with minimum degree at
least 2 and rainbow connection number equal to the corresponding upper bound
above. There exists an AT -free graph G with minimum degree at least 2 and r c(G) =
diam(G) + 2, which is 1 less than the upper bound above.

Recall that the concept of rainbow connection number is of great use in transferring
information of high security in multicomputer networks. Cayley graphs are very good
models that have been used in communication networks. So, it is of significance to
study the rainbow connection numbers of Cayley graphs.
Let  be a group, and let a ∈  be an element. We use a to denote the cyclic
subgroup of  generated by a. The number of elements of a is called the or der of
a, denoted by |a|. A pair of elements a and b in a group commutes if ab = ba. A
group is Abelian if every pair of its elements commutes. A Cayley graph of  with
respect to S is the graph C(, S) with vertex set  in which two vertices x and y are
adjacent if and only if x y −1 ∈ S (or equivalently, yx −1 ∈ S), where S ⊆  \ {1} is
closed under taking inverse [79].
Li et al. [55] investigated the rainbow connection numbers of Cayley graphs on
Abelian groups and got the following results.

Theorem 2.46 [55] Given an Abelian group  and an inverse closed set S ⊆  \ {1},
we have the following results:

(i) r c(C(, S)) ≤ min{ a∈S ∗ |a|/2 | S ∗ ⊆ S is a minimal generating set o f }.
(ii) If S is an inverse closed minimal generating set of , then

|a|/2 ≤ r c(C(, S)) ≤ sr c(C(, S)) ≤ |a|/2,
a∈S ∗ a∈S ∗

123
Graphs and Combinatorics (2013) 29:1–38 19

where S ∗ ⊆ S is a minimal generating set of .

Moreover, if every element a ∈ S has an even order, then

r c(C(, S)) = sr c(C(, S)) = |a|/2.
a∈S ∗

They also investigated the rainbow connection numbers of recursive circulants (see
[77] for an introduction to recursive circulants).
Let G be an r -regular graph with n vertices. G is said to be str onglyr egular and
denoted by S RG(v, k, λ, μ) if there are also integers λ and μ such that every two
adjacent vertices have λ common neighbours and every two nonadjacent vertices have
μ common neighbours. Clearly, a strongly regular graph with parameters (v, k, λ, μ)
is connected if and only if μ ≥ 1. Ahadi and Dehghan [1] derived the following result:
For every connected strongly regular graph G, r c(G) ≤ 600. As each strongly regular
graph is a graph with diam(G) = 2, from our next subsection (Theorem 2.55), we
know r c(G) ≤ 5 if G is a strongly regular graph with parameters (v, k, λ, μ), other
than a star [56]. But 5 may not be the optimal upper bound, so one may consider the
following question.
Question 2.47 [1] Determine max{r c(G)|G is an S RG}.
There are other results on some special graph classes. Chartrand et al. [16] investi-
gated the rainbow connection numbers of cages, and in [49], Johns et al. investigated
the rainbow connection numbers of small cubic graphs. The details are omitted.

2.4 Rainbow Connection Numbers for Dense and Sparse Graphs

For any given graph G, we know 1 ≤ r c(G) ≤ sr c(G) ≤ m. Here a graph G is called
a dense graph if its (strong) rainbow connection number is small, especially it is close
to 1; while G is called a sparse graph if its (strong) rainbow connection number is large,
especially it is close to m. By Proposition 2.1, the cases that r c(G) = 1, sr c(G) = 1
and r c(G) = m, sr c(G) = m are clear. So we investigate other cases.

2.4.1 For Dense Graphs

Caro et al. [11] investigated graphs with small rainbow connection numbers and they
gave a sufficient condition that guarantees r c(G) = 2.
Theorem 2.48 [11] Any non-complete graph with δ(G) ≥ n/2+log n has r c(G) = 2.
We know that having diameter 2 is a necessary requirement for having r c(G) = 2,
although certainly not sufficient (e.g., consider a star). Clearly, if δ(G) ≥ n/2 then
diam(G) = 2, but we do not know if this guarantees r c(G) = 2. The above theo-
rem shows that by slightly increasing the minimum degree assumption, r c(G) = 2
follows.
Kemnitz and Schiermeyer [50] gave a sufficient condition to guarantee r c(G) = 2
according to the number of edges m.

123
20 Graphs and Combinatorics (2013) 29:1–38

n−1
Theorem 2.49 [50] Let G be a connected graph of order n and size m. If +1 ≤

 2
m ≤ n2 − 1, then r c(G) = 2.

Let G = G(n, p) denote, as usual [3], the random graph with n vertices and edge
probability p. For a graph property A and for a function p = p(n), we say that G(n, p)
satisfies A almost surely if the probability that G(n, p(n)) satisfies A tends to 1 as
n tends to infinity. We say that a function f (n) is a sharp threshold function for the
property A if there are two positive constants c and C so that G(n, c f (n)) almost
surely does not satisfy A and G(n, p) satisfies A almost surely for all p ≥ C f (n). It
is well known that all monotone graph properties have a sharp threshold function (see
[8,38]). Since having r c(G) ≤ 2 is a monotone graph property (adding edges does
not destroy this property), it has a sharp threshold function. The following theorem
establishes it.
√
Theorem 2.50 [11] p = log n/n is a sharp threshold function for the graph prop-
erty r c(G(n, p)) ≤ 2.

Theorem 2.48 asserts that minimum degree n/2 + log n guarantees r c(G) = 2.
Clearly, minimum degree n/2 − 1 does not, as there are connected graphs with min-
imum degree n/2 − 1 and diameter 3 (just take two vertex-disjoint cliques of order
n/2 each and connect them by a single edge. It is therefore interesting to raise:

Problem 2.51 [11] Determine the minimum degree threshold that guarantees r c(G)
= 2.

By Proposition 2.1, we know that the problem of considering graphs with r c(G) = 2
is equivalent to that of considering graphs with sr c(G) = 2.
A bipartite graph that is not complete has diameter at least 3. A proof similar to
that of Theorem 2.50 gives the following result.

Theorem 2.52 [11] Let c = 1/log(9/7). If G is a non-complete bipartite graph with

n vertices and any two vertices in the same bipartition have at least 2clog n common
neighbors in the other vertex class, then r c(G) = 3.

The following theorem asserts however that having diameter 2 and only logarithmic
minimum degree suffices to guarantee rainbow connection number 3.

Theorem 2.53 [12] If G is an n-vertex graph with diameter 2 and minimum degree
at least 8 log n, then r c(G) ≤ 3.

Since a graph with minimum degree n/2 is connected and has diameter 2, we have as
an immediate result [12]: If G is an n-vertex graph with minimum degree at least n/2,
then r c(G) ≤ 3. We know that any graph G with r c(G) = 2 must have diam(G) = 2,
so graphs with r c(G) = 2 belong to the graph class with diam(G) = 2. By Corollary
2.30, we know that for a bridgeless graph with diam(G) = 2, r c(G) ≤ r (r + 2) ≤ 8.
As r c(G) is at least the number of bridges of G, so it may be very large if the number
of bridges of G is sufficiently large by Observation 2.11. So there is an interesting
problem:

123
Graphs and Combinatorics (2013) 29:1–38 21

Fig. 3 The figure for the four graph classes

Problem 2.54 For any bridgeless graph G with diam(G) = 2, determine the smallest
constant c such that r c(G) ≤ c.

Li et al. [56] showed that c ≤ 5 and they also gave examples for which r c(G) ≤ 4.
However, they could not show that the upper bound 5 is sharp. Dong and Li [29] gave
another proof for the upper bound 5, and moreover, examples are given to show that
the bound is best possible.

Theorem 2.55 [29] If G is a connected bridgeless graph with diameter 2, then

r c(G) ≤ 5. Moreover, the upper bound is sharp.

Li et al. [56] also showed that r c(G) ≤ k + 2 if G is connected with diameter 2 and
k bridges, where k ≥ 1. The bound k + 2 is sharp as there are infinity many graphs
of diameter 2 and k bridges whose rainbow connection numbers attain this bound.
For diameter 3, Li et al. [57] proved that r c(G) ≤ 9 if G is a bridgeless graph with
diameter 3.

2.4.2 For Sparse Graphs

Li and Sun [71,72] investigated graphs with large rainbow connection numbers and
strong rainbow connection numbers, respectively. They derived the two following
results. Note that each path P j in the member of graph class Gi (1 ≤ i ≤ 4) of Fig. 3
may be trivial.

Theorem 2.56 [71] For a connected graph G with m edges, we have r c(G) = m − 1.
Further, r c(G) = m − 2 if and only if G is a 5-cycle or belongs to one of the four
graph classes Gi (1 ≤ i ≤ 4) (see Fig. 3).

We now introduce two graph classes. Let C be the cycle of a unicyclic graph
G, where V (C) = {v1 , . . . , vk } and let TG = {Ti : 1 ≤ i ≤ k} where Ti is
the unique tree containing vertex vi in subgraph G\E(C). We say Ti and T j are
ad jacent (nonad jacent) if vi and v j are adjacent (nonadjacent) in C. Then let
G5 = {G : G is a unicyclic graph, k = 3, TG contains at most two nontrivial
elements},
G6 = {G : G is a unicyclic graph, k = 4, TG contains two nonadjacent trivial
elements and the other two (nonadjacent) elements are paths}.

123
22 Graphs and Combinatorics (2013) 29:1–38

Theorem 2.57 [72] For a connected graph G with m edges, sr c(G) = m −1. Further,
sr c(G) = m − 2 if and only if G is a 5-cycle or belongs to one of the graph classes
Gi (i = 5, 6).
Recall that r c(G) = m (or sr c(G) = m) if and only if G is a tree. Theorems 2.56
and 2.57 show that the graphs with r c(G) ≥ m − 2 (sr c(G) ≥ m − 2). Furthermore,
we raise the following problem.
Problem 2.58 Determine the graphs with r c(G) ≥ m − k (sr c(G) ≥ m − k), where
k is a small integer.
Frieze and Tsourakakis [37] considered the rainbow connection number of sparse
random graphs, and established the following results.

Theorem 2.59 [37] Let G = G(n, p), p = log n+ω n , ω → ∞, ω = o(log n). Also, let
Z 1 be the number of vertices of degree 1 in G. Then, with high probability, r c(G) ∼
max{Z 1 , L}, where L = logloglogn n and A ∼ B denotes A = (1 + o(1))B.

Theorem 2.60 [37] Let G = G(n, r ) be a random r -regular graph where r ≥ 3 is a

fixed integer. Then, with high probability, r c(G) = O(log2 n).

2.5 Rainbow Connection Numbers for Graph Operations

Products of graphs occur naturally in discrete mathematics as tools in combinatorial

constructions; they give rise to important classes of graphs and deep structural prob-
lems. The extensive literature on products that has evolved over the years presents a
wealth of profound and beautiful results [48]. Li and Sun [71] obtained some results on
the rainbow connection numbers of products of graphs, including Cartesian product,
composition (lexicographic product), union of graphs, etc. Actually, we know that the
line graph of a graph is also a graph operation.
We first introduce the rainbow connection number of the Cartesian product of some
graphs. The Cartesian product of graphs G and H is the graph GH whose vertex set
is V (G) × V (H ) and whose edge set is the set of all pairs (u 1 , v1 )(u 2 , v2 ) such that
either u 1 u 2 ∈ E(G) and v1 = v2 , or v1 v2 ∈ E(H ) and u 1 = u 2 . The str ongpr oduct
of G and H is the graph G  H whose vertex set is V (G) × V (H ) and whose edge
set is the set of all pairs (u 1 , v1 )(u 2 , v2 ) such that either u 1 u 2 ∈ E(G) and v1 = v2 ,
or v1 v2 ∈ E(H ) and u 1 = u 2 , or u 1 u 2 ∈ E(G) and v1 v2 ∈ E(H ). By definition, the
graph GH is the spanning subgraph of the graph G  H . By using the definition
and structure of Cartesian product, Li and Sun derived the following.
Theorem 2.61 [71] Let G ∗ = G 1 G 2  · · · G k (k ≥ 2), where each G i (1 ≤ i ≤
k) is connected. Then we have

k
r c(G ∗ ) ≤ r c(G i ).
i=1

Moreover, if diam(G i ) = r c(G i ) for each G i , then the equality holds.

123
Graphs and Combinatorics (2013) 29:1–38 23

We know that there are infinity many graphs with diam(G) = r c(G), such as
the unit interval graphs shown in Theorem 2.45. The following problem could be
interesting but may be difficult:

Problem 2.62 Characterize those graphs G with r c(G) = diam(G), or give some
sufficient conditions to guarantee that r c(G) = diam(G). Similar problems for the
parameter sr c(G) can be proposed.

Basavaraju et al. in [6] continued to investigate the rainbow connection numbers of

graph power and graph products according to the radius of graphs. They derived the
following results.

Theorem 2.63 [6] For a connected graph G, let G k be the k-th power of G. Then
r (G k ) ≤ r c(G k ) ≤ 2r (G k ) + 1 for k ≥ 2. Moreover,
the upper bound is tight up to
an additive constant 1. (Note that r (G k ) = r (G)k ).

Theorem 2.64 [6] If G and H are connected nontrivial graphs, then r (GH ) ≤
r c(GH ) ≤ 2r (GH ). Moreover, the bounds are tight. (Note that r (GH ) =
r (G) + r (H )).

Let G ∗ = G 1  G 2  · · ·  G k (k ≥ 2), where each G i (1 ≤ i ≤ k) is connected.

Since the Cartesian product of any two graphs is a spanning subgraph of their strong
product, G is the spanning subgraph of G ∗ , then we have the following result.

Corollary 2.65 [71] Let G ∗ = G 1 G 2 · · ·G k (k ≥ 2), where each G i (1 ≤ i ≤ k)

is connected. Then we have

k
r c(G ∗ ) ≤ r c(G i ).
i=1

Basavaraju et al. [6] proved the following result.

Theorem 2.66 [6] If G and H are connected nontrivial graphs, then r (G  H ) ≤

r c(G  H ) ≤ 2r (G  H ) + 2. The upper bound is tight up to an additive constant 2.

For i = 1, 2, . . . , r , let m i ≥ 2 be given integers. Consider the graph G whose

vertices are the r -tuples b1 b2 · · · br with bi ∈ {0, 1, . . . , m i − 1}, and let two verti-
ces be adjacent if the corresponding tuples differ in precisely one coordinate. Such
a graph is called a Hamming graph. Clearly, a graph G is a Hamming graph if and
only if it can be written in the form G = K m 1 K m 2 · · · K m r for some r ≥ 1, where
m i ≥ 2 for all i. So we call G a Hamming graph with r factors. A Hamming graph
is a hyper cube (or r -cube) [41], denoted by Q r , if and only m i = 2 for all i. The
concept of Hamming graph is useful in communication networks [48].

Corollary 2.67 [71] If G is a Hamming graph with r factors, then r c(G) = r. In

particular, r c(Q r ) = r .

123
24 Graphs and Combinatorics (2013) 29:1–38

The composition (lexicographic product) of two graphs G and H is the simple

graph G[H ] with vertex set V (G) × V (H ) in which (u, v) is adjacent to (u  , v  ) if
and only if either uu  ∈ E(G) or u = u  and vv  ∈ E(H ). By definition, G[H ] can be
obtained from G by substituting a copy Hv of H for every vertex v of G and by joining
all vertices of Hv with all vertices of Hu if uv ∈ E(G). Note that G[H ] is connected
if and only if G is connected. By definition, it is easy to show: If G is complete, then
diam(G[H ]) = 1 if H is complete (as now G[H ] is complete), diam(G[H ]) = 2
if H is not complete; If G is not complete, then diam(G[H ]) = diam(G). Then we
have the following result.
Theorem 2.68 [71] Let G and H be two graphs, where G is connected.
1. if H is complete, then r c(G[H ]) ≤ r c(G). In particular, if diam(G) = r c(G),
then r c(G[H ]) = r c(G).
2. if H is not complete, then r c(G[H ]) ≤ r c(G) + 1. In particular, if diam(G) =
r c(G), then diam(G[H ]) = 2 if G is complete and r c(G) ≤ diam(G[H ]) ≤
r c(G) + 1 if G is not complete.
Basavaraju et al. [6] proved the following result.
Theorem 2.69 [71] Let G and H be nontrivial graphs. If G is a connected, then
r (G[H ]) ≤ r c(G[H ]) ≤ 2r (G[H ]) if r (G[H ]) ≤ 2, and 1 ≤ r c(G[H ]) ≤ 3 if
r (G[H ]) = 1. Moreover, the bounds are tight.
Li and Sun [71] also investigated other graph operations, such as the union of graphs,
which we will not consider here. Gologranca et al. in [40] investigated the (strong)
rainbow connection number on direct, strong, and lexicographic product. Klav̆ar and
Mekis̆ in [42] also gave some results on the rainbow connection numbers on graph
products.

2.6 Upper Bounds for the Strong Rainbow Connection Number

The topic of rainbow connection number is interesting and recently a series papers have
been published about it. The strong rainbow connection number is also interesting,
and by definition, the investigation of it is more challenging than that of the rainbow
connection number. However, there are very few papers that have been published about
it. Chartrand et al. [14] determined the strong rainbow connection numbers for some
special graph classes including trees, complete graphs, wheels and complete bipartite
(multipartite) graphs as shown in Subsection 2.1. However, for a general graph G it
appears very difficult to give the value of sr c(G); so we present upper bounds for it
according to some graph parameters. Li and Sun [72] derived a sharp upper bound
for sr c(G) according to the number of edge-disjoint triangles (if exist) in a graph G,
and give a necessary and sufficient condition for the sharpness. We need to introduce
a new graph class.
Recall that a block of a connected graph G is a maximal connected subgraph with-
out a cut vertex. Thus, every block of G is either a maximal 2-connected subgraph
or a bridge. We now introduce a new graph class. For a connected graph G, we say
G ∈ G t , if it satisfies the following conditions:

123
Graphs and Combinatorics (2013) 29:1–38 25

Fig. 4 An example ofG ∈ G t with t = 2

C1 . Each block of G is a bridge or a triangle;

C2 . G contains exactly t triangles;
C3 . Each triangle contains at least one vertex of degree two in G.
By definition, each graph G ∈ G t is formed by (edge-disjoint) triangles and (pos-
sibly trivial) paths, these triangles and paths fit together in a treelike structure, and
G contains no cycles but the t (edge-disjoint) triangles. For example, see Fig. 4,
here t = 2, and u 1 , u 2 and u 6 are vertices of degree 2 in G. If a tree is obtained
from a graph G ∈ G t by deleting one vertex of degree 2 from each triangle, then we
call this tree is a D2 -tr ee of G, denoted by TG . For example, in Fig. 4, TG is a D2 -tree
of G. Clearly, the D2 -tree is not unique, since in this example, we can obtain another
D2 -tree by deleting the vertex u 1 instead of u 2 . On the other hand, we can say that
any element of G t can be obtained from a tree by adding t new vertices of degree 2.
It is easy to show that the number of edges of TG is m − 2t where m is the number of
edges of G.
They derived the following result.
Theorem 2.70 [72] If G is a graph with m edges and t edge-disjoint triangles, then

sr c(G) ≤ m − 2t,

the equality holds if and only if G ∈ G t .

Ahadi and Dehghan [1] also derived an upper bound for strongly regular graph: if
1
G is an S RG(n, r, λ, μ), then sr c(G) ≤ (e(4μr − 4μλ − 6μ + 1)) μ . However, we
do not know whether it is sharp.
Unlike rainbow connection number, which is a monotone graph property (adding
edges never increases the rainbow connection number), this is not the case for the
strong rainbow connection number (see Fig. 1 for an example). The investigation of
strong rainbow connection number is much harder than that of rainbow connection
number. Chakraborty et al. gave the following conjecture.
Conjecture 2.71 [12] If G is a connected graph with minimum degree at least n, then
it has a strong rainbow connection number bounded by a constant depending only on .

123
26 Graphs and Combinatorics (2013) 29:1–38

3 Rainbow k-Connectivity

In this section, we survey results on rainbow k-connectivity. By its definition, we

know that it is difficult to derive exact value or a useful upper bound of the rainbow
k-connectivity for a general graph. Chartrand et al. [17] did some basic research on
the rainbow k-connectivity of two special graph classes. They first studied the rainbow
k-connectivity of the complete graph K n for various pairs k, n of integers, and derived
the following result:
Theorem 3.1 [17] For every integer k ≥ 2, there exists an integer f (k) such that if
n ≥ f (k), then r ck (K n ) = 2.
They obtained an upper bound (k + 1)2 for f (k), namely f (k) ≤ (k + 1)2 . Li and
Sun [69] continued their investigation, and the following result is derived:
3
Theorem 3.2 [69] For every integer k ≥ 2, there exists an integer f (k) = ck 2 +C(k)
3
where c is a constant and C(k) = o(k 2 ) such that if n ≥ f (k), then r ck (K n ) = 2.
3
From Theorem 3.2, we can obtain an upper bound ck 2 + C(k) for f (k), where c
3
is a constant and C(k) = o(k 2 ), that is, they improved the upper bound of f (k) from
3
O(k 2 ) to O(k 2 ), a considerable improvement. Dellamonica, Magnant and Martin [25]
obtained the best possible upper bound 2k, which is linear in k (see Theorem 3.3).
However, the proof of Theorem 3.2 is more structural or constructive, and informative.
In the argument of [25], Dellamonica, Magnant and Martin put forward a new concept,
the rainbow(k, l)-connectivity.
Let G be an edge-colored graph G and let l and k be integers with l ≤ k. Sup-
pose the edges of G are k-colored. For a, b ∈ V (G), denote by p(a, b) the max-
imum number of internally disjoint rainbow paths of length l having endpoints a
and b. The rainbow(k, l)-connectivity of G is the minimum p(a, b) among all dis-
tinct a, b ∈ V (G). Note that this newly defined rainbow(k, l)-connectivity computes
the number of internally disjoint paths of length l (this is distinct from the rainbow
k-connectivity which, as mentioned above, computes the number of colors); and by
definition, for different edge-colorings, the values of rainbow(k, l)-connectivity could
be different.
From Theorem 3.1, we know that for any r , there exists an explicit 2-coloring of
K r in which√the number of bi-chromatic paths of length 2 between any pair of vertices
is at least  r − 1 . Using the above definition, it is a statement about the rainbow
(2,2)-connectivity of a given 2-coloring of the edges of K r . Dellamonica et al. [25]
greatly improved and generalized the above lower bound for graphs of sufficiently
large order by providing a different constructive coloring. Their construction attains
asymptotically the maximum rainbow connectivity possible.
Theorem 3.3 [25] For any k ≥ 2 and r ≥ r0 = r0 (k), there exists an explicit k-col-
oring of the edges of K r having rainbow (k, 2)-connectivity
 
k−1
− o(1) r.
k

123
Graphs and Combinatorics (2013) 29:1–38 27

More generally, they considered the problem of finding longer rainbow paths.

Theorem 3.4 [25] For any integers  and k with 3 ≤  ≤ k, there exists r0 = r0 (k)
such that for every r ≥ r0 , there is an explicit k-coloring of the edges of K r having
rainbow (k, 2)-connectivity
r
(1 − o(1)) .
−1

This result is also asymptotically best possible, since any collection of internally
disjoint paths of length  can contain at most −1r
paths. Their proof employed a very
recent breakthrough due to Bourgain [10,78], which consists of a powerful explicit
extractor. Roughly speaking, an (explicit) extractor is a polynomial time algorithm
used to convert some special probability distributions into uniform distributions. See
[81] for a good but somewhat outdated survey on extractors.
Chartrand et al. [17] also investigated the rainbow k-connectivity of r -regular com-
plete bipartite graphs for some pairs k, r of integers with 2 ≤ k ≤ r , and they showed
the following:
Theorem 3.5 [17] For every integer k ≥ 2, there exists an integer r such that
r ck (K r,r ) = 3.
However, they could not show a similar result for complete graphs, and therefore
they left an open question: For every integer k ≥ 2, determine an integer (function)
g(k), for which r ck (K r,r ) = 3 for every integer r ≥ g(k), that is, the rainbow k-con-
nectivity of the complete bipartite graph K r,r is essentially 3. Li and Sun [70] solved
this question using a similar but more complicated method to that of Theorem 3.5, and
they proved:

Theorem 3.6 [70] For every integer k ≥ 2, there exists an integer g(k) = 2k k2 
such that r ck (K r,r ) = 3 for any r ≥ g(k).

With the probabilistic method, Fujita et al. [39] improved this result to g(k) =
2k + o(k), as follows.

Theorem 3.7 [39] Let 0 < ε < 21 and k ≥ 21 (θ − 1)(1 − 2ε) + 2, where θ = θ (ε) is
the largest solution of 2x 2 e−ε (x−2) = 1. If r ≥ 2k−4
2
1−2ε + 1, then r ck (K r,r ) = 3.

On the other hand, how small can the function g(k) be? The next result shows that
the best we can hope for is approximately g(k) ≥ 3k
2 .

Theorem 3.8 [39] For any 3-coloring of the edges of K r,r , there exist u, v ∈ V (K r,r )
2
where the number of internally vertex-disjoint rainbow u − v paths is at most 3(r2r−1) .
They extended this to complete multipartite graphs with equipartitions. Let K t×r
denote the complete multipartite graph with t classes of size r . For k ≥ 2, when
considering bipartite graph K r,r , we cannot achieve r ck (K r,r ) = 2. However, we
may hope for r ck (K t×r ) = 2. Using a similar random method, Fujita et al. got
the following

123
28 Graphs and Combinatorics (2013) 29:1–38

Theorem 3.9 [39] Let 0 < ε < 21 , t ≥ 3, and k ≥ 21 θ (t − 2)(1 − 2ε) + 1, where
θ = θ (ε, t) is the largest solution of 21 t 2 x 2 e−(t−2)ε x = 1. If r ≥ (t−2)(1−2ε)
2 2k−2
, then
r ck (K t×r ) = 2.
Again, the following result shows that the best lower bound for r would be approx-
imately r ≥ t−1
2k
.
Theorem 3.10 [39] Let t ≥ 3. For any 2-coloring of the edges of K t×r , there exist
u, v ∈ V (K t×r ) where the number of internally vertex-disjoint rainbow u − v paths
is at most (t−1)r
2
2(r −1) .
Li and Sun [69] showed that for every pair of integers k ≥ 2 and r ≥ 1, there is
an integer f (k, r ) such that if t ≥ f (k, r ), then r ck (K t×r ) = 2. In [70] the same
authors showed that for any t ≥ 2 there is an integer h(k) such that if r ≥ h(k), then
r ck (K t×r ) ≤ 3. More generally, we have the following question.
Question 3.11 [39] For integers k, t ≥ 2 and n 1 ≤ n 2 ≤ · · · ≤ n t , is there an integer
h(k, t) such that if n 1 ≥ h(k, t), we have r ck (K n 1 ,n 2 ,...,n t ) = 2 if t = 2, and 3 if t ≥ 3.
If so, what is the smallest value of h(k, t)?
The case t = 2 was asked by Chartrand et al. [17]. It is surprising that this particular
case is still open, since complete bipartite graphs are very basic graphs.
Recently, He and Liang [43] investigated the rainbow k-connectivity in the set-
ting of random graphs. They determined a sharp threshold function for the property
r ck (G(n, p)) ≤ d for every fixed integer d ≥ 2. This substantially generalizes a result
due to Caro et al. (see Theorem 2.50). Their main result is as follows.
Theorem 3.12 [43] Let d ≥ 2 be a fixed integer and k = k(n) ≤ O(log n). Then
p = (log n)1/d
n (d−1)/d
is a sharp threshold function for the property r ck (G(n, p)) ≤ d.
The key ingredient of their proof is the following result: With probability at least
n)1/d
1 − n −(1) , every two different vertices of G(n, C(log
n (d−1)/d
) are connected by at least
10d
2 c0 log n internally disjoint paths of length exactly d.
He and Liang [43] also investigated the rainbow k-connectivity from an algorithmic
point of view. The N P-hardness of determining r c(G) was shown by Chakraborty et
al. as shown in Sect. 6. However, He and Liang showed that the problem (even the
search version) becomes easy in random graphs.
Theorem 3.13 [43] For any constant ∈ [0, 1), p = n − (1±o(1)) and k ≤ O(log n),
there is a randomized polynomial time algorithm that, with probability 1 − o(1),
makes G(n, p) rainbow-k-connected using at most one more than the optimal number
of colors.
Since almost all natural edge probability functions p encountered in various scenar-
ios have such a form, their result is quite strong. Note that G(n, n − ) is almost surely
disconnected when > 1 [34], which makes the problem become trivial. Therefore
they ignored these cases. Fujita et al. [39] proved the following result.
√
Theorem 3.14 [39] The probability p = log n/n is a sharp threshold function for
the property r ck (G n, p ) ≤ 2 for all k ≥ 1.

123
Graphs and Combinatorics (2013) 29:1–38 29

They also considered other random graph models. Let G n,m, p be the random bipar-
tite graph with class sizes n and m, and edge probability p. Let G n,M be the random
graph on n vertices with M edges, endowed with the uniform probability distribution.
We can analogously define sharp threshold functions for these models. Again by the
result of [8], every monotone property for these models has a sharp threshold function.
We have the following results.
√
Theorem 3.15 [39] The probability p = log n/n is a sharp threshold function for
the property r ck (G n,n, p ) ≤ 3 for all k ≥ 1.

Theorem 3.16 [39] The probability p = n 3 log n is a sharp threshold function for
the property r ck (G n,M ) ≤ 2 for all k ≥ 1.
Finally, for random graphs we can obviously raise the following
Problem 3.17 For d ≥ 2, determine a sharp threshold function for the property
r ck (G) ≤ d, where G is another random graph model.
In particular, an answer for random regular graphs would be interesting. Fujita et al.
[39] also considered r c2 (G) when G has fixed vertex-connectivity. By using the Fan
Lemma, they obtained the following result.
Theorem 3.18 [39] If  ≥ 2 and G is an -connected graph on n ≥  + 1 vertices,
then r c2 (G) ≤ (+1)n
 .
For  = 2 they found a shorter proof by using a minimally 2-connected spanning
subgraph of a 2-connected graph. A 2-connected series-parallel graph is a (simple)
graph which can be obtained from a K 3 , and then repeatedly applying a sequence of
operations, each of which is a subdivision, or replacement of an edge by a double
edge. These graphs are a well-known subfamily of the 2-connected graphs, and for
which we can do better.
Fujita et al. [39] also proved that r c2 (G) ≤ n, when G is a 2-connected series-paral-
lel graph on n ≥ 3 vertices. Since any 3-connected planar graph contains a 2-connected
series-parallel spanning subgraph, see [32], as a consequence one can get that if G is
a 3-connected planar graph of order n, then r c2 (G) ≤ n. Note that this bound is sharp
when G is a generalized -graph, that is, G = q1 ,...,qt is the union of t ≥ 2 paths
with lengths q1 ≥ · · · ≥ qt ≥ 1, where qt−1 ≥ 2, and the paths are pairwise internally
vertex-disjoint with the same two end-vertices, as we know that if G = q1 ,...,qt , then
r c2 (G) = n when t = 2; n − 1 or n − 2 when t ≥ 3. These results naturally lead to the
following problem: What is the minimum constant c > 0 such that for all 2-connected
graphs G on n vertices, we have r c2 (G) ≤ cn? Li and Liu [62] solved this problem
by showing that c = 1.
Theorem 3.19 [62] If G is a 2-connected graph on n vertices, then r c2 (G) ≤ n with
equality if and only if G is a cycle of order n.
Clearly, there are many additional things that one can do with this concept. As men-
tioned above, it is difficult to derive the precise value or a nice upper bound for r ck (G)
of a κ-connected graph G, where 2 ≤ k ≤ κ. More generally, one may consider the
following problem.

123
30 Graphs and Combinatorics (2013) 29:1–38

Problem 3.20 [39] Let 2 ≤ k ≤ κ. Find the least constant c = c(k, κ), where
0 < c ≤ k, such that for all κ-connected graph G on n vertices, we have r ck (G) ≤ cn.
Note that a result of Mader [75] implies that any minimally κ-connected graph on
n vertices has at most κn edges. If G is κ-connected on n vertices, then by considering
a minimally κ-connected spanning subgraph of G, we have r ck (G) ≤ κn.

4 The k-Rainbow Index of a Graph

The k-rainbow coloring as defined above, is another generalization of the rainbow

coloring. Chartrand et al. [18] did some basic research on this topic. There is a rather
simple upper bound for r xk (G) in terms of the order of G, regardless the value of k.
Proposition 4.1 [18] Let G be a nontrivial connected graph of order n ≥ 3. For each
integer k with 3 ≤ k ≤ n − 1, r xk (G) ≤ n − 1 while r xn (G) = n − 1.
There is a class of graphs of order n ≥ 3 whose k-rainbow index attains the upper
bound of Proposition 4.1, it is an immediate consequence of Observation 2.11.
Proposition 4.2 [18] Let T be a tree of order n ≥ 3. For each integer k with 3 ≤ k ≤ n,
r xk (T ) = n − 1.
There is also a rather obvious lower bound for the k-rainbow index of a connected
graph G of order n, where 3 ≤ k ≤ n. The Steiner distance d(S) of a set S of vertices
in G is the minimum size of a tree in G containing S. Such a tree is called a Steiner
S-tree or simply a Steiner tree. The k-Steiner diameter, say sdiam k (G) of G is the
maximum Steiner distance of S among all sets S with k vertices in G. Thus if k = 2 and
S = {u, v}, then d(S) = d(u, v) and the 2-Steiner diameter sdiam 2 (G) = diam(G).
The k-Steiner diameter then provides a lower bound for the k-rainbow index of G:
for every connected graph G of order n ≥ 3 and each integer k with 3 ≤ k ≤ n,
r xk (G) ≥ sdiam k (G) ≥ k − 1.
Theorem 4.3 [18] If G is a unicyclic graph of order n ≥ 3 and girth g ≥ 3, then

n−2 if k = 3 and g ≥ 4,
r xk (G) =
n−1 if g = 3 or 4 ≤ k ≤ n.

The investigation of r xk (G) for a general k and a general graph G is rather difficult.
So one may consider r xk (G) for a special graph class, or, for a general graph and small
k, such as k = 3.
Problem 4.4 Derive a sharp upper bound for r x3 (G).
Problem 4.5 For k ≥ 3, characterize the graphs with r xk (G) = n − 1.
Problem 4.6 Consider the relationship between r xk (G) and r xk (L(G)).
There is also a generalization of the k-rainbow index, say (k, )-rainbow index
r xk, , of G which is mentioned in [18] and we will not introduce it here.

123
Graphs and Combinatorics (2013) 29:1–38 31

5 The Rainbow Vertex-Connection Number of a Graph

The above several parameters are all defined on edge-colored graphs. Here we will
introduce a new graph parameter which is defined on vertex-colored graphs. It is, as
mentioned above, a vertex-version of the rainbow connection number. Krivelevich
and Yuster [53] put forward this new concept and proved a theorem analogous to
Theorem 2.17.

Theorem 5.1 [53] A connected graph G with n vertices has r vc(G) < 11n
δ(G) .

The argument of this theorem used the concept of k-str ong two-step dominating
sets. They proved that if H is a connected graph with n vertices and minimum degree
δ, then it contains a 2δ -strong two-step dominating set S whose size is at most δ+2
2n
.
δ
Then they derived an edge-coloring for G according to its connected 2 -strong two-step
dominating set. And they showed that, with positive probability, their coloring yields
a rainbow connected graph by the Lovász Local Lemma (see [3]).
Motivated by the method of Theorem 5.1, Li and Shi derived an improved result.

Theorem 5.2 [65] A connected√graph G of order n with minimum degree δ has

r vc(G) ≤ 3n/(δ+1)+5
√ for δ ≥ n − 1−1, n ≥ 290, while r vc(G) ≤ 4n/(δ+1)+5
for 16 ≤ δ ≤ n − 1 − 2, r vc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 16 where
3 log(δ 3 +2δ 2 +3)−3(log 3−1)
−2
C(δ) = e δ−3 , r vc(G) ≤ n/2 − 2 for δ = 5, r vc(G) ≤ 3n/5 − 8/5
for δ = 4,r
√ vc(G) ≤ 3n/4 − 2 for δ = 3. Moreover, an example shows that when
when δ ≥ n − 1 − 1, and δ = 3, 4, 5 the bounds are seen to be tight up to additive
factors.

Motivated by the method of Theorem 5.1, Dong and Li [28] also proved a theorem
analogous to Theorem 2.22 for the rainbow vertex-connection version according to
the degree sum condition σk , which is stated as follows:

Theorem 5.3 [28] Let G be a connected graph of order n with k independent ver-
tices, then r vc(G) ≤ (4k+2k
2 )n
σk +k + 5k if σk ≤ 7k or σk ≥ 8k; whereas r vc(G) ≤
( 38k
9 +2k )n
2

σk +k + 5k if 7k < σk < 8k.

Li and Liu [61] gave a sharp upper bound for the rainbow vertex-connection number
of 2-connected graphs.

Theorem 5.4 [61] Let G be a 2-connected graph of order n(n ≥ 3). Then r vc(G) = 0
if n = 3; 1 if n = 4, 5; 3 if n = 9;  n2  − 1 if n = 6, 7, 8, 10, 11, 12, 13 or 15;  n2  if
n ≥ 16 or n = 14, and the upper bound can be achieved by the cycle Cn .

Similarly, Chen et al. [21] investigated the Nordhaus-Gaddum-type result also for
the rainbow vertex-connection number.

Theorem 5.5 [21] When G and G are both connected, then 2 ≤ r vc(G) + r vc(G) ≤
n − 1. Both the upper and the lower bounds are best possible for all n ≥ 5.

123
32 Graphs and Combinatorics (2013) 29:1–38

From the examples in Sect. 1, if G is a graph with many cut vertices, then one can
see that the difference |r c(G) − r vc(G)| could be very large (cannot be bounded by
a constant). However, if G does not have any cut-vertex, i.e., G is 2-connected, then
many examples support that |r c(G) −r vc(G)| is very small. So we have the following
problem.
Problem 5.6 For a 2-connected graph G, find good bounds to the difference |r c(G)−
r vc(G)|. Is this difference a very small constant ?
Another problem is as follows:
Problem 5.7 Is it true that for any 2-connected graph G, r vc(G) ≤ r c(G) ?
Li et al. [64] introduced the definition of strong rainbow vertex-connection of a
graph. If for every pair u, v of distinct vertices, G contains a rainbow u − v geodesic,
then G is strongly rainbow vertex-connected. The minimum k for which there exists
a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph
is called the strong rainbow vertex-connection number of G, denoted by sr vc(G).
Observe that r vc(G) ≤ sr vc(G) for any nontrivial connected graph G. They also
gave some bounds of sr vc(G) and proved a similar result as that in [23] for r vc(G)
and sr vc(G).

6 Algorithms and Computational Complexity

At the end of [11], Caro et al. gave two conjectures (see Conjecture 4.1 and Conjec-
ture 4.2 in [11]) on the complexity of determining the rainbow connection numbers of
graphs. Chakraborty et al. [12] solved these two conjectures by the following theorem.
Independently, Le and Tuza [54] also solved these two conjectures.
Theorem 6.1 [12] Given a graph G, deciding if r c(G) = 2 is NP-complete. In par-
ticular, computing r c(G) is NP-hard.
Chakraborty et al. divided the proof of Theorem 6.1 into three steps: the first step is
showing the computational equivalence of the problem of rainbow connection num-
ber 2, that asks for a red-blue edge coloring in which all vertex pairs have a rainbow
path connecting them, to the problem of subset rainbow connection number 2, that
asks for a red-blue coloring in which every pair of vertices in a given subset of pairs
has a rainbow path connecting them. In the second step, they reduced the problem of
extending to rainbow connection number 2, asking whether a given partial red-blue
coloring can be completed to obtain a rainbow connected graph, to the problem of
subset rainbow connection number 2. Finally, the proof of Theorem 6.1 is completed
by reducing 3-SAT to the problem of extending to rainbow connection number 2.
Chakraborty et al. [12] also proposed a problem: Suppose that we are given a graph
G for which we are told that r c(G) = 2, Can we rainbow-color it in polynomial time
with o(n) colors? For the usual coloring problem, this version has been well studied. It
is known that if a graph is 3-colorable (in the usual sense), then there is a polynomial
time algorithm that colors it with Õ(n 3/14 ) colors [7]. Dong and Li [30] solved this
problem by showing a stronger result.

123
Graphs and Combinatorics (2013) 29:1–38 33

Theorem 6.2 [30] Suppose that we are given a graph G for which we are told that
r c(G) = 2. One can rainbow-color it in polynomial time with no more than 5 colors.

In the 16th C5 Graph Theory Workshop (Rathen, May 2012), Schiermeyer asked
the question: Suppose we know that a graph G has r c(G) = 2. Can we rainbow-color
it in polynomial time with 4 colors?
For general k, it has been shown in [54] that for every k ≥ 2, deciding if r c(G) = k
is N P-complete. Ananth and Nasre in [4] derived the following results.
Theorem 6.3 [4] For every k ≥ 3, deciding whether r c(G) ≤ k is N P-hard.
For the strong rainbow connection number, they obtained a similar result.
Theorem 6.4 [4] For every k ≥ 3, deciding whether sr c(G) ≤ k, is N P-hard even
when G is bipartite.
From the same construction as in the proof of Theorem 6.4, one can see that the
following corollary is immediate.
Corollary 6.5 [4] Deciding if the rainbow connection number of a graph G is at most
3 is N P-hard even when G is bipartite.
Li and Li [58] showed that for any fixed integer k, the problems in Theorems 6.3
and 6.4 as well as Corollary 6.5 are all in N P class, and therefore, “N P-hard” can be
replaced by “N P-complete” in the three results if we replace “For every k” by “For
any fixed k”. Corollary 6.5 suggests us the following problem.
Problem 6.6 For every (any fixed) integer k ≥ 2, deciding if a given bipartite graph
G has r c(G) ≤ k is N P-hard (complete).
On the other hand, in [12], Chakraborty et al. also derived some positive algorithmic
results. Parts of the following two results will be shown in Theorems 2.16 and 2.52.

Theorem 6.7 [12] For every > 0 there is a constant C = C( ) such that if G is a
connected graph with n vertices and minimum degree at least n, then r c(G) ≤ C.
Furthermore, there is a polynomial time algorithm that constructs a corresponding
coloring for a fixed .

As mentioned above, Theorem 6.7 is based upon a modified degree-form version

of Szemerédi Regularity Lemma that they proved and that may be useful in other
applications. From their algorithm it is also not hard to find a probabilistic polynomial
time algorithm for finding this coloring with high probability (using on the way the
algorithmic version of the Regularity Lemma from [2] or [36]).

Theorem 6.8 [12] If G is an n-vertex graph with diameter 2 and minimum degree at
least 8logn, then r c(G) ≤ 3. Furthermore, such a coloring is given with high proba-
bility by a uniformly random 3-edge-coloring of the graph G, and can also be found
by a polynomial time deterministic algorithm.

Because computing r c(G) is N P-hard, it was tried to give approximate algorithms

to compute the rainbow connection number. Basavaraju et al. in [5] presented an

123
34 Graphs and Combinatorics (2013) 29:1–38

(r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-fac-

tor approximation algorithm which runs in O(dm) time to rainbow color any connected
graph G on n vertices, with m edges, diameter d and radius r .
Suppose we are given an edge-coloring of a graph. Is it then easier to verify whether
the colored graph is rainbow connected? Clearly, if the number of colors is con-
stant, then this problem becomes easy. However, if the coloring is arbitrary (with an
unbounded number of colors), the problem becomes N P-complete.
Theorem 6.9 [12] The following problem is N P-complete: Given an edge-colored
graph G, check whether the given coloring makes G rainbow connected.
Li and Li [58] showed that this problem remains NP-complete even when restricted
to the class of bipartite graphs. Reducing also from Theorem 6.9, Huang et al. in
[47] first obtained a result: Given an edge-colored planar graph G, checking whether
the given coloring makes G rainbow connected is N P-complete. Then they got the
following stronger result.
Theorem 6.10 [47] Given an edge-colored bipartite planar graph G, checking
whether the given coloring makes G rainbow connected is N P-complete.
Uchizawa et al. [82] derived the following results: Determining the rainbow con-
nection number of graphs is strongly NP-complete even for outerplanar graphs. Note
that constant factor approximation algorithms for bridgeless chordal graphs, and addi-
tive approximation algorithms for interval, AT-free, threshold and circular arc graphs
without pendant vertices will follow from the proofs of their upper bounds in [13]
(Theorem 2.45). Recently, Chandran and Rajendraprasad in [15] considered the prob-
lem of rainbow coloring split graphs and a special subclass of split graphs called
threshold graphs, and got the following results.
Theorem 6.11 [15] (i). The problem of deciding whether a graph can be rainbow
colored using 3 colors remains NP-complete even when restricted to the class of split
graphs. However, any split graph can be rainbow colored in linear time using at most
one more color than the optimum. (ii). For every integer k ≥ 3, the problem of decid-
ing whether a graph can be rainbow colored using k colors remains NP-complete
even when restricted to the class of chordal graphs. (iii). For every positive integer
k, threshold graphs with rainbow connection number k can be characterized based
on their degree sequence alone. Further, one can optimally rainbow color a threshold
graph in linear time.
As mentioned, He and Liang [43] investigated the rainbow k-connectivity in the
setting of random graphs. They also investigated rainbow k-connectivity from the
algorithmic point of view. The NP-hardness of determining r c(G) was shown by Cha-
kraborty et al. as shown above. They showed that the problem (even the search version)
becomes easy in random graphs.
Theorem 6.12 [43] For any constant ∈ [0, 1), p = n − (1±o(1)) and k ≤ O(log n),
there is a randomized polynomial time algorithm that, with probability 1 − o(1),
makes G(n, p) rainbow-k-connected using at most one more than the optimal number
of colors.

123
Graphs and Combinatorics (2013) 29:1–38 35

Since almost all natural edge probability functions p encountered in various sce-
narios have such form, their result is quite strong. Note that G(n, n − ) is almost surely
disconnected when > 1 [34], which makes the problem become trivial. Therefore
they ignored these cases.
Recall that the values of rainbow (k, l)-connectivity may be different for distinct
edge-colorings. Dellamonica et al. [25] derived that a random k-coloring of a suffi-
ciently large complete graph has asymptotically optimal rainbow rainbow (k, l)-con-
nectivity (see Theorems 3.3 and 3.4). They obtained an explicit edge-coloring. By
explicit, we mean that they gave a polynomial time algorithm to compute such an
edge-coloring.
The computational complexity of rainbow vertex-connection numbers has been
determined by Chen et al. [22]. Motivated by the proofs of Theorems 6.1 and 6.9, they
derived two corresponding results to the rainbow vertex-connection.

Theorem 6.13 [22] Given a graph G, deciding if r vc(G) = 2 is NP-complete. In

particular, computing r vc(G) is NP-hard.

Theorem 6.14 [22] The following problem is NP-complete: Given a vertex-colored

graph G, check whether the given coloring makes G rainbow vertex-connected.

From Theorem 6.14, we know that deciding whether a given vertex-colored graph
is rainbow vertex-connected is NP-complete. Huang et al. in [47] showed that it is still
NP-complete even when the vertex-colored graph is a line graph.

Acknowledgments The authors are very grateful to the referees for their comments and suggestions
which helped to improve the presentation of the paper.

References

1. Ahadi, A., Dehghan, A.: On rainbow connection of strongly regular graphs. arXiv:1001.3413v1
[math.CO] (2010)
2. Alon, N., Duke, R., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the Regularity
Lemma. J. Algorithms 6, 80–109 (1994)
3. Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)
4. Ananth, P., Nasre, M.: New hardness results in rainbow connectivity. arXiv:1104.2074v1 [cs.CC]
(2011)
5. Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number
and radius. Graphs Combin. (2012) (to appear)
6. Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number
of graph power and graph products. arXiv:1104.4190v1 [math.CO] (2011)
7. Blum, A., Karger, D.: An Õ(n 3/14 )-coloring algorithm for 3-colorable graphs. Inf. Process.
Lett. 61(1), 49–53 (1997)
8. Bollobás, B., Thomason, A.: Threshold functions. Combinatorica 7, 35–38 (1986)
9. Bondy, J.A., Murty, U.S.R.: Graph Theory. GTM 244, Springer, Berlin (2008)
10. Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number
Theory 1, 1–32 (2005)
11. Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connection. Electron. J. Com-
bin. 15, R57 (2008)
12. Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connectiv-
ity. In: 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, pp.
243–254 (2009) (Also, see J. Combin. Optim. 21, 330–347 (2011))

123
36 Graphs and Combinatorics (2013) 29:1–38

13. Chandran, L.S., Das, A., Rajendraprasad, D., Varma, N.M.: Rainbow connection number and connected
dominating sets. J. Graph Theory 71, 206–218 (2012)
14. Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math.
Bohem. 133, 85–98 (2008)
15. Chandran, L.S., Rajendraprasad, D.: Rainbow colouring of split and threshold graphs COCOON. In:
LNCS, vol. 7434, pp. 181–192. Springer, Berlin (2012)
16. Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: On the rainbow connectivity of cages. Congr.
Numer. 184, 209–222 (2007)
17. Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: The rainbow connectivity of a graph. Net-
works 54(2), 75–81 (2009)
18. Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Net-
works 55, 360–367 (2010)
19. Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall, London (2008)
20. Chen, L., Li, X., Lian, H.: Nordhaus-Gaddum-type theorem for rainbow connection number of graphs.
Graphs Combin. (2012) (in press)
21. Chen, L., Li, X., Liu, M.: Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number
of a graph. Util. Math. 86, 335–340 (2011)
22. Chen, L., Li, X., Shi, Y.: The complexity of determining the rainbow vertex-connection of graphs. The-
oret. Comput. Sci. 412, 4531–4535 (2011)
23. Chen, X., Li, X.: A solution to a conjecture on the rainbow connection number. Ars Combin. 104, 193–
196 (2012)
24. Corneil, D., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM J. Discrete Math. 10(3), 399–
430 (1997)
25. Dellamonica, D. Jr., Magnant, C., Martin, D.: Rainbow paths. Discrete Math. 310, 774–781 (2010)
26. Dong, J., Li, X.: Upper bounds involving parameter σ2 for the rainbow connection. Acta Math. Appl.
Sin. (2012) (to appear)
27. Dong, J., Li, X.: Rainbow connection number, bridges and radius. Graphs Combin. (2012) (in press)
28. Dong, J., Li, X.: Rainbow connection numbers and the minimum degree sum of a graph. Sci. China
Ser. A (2012) (to appear)
29. Dong, J., Li, X.: Sharp upper bound for the rainbow connection number of a graph with diameter 2.
arXiv:1106.1258v3 [math.CO] (2011)
30. Dong, J., Li, X.: On a question on graphs with rainbow connection number 2. arXiv:1109.5004v2
[math.CO] (2011)
31. Ekstein, J., Holub, P., Kaiser, T., Kochy, M., Camachoy, S.M., Ryjáček, Z., Schiermeyer, I.: The rainbow
connection number of 2-connected graphs. Discrete Math. (2012) (in press)
32. Elmallah, E.S., Colbourn, C.J.: Series-parallel subgraphs of planar graphs. Networks 22(6), 607–
614 (1992)
33. Erdős, P., Pach, J., Pollack, R., Tuza, Z.: Radius, diameter, and minimum degree. J. Combin. Theory,
Ser. B. 47(1), 73–79 (1989)
34. Erdős, P., Rényi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int.
Kozl. 5, 17–61 (1960)
35. Ericksen, A.: A matter of security. Graduating Engineer & Computer Careers, pp. 24–28 (2007)
36. Fischer, E., Matsliah, A., Shapira, A.: Approximate hypergraph partitioning and applications. In: Pro-
ceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 579–589
(2007)
37. Frieze, A., Tsourakakis, C.E.: Rainbow connectivity of sparse random graphs. arXiv:1201.4603v2
[math.CO] (2012)
38. Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Am. Math.
Soc. 124, 2993–3002 (1996)
39. Fujita, S., Liu, H., Magnant, C.: Rainbow k-connection in dense graphs. preprint. Available at www.
cantab.net/users/henry.liu/maths.htm. Extended abstract in Proceedings of Euro- Combédb́b11, Elec-
tron. Notes Discrete Math. (to appear)
40. Gologranca, T., Mekiš, G., Peterin, I.: Rainbow connection and graph products. IMFM Preprint
Series 49, –#1149 (2011)
41. Harary, F., Hayes, J., Wu, H.: A survey of the theory of hypercube graphs. Comput. Math. Appl. 15, 277–
289 (1988)

123
Graphs and Combinatorics (2013) 29:1–38 37

42. Klav̆ar, S., Mekis̆, G.: On the rainbow connection of Cartesian products and their subgraphs. Discuss.
Math. Graph Theory (2012) (to appear)
43. He, J., Liang, H.: On rainbow-k-connectivity of random graphs. Inf. Process. Lett. 112(10), 406–
410 (2012)
44. Hedetniemi, S.T., Slater, P.J.: Line graphs of triangleless graphs and iterated clique graphs. In: Alavi,
Y. et al. (eds.) Graph Theory and Applications. Lecture Notes in Mathematics, vol. 303, , pp. 139–147.
Springer, Berlin 1972; MR49#151
45. Hemminger, R., Beineke, L.: Line graphs and line digraphs. In: Beineke, L. et al. (eds.) Selected Topics
in Graph Theory, pp. 271–305. Academic Press, London (1978)
46. Huang, X., Li, H., Li, X., Sun, Y.: Oriented diameter and rainbow connection number of a graph.
arXiv:1111.3480v1 [math.CO] (2011)
47. Huang, X., Li X., Shi, Y.: Rainbow connection for planar graphs and line graphs. arXiv:1110.3147
[cs.CC] (2011)
48. Imrich, W., Klavzar, S.: Product Graphs–Structure and Recognition. Wiley, New York (2000)
49. Johns, G.L., Okamoto, F., Zhang, P.: The rainbow connectivities of small cubic graphs. Ars Combin.
(2012) (to appear)
50. Kemnitz, A., Schiermeyer, I.: Graphs with rainbow connection number two. Discuss. Math. Graph
Theory 31, 313–320 (2011)
51. Kemnitz, A., Przybylo, J., Schiermeyer I., Wozniak, M.: Rainbow connection in sparse graphs. Discuss.
Math. Graph Theory (2012) (to appear)
52. Komlós, J., Simonovits, M.: Szemerédi’s Regularity Lemma and its applications in graph theory. In:
Miklós, D., Sós, V.T., Szönyi, T. (eds.) Combinatorics, Paul Erdő is Eighty, vol. 2, pp. 295–352. Bolyai
Society Mathematical Studies, Budapest (1996)
53. Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (at most) reciprocal to its minimum
degree. J. Graph Theory 63(3), 185–191 (2009)
54. Le, V., Tuza, Z.: Finding optimal rainbow connection is hard. Preprint (2009)
55. Li, H., Li, X., Liu, S.: The (strong) rainbow connection numbers of Cayley graphs on Abelian
groups. Comput. Math. Appl. 62(11), 4082–4088 (2011)
56. Li, H., Li, X., Liu, S.: Rainbow connection in graphs with diameter 2. Discrete Math. 312(8), 1453–
1457 (2012)
57. Li, H., Li, X., Sun, Y.: Upper bound for the rainbow connection number of bridgeless graphs with
diameter 3. arXiv:1109.2769v1 [math.CO] (2011)
58. Li, S., Li, X.: Note on the complexity of deciding the rainbow connectedness for bipartite graphs.
arXiv:1109.5534v2 [cs.CC] (2011)
59. Li, X., Liu, M., Schiermeyer, I.: Rainbow connection number of dense graphs. Discuss. Math. Graph
Theory (2012) (to appear)
60. Li, X., Liu, S.: Sharp upper bound for the rainbow connection numbers of 2-connected graphs.
arXiv:1105.4210v2 [math.CO] (2011)
61. Li, X., Liu, S.: Rainbow vertex-connection number of 2-connected graphs. arXiv:1110.5770 [math.CO]
(2011)
62. Li, X., Liu, S.: A sharp upper bound for the rainbow 2-connection number of 2-connected graphs.
arXiv:1204.0392 [math.CO] (2011)
63. Li, X., Liu, S., Chandran, L.S., Mathew, R., Rajendraprasad, D.: Rainbow connection number and
connectivity. Electron. J. Combin. 19, P20 (2012)
64. Li, X., Mao, Y., Shi, Y.: The strong rainbow vertex-connection of graphs. arXiv:1201.1541 [math.CO]
(2011)
65. Li, X., Shi, Y.: On the rainbow vertex-connection. Discuss. Math. Graph Theory (2012) (to appear)
66. Li, X., Shi, Y.: Rainbow connection in 3-connected graphs. Graphs Combin. (2012) (in press)
67. Li, X., Sun, Y.: Rainbow connection numbers of line graphs. Ars Combin. 100, 449–463 (2011)
68. Li X, Sun Y (2012) Upper bounds for the rainbow connection numbers of line graphs. Graphs Combin.
28(2), 251–263
69. Li, X., Sun, Y.: On the rainbow k-connectivity of complete graphs. Australasian J. Combin. 49, 217–
226 (2011)
70. Li, X., Sun, Y.: Note on the rainbow k-connectivity of regular complete bipartite graphs. Ars Com-
bin. 101, 513–518 (2011)
71. Li, X., Sun, Y.: Characterize graphs with rainbow connection number m − 2 and rainbow connection
numbers of some graph operations. Preprint (2010)

123
38 Graphs and Combinatorics (2013) 29:1–38

72. Li, X., Sun, Y.: On the strong rainbow connection number. Bull. Malays. Math. Sci. Soc. (2012) (in
press)
73. Li, X., Sun, Y.: Rainbow connection numbers of complementary graphs. Util. Math. 86, 23–31 (2011)
74. Li, X., Sun, Y.: Rainbow Connections of Graphs, Springer Briefs in Mathematics. Springer, New
York (2012)
75. Mader, W.: Ecken vom Grad n in minimalen n-fach zusammenhangenden Graphen. Arch.
Math. 23, 219–224 (1972)
76. Nordhaus, E.A., Gaddum, J.W.: On complementary graphs. Am. Math. Monthly 63, 175–177 (1956)
77. Park, J.H., Chwa, K.Y.: Recursive circulants and their embeddings among hypercubes. Theoret. Com-
put. Sci. 244, 35–62 (2000)
78. Rao, A.: An exposition of Bourgain’s 2-source extractor. in: ECCCTR: Electronic Colloquium on
Computational Complexity, Technical Reports (2007)
79. Rotman, J.J.: An Introduction to the Theory of Groups, GTM 148, Springer, Berlin (1994)
80. Schiermeyer, I.: Rainbow connection in graphs with minimum degree three. IWOCA 2009. In: LNCS,
vol. 5874, pp. 432–437 (2009) (also see Discrete Appl. Math. (in press))
81. Shaltiel, R.: Recent developments in explicit constructions of extractors. Bull. EATCS, 67–95 (2002)
82. Uchizawa, K., Aoki, T., Ito, T., Suzuki, A., Zhou, X.: On the rainbow connectivity of graphs: complexity
and FPT algorithms. In: COCOON 2011, LNCS, vol. 6842, pp. 86–97. Springer, Berlin (2011)
83. Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932)
84. Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Alg. Discrete Meth-
ods 3(3), 351–358 (1982)

123