Rainbow Connections of Graphs

SpringerBriefs in Mathematics

For further volumes: http://www.springer.com/series/10030

Xueliang Li • Yuefang Sun

Rainbow Connections of Graphs

123

Xueliang Li Center for Combinatorics Nankai University Tianjin 300071, P.R. China [email protected]

Yuefang Sun Center for Combinatorics Nankai University Tianjin 300071, P.R. China [email protected]

ISSN 2191-8198 e-ISSN 2191-8201 ISBN 978-1-4614-3118-3 e-ISBN 978-1-4614-3119-0 DOI 10.1007/978-1-4614-3119-0 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2012932206 Mathematics Subject Classification (2010): 05C15, 05C40, 05C69, 05C75, 05C76, 05C80, 68M10, 68Q17, 68Q25, 68R10, 90B18, 90C27, 94C15 © Xueliang Li, Yuefang Sun 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface

The concept of rainbow connection of a graph was first introduced by G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang in 2006. Let G be a nontrivial connected 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-colored graph G is rainbow connected if every two distinct 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, every connected graph has a trivial edge-coloring that makes it rainbow connected by coloring edges with distinct colors. Thus, we define the rainbow connection number of a connected graph G, denoted by rc(G), as the smallest number of colors that are needed in order to make G rainbow connected. A rainbow coloring using rc(G) colors is called a minimum rainbow coloring. Obviously, the rainbow connection number can be viewed as a new kind of chromatic index. The rainbow connection number is not only a natural combinatorial measure, but it also has applications to the secure transfer of classified information between agencies. In addition, the rainbow connection number can also be motivated by its interesting interpretation in the area of networking. 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 channel (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 rc(G). There is a vertex version of the rainbow connection, called the rainbow vertexconnection number rvc(G), which was introduced by M. Krivelevich and R. Yuster. There are also the concepts of strong rainbow connection or rainbow diameter, the rainbow connectivity, and the rainbow index. For details, we refer to Sect. 1.4 of this book. The rainbow connections of graphs are very new concepts. Recently, there has been great interest in these concepts and a lot of results have been published. The goal of this book is to bring together most of the results that deal with rainbow v

vi

Preface

connections of graphs. We begin with an introductory chapter. In Chap. 2, we address the computing complexity of the rainbow connections. In general, it is NP-hard. Many upper bounds have been obtained in the literature, which appear in Chap. 3. In Chaps. 4 and 5, dense and sparse graphs and some graph classes are studied. Chapter 6 concerns graph products, such as the Cartesian product, the direct product, the strong product, and the composition or lexicographic product of graphs. Chapter 7 is on the rainbow connectivity, which actually includes the rainbow k-connectivity, the k-rainbow index, and the (k, )-rainbow index. In the final chapter, results of the vertex version, the rainbow vertex-connection number, are reported. In each chapter we list conjectures, open problems, or questions at appropriate places. We hope that this can motivate more young graph theorists and graduate students to do further study in this subject. We do not give proofs for all results. Instead, we only select some of them for which we give their proofs because we feel that these proofs employed some typical techniques, and these proof techniques are popular in the study of rainbow connections. New results are still appearing. There must be some or even many of them for which we have not realized their existence, and therefore have not included them in this book. The readers of the book are expected to have some background in graph theory and some related knowledge in combinatorics, probability, algorithms, and complexity analysis. All relevant notions from graph theory are properly defined in Chap. 1, but also elsewhere where needed. The anticipated readers of the book are mathematicians and students of mathematics, whose fields of interest are graph theory, combinatorial optimization as well as communication network design. Consequently, the present book will be found suitable for courses in these fields. The exposition of the details of the proofs of some main results will enable students to understand and eventually master a good part of graph theory and combinatorial optimization. People working on communication networks may also be interested in some aspects of the book. They will find it useful for designing networks that can securely transfer classified information. The material presented in this book was used in graph theory seminars, held three times at Nankai University, in 2009, 2010, and 2011. We thank all the members of our group for their help in the preparation of this book. Without their help, we would have not finished writing it in such a short period of time. We also thank the Natural Science Foundation of China (NSFC) for financial support to our research project on rainbow connections. Last, but not least, we are very grateful to the editor for algebraic combinatorics and graph theory of this new series of books of Springer Briefs, Professor Ping Zhang, for inviting us to write this book. Without her encouragement, this book may not exist. Xueliang Li and Yuefang Sun Tianjin, China

Contents

1

Introduction .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.2 Motivation and Examples .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.3 Basic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4 Rainbow Vertex-Connection, Rainbow Connectivity, Rainbow Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

1 1 3 6 11

2 Algorithms and Computational Complexity .. . . . . . . . .. . . . . . . . . . . . . . . . . . . .

15

3 Upper Bounds for Rainbow Connection Numbers . . .. . . . . . . . . . . . . . . . . . . . 3.1 Bounds in Terms of Order and Minimum Degree .. . . . . . . . . . . . . . . . . . . . 3.2 Bounds in Terms of Connectivity . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.3 Bounds in Terms of Radius and Bridges . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.4 Complementary Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.5 Miscellaneous Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 3.6 Bound for Strong Rainbow Connection Number ... . . . . . . . . . . . . . . . . . . .

25 25 36 43 47 51 52

4 Dense and Sparse Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 4.1 Dense Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 4.2 Sparse Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

57 57 62

5 Rainbow Connection Numbers of Some Graph Classes . . . . . . . . . . . . . . . . . 5.1 Line Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 5.2 Other Graph Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

65 65 70

6 Rainbow Connection Numbers of Graph Products . .. . . . . . . . . . . . . . . . . . . .

73

7 Rainbow Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 7.1 Rainbow k-Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 7.2 k-Rainbow Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 7.3 (k, )-Rainbow Index .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

77 77 85 87

vii

viii

Contents

8 Rainbow Vertex-Connection Number . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

89

References .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .

97

Index . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 101

Chapter 1

Introduction

1.1 Basic Concepts In this section, we want to collect most of the terminology and notations used in this monograph. For those not given here, they will be defined when needed. All graphs considered in this book are finite, simple, and undirected. We follow the terminology and notations 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, and E[X] the edge set of G[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 we denote V (G ) = G∈G V (G), and  E(G ) = G∈G E(G), which is the union of all the graphs in G . A clique of a graph G is defined as 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 path on n vertices is denoted by Pn , whose length is n − 1 and denoted by (Pn ). 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 by Cn a cycle on n vertices. For n ≥ 3, the wheel Wn is constructed by joining a new vertex to every vertex of Cn . Let Ks,t be a complete bipartite graph whose sizes of two parts are s,t, respectively. The line graph of a graph G is the graph L(G) (or L1 (G)) whose vertex set V (L(G)) = E(G) and two vertices e1 , e2 of L(G) are adjacent if and only if they are adjacent in G. The iterated line graph of a graph G, denoted by L2 (G), is the line graph of the graph L(G). More generally, the k-iterated line graph Lk (G) is the line graph of Lk−1 (G) (k ≥ 2). An intersection graph of a family F of sets 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 nonempty intersection. An interval graph is an intersection X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 1, © Xueliang Li, Yuefang Sun 2012

1

2

1 Introduction

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 independent 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 neighbor of the third. A graph without ATs is called an AT - f ree graph [25]. 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 ) such that N(a1 ) ⊆ N(a2 ) ⊆ · · · ⊆ N(ak ) [96]. Let Γ be a group [88], and let a be an element of Γ. We use a to denote the cyclic subgroup of Γ generated by a. The number of elements of a is called the order 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 xy−1 ∈ S (or equivalently, yx−1 ∈ S), where S ⊆ Γ \ {1} is closed under taking inverse. A k-regular graph G of order v is said to be strongly regular and denoted by SRG(v, k, λ , μ ) if there are integers λ and μ such that every two adjacent vertices have λ common neighbors and every two nonadjacent vertices have μ common neighbors. Let G be a connected graph. 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) := maxx∈V (G) d(v, x). The diameter of G is diam(G) := maxx∈V (G) ecc(x). The radius of G is rad(G) := minx∈V (G) ecc(x). Distance between a vertex v and a set S ⊆ V (G) is d(v, S) := minx∈S d(v, x). The k-step open neighborhood 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 [55] if every vertex that is not dominated by it has at least k neighbors that are dominated by it. In [13], Chandran, Das, Rajendraprasad, and Varma 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 (1) every pendant vertex of G is included in D and (2) every vertex in N 2 (D) has at least two neighbors in N 1 (D). Note that if δ (G) ≥ 2, then every (connected) dominating set in G is a (connected) two-way dominating set. Let F be a subgraph of a graph G. An ear of F in G is a nontrivial path in G whose ends are in F but whose internal vertices are not. A nested sequence of graphs is a sequence (G0 , G1 , · · · , Gk ) of graphs such that Gi ⊂ Gi+1 , 0 ≤ i < k. An ear

1.2 Motivation and Examples

3

decomposition of a 2-connected graph G is a nested sequence (G0 , G1 , · · · , Gk ) of  2-connected subgraphs of G such that: (1) G0 is a cycle; (2) Gi = Gi−1 Pi , where Pi is an ear of Gi−1 in G, 1 ≤ i ≤ k; (3) Gk = G. A subgraph H of a graph G is called isometric if the distance between every 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. We use g(G) to denote the girth of G, that is, the length of a shortest cycle of G, and use δ (G) to denote the minimum degree of a graph G. The join of two disjoint graphs G and H, denoted by G ∨ H, is the graph with vertex set V (G) ∪V (H) and edge set E(G) ∪ E(H) ∪ {uv|u ∈ V (G), v ∈ V (H)}. The Cartesian product of G and H is the graph GH whose vertex set is V (G) × V (H) and whose edge set is the set of pairs (u, v)(u , v ) such that either uu ∈ E(G) and v = v , or vv ∈ E(H) and u = u . The direct product G × H of G and H has the vertex set V (G)×V (H), and two vertices (u, v) and (u , v ) are adjacent if the projections on both coordinates are adjacent, i.e., uu ∈ E(G) and vv ∈ E(H). The strong product 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 pairs (u, v)(u , v ) such that either uu ∈ E(G) and v = v , or vv ∈ E(H) and u = u , or uu ∈ E(G) and vv ∈ E(H). One can see that the strong product of two graphs is the union of the Cartesian product and the direct product of them. The composition (lexicographic product) of 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).

1.2 Motivation and Examples Connectivity is one of the most fundamental graph-theoretic subjects, both in combinatorial sense and the algorithmic sense. There are many elegant and powerful results on connectivity in graph theory. There are also many ways to strengthen the connectivity concept, such as requiring hamiltonicity, k-connectivity, imposing bounds on the diameter, requiring the existence of edge-disjoint spanning trees, and so on. An interesting way to quantitatively strengthen the connectivity requirement, the rainbow connection, was first introduced by Chartrand et al. [15] in 2006, which is restated as follows: This new concept comes from the secure 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 secure transfer of classified information after the September 11, 2001 terrorist attacks. Ericksen [38] made the following observation: An unanticipated aftermath of those deadly attacks was the

4

1 Introduction

realization that law enforcement and intelligence agencies could not 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 twofold 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 has a graph-theoretic model. Let G be a nontrivial connected 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-colored graph G is rainbow connected if every two distinct 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, every connected graph has a trivial edge-coloring that makes it rainbow connected, namely by coloring edges with distinct colors. Thus, we define the rainbow connection number of a connected graph G, denoted by rc(G), as the smallest number of colors that are needed in order to make G rainbow connected [15]. A rainbow coloring using rc(G) colors is called a minimum rainbow coloring. So the question mentioned above can be modeled by means of computing the value of rainbow connection number. Obviously, the rainbow connection number can be viewed as a new kind of chromatic index. For a basic introduction to the topic, we refer the readers to Chap. 11 in [19]. The readers also can see [81] for a survey. In addition to regarding rainbow coloring as a natural combinatorial measure and its application for the secure transfer of classified information between agencies, rainbow connection 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 channel (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 rc(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). A graph G is strongly rainbow connected if there exists a rainbow u − v geodesic for every pair of distinct 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

1.2 Motivation and Examples

5

Fig. 1.1 A rainbow 3-coloring and a strong rainbow 4-coloring of the Petersen graph

Fig. 1.2 A graph G with rc(G) = src(G) = 4

3 1 2

a u1 4 v1

1

2

1

3 1

2 3

3

1

u 3 2 u3 u2 4 4 2 3 v2 v

1

v3

2

3

1 2 3

1 2

b u1 2 v1

1

3

1

2

4 1

2 3

3

1

u 3 2 u2 v2

2 4 4 3

u3 v3

v

number of a connected graph G, denoted by src(G), as the smallest number of colors that are needed in order to make G strong rainbow connected [15]. Note that this number is also called the rainbow diameter number in [12]. A strong rainbow coloring of G using src(G) colors is called a minimum strong rainbow coloring of G. Clearly, we have diam(G) ≤ rc(G) ≤ src(G) ≤ m, where diam(G) denotes the diameter of G and m is the size of G. To illustrate these new concepts, the authors of [15] considered the Petersen graph P of Fig. 1.1, where a rainbow 3-coloring of P is also shown. Thus rc(P) ≤ 3. On the other hand, if u and v are two nonadjacent vertices of P, then d(u, v) = 2 and so the length of a u − v path is at least 2. Thus, any rainbow coloring of P uses at least two colors and so rc(P) ≥ 2. If P has a rainbow 2-coloring c, then there exist two adjacent edges of G that are colored the same by c, say e = uv and f = vw are colored the same. Since there is exactly one u − w path of length 2 in P, there is no rainbow u − w path in P, which is a contradiction. Therefore, rc(P) = 3. Since rc(P) = 3, it follows that src(P) ≥ 3. Furthermore, since the chromatic index of the Petersen graph is known to be 4, any 3-coloring c of the edges of P results in two adjacent edges uv and vw being assigned the same color. Since u, v, w is the only u − w geodesic in P, the coloring c is not a strong rainbow coloring. Because the 4-coloring of the edges of P shown in Fig. 1.1 is a strong rainbow coloring, then src(P) = 4. As another example, they considered the graph G of Fig. 1.2a, where a rainbow 4-coloring of G is also shown. In fact, c is a minimum rainbow coloring of G and so rc(G) = 4, as we now verify. Since diam(G) ≥ 3, it follows that rc(G) ≥ 3. Assume, to the contrary, rc(G) = 3. Then there exists a rainbow 3-coloring c of G. Since every u − v path in G has length 3, at least one of the three u − v paths in G is a rainbow u − v path, say u, u1 , v1 , v is a rainbow u − v path. We may assume that c (uu1 ) = 1, c (u1 v1 ) = 2, and c (v1 v) = 3. (See Fig. 1.2b.)

6

1 Introduction

If x and y are two vertices in G such that d(x, y) = 2, then G contains exactly one x − y path of length 2, while all other x − y paths have length 4 or more. This implies that no two adjacent edges can be colored the same. Thus we may assume, without loss of generality that c (uu2 ) = 2 and c (uu3 ) = 3. (See Fig. 1.2b.) Thus {c (vv2 ), c (vv3 )} = {1, 2}. If c (vv2 ) = 1 and c (vv3 ) = 2, then c (u2 v2 ) = 3 and c (u3 v3 ) = 1. In this case, there is no rainbow u1 − v3 path in G. On the other hand, if c (vv2 ) = 2 and c (vv3 ) = 1, then c (u2 v2 ) ∈ {1, 3} and c (u3 v3 ) = 2. If c (u2 v2 ) = 1, then there is no rainbow u2 − v3 path in G; while if c (u2 v2 ) = 3, there is no rainbow u2 − v1 path in G, a contradiction. Therefore, as claimed, rc(G) = 4. Since 4 = rc(G) ≤ src(G) for the graph G of Fig. 1.2 and the rainbow 4-coloring of G in Fig. 1.2a is also a strong rainbow 4-coloring, then src(G) = 4 as well.

1.3 Basic Results In [15], Chartrand, Johns, McKeon, and Zhang did some basic research on the (strong) rainbow connection numbers of graphs. They determined the precise values of (strong) rainbow connection numbers for several special graph classes including trees, complete graphs, cycles, wheel graphs, complete bipartite graphs, and complete multipartite graphs. We list these results and give a detailed proof only for Proposition 1.3.4. Proposition 1.3.1 ([15]). Let G be a nontrivial connected graph of size m. Then (a) (b) (c)

rc(G) = 1 if and only if G is complete, src(G) = 1 if and only if G is complete; rc(G) = 2 if and only if src(G) = 2; rc(G) = m if and only if G is a tree, src(G) = m if and only if G is a tree.

Proposition 1.3.2 ([15]). For each integer n ≥ 4, rc(Cn ) = src(Cn ) = n2 . Proposition 1.3.3 ([15]). For each integer n ≥ 3, we have ⎧ ⎨ 1 if n = 3, rc(Wn ) = 2 if 4 ≤ n ≤ 6, ⎩ 3 if n ≥ 7, and src(Wn ) = n3 . Proposition 1.3.4 ([15]). For integers s and t with 2 ≤ s ≤ √ √ t, rc(Ks,t ) = min { s t, 4}, and for integers s and t with 1 ≤ s ≤ t, src(Ks,t ) = s t. Proof. We first prove the latter part.√Since src(K1,t ) = t, the result√follows for s = 1. So we may assume that s ≥ 2. Let s t = k. Hence, 1 ≤ k − 1 < s t ≤ k. Therefore, (k − 1)s < t ≤ ks and so (k − 1)s + 1 ≤ t ≤ ks . First, we show that src(Ks,t ) ≥ k. Assume, to the contrary, that src(Ks,t ) ≤ k − 1. Then there exists a strong rainbow (k − 1)-coloring of Ks,t . Let U and W be the partite sets of Ks,t , where |U| = s and |W | = t. Suppose that U = {u1 , u2 , · · · , us }.

1.3 Basic Results

7

Let there be given a strong rainbow (k − 1)-coloring c of Ks,t . For each vertex w ∈ W , we can associate an ordered s-tuple code(w) = (a1 , a2 , · · · , as ) called the color code of w, where ai = c(ui w) for 1 ≤ i ≤ s. Since 1 ≤ ai ≤ k − 1 for each i(1 ≤ i ≤ s), the number of distinct color codes of the vertices of W is at most (k − 1)s . However, since t > (k − 1)s , there exist at least two distinct vertices w and w of W such that code(w ) = code(w ). Since c(ui w ) = c(ui w ) for all i(1 ≤ i ≤ s), it follows that Ks,t contains no rainbow w − w geodesic in Ks,t , contradicting our assumption that c is a strong rainbow (k − 1)-coloring of Ks,t . Thus, as claimed, src(Ks,t ) ≥ k. Next, we show that src(Ks,t ) ≤ k, which we establish by providing a strong rainbow k-coloring of Ks,t . Let A = {1, 2, · · · , k} and B = {1, 2, · · · , k − 1}. The sets As and Bs are Cartesian products of the s sets A and s sets B, respectively. Thus, |As | = ks and |Bs | = (k − 1)s . Hence, |Bs | < t ≤ |As |. Let W = {w1 , w2 , · · · , wt }, where the vertices of W are labeled with t elements of As and such that the vertices w1 , w2 , · · · , w(k−1)s are labeled by the (k − 1)s elements of Bs . For each i with 1 ≤ i ≤ t, denote the label of wi by wi = (wi,1 , wi,2 , · · · , wi,s ). For each i with 1 ≤ i ≤ (k − 1)s , we have 1 ≤ wi, j ≤ k − 1 for 1 ≤ j ≤ s. We now define a coloring c : E(Ks,t ) → {1, 2, · · · , k} of the edges of Ks,t in which c(wi u j ) = wi, j for 1 ≤ i ≤ t and 1 ≤ j ≤ s. Thus, for 1 ≤ i ≤ t, the color code code(wi ) of wi provided by the coloring c is in fact wi . Hence, distinct vertices in W have distinct color codes. We show that c is a strong rainbow k-coloring of Ks,t . Certainly, for wi ∈ W and u j ∈ U, the wi − u j path wi , u j is a rainbow geodesic. Let wa and wb be two vertices of W . Since these vertices have distinct color codes, there exists some  with 1 ≤  ≤ s such that code(wa ) and code(wb ) have different -th coordinates. Thus, c(wa u ) = c(wb u ) and wa , u , wb is a rainbow wa − wb geodesic in Ks,t . We now consider two vertices u p and uq in U, where 1 ≤ p < q ≤ s. Since there exists a vertex wi ∈ W with 1 ≤ i ≤ (k − 1)s such that wi,p = wi,q , it follows that u p , wi , uq is a rainbow u p − uq geodesic in Ks,t . Thus, as claimed, c is a strong rainbow k-coloring of Ks,t and so src(Ks,t ) ≤ k. √ Next we will prove the former part. First, observe that for 2 ≤ s ≤ t, s t ≥ 2. Let U and W be the partite sets of Ks,t , where |U| = s and |W | = t. Suppose that U = {u1 , u2 , · · · , us }. We consider three cases. √ √ Case 1. s t = 2. Then, s ≤ t ≤ 2s . Since 2 ≤ rc(Ks,t ) ≤ src(Ks,t ) = s t = 2, it follows that rc(Ks,t ) = 2. √ √ Case 2. s t = 3. Then, 2s + 1 ≤ t ≤ 3s . Since 2 ≤ rc(Ks,t ) ≤ src(Ks,t ) = s t = 3, it follows that rc(Ks,t ) = 2 or 3. We claim that rc(Ks,t ) = 3. Assume, to the contrary, that there exists a rainbow 2-coloring of Ks,t . Corresponding to this rainbow 2coloring of Ks,t , there is a color code code(w) assigned to each vertex w ∈ W , consisting of an ordered s-tuple (a1 , a2 , · · · , as ), where ai = c(ui w) ∈ {1, 2} for 1 ≤ i ≤ s. Since t > 2s , there exist two distinct vertices w and w of W such that code(w ) = code(w ). Since the edges of every w − w path of length 2 are colored the same, there is no rainbow w − w path in Ks,t , a contradiction. Thus, as claimed, rc(Ks,t ) = 3. √ Case 3. s t ≥ 4. Then t ≥ 3s + 1. We claim that rc(Ks,t ) = 4. First, we show that rc(Ks,t ) ≥ 4. Assume, to the contrary, that there exists a rainbow 3-coloring of

8

1 Introduction

Ks,t . In this case, corresponding to this rainbow 3-coloring of Ks,t , there is a color code, code(w), assigned to each vertex w ∈ W , consisting of an ordered s-tuple (a1 , a2 , · · · , as ), where ai = c(ui w) ∈ {1, 2, 3} for 1 ≤ i ≤ s. Since t > 3s , there exist two distinct vertices w and w of W such that code(w ) = code(w ). Since every w − w path in Ks,t has even length, the only possible rainbow w − w path must have length 2. However, since code(w ) = code(w ), the colors of the edges of every w − w path of length 2 are the same. Hence, there is no rainbow w − w path in Ks,t , a contradiction. Thus, as claimed, rc(Ks,t ) ≥ 4. To verify that rc(Ks,t ) ≤ 4, we show that there exists a rainbow 4-coloring of Ks,t . Let A = {1, 2, 3}, W = {w1 , w2 , · · · , wt }, W = {w1 , w2 , · · · , w3s }, and W = W −W . Assign to the vertices in W the 3s distinct elements of As and assign to the vertices in W the identical code whose first coordinate is 4 and all whose remaining coordinates are 3. Corresponding to this assignment of codes is a coloring of the edges of Ks,t , where c(wi u j ) = k if the j-th coordinate of code(wi ) is k. We claim that this coloring is, in fact, a rainbow 4-coloring of Ks,t . Let x and y be two nonadjacent vertices of Ks,t . Suppose first that x, y ∈ W . We consider three subcases. Subcase 3.1. x, y ∈ W . Since code(x) = code(y), there exists an i with 1 ≤ i ≤ s such that code(x) and code(y) have different i-th coordinates. Then the path x, ui , y is a rainbow x − y path of length 2 in Ks,t . Subcase 3.2. x ∈ W and y ∈ W . Suppose that the first coordinate of code(x) is a, where 1 ≤ a ≤ 3. Then x, u1 , y is a rainbow x − y path of length 2 in Ks,t whose edges are colored a and 4. Subcase 3.3. x, y ∈ W . Let z ∈ W such that the first coordinate of code(z) is 1 and the second coordinate of code(z) is 2. Then x, u1 , z, u2 , y is a rainbow x − y path of length 4 in Ks,t whose edges are colored 4, 1, 2, 3, respectively. Finally, suppose that x, y ∈ U. Then x = ui and y = u j , where 1 ≤ i < j ≤ s. Then there exists a vertex w ∈ W whose i-th and j-th coordinates are distinct. Then x, w, y is a rainbow x − y path in Ks,t . Thus, this coloring is a rainbow 4-coloring of Ks,t and so rc(Ks,t ) = 4.   Proposition 1.3.5 ([15]). Let G = Kn1 ,n2 ,...,nk be a complete k-partite graph, where k ≥ 3 and n1 ≤ n2 ≤ . . . ≤ nk such that s = ∑k−1 i=1 ni and t = nk . Then ⎧ ⎪ ⎨1 rc(G) = 2 ⎪ √ ⎩ min{ s t, 3} and

⎧ ⎪ ⎨1 src(G) = 2 ⎪ ⎩ √

s t

if nk = 1, if nk ≥ 2 and s > t, if s ≤ t,

if nk = 1, if nk ≥ 2 and s > t, if s ≤ t.

1.3 Basic Results

9

By Proposition 1.3.1, it follows that for every positive integer a and for every tree T of size a, rc(T ) = src(T ) = a. Furthermore, for a ∈ {1, 2}, rc(G) = a if and only if src(G) = a. If a = 3, b ≥ 4, then by Proposition 1.3.3, rc(W3b ) = 3 and src(W3b ) = b. For a ≥ 4, we have the following. Theorem 1.3.6 ([15]). Let a and b be positive integers with a ≥ 4 and b ≥ Then there exists a connected graph G such that rc(G) = a and src(G) = b.

5a−6 3 .

Then, combining Propositions 1.3.1 and 1.3.3 with Theorem 1.3.6, they got the following result. Corollary 1.3.7 ([15]). 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 rc(G) = a and src(G) = b. Finally, they considered the question of whether the condition b ≥ 5a−6 3 can be deleted. This was left by them as a conjecture in [15] and recently has been settled down by Chen and Li in [24]. Theorem 1.3.8 (Conjecture 3.3 of [15]). Let a and b be positive integers. Then there exists a connected graph G such that rc(G) = a and src(G) = b if and only if a = b ∈ {1, 2} or 3 ≤ a ≤ b. Proof. The necessity is clear. For the sufficiency, when a = b ∈ {1, 2}, from Corollary 1.3.7, the conjecture is true. So, we just need to consider the situation when 3 ≤ a ≤ b. Let n = 3b(b − a + 2), and let Hn be the graph consisting of an n-cycle Cn : v1 , v2 , · · · , vn and another two vertices w and v, each of which joins to every vertex of Cn . Let G be the graph constructed from Hn of order n + 2 and the path Pa−1 : u1 , u2 , · · · , ua−1 on a − 1 vertices by identifying v and ua−1 . First, we will show that rc(G) = a. Clearly, we have rc(G) ≥ diam(G) = a. It remains to show that rc(G) ≤ a. Note that n = 3b(b − a + 2) ≥ 18. Define a coloring c for the graph G by the following rules: ⎧ i if e = ui ui+1 for 1 ≤ i ≤ a − 2, ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ a − 1 if e = vi v and i is odd, c(e) = a if e = vi v and i is even, ⎪ ⎪ ⎪ ⎪a if e = vi w and 1 ≤ i ≤ n, ⎪ ⎪ ⎩ 1 otherwise. Since c is a rainbow a-coloring of the edges of G, it follows that rc(G) ≤ a. This implies rc(G) = a. Next, we will show that src(G) = b. We first show that src(G) ≤ b, by giving a strong rainbow b-coloring c for the graph G as follows:

10

1 Introduction

⎧ i if e = ui ui+1 for 1 ≤ i ≤ a − 2, ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ a − 2 + i if e = v3b(i−1)+ j v for 1 ≤ i ≤ b − a + 2 and 1 ≤ j ≤ 3b, ⎪ ⎪ ⎪ ⎪ ⎪ if e = v3( j−1)b+3(i−1)+kw for 1 ≤ j ≤ b − a + 2 and 1 ≤ i ≤ b ⎪ ⎨i c(e) = and 1 ≤ k ≤ 3, ⎪ ⎪ ⎪ ⎪ 1 if e = v3(i−1)+1 v3(i−1)+2 for 1 ≤ i ≤ b(b − a + 2), ⎪ ⎪ ⎪ ⎪ ⎪ 2 if e = v3(i−1)+2 v3(i−1)+3 for 1 ≤ i ≤ b(b − a + 2), ⎪ ⎪ ⎪ ⎩ 3 otherwise It remains to show that src(G) ≥ b. By contradiction, suppose that src(G) < b. Then there exists a strong rainbow (b − 1)-coloring c : E(G) → {1, 2, · · · , b − 1}. For every vi (1 ≤ i ≤ n), d(vi , u1 ) = a − 1, and the path vi , v, ua−2 , · · · , u1 is the only path of length a − 1 connecting vi and u1 , and so vi , v, ua−2 , · · · , u1 is a rainbow path. Without loss of generality, suppose that c(u2 u1 ) = 1, c(u3 u2 ) = 2, · · · , c(ua−1 ua−2 ) = a − 2. Then c(vi v) ∈ {a − 1, a, · · · , b}, for 1 ≤ i ≤ n. We first consider the set of edges A = {vi v, 1 ≤ i ≤ n}, and so |A| = n. Thus, there exist at n least b−a+1  ≥ 3b + 1 edges in A colored the same. Suppose there exist m edges n v j1 v, · · · , v jm v, (1 ≤ j1 < j2 < · · · < jm ≤ n) colored the same and m ≥ b−a+1 ≥ 3b+1. Secondly, we consider the set of edges B = {v j1 w, · · · , v jm w}. Since c(v ji w) ∈ m  ≥ 3b+1 {1, 2, · · · , b−1}, for 1 ≤ i ≤ m, there exist at least b−1 b−1  ≥ 4 edges colored the same. Thus, from B we can choose 4 edges of the same color. Since n ≥ 18, from the corresponding vertices on the cycle Cn of the four edges chosen above, we can get two vertices such that their distance on the cycle Cn is more than 3. Without loss of generality, we assume that the two vertices are v1 , v2 and their distance in graph G is 2. Then the geodesic between v1 and v2 in graph G is either v1 , w, v2 or v1 , v, v2 . However, neither v1 , w, v2 nor v1 , v, v2 is a rainbow path. Thus, the coloring c is not a strong rainbow coloring of G, a contradiction. Therefore src(G) ≤ b and so src(G) = b. The proof is thus complete.   From the above propositions, we know that rc(G) = src(G) hold for some special graph classes. The following problem may be challenging. Problem 1.1. Characterize those graphs G for which rc(G) = src(G) or describe sufficient conditions to guarantee rc(G) = src(G). Estimate the difference src(G) − rc(G) in terms of other graph parameters or under some structural conditions. Li et al. [57] showed that for hypercubes and many Cayley graphs G, rc(G) = src(G) holds. See Theorem 5.2.4. From the definition, it is easy to see that if H is a connected spanning subgraph of G, then rc(G) ≤ rc(H). This fact is very useful to bounding the value of rc(G) by giving bounds for its connected spanning subgraphs. We have noted that if, in addition, diam(H) = 2, then src(G) ≤ src(H). The authors of [15] naturally raised the following conjecture: If H is a connected spanning subgraph of a nontrivial (connected) graph G, then src(G) ≤ src(H). This conjecture was

1.4 Rainbow Vertex-Connection, Rainbow Connectivity, Rainbow Index

11

disproved, however, by Chakraborty et al. [12]. They presented the following example G: Take two disjoint copies of K1,6 with centers u and v and leaves {u1 , · · · , u6 } and {v1 , · · · , v6 }, respectively. The graph H is obtained by identifying ui and vi for i = 1, 2, 3, and the graph G is then 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 uses at least seven colors to ensure its strong rainbow connection. It is easy to have the following observations: Theorem 1.3.9 ([78]). If G is a connected graph, and G is obtained from G by splitting a vertex v, then rc(G ) ≤ rc(G) + 1. In particular, if G is obtained from G by subdividing an edge e, then rc(G ) ≤ rc(G) + 1. Theorem 1.3.10 ([11]). If G is a connected graph and H1 , · · · , Hk is a partition of the vertex set of G into connected subgraphs, then rc(G) ≤ k − 1 + ∑ki=1 rc(Hi ). From this result, one immediately gets: Theorem 1.3.11 ([90]). Let G be a connected graph and H be a connected subgraph of G. Let G denote the graph obtained from G by contracting H to a single vertex. Then rc(G) ≤ rc(G ) + rc(H).

1.4 Rainbow Vertex-Connection, Rainbow Connectivity, Rainbow Index As one can see, the above rainbow connection number involves edge-colorings of graphs. A natural idea is to generalize it to a concept that involves vertexcolorings. Krivelevich and Yuster [55] are the first to introduce a new parameter corresponding to the rainbow connection number which is defined on a vertexcolored graph. A vertex-colored graph G is rainbow vertex-connected if its every two distinct 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 vertex-connection number of a connected graph G, denoted by rvc(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 rvc(G) ≤ n − 2 (except for the singleton graph), and rvc(G) = 0 if and only if G is a complete graph. Note that an uncolored graph is also viewed as a vertex-colored graph with 0 color. Also clearly, rvc(G) ≥ diam(G) − 1 with equality if the diameter of G is 1 or 2. Note that rvc(G) may be much smaller than rc(G) for some graph G. For example, rvc(K1,n−1 ) = 1 while rc(K1,n−1 ) = n − 1. rvc(G) may also be much larger than rc(G) for some graph G. For example, take n vertex-disjoint triangles and, by designating a vertex from each of them, add a complete graph on the designated vertices. This graph has n cut vertices and hence rvc(G) ≥ n. In fact, rvc(G) = n

12

1 Introduction

by coloring only the cut vertices with distinct colors. On the other hand, it is not difficult to see that rc(G) ≤ 4. Just color the edges of the Kn with, say, color 1, and color the edges of each triangle with the colors 2, 3, 4. In a rainbow coloring, we only need to find one rainbow path connecting any two vertices. So another natural generalization is as follows: the number of rainbow paths between any two vertices is at least an integer k with k ≥ 1 in some edgecoloring. A well-known theorem of Menger [83] shows that in every κ -connected graph G with κ ≥ 1, there are k internally disjoint u − v paths connecting every 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 rainbow u − v paths connecting any two distinct vertices u and v. Chartrand et al. [16] defined the rainbow k-connectivity rck (G) of G to be the minimum integer j such that there exists a j-edge-coloring which is a rainbow kcoloring. A rainbow k-coloring using rck (G) colors is called a minimum rainbow k-coloring. By definition, rck (G) is a generalization of rc(G) and rc1 (G) = rc(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 internally disjoint rainbow paths and that rck (G) is defined for every 1 ≤ k ≤ κ . So rck (G) is welldefined. Furthermore, rck (G) ≤ rc j (G) for 1 ≤ k ≤ j ≤ κ . Note that this new defined rainbow k-connectivity computes the number of colors, this is distinct with connectivity (edge-connectivity) which computes the number of internally (edge) disjoint paths. So, we could call it rainbow k-connection number. One more generalization of the rainbow connection number was introduced by Chartrand 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 rxk (G) of G is the minimum number of colors needed in a k-rainbow coloring of G. A k-rainbow coloring using rxk (G) colors is called a minimum k-rainbow coloring. Thus rx2 (G) is the rainbow connection number rc(G) of G. It follows, for every nontrivial connected graph G of order n, that rx2 (G) ≤ rx3 (G) ≤ · · · ≤ rxn (G). The following is an easy but useful observation. Suppose that G contains two bridges e = uv and f = xy. Then G− e− f contains three components Gi (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 (G1 ), x ∈ V (G2 ) and v, y ∈ V (G3 ). If S is a set of k vertices containing u and x, then every tree containing 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 1.4.1 ([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 .

1.4 Rainbow Vertex-Connection, Rainbow Connectivity, Rainbow Index

13

From Observation 1.4.1, we know that if G is rainbow connected under some edge-coloring, then any two bridges obtain distinct colors. This observation is used later in proofs frequently. The following is an immediate consequence: Observation 1.4.2 ([90]). Let G be a connected graph on n ≥ 3 vertices with n1 (G) pendant edges. Then rc(G) ≥ max{diam(G), n1 (G)}.

Chapter 2

Algorithms and Computational Complexity

As we saw in the last chapter, for some special graphs the computation of the rainbow connection numbers can be done without much difficulty. However, computing the rainbow connection number for a general graph is a hard problem. For the introduction of complexity theory, see [43]. In [11], Caro, Lev, Roditty, Tuza, and Yuster gave two conjectures (see Conjectures 4.1 and 4.2 in [11]) on the complexity of determining the rainbow connection numbers of graphs. Later, Chakraborty, Fischer, Matsliah and Yuster [12] verified these two conjectures. Theorem 2.0.1 ([12]). Given a graph G, deciding if rc(G) = 2 is NP-complete. In particular, computing rc(G) is NP-hard. Proof. The proof will be divided into three steps: the first step (Claim 1) shows the computational equivalence of the problem of rainbow connection number 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 (Claim 2), we reduce 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 the theorem is completed by reducing the problem 3-SAT to the problem of extending to rainbow connection number 2. Claim 1. The following problems are polynomial-time equivalent: 1. Given a graph G decide whether rc(G) = 2. 2. Given a graph G and a set of pairs P ⊆ V (G) × V (G), decide whether there is an edge-coloring of G with two colors such that all pairs (u, v) ∈ P are rainbow connected. Proof of Claim 1. It is enough to describe a reduction from Problem 2 to Problem 1. Given a graph G = (V, E) and a set of pairs P ⊆ V × V , we construct a graph G = (V  , E  ) as follows. X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 2, © Xueliang Li, Yuefang Sun 2012

15

16

2 Algorithms and Computational Complexity

For every vertex v ∈ V , we introduce a new vertex xv , and for every pair (u, v) ∈ (V × V ) \ P we introduce a new vertex x(u,v) . We set V  = V ∪ {xv : v ∈ V } ∪ {x(u,v) : (u, v) ∈ (V × V ) \ P} and E  = E ∪ {{v, xv } : v ∈ V } ∪ {{u, x(u,v)}, {v, x(u,v) } : (u, v) ∈ (V × V ) \ P} ∪{{x, x } : x, x ∈ V  \ V }. It is not hard to show that G is 2-rainbow connected if and only if there is an edge coloring of G with two colors such that all pairs (u, v) ∈ P are rainbow connected. Claim 2. The first problem defined below is polynomially reducible to the second one: 1. Given a graph G and a partial 2-edge-coloring χˆ : Eˆ → {0, 1} for Eˆ ⊂ E, decide whether χˆ can be extended to a complete 2-edge-coloring χ : E → {0, 1} that makes G rainbow connected. 2. Given a graph G and a set of pairs P ⊆ V (G) × V (G), decide whether there is an edge-coloring of G with two colors such that all pairs (u, v) ∈ P are rainbow connected. Proof of Claim 2. Since the identity of the colors does not matter, it is more convenient that instead of a coloring χ : E → {0, 1} we consider the corresponding partition πχ = (E1 , E2 ) of E. Similarly, in the case of a partial coloring χˆ , the pair πχˆ = (Eˆ1 , Eˆ2 ) will contain the corresponding disjoint subsets of E (which may not cover E). Now, given such a partial coloring χˆ , we extend the original graph G = (V, E) to a graph G = (V  , E  ), and define a set P of pairs of vertices. Let  : V → [|V |] be arbitrary linear ordering of the vertices, and let high: E → V be a mapping that maps an edge e = {u, v} to u if (u) > (v), and to v otherwise. Similarly, let low: E → V be a mapping that maps an edge e = {u, v} to u if (u) < (v), and to v otherwise. We construct G as follows. We add 3 + |Eˆ1| + |Eˆ2| new vertices {b1 , c, b2 } ∪ {ce : e ∈ (Eˆ1 ∪ Eˆ2 )} and add the edges {{b1 , c}, {c, b2 }} ∪ {{bi, ce } : i ∈ {1, 2}, e ∈ Eˆi } ∪ {{ce, low(e)} : e ∈ (Eˆ1 ∪ Eˆ2 )}. Now we define the set P of pairs of vertices that have to be 2-rainbow connected: P = {{b1, b2 }} ∪ {{u, v} : u, v ∈ V } ∪ {{c, ce} : e ∈ (Eˆ1 ∪ Eˆ2 )} ∪{{bi , low(e)} : i ∈ {1, 2}, e ∈ Eˆi } ∪ {{ce, high(e)} : e ∈ (Eˆ1 ∪ Eˆ2 )}. It is not hard to show that the answer for Problem 2 for the resulting graph G is yes if and only if the answer for Problem 1 for the original graph G is yes.

2 Algorithms and Computational Complexity

17

We show that Problem 1 of Claim 2 is NP-hard, and then deduce that 2-rainbowcolorability is NP-complete by applying Claims 1 and 2 while observing that it clearly belongs to NP. We reduce the problem 3-SAT to Problem 1 of Claim 2. Given a 3CNF formula φ = ∧m i=1 ci over variables x1 , x2 , · · · , xn , we construct a graph Gφ and a partial 2-edge coloring χ  : E(Gφ ) → {0, 1} such that there is an extension χ of χ  that makes Gφ rainbow connected if and only if φ is satisfiable. We define Gφ as follows: V (Gφ ) = {ci : i ∈ [m]} ∪ {xi : i ∈ [n]} ∪ {a} E(Gφ ) = {{ci , x j } : x j ∈ ci in φ } ∪ {{xi, a} : i ∈ [n]} ∪ {{ci, c j } : i, j ∈ [m]} ∪{{xi , x j } : i, j ∈ [n]} and we define the partial coloring χ  as follows: ∀ i, j ∈ [m] χ  ({ci , c j }) = 0,

∀i, j ∈ [n] χ  ({xi , x j }) = 0,

∀ {xi , c j } ∈ E(Gφ ) χ  ({xi , c j }) = 0 if xi is positive in c j , 1 otherwise while all the edges in {{xi , a} : i ∈ [n]} (and only they) are left uncolored. Assuming without loss of generality that all variables in φ appear both as positive and as negative, one can verify that a 2-rainbow-coloring of the uncolored edges corresponds to a satisfying assignment of φ and vice versa. 

Chakraborty et al. [12] also proposed a problem. Suppose that we are given a graph G for which we are told that rc(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 ˜ 3/14 ) colors [7]. Dong and Li [32] polynomial time algorithm that colors it with O(n solved this problem by showing a stronger result. Theorem 2.0.2 ([32]). Suppose that we are given a graph G for which we are told that rc(G) = 2. We can rainbow-color it in polynomial time with no more than five colors. For general k, it has been shown in [56] that for every k ≥ 2, deciding if rc(G) = k is NP-complete. Ananth and Nasre in [4] derived the following results. Theorem 2.0.3 ([4]). For every k ≥ 3, deciding whether rc(G) ≤ k is NP-hard. Proof. We only describe the outline of our reduction. Let (G = (V, E), P) be the input to the k-subset rainbow connected problem where P ⊆ V × V . We construct a graph G = (V  , E  ) such that G is a subgraph of G and rc(G ) ≤ k if and only if G is k-subset rainbow connected. To construct G , we first construct a graph Hk = (Wk , Ek ) such that V ⊂ Wk and V  = Wk . Corresponding to the set P of pairs of vertices we associate a set of pairs of vertices Pk with respect to the graph Hk (The set Pk is only a relabeling of pairs of vertices in the set P). Then, the edge disjoint union

18

2 Algorithms and Computational Complexity

of the two graphs G and Hk will yield the graph G . The graph G is constructed such that it satisfies the following two properties: (1) There exists an edge-coloring χ of Hk with k colors such that all pairs of vertices in G except those in P, i. e., all pairs in (V  × V  ) \ P are rainbow connected. Thus, if G is k-subset rainbow connected then there exists a k-edge-coloring of G such that all pairs in P will be rainbow connected. From this, we prove that G can be rainbow colored using k colors if G is k-subset rainbow connected. (2) All paths of length k or less between any pair of vertices in P are contained entirely in G (as a subgraph of G ) itself. This ensures that for a rainbow coloring of G with k colors, any pair of vertices in P should have all its rainbow paths inside G itself. Hence, if G can be rainbow colored with k colors, then G can be edge-colored with k colors such that it is subset rainbow connected with respect to P. We construct the family of graphs Hk inductively. For the base cases k = 2 and k = 3 we give explicit constructions, then show our inductive step. Finally, we describe our graph G . Construction of H2 : The construction of the graph H2 is derived from the reduction of Chakraborty et al. [12] used to prove that the 2-subset rainbow connected problem is NP-hard (see the proof of Theorem 2.0.1). Let H2 = (W2 , E2 ) where the vertex set W2 is defined as follows: (1)

(2)

W2 = W2 ∪W2 , (2)

W2

(1)

W2

= {vi,2 : i ∈ {1, · · · , n}},

= {ui : i ∈ {1, · · · , n}} ∪ {wi, j : (vi , v j ) ∈ (V × V ) \ P}.

The edge set E2 is defined as: (1)

(2)

(3)

E2 = E2 ∪ E2 ∪ E2 ,

(1)

E2 = {(vi,2 , ui ) : i ∈ {1, · · · , n}},

(2)

E2 = {(vi,2 , wi, j ), (v j,2 , wi, j ) : (vi , v j ) ∈ (V ×V ) \ P},

  (3) (2) . E2 = (x, y) : x, y ∈ W2

(1)

The set of vertices in W2 are referred to as base vertices of H2 . Let P2 = {(vi,2 , v j,2 ) : (vi , v j ) ∈ P}. The graph H2 has the property that for all (vi,2 , v j,2 ) ∈ P2 there is no path of length ≤ 2 between vi,2 and v j,2 . Also, if (vi,2 , v j,2 ) ∈ P2 the shortest path between vi,2 and v j,2 is of length 2. Construction of H3 : We now describe the construction of the graph H3 . Let H3 = (W3 , E3 ) be a graph where the vertex set W3 is defined as follows: (1)

(2)

(3)

(1)

W3 = W3 ∪W3 ∪W3 , W3

= {vi,3 : i ∈ {1, · · · , n}},

(2)

= {ui : vi ∈ V } ∪ {ai, j , bi, j : (vi , v j ) ∈ (V × V ) \ P},

(3)

= {ui : vi ∈ V } ∪ {ai, j , bi, j : (vi , v j ) ∈ (V × V ) \ P}.

W3 W3

2 Algorithms and Computational Complexity

19

The edge set E3 is defined as: (1)

(2)

(3)

(4)

(1)

E3 = E3 ∪ E3 ∪ E3 ∪ E3 , E3 = {(vi,3 , ui ) : vi ∈ V }, (2)

E3 = {(vi,3 , ai, j ), (v j,3 , bi, j ) : (vi , v j ) ∈ (V × V ) \ P}, (3)

(2)

(3)

(4)

E3 = {(x, x ) : x ∈ W3 , x ∈ W3 }, E3 = {(ai, j , bi. j ) : (vi , v j ) ∈ (V × V ) \ P}. (1)

The set of vertices in W3 are referred to as base vertices of H3 . Let P3 = {(vi,3 , v j,3 ) : (vi , v j ) ∈ P}. The graph H3 has the property that for all (vi,3 , v j,3 ) ∈ P3 there is no path of length ≤ 3 between vi,3 and v j,3 . Also, if (vi,3 , v j,3 ) ∈ P3 , then the shortest path between vi,3 and v j,3 is of length 3. Inductive Step: Assume that we have constructed Hl−2 = (Wl−2 , El−2 ). From  Hl−2 , we first construct an intermediate graph Hl−2 from which we construct Hl .  The graph Hl−2 is constructed as follows: Each base vertex vi,l−2 in Wl−2 is (1)

(2)

(3)

split into three vertices vi,l−2 ,vi,l−2 ,vi,l−2 and edges are added between them, i. e., (1)

(2)

(3)

the vertices vi,l−2 , vi,l−2 , vi,l−2 form a triangle. Any edge of the form (w, vi,l−2 ) is (1)

(2)

(3)

 = replaced by three edges (w, vi,l−2 ), (w, vi,l−2 ), (w, vi,l−2 ). Formally, the graph Hl−2 (1)

(2)

 , E  ) is defined as follows. The set of vertices is W  = W (Wl−2 l−2 l−2 l−2 ∪Wl−2 where (1)

(1)

(2)

(3)

(2)

Wl−2 = {vi,l−2 , vi,l−2 , vi,l−2 : i ∈ {1, · · · , n}}, Wl−2 = Wl−2 \ {vi,l−2 : i ∈ {1, · · · , n}} (1)

(2)

(3)

 = El−2 ∪ El−2 ∪ El−2 where and the edge set is El−2 (1)

(j )

(2)

(j )

1 , w) : (vi,l−2 , w) ∈ El−2 , j1 ∈ {1, 2, 3}}, El−2 = {(vi,l−2

(j )

(3)

1 2 El−2 = {(vi,l−2 , vi,l−2 ) : j1 , j2 ∈ {1, 2, 3}}, El−2 = El−2 \ {(vi,l−2 , w) : w ∈ Wl−2 }.

 ∪V and E = E  ∪ E  such that The graph Hl = (Wl , El ) where Wl = Wl−2 l l l−2

Vl = {v1,l , · · · , vn,l },

(1)

(2)

(3)

E  = {(vi,l−2 , vi,l ), (vi,l−2 , vi,l ), (vi,l−2 , vi,l ) : 1 ≤ i ≤ n}.

The vertices in Vl are the base vertices of Hl (see Fig. 2.1 for the construction of Hl ). Reduction: Let the instance for k-subset rainbow connected problem be (G = (V, E), P). We construct a graph G as an instance for k-rainbow connected problem as follows: (1) Construct Hk = (Vk , Ek ). (2) Let V  = Wk , E  = Ek ∪ {(vi,k , v j,k ) : (vi , v j ) ∈ E}. Then G = (V  , E  ) is the required graph. We call the induced subgraph of G containing the base vertices as base graph Gk . It can be seen that Gk is isomorphic to G. Then, it is not difficult to check that G is k-subset rainbow connected if and only if G is k-rainbow connected. The details are omitted. 

For the strong rainbow connection number, they obtained a similar result. Theorem 2.0.4 ([4]). For every k ≥ 3, deciding whether src(G) ≤ k, is NP-hard even when G is bipartite.

20

2 Algorithms and Computational Complexity

Fig. 2.1 Construction of Hl

Base vertices

Base vertices

Proof. We will first consider an intermediate problem called the k-subset strong rainbow connected problem which is the decision version of the subset strong rainbow connected problem. The input to the k-subset strong rainbow connected problem is a graph G along with a set of pairs P = {(u, v) : (u; v) ⊆ V × V } and an integer k. Our goal is to answer whether there exists an edge-coloring of G with at most k colors such that every pair (u, v) ∈ P has a geodesic rainbow path. Let G = (V, E) be an instance of the k-vertex-coloring problem. We say that G can be vertex-colored using k colors if there exists an assignment of at most k colors to the vertices of G such that no pair of adjacent vertices are colored using

2 Algorithms and Computational Complexity

21

the same color. This problem is NP-hard for k ≥ 3. Given an instance G = (V, E) of the k-vertex-coloring problem, we construct an instance (G = (V  , E  ), P) of the k-subset strong rainbow connected problem below: V  = {a} ∪V; E  = {(a, v) : v ∈ V },

P = {(u, v) : (u, v) ∈ E}.

It is not hard to show the following claim which establishes the hardness of the k-subset strong rainbow connected problem. Claim 3. The graph G = (V, E) is vertex colorable using k( ≥ 3) colors if and only if the graph G = (V  , E  ) can be colored using k colors such that for every pair (u, v) ∈ P there is a geodesic rainbow path between u and v. Note that our graph G construed in the above reduction is a tree, in fact a star and hence between every pair of vertices there is exactly one path. Thus, all the above arguments apply for the k-subset rainbow connected problem as well. As a consequence we can conclude the following: For every k ≥ 3, the k-subset strong rainbow connected problem and the k-subset rainbow connected problem are NPhard even when the input graph G is a star (which is a bipartite graph). Next, we will show that the problem of deciding whether a graph G can be strongly rainbow colored using k colors is polynomial time equivalent to the k-subset strong rainbow connected problem. Claim 4. The following two problems are reducible to each other in polynomial time: (1) Given a graph G = (V, E) and an integer k, decide whether the edges of G can be colored using k colors such that between every pair of vertices in G there is a geodesic rainbow path. (2) Given a graph G = (V, E), an integer k and a set of pairs P ⊆ V × V , decide whether the edges of G can be colored using k colors such that between every pair (u, v) ∈ P there is a geodesic rainbow path. Proof of Claim 4. It suffices to show that problem (2) reduces to problem (1). Let (G = (V, E), P) be an instance of the k-subset strong rainbow connected problem. As noted above, we know that the k-subset strong rainbow connected problem is NP-hard even when G is a star as well as the pairs (u, v) ∈ P are such that both u and v are leaves of the star. We assume both these properties on the input (G, P) and use it crucially in our reduction. Let us denote the central vertex of the star G by a and the leaves by L = {v1 , v2 , · · · , vn }, that is, V = {a} ∪ L. Using the graph G and the pairs P, we construct a new graph G = (V  , E  ) as follows: For every leaf vi ∈ L we introduce two new vertices ui and ui , and for every pair of leaves (vi , v j ) ∈ (L × L) \ P, we introduce two new vertices wi, j and wi, j . Then the vertex set V  is defined as V  = V ∪V1 ∪V2 , V1 = {ui : i ∈ {1, · · · , n}} ∪ {wi, j : (vi , v j ) ∈ (L × L) \ P}, V2 = {ui : i ∈ {1, · · · , n}} ∪ {wi, j : (vi , v j ) ∈ (L × L) \ P},

22

2 Algorithms and Computational Complexity

and the edge set E  is defined as E  = E ∪ E1 ∪ E2 ∪ E3 , E1 = {(vi , ui ) : vi ∈ L, ui ∈ V1 } ∪ {(vi, wi, j ), (v j , wi, j ) : (vi , v j ) ∈ (L × L) \ P}, E2 = {(x, x ) : x ∈ V1 , x ∈ V2 }, E3 = {(a, x ) : x ∈ V2 }. It is not hard to show that G is strongly rainbow colorable using k colors if and only if there is an edge-coloring of G (using k colors) such that every pair (u, v) ∈ P has a strong rainbow path. The details are omitted. Note that the graph G = (V  , E  ) constructed in the proof of Claim 4 is in fact bipartite, i.e., the vertex set V  can be partitioned into two sets A and B, where A = {a} ∪V1 and B = L ∪V2 such that there are no edges between vertices in the same partition. The result is thus proved. 

From the same construction above, one can see that the following corollary is immediate. Corollary 2.0.5 ([4]). Deciding if the rainbow connection number of a graph G is at most 3 is NP-hard even when G is bipartite. In [64] Li and Li showed that for any fixed integer k, the problems in Theorems 2.0.3 and 2.0.4 as well as Corollary 2.0.5 are all in NP class, and therefore, “NPhard” can be replaced by “NP-complete” in the three results if we replace “For every k” by “For any fixed k.” Corollary 2.0.5 suggests us the following problem. Problem 2.1. For every (any fixed) integer k ≥ 2, deciding if a given bipartite graph G has rc(G) ≤ k is NP-hard (complete). In [12], Chakraborty, Fischer, Matsliah and Yuster also derived some positive algorithmic results. Parts of the following two results will be shown in Theorems 3.1.9 and 4.1.9. Theorem 2.0.6 ([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 rc(G) ≤ C. Furthermore, there is a polynomial time algorithm that constructs a corresponding coloring for a fixed ε . As mentioned above, Theorem 2.0.6 is based upon a modified degree-form version of Szemer´edi 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 [39]). Theorem 2.0.7 ([12]). If G is an n-vertex graph with diameter 2 and minimum degree at least 8logn, then rc(G) ≤ 3. Furthermore, such a coloring is given with high probability by a uniformly random 3-edge-coloring of the graph G, and can also be found by a polynomial time deterministic algorithm. Because computing rc(G) is NP-hard, it was tried to give approximate algorithms to compute the rainbow connection number. Basavaraju, Chandran, Rajendraprasad

2 Algorithms and Computational Complexity

23

and Ramaswamy in [5] presented an (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor 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 constant, then this problem becomes easy. However, if the coloring is arbitrary (with an unbounded number of colors), the problem becomes NP-complete. Theorem 2.0.8 ([12]). The following problem is NP-complete: Given an edgecolored graph G, check whether the given coloring makes G rainbow connected. For the proof of Theorem 2.0.8, Chakraborty, Fischer, Matsliah and Yuster first showed that the s − t version of the problem is NP-complete, that is, given two vertices s and t of an edge-colored graph, decide whether there is a rainbow path connecting them. Then they reduced the problem of Theorem 2.0.8 from it. By subdividing each edge of a given edge-colored graph G exactly once, one can get a bipartite graph G . Then color the edges of G as follows: Let e and e be the two edges of G produced by subdividing at the edge e of G. Then color the edge e with the same color of e and color the edge e with a new color, such that all the new colors of the edges e are distinct. In this way, Li and Li [64] reduced from Theorem 2.0.8 a result: Given an edge-colored bipartite graph G, checking whether the given coloring makes G rainbow connected is NP-complete. Reducing also from Theorem 2.0.8 in a clever way, Huang et al. in [49] first obtained a result: Given an edge-colored planar graph G, checking whether the given coloring makes G rainbow connected is NP-complete. Then by using the same subdividing technique as above, they got the following stronger result. Theorem 2.0.9 ([49]). Given an edge-colored bipartite planar graph G, checking whether the given coloring makes G rainbow connected is NP-complete.

Chapter 3

Upper Bounds for Rainbow Connection Numbers

From Chap. 2, we know that it is almost impossible to give the precise value of the rainbow connection number for a given arbitrary graph. This suggests the problem of determining bounds of it, especially sharp upper bounds. In this chapter, we survey many upper bounds for the rainbow connection numbers in terms of other graph parameters, such as minimum degree and connectivity, etc.

3.1 Bounds in Terms of Order and Minimum Degree In this section, we survey the results on the relationship between the minimum degree δ (G) and the rainbow connection number of a graph G. For δ (G) = 1, there are graphs with minimum degree 1 and with rc(G) = n − 1, say, any trees of order n. For δ (G) = 2, Schiermeyer [90] obtained the following result. Theorem 3.1.1 ([90]). Let G be a connected graph of order n ≥ 3 with minimum / {K3 ,C4 , K4 − e,C5 }, then rc(G) ≤ n − 3. degree δ (G) = 2. If G ∈ In [11], Caro et al. observed that there are graphs with minimum degree 2 and with rc(G) = n − 3 (connecting two vertex-disjoint triangles by a path of length n − 5). Motivated by the above facts, it is interesting to study the rainbow connection number of a graph with minimum degree at least 3 and they considered the following question: Is it true that a graph G with minimum degree at least 3 guarantees that rc(G) ≤ α n where α < 1 is independent of n. This turns out to be true. Caro et al. [11] showed that if G is a connected graph with n vertices and δ (G) ≥ 3, then rc(G) < 56 n. In their proof, they first gave an upper bound for the rainbow connection number of 2-connected graphs (see Theorem 3.2.1), then from it, they next derived an upper bound for the rainbow connection number of a connected bridgeless graph (see Theorem 3.2.11). The constant 56 is not optimal, but it probably cannot be replaced with a constant smaller than 34 since there are 3-regular connected graphs X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 3, © Xueliang Li, Yuefang Sun 2012

25

26

3 Upper Bounds for Rainbow Connection Numbers

with rc(G) = diam(G) = 3n−10 and one such graph can be constructed as follows 4 [89]: Take two vertex-disjoint copies of the graph K5 − (P3 ∪ P2 ) and label the two vertices of degree 2 with w1 and w2k+2 , where k ≥ 1 is an integer. Next connect 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 K4 − e and we identify the two vertices of degree 2 in K4 − e with w2i and w2i+1 . The resulting graph G4k+10 is 3-regular, has order n = 4k + 10 and rc(G4k+10 ) = diam(G4k+10 ) = 3k + 5 = 3n−10 4 . So Caro et al. [11] conjectured that if G is a connected graph with n vertices and δ (G) ≥ 3, then rc(G) < 34 n. Schiermeyer in [89] confirmed the conjecture by showing the following result. Theorem 3.1.2 ([89]). If G is a connected graph with n vertices and δ (G) ≥ 3, then rc(G) ≤ 3n−1 4 . Proof. As we will see, in Theorem 3.2.1, if G is a 2-connected graph with n vertices, then rc(G) ≤ 2n/3. So the result holds for 2-connected graphs. It remains to proof it for graphs with connectivity 1. We extend the concept of rainbow connection 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 rc∗ (G). Then rc(G) ≤ rc∗ (G) for every graph G and rc(G) = rc∗ (G) for every 2-connected graph G. Next we will show that if G is a connected graph with n vertices, connectivity κ (G) = 1 and δ (G) ≥ 3, then rc∗ (G) ≤ 3n−10 4 , and then the theorem holds. We need to have some preparatory results. At first, we determine the structure of endblocks. Let B = {K4 , K5 , K5 − e, K5 − P3 , K5 − 2P2, K5 − (P3 ∪ P2 )}. Then rc(K4 ) = rc(K5 ) = 1 and rc(K5 − e) = rc(K5 − P3 ) = rc(K5 − 2P2) = rc(K5 − (P3 ∪ P2 )) = 2. For B ∈ B, let B ∪ K2 be an endblock with an attached K2 . If B ∈ {K4 , K5 , K5 − e, K5 − 2P2}, then the K2 can be attached to any vertex of B. If B ∈ {K5 − P3 , K5 − (P3 ∪ P2 )}, then the K2 is attached to the vertex of degree 2 in K5 − P3 or K5 − (P3 ∪ P2 ). Now the following claims are easily verified. Claim 1. Let G be a connected graph with δ (G) ≥ 3. If G = G1 ∪ G2 with V (G1 ) ∩V (G2 ) = w for a cut vertex w, and moreover |V (G1 )| ≤ 5, or |V (G1 ) = 6| and dG1 (w) = 1, then G1 ∼ = B or G1 ∼ = B ∪ K2 for some B ∈ B. Claim 2. Let B ∈ B be an endblock. Then rc(B) ≤

3n−7 4

and rc(B ∪ K2 ) ≤

3n−6 4 .

The key idea of the proof is an induction using a cut vertex of the graph G. For a subgraph F ⊂ G, n(F) denotes the order of F. Claim 3. Let G be a connected graph with a cut vertex w. Suppose G = G1 ∪ G2 with V (G1 ) ∩V (G2 ) = w, dG1 (w) ≥ 2, dG2 (w) ≥ 1, |V (G1 )| ≥ 6, and |V (G2 )| ≥ 7. Then rc∗ (G) ≤ 3n−10 by induction. 4 Proof of Claim 3. We construct two graphs H1 and H2 as follows: Let H1 = (K5 − P3 ) ∪ G2 , where we identify the vertex of degree 2 in K5 − P3 with the vertex w

3.1 Bounds in Terms of Order and Minimum Degree

27

of G2 . Let H2 = G1 ∪ K2 ∪ (K5 − P3), where we identify one vertex of the K2 with the vertex w of G1 and the other vertex of the K2 with the vertex of degree 2 in K5 − P3 . Then |V (H1 )| = |V (K5 − P3 )| + |V (G2 )| − 1 < |V (G1 )| + |V (G2 )| − 1 = |V (G)| and |V (H2 )| = |V ((K5 − P3 ) ∪ K2 )| + |V (G1 )| − 1 < |V (G1 )| + |V (G2 )| − 1 = |V (G)|. Hence, by induction we have rc∗ (H1 ) ≤ 3n(H14)−10 and rc∗ (H2 ) ≤ 3n(H24)−10 , − 3 = 3n(G41 )−7 and rc∗ (G2 ) ≤ 3(n(G2 )+4)−10 −2 = implying rc∗ (G1 ) ≤ 3(n(G1 )+5)−10 4 4 3n(G2 )−6 . 4

This gives rc∗ (G) = rc∗ (G1 ) + rc∗(G2 ) ≤ 3n−10 4 . We now consider the block tree T of G. Let V (T ) = {w1 , w2 , · · · , b1 , b2 , · · · }, where wi is a cut vertex of G and bi represents the block Bi of G. Then wi b j ∈ E(T ) if and only if wi is incident with B j in G. We make the following useful observations. Observation 1. If Bi is an endblock of G (that is, bi is a leaf of T ), then |V (Bi )| ≥ 4, since δ ≥ 3.

Observation 2. If dT (w) ≥ 4 for a cut vertex w of G, then G = G1 ∪ G2 with G1 ∩ G2 = w and G1 and G2 both contain at least two nontrivial blocks. Then |V (Gi )| ≥ 2 · 4 − 1 = 7 for i = 1, 2 and we can apply induction. Hence, we may assume that 2 ≤ dT (w) ≤ 3 for every cut vertex w. Observation 3. If a cut vertex w has degree 3, then G = G1 ∪ G2 ∪ G3 . By the previous argument (in Observation 2) each Gi contains exactly one nontrivial block, which is an endblock. We have |V (Gi )| ≤ 6 for 1 ≤ i ≤ 3, since otherwise we could apply induction. With |V (G)| = |V (G1 )|+|V (G2 )|+|V (G3 )|−2 we obtain rc∗ (G) ≤ 3n(G1 )−6 + 3n(G42 )−6 + 3n(G43 )−6 = 3n−12 < 3n−10 4 4 4 . Observation 4. If a vertex b (corresponding to a block B) has degree p ≥ 3, then B is incident with p cut vertices w1 , w2 , · · · , w p . Hence G = B ∪ G1 ∪ G2 ∪ · · · ∪ G p . 2n(B) p 3n(Gi )−6 3n(B)−1 3(n+p−n(B))−6p Then rc∗ (G) ≤ 3 + ∑i=1 ≤ 4 + = 3n−1−3p ≤ 3n−10 4 4 4 4 . Hence, we may assume that Δ (T ) = 2 and thus T is a path. So, finally G contains at most one nontrivial inner block B, since otherwise we could apply induction. Therefore, for the path T , the following graph structures (of blocks) are possible: 1. 2. 3. 4. 5.

B1 , B2 rc∗ (G) ≤ 3n(B41 )−7 + 3n(B42 )−7 < 3n−10 4 . 3n(B1 ∪K2 )−6 3n(B2 )−7 ∗ + = 3n−10 B1 , K2 , B2 rc (G) ≤ 4 4 4 . 3n(B1 )−7 3n(B)−4 3n(B2 )−7 ∗ + 4 + < 3n−10 B1 , B, B2 rc (G) ≤ 4 4 4 . 3n(B ∪K )−6 3n(B)−4 3n(B ∗ 1 2 2 )−7 + 4 + < 3n−10 B1 , K2 , B, B2 rc (G) ≤ 4 4 4 . 3n(B1 ∪K2 )−6 3n(B)−4 3n(B2 ∪K2 )−6 ∗ + + = B1 , K2 , B, K2 , B2 rc (G) ≤ 4 4 4

3n−10 4 .



Not surprisingly, as the minimum degree increases, the graph would become more dense and therefore the rainbow connection number would decrease. Specifically, Caro, Lev, Roditty, Tuza and Yuster also proved the following upper bounds in terms of the minimum degree.

28

3 Upper Bounds for Rainbow Connection Numbers

Theorem 3.1.3 ([11]). If G is a connected graph with n vertices and minimum degree δ , then   ln δ 4 ln δ + 3 rc(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 neighbors in S) and the probabilistic method. They showed that in any case it cannot δ +7 be improved below δ3n +1 − δ +1 , as they constructed a connected n-vertex graph with minimum degree δ and this diameter: Take m copies of Kδ +1 , denoted by X1 , · · · , Xm , and label the vertices of Xi with xi,1 , · · · , xi,δ +1 . Take two copies of Kδ +2 , denoted by X0 , Xm+1 , and similarly label their vertices. Now, join xi,2 and xi+1,1 for i = 0, · · · , m by 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 δ +7 to xm+1,2 has length 3m + 5 = δ3n +1 − δ +1 . This, naturally, raised the open problem of determining the true behavior of rc(G) as a function of δ . In [12], Chakraborty et al. proved that any connected graph of order n with minimum degree Θ(n) has a bounded rainbow connection number. The proof of their result is based upon a modified degree-form version of Szemer´edi Regularity Lemma that they proved. We will give the proof of it. We begin by introducing the Regularity Lemma and the already known degree-form version of it. The Regularity Lemma of Szemer´edi [95] is one of the most important results in graph theory and combinatorics, as it guarantees that every graph has an ε -approximation of constant descriptive size, namely a size that depends only on ε and not on the size of the graph. This approximation “breaks” the graph into a constant number of pseudo-random bipartite graphs. This is very useful in many applications since dealing with random-like graphs is much easier than dealing with arbitrary graphs. For a good survey on Regularity Lemma, we refer to [54], where readers can find many examples and applications. We first state the lemma. For two nonempty disjoint vertex sets A and B of a graph G, we define E(A, B) to be the set of edges of G between A and B. The edge density of the pair is defined by d(A, B) = |E(A, B)|/(|A||B|). A pair (A, B) is ε -regular if for every A ⊆ A and B ⊆ B satisfying |A | ≥ ε |A| and |B | ≥ ε |B|, we have |d(A , B ) − d(A, B)| ≤ ε . An ε -regular pair can be thought of as a pseudo-random bipartite graph in the sense that it behaves almost as we would expect from a random bipartite graph of the same density. Intuitively, in a random bipartite graph with edge density d, all large enough subpairs should have similar densities. A partition V1 , · · · ,Vk of the vertex set of a graph is called an equipartition if |Vi | and |V j | differ by no more than 1 for all 1 ≤ i < j ≤ k (so in particular every Vi has one of two possible sizes). The order of an equipartition denotes the number of

3.1 Bounds in Terms of Order and Minimum Degree

29

partition classes (k above). An equipartition V1 , · · · ,Vk of the vertex set of a graph is  called ε -regular if all but at most ε 2k of the pairs (Vi ,V j ) are ε -regular. Szemer´edi’s Regularity Lemma can be formulated as follows. Lemma 3.1.4 (Regularity Lemma [95]). For every ε > 0 and positive integer K, there exists N = N1 (ε , K), such that any graph with n ≥ N vertices has an ε -regular equipartition of order k, where K ≤ k ≤ N. As mentioned earlier, the following variation of the lemma comes useful. Lemma 3.1.5 (Regularity Lemma—Degree Form [54]). For every ε > 0 and positive integer K there is N = N2 (ε , K) such that given any graph G = (V, E) with n > N vertices, there is a partition of the vertex set V into k + 1 sets V0 ,V1 , · · · ,Vk , and there is a subgraph G of G with the following properties: K ≤ k ≤ N, s  |V0 | ≤ ε 10 n and all other components Vi , i ∈ [k] are of size   n−s k , for all i ∈ [k], Vi induces an independent set in G , for all i, j ∈ [k], the pair (Vi ,V j ) is ε 10 -regular in G , with density either 0 or at least ε4 , 5. for all v ∈ V , degG (v) > degG (v) − ε3 n. 1. 2. 3. 4.

This form of the lemma (see e.g. [54]) can be obtained by applying the original Regularity Lemma (with a smaller value of ε ), and then “cleaning” the resulting partition. Namely, adding to the exceptional set V0 all components Vi incident to many irregular pairs, deleting all edges between any other pairs of clusters that either do not form an ε -regular pair or they do but with density less than ε , and finally adding to V0 also vertices whose degree decreased too much by this deletion of edges. In order to prove that graphs with minimum degree ε n have bounded rainbow connection numbers, we need a special version of the Regularity Lemma, which is stated next and its proof is omitted. Lemma 3.1.6 (Regularity Lemma—New Form [12]). For every ε > 0 and positive integer K there is N = N3 (ε , K) so that the following holds: If G = (V, E) is a graph G = (V, E) with n > N vertices and minimum degree at least ε n, then there is a subgraph G of G, and a partition of V into V1 , · · · ,Vk , with the following properties: K ≤ k ≤ N, for all i ∈ [k], (1 − ε ) nk ≤ |Vi | ≤ (1 + ε 3) nk , for all i ∈ [k], Vi induces an independent set in G , for all i, j ∈ [k], the pair (Vi ,V j ) is ε 3 -regular in G , with density either 0 or at ε least 16 , 5. for all i ∈ [k] and every v ∈ Vi there is at least one other class V j so that the ε number of neighbors of v in G belonging to V j is at least 3k n. 1. 2. 3. 4.

The new version of the Regularity Lemma will be useful in our proof. First we need some definitions. Given a graph G = (V, E) and two subsets V1 ,V2 ⊆ V ,

30

3 Upper Bounds for Rainbow Connection Numbers

let E(V1 ,V2 ) denote the set of edges having one endpoint in V1 and the other endpoint in V2 . Given a vertex v, let Γ(v) denote the set of neighbors of v, and for W ⊆ V , let ΓW (v) denote the set W ∩ Γ(v). For an edge-coloring χ : E → K , let πχ denote the corresponding partition of E into (at most) |K | components. For two edge-colorings χ and χ , we say that χ is a refinement of χ if πχ is a refinement of πχ , which is equivalent to saying that χ (e) = χ (e ) always implies χ (e) = χ (e ). Observation 3.1.7 ([12]). Let χ and χ be two edge-colorings of a graph G such that χ is a refinement of χ . For any path P in G, if P is a rainbow path under χ , then P is a rainbow path under χ . In particular, if χ makes G rainbow connected, then so does χ . We define a set of eight distinct colors K = {a1 , a2 , a3 , a4 , b1 , b2 , b3 , b4 }. Given a coloring χ : E → K , we say that u, v ∈ V are a-rainbow connected if there is a rainbow path from u to v using only the colors a1 , a2 , a3 , a4 . We similarly define b-rainbow connected pairs. The following is a central lemma in our proof. Lemma 3.1.8 ([12]). For any ε > 0, there is N = N4 (ε ) such that any connected graph G = (V, E) with n > N vertices and minimum degree at least ε n satisfies the following. There is a partition Π of V into k ≤ N components V1 ,V2 , · · · ,Vk , and a coloring χ : E → K such that for every i ∈ [k] and every u, v ∈ Vi , the pair u, v is both a-rainbow connected and b-rainbow connected under χ . Proof. First we state a claim. Claim 4. For every ε > 0 there exists N = N5 (ε ) such that any graph G = (V, E) with n > N vertices and minimum degree at least ε n satisfies the following: There exists a partition Π = V1 , · · · ,Vk of V such that for every i ∈ [k] and every u, v ∈ Vi , the number of edge-disjoint paths of length at most four from u to v is larger than 85 log n. Proof of Claim 4. Given ε > 0 let L = N3 (ε , 1) and set N to be the smallest number that satisfies ε 4 NL > 85 log N. Now, given any graph G = (V, E) with n > N vertices and minimum degree at least ε n, we apply Lemma 3.1.6 with parameters ε and 1. Let Π = V1 ,V2 , · · · ,Vk be the partition of V obtained from Lemma 3.1.6, while as promised, k ≤ L = N3 (ε , 1). Fix i ∈ [k] and u, v ∈ Vi . From Lemma 3.1.6, we know that there is a component ε Va such that u has at least 3k n neighbors in Va . Similarly, there is a component Vb ε such that v has at least 3k n neighbors in Vb . Let Γu,a denote the set of neighbors of u in Va , and similarly, let Γv,b denote the set of neighbors of v in Vb . We assume in this proof that Va = Vb , and later it will be clear that the case Va = Vb can only benefit. We say that a set Wu = {w1 , · · · , wt } ⊆ Vi is distinctly reachable from u if there are distinct vertices w 1 , · · · , wt ∈ Γu,a such that for every j ∈ [t], {w j , w j } ∈ E. Notice that the collection of pairs {w j , w j } corresponds to a matching in the graph G, where all edges of the matching have one endpoint in Vi and the other endpoint in Γu,a . Similarly, we say that Wv ⊆ Vi is distinctly reachable from v if there are distinct vertices w 1 , · · · , wt ∈ Γv,b such that for every j ∈ [t], {w j , w j } ∈ E. Observe that it

3.1 Bounds in Terms of Order and Minimum Degree

31

is enough to prove that there exists a set W ⊆ Vi of size ε 4 NL > 85 log N which is distinctly reachable from both u and v. This will imply the existence of 85 log N edge-disjoint paths of length four from u to v. Before we proceed, notice that if the same holds when Va = Vb , then the number of disjoint paths from u to v remains the same while their lengths can shrink to 2 (if the corresponding subsets of Γu,a and Γv,b intersect), which is even better for our analysis. Our first goal is to bound from below the size of the maximal set Wu as above. ε Since (by Lemma 3.1.6) Va and Vi are ε 3 -regular pairs with density ≥ 16 and since ε 3 3 ε < ε /3, the number of edges between Γu,a and Vi is at least ( 16 − ε )|Γu,a | · |Vi |. Before proceeding, we make the following useful observation. Observation. Let H = (A, B) be a bipartite graph with γ |A||B| edges. Then H |A||B| . contains a matching M of size γ |A|+|B| Proof of the Observation. Consider the following process that creates M. Initially, M0 = 0. / Then in step i, we pick an arbitrary edge {a, b} ∈ E(H), set Mi+1 = Mi ∪ {a, b} and remove from E(H) all the edges incident with either a or b. Clearly, in each step the number of removed edges is bounded by |A| + |B|, so the process  E(H) |A||B| |A||B| continues for at least |A|+|B| = γ |A|+|B| steps. Hence, |M| = | i Mi | ≥ γ |A|+|B| . By the above observation, the size of a maximal set Wu as above is at least ε  |Γ ||V |  (ε n/(3k))(n/k) ε ε2 u,a i − ε3 ≥ − ε3 ≥ n. 16 |Γu,a | + |Vi | 16 (ε n/(3k)) + (n/k) 100k To prove that W = Wu ∩Wa is large, we similarly use the regularity condition, but now on the pair (Γv,b ,Wu ). We get, |E(Γv,b ,Wu )| ≥

ε  − ε 3 |Γv,b ||Wu |. 16

Here too, by the above observation, we can bound from below the size of a maximal matching in the pair (Γv,b ,Wu ) with ε2 ε ε  |Γ ||W |  ε u v,b 3 3 ( 3k n)( 100k n) −ε ≥ −ε > 85 log N, 2 ε 16 |Γv,b | + |Wu| 16 n+ ε n 3k

100k

where the inequalities follow from our choice of N and the assumption that ε is small. Recall that the matching that we found defines the desired set W , concluding the proof of the claim. Now we continue to prove the lemma, first we apply the above claim to get the partition Π. Now the proof follows by a simple probabilistic argument. Namely, we color every edge e ∈ E by choosing one of the colors in K = {a1 , · · · , a4 , b1 , · · · , b4 } uniformly and independently at random. Observe that a fixed path P of length at most four is an a-rainbow path with probability at least 8−4 . Similarly, P is a b-rainbow path with probability at least 8−4 . So any fixed pair u, v ∈ Vi is

32

3 Upper Bounds for Rainbow Connection Numbers

not both a-rainbow-connected and b-rainbow-connected with probability at most 5 2(1 − 8−4 )8 log n < n−2 , and therefore the probability that all such pairs are both a-rainbow connected and b-rainbow connected is strictly positive. Hence, the desired coloring must exist. 

Now we use Lemma 3.1.8 to prove the following result. Theorem 3.1.9 ([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 rc(G) ≤ C. Proof. For a given ε > 0, set N = N4 (ε ) and set C = 3ε N + 8. Clearly, any connected graph G = (V, E) with n ≤ C vertices satisfies rc(G) ≤ C. So we assume that n > C ≥ N, and let Π = V1 , · · · ,Vk be the partition of V from Lemma 3.1.8, while we know that k ≤ N. First observe that since the minimal degree of G is ε n, the diameter of G is bounded by 3/ε . This can be verified, e.g., by taking an arbitrary vertex r ∈ V and executing a BFS algorithm from it. Let L1 , · · · , Lt be the layers of vertices in this execution, where Li are all vertices at distance i from r. Observe that since the minimal degree is at least ε n, the total number of vertices in every three consecutive layers must be at least ε n, thus t ≤ 3/ε . Since the same claim holds for any r ∈ V , this implies that diam(G) ≤ t ≤ 3/ε . Now let T = (VT , ET ) be a connected subtree of G on at most k · diam(G) ≤ ε3 N vertices such that for every i ∈ [k], VT ∩ Vi = 0. / Such a subtree must exist in G since as observed earlier, diam(G) ≤ 3/ε . Let χ : E → K be the coloring from Lemma 3.1.8, and let H = {h1 , h2 , · · · , h|ET | } be a set of |ET | ≤ ε3 N fresh colors. We refine χ by recoloring every ei ∈ E(T ) with color hi ∈ H . Let χ : E → (K ∪H ) be the resulting coloring of G. The following claim completes the proof of the theorem. Claim 5. The coloring χ makes G rainbow connected. Consequently, rc(G) ≤ |ET | + 8 ≤ C. Proof of Claim 5. Let u, v ∈ V be any pair of vertices of G. If u and v reside in the same component Vi of the partition Π, then (by Lemma 3.1.8) they are connected by a path P of length at most four, which is a rainbow path under the original coloring χ . Since χ is a refinement of χ , the path P remains a rainbow path under χ as well (see Observation 3.1.7). Otherwise, let u ∈ Vi and v ∈ V j for i = j. Let ti and t j be vertices of the subtree T , residing in Vi and V j respectively. By definition of χ , there is a rainbow path from ti to t j using colors from H . Let Pt denote this path. In addition, by Lemma 3.1.8 we know that for the original coloring χ , there is a rainbow path Pa from u to ti using colors a1 , · · · , a4 and there is a rainbow path Pb from v to t j using colors b1 , · · · , b4 . Based on the fact that χ is a refinement of χ , it is now easy to verify that Pt , Pa , and Pb can be combined to form a rainbow path from u to v under χ . This concludes the proof of the theorem. 

The above lower bound construction suggests that the logarithmic factor in their upper bound may not be necessary and that, in fact rc(G) ≤ Cn/δ where C is a

3.1 Bounds in Terms of Order and Minimum Degree

33

universal constant. If true, notice that for a graph with a linear minimum degree ε n, this implies that rc(G) is at most C/ε . However, Theorem 3.1.9 does not even guarantee the weaker claim that rc(G) is a constant. The constant C = C(ε ) they obtained is a tower function in 1/ε and in particular extremely far from being reciprocal to 1/ε . Later, Krivelevich and Yuster in [55] determined the behavior of rc(G) as a function of δ (G) and settled the above-mentioned open problem. Theorem 3.1.10 ([55]). A connected graph G with n vertices has rc(G) <

20n δ (G) .

The proof of Theorem 3.1.10 uses the concept of a connected two-step dominating set. Krivelevich and Yuster first proved that for a connected graph H with minimum degree k and n vertices, there exists a two-step dominating set S whose n 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. The authors of [55] noticed 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 3.1.3, one cannot expect to replace C by a constant smaller than 3. Schiermeyer [93] improved the constant into 4. Motivated by the results of Theorems 3.1.2, 3.1.3 and 3.1.10, Schiermeyer raised the following open problem in [89]. Problem 3.1 ([89]). For every k ≥ 2, find a minimal constant ck with 0 < ck ≤ 1 such that rc(G) ≤ ck n for all graphs G with minimum degree δ (G) ≥ k. Is it true 3 that ck = k+1 for all k ≥ 2? This is true for k = 2, 3 as shown before (c2 = 1 and c3 = 34 ). Finally, 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 3.1.11 ([13]). (i) If D is a connected two-way two-step dominating set in a graph G, then rc(G) ≤ rc(G[D]) + 6. (ii) Every connected graph G of order n ≥ 4 and minimum degree δ has a connected two-way two-step dominating set D of size at most δ3n +1 − 2. Moreover, for every δ ≥ 2, there exist infinitely many connected graphs G such that γc2 (G) ≥ 3(n−2) δ +1 − 4. Proof. We prove (i) by demonstrating a rainbow coloring that uses at most rc(G[D]) +6 colors. For x ∈ N k (D), its neighbors in N k−1 (D), k = 1, 2 will be called foots of x and the corresponding edges will be called legs. Any rainbow path whose edge colors are contained in {1, 2, · · · , k} will be called a k-rainbow path.

34

3 Upper Bounds for Rainbow Connection Numbers

Rainbow color G[D] using colors {1, 2, · · · , k := rc(G[D])}. Construct a new graph H on N 1 (D) with the edge set E(H) = {{x, y}|x, y ∈ N 1 (D), {x, y} ∈ E(G) or ∃ z ∈ N 2 (D) such that {x, z}, {y, z} ∈ E(G)}. Recall that, in a two-way two-step dominating set D, there are no pendant vertices outside D and every vertex in N 2 (D) has at least two neighbors in N 1 (D). Hence in the above graph H, the isolated vertices are only those which have all their neighbors (at least 2) in D. Denote the collection of these isolated vertices by Z. Choose a spanning tree in every nonsingleton connected component of H. This gives a spanning forest of V (H) \ Z with no isolated vertices. Let X and Y be any bipartition defined by this forest. Color every X − D edge with (k + 1) and every Y − D edge with (k + 2). For every vertex in Z, color one of its legs with (k + 1) and the remaining with (k + 2). Color every edge of G within N 1 (D) by k + 3. Partition the vertices of N 2 (D) into A and B as follows: A = {x ∈ N 2 (D)|N(x) ∩ X = 0/ and N(x) ∩Y = 0} / and B = N 2 (D) \ A. Color every A − X edge with (k + 3) and every A −Y edge with (k + 4). It is not hard to show that G := G[D ∪ N 1 (D) ∪ A] is rainbow connected using colors 1 to k + 4. Now only the vertices of B remain. All of them have at least two neighbors in G . Color one edge to G with k + 5 and all the other edges with k + 6. It is easily seen that we now have a rainbow coloring of entire G. For (ii), the case when δ ≤ 1 can be checked easily. So we assume δ ≥ 2 and execute the following two-stage procedure. Stage 1. D = {u}, for some u ∈ V (G). / While N 3 (D) = 0, { Pick any v ∈ N 3 (D). Let (v, x2 , x1 , x0 ), x0 ∈ D be a shortest v − D path. D = D ∪ {x1 , x2 , v}. } Stage 2. D = D. While ∃ v ∈ N 2 (D ) such that |N(v) ∩ N 2 (D )| ≥ δ − 1 , { D = D ∪ {x1 , v} where (v, x1 , x0 ), x0 ∈ D is a shortest v − D path. } Clearly, the set D remains connected after every iteration in Stage 1. Since Stage 1 ends only when N 3 (D) = 0, / the final D is a two-step dominating set. Let k1 be the number of iterations executed in Stage 1. When Stage 1 starts, we have that |D ∪ N 1 (D)| ≥ δ + 1. Since a new vertex from N 3 (D) is added to D, |D ∪ N 1 (D)| increases by at least δ + 1 in every iteration. Therefore, when Stage 1 ends, we 1 (D)| 2 (D)| have that k1 + 1 ≤ |D∪N = n−|N δ +1 δ +1 . Since D starts as a singleton set and each (D)|) iteration adds three more vertices, we have that |D| = 3k1 + 1 ≤ 3(n−|N − 2. δ +1 Note that D remains a connected two-step dominating set throughout Stage 2. Stage 2 ends only when every vertex v ∈ N 2 (D ) has at most δ − 2 neighbors in N 2 (D ). Hence, at least two neighbors of v are in N 1 (D ). Moreover, since δ ≥ 2, 2

3.1 Bounds in Terms of Order and Minimum Degree

35

there are no pendant vertices in G. So the final D is a connected two-way two-step dominating set. Let k2 be the number of iterations executed in Stage 2. Since we add to D a vertex who has at least δ − 1 neighbors in N 2 (D ), |N 2 (D )| reduces by at least δ in every iteration. Since we started with |N 2 (D)| vertices, then k2 ≤ |N 2 (D)| . Since we add two vertices to D in each δ 2 2 3(n−|N (D)|) − 2 + 2|N δ(D)| ≤ δ3n δ +1 +1 − 2 for δ ≥ 2.

iteration, then |D | = |D| + 2k2 ≤

For every δ > 2, construction for infinitely many graphs G with diam(G) = − 1 was reported in [11, 36]. It is easy to see that for every graph G,

3(n−2) δ +1

diam(G) ≤ γc2 (G) + 3. Hence, γc2 (G) ≥

3(n−2)  δ +1 − 4 for every graph in that family.

Observe that the connected (two-way two-step dominating) set D can be rainbow

colored using |D | − 1 colors by ensuring that every edge of some spanning tree gets distinct colors. So we have the following theorem. The family of tight examples is demonstrated under Theorem 3.1.3.

Theorem 3.1.12 ([13]). For every connected graph G of order n and minimum degree δ , 3n + 3. rc(G) ≤ δ +1 Moreover, for every δ ≥ 2, there exist infinitely many connected graphs G such that rc(G) ≥ 3(n−2) δ +1 − 1. Theorem 3.1.12 answers Problem 3.1 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 3.1.3) and [36]. And therefore, for graphs with linear minimum degree ε n, the rainbow connection number is bounded by a constant. It is also tried to look for some other better parameters to replace δ . Such a natural parameter is σk . Recall that for a graph G, σk (G) = min{d(u1 ) + d(u2 ) + · · · + d(uk )| u1 , u2 , . . . , uk ∈ V (G), ui u j ∈ E(G), i = j, i, j ∈ {1, · · · , k}}. Observe that σk is monotonically increasing in k. Dong and Li in [28] derived two upper bounds of the rainbow connection number under given degree-sum condition σk . Clearly, σ1 = δ , and σk ≥ kδ . They used a similar idea to the proof of Theorem 3.1.12, and got an upper bound first according to σ2 . Theorem 3.1.13 ([28]). For a connected graph G of order n, rc(G) ≤

6n σ2 +2

+ 8.

From the example below Theorem 3.1.3, we know that the rainbow connection number of that graph is at least its diameter diam(G) = σ26n+2 − ( σ22 + 7)/( σ22 + 1). So, the above bound could be seen to be tight up to additive factors. Note that for σ2 , Schiermeyer [90] got that if G is a connected graph of order n, then rc(G) ≤ n −  σ22 . Unfortunately, his proof is not correct, see [67]. For a general k, Dong and Li further got the following result, also using a method similar to that of Theorem 3.1.12.

36

3 Upper Bounds for Rainbow Connection Numbers

Theorem 3.1.14 ([29]). If G is a connected graph of order n with k independent vertices, then rc(G) ≤ σ3kn +k + 6k − 3. k

From the following examples, one can see that σk really works very well in ∗ the graph decreasing the upper bound of rc(G). First of all, we denote by Ka,b obtained from the complete bipartite graph Ka,b by joining every pair of vertices in the b-part by a new edge. Example 3.1.15. Let

n−2 k−1

be an integer and let H = K2,∗ n−2 −2 , H1 = K2,∗ n−2 −1 , and k−1

k−1

Hk = K1 with V (K1 ) = {v}. Take k − 2 copies of H, denoted by H2 , · · · , Hk−1 . Label the two nonadjacent vertices of Hi by xi,1 , xi,2 , for i ∈ {1, · · · , k − 1}. Now, connect xi,2 and xi+1,1 with an edge for every i ∈ {1, · · · , k − 1}, and connect v and xk−1,2 with an edge. The resulting graph is denoted by G. From the construction, it is not difficult to check that for every v ∈ V (Hi ), i ∈ {2, · · · , k −1}, we have d(v) = n−2 k−1 −1. n−2 − 1, σ = ( − 1)(k − 1) + 1 = n − k, and δ (G) = 1. In addition, d(x1,1 ) = n−2 k k−1 k−1 From these facts, one can see that the upper bound of Theorem 3.1.12 is rc(G) ≤ 3n/2 + 3, which is linear in n, nevertheless, the upper bound in our Theorem 3.1.14 is rc(G) < 9k − 4, which is a constant when k is small, say 2, 3, etc. Notice that here we can make δ be 2, 3, etc, simply by adding a few edges properly. Example 3.1.16. Let

σk k

be an integer and let H = K ∗ σk

, H = K ∗ σk . Take t 2, k −1 2, k copies of H , denoted by H0 , Ht+1 .

copies of H, denoted by H1 , · · · , Ht , and take two Label the two nonadjacent vertices of Hi by xi,1 , xi,2 , for i ∈ {0, 1, · · · ,t + 1}. Now, connect xi,2 and xi+1,1 for i ∈ {0, · · · ,t + 1} with an edge. The resulting graph G has n = (t +2)( σkk +1)+2 vertices. It is straightforward to verify that for i ∈ {1, 2, · · · ,t} and any v ∈ V (Hi ), we have d(v) = σkk . In addition, d(x0,1 ) = d(xt+1,2 ) = σkk , and − 1 = 3t + 5, and rc(G) ≥ diam(G), diam(G) = d(x0,1 , xt+1,2 ) = 3t + 5. From σ3kn k +k

one can see that the bound rc(G) ≤ σ3kn + 6k − 3 of Theorem 3.1.14 could be seen k +k as a tight upper bound up to additive factors 6k − 3 when k is small.

3.2 Bounds in Terms of Connectivity The connectivity can be seen as another parameter to replace the minimum degree parameter. With respect to the relation between rc(G) and the connectivity κ (G), mentioned in [89], Broersma asked a question at the IWOCA workshop: Problem 3.2 ([89]). What happens with the value rc(G) for graphs with higher connectivity? For κ (G) = 1, Theorem 3.1.2 means that if G is a graph of order n, connectivity κ (G) = 1 and δ ≥ 3, then rc(G) ≤ 3n−1 4 . For κ (G) = 2, Caro et al. [11] obtained the following result.

3.2 Bounds in Terms of Connectivity

37

Theorem 3.2.1 ([11]). √ If G is a 2-connected graph with n vertices, then rc(G) ≤ min{2n/3, n/2 + O( n)}. That is, if G is a graph of order n, connectivity κ (G) = 2, then rc(G) ≤ In [89], Schiermeter got another bound for a 2-connected graph.

2n 3 .

Theorem 3.2.2 ([89]). Let G be a 2-connected graph with n vertices and degree sequence 2 ≤ d1 ≤ d2 ≤ · · · ≤ dn . If d3 ≥ 3, then rc(G) ≤ (2n − 2)/3 for 4 ≤ n ≤ 7 and rc(G) ≤ (2n − 1)/3 for n ≥ 8. Li and Liu got a best possible upper bound in [69] for 2-connected graphs. At first we introduce some new notions. Let c be a rainbow coloring of a connected graph G with k colors. If a rainbow path P in G has length k, we call P a complete rainbow path; otherwise, it is an incomplete rainbow path. A rainbow coloring c of G is incomplete if for any vertex u ∈ V (G), G has at most one vertex v such that all the rainbow paths between u and v are complete; otherwise, it is complete. For a connected graph G, if a spanning subgraph has an (incomplete) rainbow coloring with k colors, then G has an (incomplete) rainbow coloring with k colors. This simple fact will be used in the following proofs. Lemma 3.2.3 ([69, 71]). Let G be a Hamiltonian graph of order n (n ≥ 3). Then G has an incomplete rainbow coloring with  n2  colors, i.e., rc(G) ≤  n2 . The proof is not difficult and is thus omitted. Let G be a 2-connected non-Hamiltonian graph of order n (n ≥ 4). Then G must have an even cycle. In fact, since G is 2-connected, G must have a cycle C. If C is an even cycle, we are done. Otherwise, C is an odd cycle, we then choose an ear P of C such that V (C) V (P) = {a, b}. Since the lengths of the two segments between a, b on C have different parities, P joining with one of the two segments forms an even cycle. Then, starting from an even cycle G0 , there exists a nonincreasing ear  decomposition (G0 , G1 , · · · , Gt , Gt+1 , · · · , Gk ) of G, such that Gi = Gi−1 Pi (1 ≤ i ≤ k) and Pi is a longest ear of Gi−1 , i.e., (P1 ) ≥ (P2 ) ≥ · · · ≥ (Pk ). Suppose that V (Pi ) V (Gi−1 ) = {ai , bi } (1 ≤ i ≤ k). We call the distinct vertices ai , bi (1 ≤ i ≤ k) the end vertices of the ear Pi . Without loss of generality, suppose that (Pt ) ≥ 2 and (Pt+1 ) = · · · = (Pk ) = 1. So Gt is a 2-connected spanning subgraph of G. Since G is a non-Hamiltonian graph, we have t ≥ 1. Denote the order of Gi (0 ≤ i ≤ k) by ni . All these notations will be used in the sequel. Lemma 3.2.4 ([69, 71]). Let G be a 2-connected non-Hamiltonian graph of order n (n ≥ 4). If G has at most one ear with length 2 in the nonincreasing ear decomposition, then G has an incomplete rainbow coloring with  n2  colors, i.e., rc(G) ≤  n2 . Proof. Since Gt (t ≥ 1) in the nonincreasing ear decomposition is a 2-connected spanning subgraph of G, it only needs to show that Gt has an incomplete rainbow coloring with  n2t  colors. We will apply induction on t.

38

3 Upper Bounds for Rainbow Connection Numbers

First, consider the case that t = 1. Let G be a 2-connected non-Hamiltonian graph with t = 1 in the nonincreasing ear decomposition. The spanning subgraph  G1 = G0 P1 of G consists of an even cycle G0 and an ear P1 of G0 . Without loss of generality, suppose that G0 = v1 , v2 , · · · , v2k , v2k+1 (=v1 ) where k ≥ 2. We color the edges of G0 with k colors. Define the edge-coloring c0 of G0 by c0 (vi vi+1 ) = i for 1 ≤ i ≤ k and c0 (vi vi+1 ) = i − k if k + 1 ≤ i ≤ 2k. Clearly, the coloring c0 is an incomplete rainbow coloring of G0 with k colors. Now consider G1 according to the parity of (P1 ). If (P1 ) is even, then n1 is odd and color the edges of P1 with (P21 ) (P )

new colors. For the first 21 edges of P1 the colors are all distinct, and the same ordering of colors is repeated for the last (P21 ) edges of P1 . It is easy to verify that the obtained coloring c1 of G1 is an incomplete rainbow coloring with  n21  colors such that for every pair of vertices in G, there exists an incomplete rainbow path connecting them. If (P1 ) is odd, then n1 is even and color the edges of P1 with (P1 )−1 new colors. The middle edge of P1 receives any color that already appeared 2 in G0 . The first (P12)−1 edges of P1 all receive distinct new colors and for the last (P1 )−1 edges of P1 , this coloring is repeated in the same order. It is easy to verify 2 that the obtained coloring c1 of G1 is an incomplete rainbow coloring with  n21  colors. Let G be a 2-connected non-Hamiltonian graph with t ≥ 2 in the nonincreasing ear decomposition. Assume that the subgraph Gi (1 ≤ i ≤ t − 1) has an incomplete rainbow coloring ci with  n2i  colors such that when ni is odd, every pair of vertices have an incomplete rainbow path. We distinguish the following three cases. Case 1. (Pt ) (≥ 3) is odd. Suppose that Pt = v0 (=at ), v1 , · · · , vr , vr+1 , · · · , v2r , v2r+1 (=bt ), where r ≥ 1. We color the edges of Pt with r new colors to obtain an incomplete coloring ct of Gt . Define an edge-coloring of Pt by c(vi−1 vi ) = xi (1 ≤ i ≤ r), c(vr vr+1 ) = x and c(vi−1 vi ) = xi−r−1 (r + 2 ≤ i ≤ 2r + 1), where x1 , x2 , · · · , xr are new colors and x is a color appeared in Gt−1 . It is easy to check that the obtained coloring ct of Gt is a rainbow coloring with  n2t  colors. Now we show that ct is incomplete such that when nt is odd, every pair of vertices have an incomplete rainbow path. For every pair of vertices u, v ∈ V (Gt−1 ) × V (Gt−1 ), the rainbow path P from u to v in Gt−1 is incomplete in Gt , because the new colors x1 , x2 , · · · , xr (r ≥ 1) do not appear in P. For every pair of vertices u, v ∈ V (Pt ) ×V (Pt ), if there exists a rainbow path P from u to v on Pt , then P is incomplete in Gt , since some color in Gt−1 does not appear in P; if not, there exists an incomplete rainbow path P from u to v through some vertices of Gt−1 such that at least one new color does not appear in P. For every pair of vertices u, v ∈ V (Gt−1 ) × (V (Pt )\{vr , vr+1 }), there exists an incomplete rainbow path from u to v in which at least one new color does not appear. If there exists a vertex all of whose rainbow paths to at (respectively, to bt ) in Gt−1 are complete, we denote the vertex by at (respectively, by bt ). For vertex vr (respectively, vr+1 ), only the vertex at (respectively, bt ) possibly has no incomplete rainbow path to vr (respectively, to vr+1 ) in Gt . So there possibly exist two pairs of vertices at , vr and bt , vr+1 which have

3.2 Bounds in Terms of Connectivity

39

no incomplete rainbow path. Since at , bt are distinct in Gt−1 , the rainbow coloring ct is incomplete. If nt is odd, then nt−1 is odd. By induction, at , bt do not exist when nt−1 is odd. Hence, every pair of vertices have a incomplete rainbow path. Case 2. (Pt ) (≥2) is even and nt−1 is even. In this case, nt is odd. Suppose that Pt = v0 (=at ), v1 , · · · , vr , vr+1 , · · · , v2r−1 , v2r (=bt ), where r ≥ 1. Define an edge-coloring of Pt by c(vi−1 vi ) = xi for 1 ≤ i ≤ r and c(vi−1 vi ) = xi−r for r + 1 ≤ i ≤ 2r. It is clear that the obtained coloring ct of Gt is a rainbow coloring with  n2t  colors. Now we prove that ct is incomplete such that when nt is odd, every pair of vertices have an incomplete rainbow path. For every pair of vertices in V (Gt−1 )×V (Gt−1 ) or V (Pt ) × V (Pt ), there is an incomplete rainbow path connecting them in Gt , similar to Case 1. For every pair of vertices u ∈ V (Gt−1 ), v ∈ V (Pt ) (v = vr ), there is an incomplete rainbow path P from u to v such that at least one new color does not appear in P. For any vertex u ∈ V (Gt−1 ), since the coloring ct−1 is incomplete, u has an incomplete rainbow path P in Gt−1 to one of at , bt (say at ). Then P joining with at Pt vr is an incomplete rainbow path from u to vr in Gt . Therefore, the rainbow coloring ct of Gt is incomplete such that every pair of vertices have an incomplete rainbow path. Case 3. (Pt ) (≥2) is even and nt−1 is odd. In this case, nt is even. We consider the following three subcases.

Subcase 3.1. [V (Pt ) V (Pt−1 )]\V (Gt−2 ) = 0. / = Gt−2 If (Pt−1 ) is odd, let Gt−1



Pt and Gt = Gt−1 nt−1



Pt−1 . By induction, Gt−1

). has an incomplete rainbow coloring with  2  colors (nt−1 is the order of Gt−1 Similar to Case 1, we can obtain an incomplete rainbow coloring of Gt from Gt−1 nt with  2  colors. Suppose that (Pt−1 ) is even. By induction, Gt−2 has an incomplete rainbow n coloring ct−2 with  t−2 2  colors. Suppose that Pt−1 = v0 (=at−1 ), v1 , · · · , vr , vr+1 , · · · , v2r−1 , v2r (=bt−1 ) and Pt = v 0 (=at ), v 1 , · · · , v s , v s+1 , · · · , v 2s−1 , v 2s (=bt ), where r ≥ 2, s ≥ 1. Since ct−2 is incomplete and ai , bi (1 ≤ i ≤ k) are two distinct vertices, then at−1 has an incomplete rainbow path P to one of at , bt (say at ) and bt−1 has an incomplete rainbow path P to the other vertex. Suppose that x is the color in Gt−2 that does not appear in P . Now color the edges of Pt−1 , Pt with r + s − 1 new colors and the color x. Define an edge-coloring of Pt−1 by c(vi−1 vi ) = xi (1 ≤ i ≤ r) and c(vi−1 vi ) = xi−r (r + 1 ≤ i ≤ 2r), where x1 , x2 , · · · , xr are new colors. And define an edge-coloring of Pt by c(v i−1 v i ) = yi (1 ≤ i ≤ s − 1), c(v s−1 v s ) = x, c(v s v s+1 ) = x1 and c(v i−1 v i ) = yi−s−1 (s + 2 ≤ i ≤ 2s), where y1 , y2 , · · · , ys−1 are new colors. Similar to Case 2, the obtained coloring ct−1 of Gt−1 is an incomplete rainn bow coloring with  t−1 2  colors such that every pair of vertices have an incomplete rainbow path. It is obvious that Gt is rainbow connected. The path (v s Pt at )P (at−1 Pt−1 vr ) is a rainbow path from v s to vr which is possibly complete. For any other pair of vertices in Gt , there is an incomplete rainbow path connecting them. Hence, the rainbow coloring ct of Gt is incomplete.

40

3 Upper Bounds for Rainbow Connection Numbers



Subcase 3.2. [V (Pt ) V (Pt−1 )]\V (Gt−2 ) = {bt }. If (Pt−1 ) is odd, suppose that Pt−1 = v0 (= at−1 ), v1 , · · · , vr , vr+1 , · · · , v2r , v2r+1 (= bt−1 ). Since Pt−1 is a longest ear of Gt−2 and bt ∈ V (Pt−1 ) \ V (Gt−2 ), we have r ≥ 2. Define an edge-coloring of Pt−1 by c(vi−1 vi ) = xi (1 ≤ i ≤ r), c(vr vr+1 ) = x and c(vi−1 vi ) = xi−r−1 (r + 2 ≤ i ≤ 2r + 1), where x1 , x2 , · · · , xr are new colors and x is a color that appears in Gt−2 . Similar to Case 1, the obtained coloring ct−1 of Gt−1 n is an incomplete rainbow coloring with  t−1 2  colors such that every pair of vertices have an incomplete rainbow path. If (Pt−1 ) is even, suppose that Pt−1 = v0 (= at−1 ), v1 , · · · , vr , vr+1 , · · · , v2r−1 , v2r (= bt−1 ), where r ≥ 2. Define an edge-coloring of Pt−1 by c(vi−1 vi ) = xi (1 ≤ i ≤ r), and c(vi−1 vi ) = xi−r (r + 1 ≤ i ≤ 2r), where x1 , x2 , · · · , xr are new colors. Similar to Case 2, the obtained coloring ct−1 of Gt−1 is n an incomplete rainbow coloring with  t−1 2  colors such that every pair of vertices have an incomplete rainbow path. Without loss of generality, assume that bt belongs to the first half of Pt−1 and that Pt = v 0 (= at ), v 1 , · · · , v s , v s+1 , · · · , v 2s−1 , v 2s (= bt ), where s ≥ 1. We color the edges of Pt with s − 1 new colors. Define an edge-coloring of Pt by c(v i−1 v i ) = yi (1 ≤ i ≤ s − 1), c(v s−1 v s ) = x1 , c(v s v s+1 ) = y and c(v i−1 v i ) = yi−s−1 (s + 2 ≤ i ≤ 2s), where y1 , y2 , · · · , ys−1 are new colors, y is a color in Gt−2 , and x = y. It is easy to verify that the obtained coloring ct of Gt is a rainbow coloring with  n2t  colors. For every pair of vertices v ∈ V (Pt )(v = v s ) and v ∈ V (Gt−1 ), there exists an incomplete rainbow path P connecting them, since the path from v to the nearer end vertex of Pt joining with the incomplete rainbow path from the end vertex to v in V (Gt−1 ) is an incomplete rainbow path from v to v in Gt . For v s , there is  an incomplete rainbow path from v s to any vertex in V (Gt−2 ) V (bt−1 Pt−1 vr+2 ) through edge e = v s−1 v s ; and an incomplete rainbow path from v s to any vertex in V (at−1 Pt−1 vr+1 ) through edge e = v s v s+1 . For every pair of vertices in V (Pt ) × V (Pt ), there is an incomplete rainbow path connecting them obviously. Hence, the rainbow coloring ct is incomplete.

Subcase 3.3. [V (Pt ) V (Pt−1 )]\V (Gt−2 ) = {at , bt }. We can prove this subcase in a way similar to Subcase 3.2. Without loss of generality, we can assume that at = v p (1 ≤ p ≤ r − 1) and bt = vq (q ≥ p + 2). Color all the edges of Pt−1 and Pt as in Subcase 3.2 but only the edge e = v s−1 v s which is colored by x p+1 in Pt−1 instead. The obtained coloring ct of Gt is an incomplete rainbow coloring with  n2t  colors. Lemma 3.2.5 ([69, 71]). Let G be a 2-connected non-Hamiltonian graph of order n (n ≥ 4). If G has at least two ears of length 2 in the nonincreasing ear decomposition, then rc(G) ≤  n2 . Proof. We only need to prove that there exists a rainbow coloring ct of the spanning subgraph Gt in the nonincreasing ear decomposition that uses at most  n2t  colors. If G has two or three ears of length 2 in the nonincreasing ear decomposition, then Gt−2 has at most one ear of length 2 and (Pt−1 ) = (Pt ) = 2. From Lemmas 3.2.3 n and 3.2.4, Gt−2 has an incomplete rainbow coloring ct−2 with  t−2 2  colors. Assume

3.2 Bounds in Terms of Connectivity

41

that Pt−1 = at−1 , v, bt−1 , and Pt = at , v , bt . Since Pt−1 is a longest ear of Gt−2 , we have at , bt ∈ V (Gt−2 ). Since the coloring ct−2 is incomplete, at−1 has an incomplete rainbow path P to one of at , bt (say at ) such that the color x in Gt−2 does not appear in P. Define an edge-coloring of Pt−1 and Pt by c(at−1 v) = c(bt−1 v) = c(bt v ) = x1 and c(at v ) = x, where x1 is a new color. It is clear that vat−1 Pat v is a rainbow path from v to v , and the obtained coloring of Gt is a rainbow coloring with  n2t  colors. Now consider the case that G has at least four ears of length 2 in the nonincreasing ear decomposition. Suppose that (Pt −1 ) ≥ 3 and (Pt ) = (Pt +1 ) = · · · = (Pt ) = 2. Since Pi (1 ≤ i ≤ k) is a longest ear, we have that at , bt , · · · , at , bt ∈ V (Gt −1 ), i.e., V (Gt −1 ) is a connected 1-step dominating set. From Lemmas 3.2.3 and 3.2.4, there n exists a rainbow coloring ct −1 of Gt −1 with  t 2−1  colors. Color one edge of Pi (t ≤ i ≤ t) with x1 and the other with x2 , where x1 , x2 are two new colors. It is obvious that Gt is rainbow connected. Since G has at least four ears of length 2, the obtained rainbow coloring of Gt uses at most  n2t  colors. From the above three lemmas and the fact that rc(Cn ) =  n2  (n ≥ 4), we can get the following result. Theorem 3.2.6 ([69, 71]). Let G be a 2-connected graph of order n (n ≥ 3). Then rc(G) ≤  n2 , and the upper bound is tight for n ≥ 4. In [34] Ekstein et al. rediscovered this result, and their proof is very long. Since for any two distinct vertices in a κ -connected graph G of order n, there exist at least κ internally disjoint paths connecting them, the diameter of G is not more than  κn . One could think of generalizing Theorem 3.2.6 to the case of higher connectivity. Li and Liu [69, 71] raised the following stronger conjecture that for every κ ≥ 1, if G is a κ -connected graph of order n, then rc(G) ≤ n/κ . Unfortunately, Ekstein et al. in [34] found examples showing that for every κ there are κ -connected graphs G of order n with rc(G) ≥ n−2 κ + 1, which is slightly bigger than n/κ  when κ (≥3) divides n. From Theorem 3.1.12, we can easily obtain an upper bound of the rainbow connection number according to the connectivity: rc(G) ≤

3n 3n +3 ≤ + 3. δ +1 κ +1

3n Therefore, for κ (G) = 3, rc(G) ≤ 3n 4 + 3; for κ (G) = 4, rc(G) ≤ 5 + 3. Motivated by the results in [11], and by using the Fan Lemma, Li and Shi [73] improved this bound by showing the following result:

Theorem 3.2.7 ([73]). If G is a 3-connected graph with n vertices, then rc(G) ≤ 3(n+1) 5 . For general κ , Chandran et al. [14] derived a corresponding result as shown in Theorem 3.2.11. To show it, we need several lemmas first. Lemma 3.2.8 ([14, 71]). If G is a bridgeless graph, and D is a connected -step dominating set of G, then

42

3 Upper Bounds for Rainbow Connection Numbers

rc(G) ≤ rc(G[D ]) + ( + 2) ≤ |D | − 1 + ( + 2). The proof of the lemma follows from repeated application of Lemma 3.3.3 which we will see in next section. Lemma 3.2.9 ([14, 71]). Every κ -connected (κ≥ 1) graph G of order n has a connected 2-step dominating set of size at most κ2+1 +1 n for every natural number  ≥ 0. The proof of this lemma is similar to that of Theorem 3.1.11 and thus is omitted. Theorem 3.2.10 ([14,71]). If G is a κ -connected (κ ≥ 1) graph of order n, then for every natural number  ≥ 0,

rc(G) ≤

 2 + 1 n + 2(2 + 2) − 1. κ + 1

Proof. The case κ = 1 is trivial. Hence, we assume κ ≥ 2 and therefore G is bridgeless. Since G is κ -connected, by Lemma  3.2.9, for every  ≥ 0 we have a 2step dominating set D of size at most κ2+1 +1 n. Now an application of Lemma 3.2.8 gives the result. Theorem 3.2.11 ([14, 71]). For every κ ≥ 1, if G is a κ -connected graph of order n, then for every ε ∈ (0, 1),

rc(G) ≤

2+ε κ

 n+

23 . ε2

Proof. Given an ε ∈ (0, 1), choose  =  ε1 . Then the result follows from Theorem 3.2.10. Note that 2(2 + 2) − 1 ≤ 23/ε 2 . The above bound may not be tight, and we are tempted to believe that the following conjecture might be true. Conjecture 3.2.12 ([14, 71]). For every κ ≥ 1, if G is a κ -connected graph of order n, then rc(G) ≤ n/κ + C, where C is a constant. In [14], the authors showed some cases in which Conjecture 3.2.12 is true, namely high girth graphs, chordal graphs. Theorem 3.2.13 ([14,71]). If G is a κ -connected graph such that κ ≥ 3 and g(G) ≥ 7, then rc(G) ≤ n/κ + 41. If G is κ -connected such that κ ≥ 5 and g(G) ≥ 5, then rc(G) ≤ n/κ + 19. Actually, the above result holds when replacing κ by δ . Theorem 3.2.14 ([14, 71]). For every κ -connected chordal graph G of order n, rc(G) ≤

n + 3. κ

3.3 Bounds in Terms of Radius and Bridges

43

For the edge-connectivity λ , Caro et al. [11] derived a result for 2-edgeconnected (bridgeless) graph: Theorem 3.2.15 ([11]). If G is a connected bridgeless graph with n vertices, then rc(G) ≤ 4n 5 − 1. From Theorem 3.1.12, we can also easily obtain an upper bound of the rainbow connection number according to λ : rc(G) ≤

3n 3n +3 ≤ + 3. δ +1 λ +1

The following is a construction of a λ -edge-connected graph G on n vertices with diameter d = λ3n +1 − 3 [14, 71]: Let d ≥ 1 be a natural number, and λ a natural number such that λ + 1 is a multiple of 3 and λ ≥ 8. Set k := λ +1 3 , and set V (G) = 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 = λ3n +1 − 3. By considering all pairs of vertices, it can be seen that G is λ -edge-connected. So, this upper bound in terms of the edge-connectivity is best possible.

3.3 Bounds in Terms of Radius and Bridges Note that all the above upper bounds are determined by n and other parameters such as (edge-) connectivity, minimum degree. Diameter of a graph, and hence its radius, are obvious lower bounds for the 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 cannot be upper bounded by a function of r alone. For instance, the star K1,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 Lemma 3.3.3, but at first we need to state two lemmas which will be used in its proof. Lemma 3.3.1 ([5]). For every edge e in a graph G, any shortest cycle in G containing e is isometric. The proof is not hard and thus is omitted. 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 }. The path P may be closed, 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 ). The proof of the following lemma is easy and uses Lemma 3.3.1.

44

3 Upper Bounds for Rainbow Connection Numbers

Lemma 3.3.2 ([5]). If P is an acceptable D-ear in a graph G for some D ⊂ V (G), then dG (x, D) = dP (x, D) for every x ∈ P where dP (x, D) is the length of a shortest x − D path along P. Lemma 3.3.3 ([5]). If G is a bridgeless graph, then for every connected k-step dominating set Dk of G, k ≥ 1, there exists a connected (k − 1)-step dominating set Dk−1 ⊃ Dk such that rc(G[Dk−1 ]) ≤ rc(G[Dk ]) + min{2k + 1, ζ }, where ζ = iso(G). Proof. Given Dk , we rainbow color G[Dk ] with rc(G[Dk ]) colors. Let m = min{2k + 1, ζ } and let A = {a1 , a2 , · · · } and B = {b1 , b2 , · · · } be two pools of colors, none of which are used to color G[Dk ]. A Dk -ear P = (x0 , x1 , · · · , x p ) will be called evenly colored if its edges are colored a1 , a2 , · · · , a p  , b p  , · · · , b2 , b1 in that order. 2

2

We prove this lemma by constructing a sequence of sets Dk = D0 ⊂ D1 ⊂ · · · ⊂ Dt = Dk−1 such that Di+1 = Di ∪ P where P is an acceptable Dk -ear and then coloring G[Di+1 ] in such a way that P is evenly colored using at most m colors from A ∪ B. In particular, this ensures that every x ∈ Di \ Dk , 0 ≤ i ≤ t, lies in an evenly colored acceptable Dk -ear throughout the construction. If N(Dk ) ⊂ Di , then Di is a (k − 1)-step dominating set and we stop the procedure by setting t = i. Otherwise pick any edge e = (x0 , x1 ) ∈ Dk × (N(Dk ) \ Di ) of G and let Q = (x0 , x1 , · · · , xq ) be the shortest Dk -ear containing e. Such a ear always exists since G is bridgeless. Let xl be the first vertex of Q in Di . If xl = xq , then evenly color Q. Hence, P = Q is an evenly colored acceptable Dk -ear. Otherwise, xl is on some evenly colored acceptable Dk -ear P added in an earlier iteration. By Lemma 3.3.2, dP (xl , Dk ) = dG (xl , Dk ). Hence, the shorter segment R of P (with respect to xl ) together with L = (x0 , x1 , · · · , xl ) is also an acceptable Dk -ear, P = L∪R containing e. Color the edges of L so that P is evenly colored. This is possible because (1) R uses colors exclusively from one pool (|R| ≤ |P |/2, since it is a shorter segment of P ) and (2) R forms a shorter segment of P(|L| ≥ dG (xl , Dk ) = |R|, by Lemma 3.3.2). Hence, the coloring of R can be evenly extended to L. Set Di+1 = Di ∪ P. First, we claim that at most m new colors are used in the above procedure for constructing Dk−1 from Dk . Since Dk is a k-step dominating set and since the Dk -ear P = (x0 , x1 , · · · , x p ) added in each iteration is acceptable, it follows that |P| ≤ 2k + 1. Otherwise, a middle vertex x p  of P will be at a distance more than k from Dk 2 (Lemma 3.3.2). Let C be a shortest cycle containing e = (x0 , x1 ). Such a C exists since G is bridgeless. By Lemma 3.3.1, the cycle C is isometric and hence |C| ≤ ζ . Further, |P| ≤ |C| since a subpath of C is a Dk -ear containing e. Thus, |P| ≤ m = min{2k + 1, ζ } in every iteration. Next, we claim that the G[Dk−1 ] constructed this way is rainbow connected. Every pair (x, y) ∈ Dk × Dk , is rainbow connected in G[Dk ]. For every pair (x, y) ∈ (Dk−1 \ Dk ) × Dk , let P = (x0 , x1 , · · · , xi = x, · · · , x p ) be the evenly colored (acceptable) Dk -ear containing x. Joining (x = xi , xi+1 , · · · , x p ) with a x p − y rainbow

3.3 Bounds in Terms of Radius and Bridges

45

path in G[Dk ] gives a x − y rainbow path. For every pair (x, y) ∈ (Dk−1 \ Dk ) × (Dk−1 \ Dk ), let P = (x0 , x1 , · · · , xi = x, · · · , x p ) and Q = (y0 , y1 , · · · , y j = y, · · · , yq ) be evenly colored (acceptable) Dk -ears containing x and y, respectively. Without loss of generality, we assume that the vertices of P and Q are ordered in such a way that their first halves get colors from Pool A . We consider the following four cases. If i ≤  2p  and j >  q2 , then joining (y = y j , y j+1 , · · · , yq ) (which is B-colored) to the yq − x0 rainbow path in G[Dk ] followed by (x0 , x1 , · · · , xi = x) (which is A colored) gives a x − y rainbow path. The case when i >  2p  and j ≤  q2  is similar. When i ≤  2p  and j ≤  q2  check if i ≤ j. If yes, join (y = y j , y j+1 , · · · , yq ) (which uses colors from {a ∈ A :  ≥ j + 1} ∪ B) to the yq − x0 rainbow path in G[Dk ] followed by (x0 , x1 , · · · , xi = x)(which uses colors from {a ∈ A :  ≤ i}) to get an x − y rainbow path. If i > j, then do the reverse. In the final case, when i >  2p  and j >  q2  check if q − j ≤ p − i. If yes, join (y = y j , y j+1 , · · · , yq ) (which uses colors from {b ∈ B :  ≤ q − j} to the yq − x0 rainbow path in G[Dk ] followed by (x0 , x1 , · · · , xi = x) (which uses colors from A ∪ {b ∈ B :  ≥ p − i + 1}) to get an x − y rainbow path. If q − j > p − i, then do the reverse. Any edge in G[Dk− 1] left uncolored by the procedure can be assigned any used color to complete the rainbow coloring. 

If u is a central vertex of G, i.e., ecc(u) = r, then Dr = {u} is an r-step dominating set in G and rc(G[Dr ]) = 0. The only 0-step dominating set in G is V (G). Hence, repeated application of Lemma 3.3.3 gives the following upper bound. Theorem 3.3.4 ([5]). For every connected bridgeless graph G, r

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

where r is the radius of G. Theorem 3.3.4 has two corollaries. Corollary 3.3.5 ([5]). For every connected bridgeless graph G with radius r, rc(G) ≤ r(r + 2). Moreover, for every integer r ≥ 1 there exists a bridgeless graph with radius r and rc(G) = r(r + 2). Corollary 3.3.6 ([5]). For every connected bridgeless graph G with radius r and chordality k, r

rc(G) ≤ ∑ min{2i + 1, k} ≤ rk. 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 rc(G) = ∑ri=1 min{2i + 1, k}. Corollary 3.3.5 answered the above question in the affirmative, the bound is sharp and is a function of the radius r alone. Basavaraju, Chandran, Rajendraprasad

46

3 Upper Bounds for Rainbow Connection Numbers

V0

V1

x0,1

x1,1

x2,1

x3,1

x4,1

x5,1

x6,1

x7,1

x8,1

x9,1

x10,1

x11,1

x0,0

x1,0

x2,0

x3,0

x4,0

x5,0

x6,0

x7,0

x8,0

x9,0

x10,0

x11,0

Vt

x12,0

Fig. 3.1 Graph X3,2

and Ramaswamy also demonstrated that the bound cannot be improved even if we assume stronger connectivity by constructing a κ -vertex-connected graph of radius r whose rainbow connection number is r(r + 2) for any two given integers κ , r ≥ 1: Let s(0) := 0, s(i) := 2∑r−i+1 j for 1 ≤ i ≤ r and t := s(r) = r(r + 1). j=r Let V = V0  V1  · · ·  Vt where Vi = {xi,0 , xi,1 , · · · , xi,κ −1 } for 0 ≤ i ≤ t − 1 and Vt = {xt,0 }. Construct a graph Xr,κ 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}. Figure 3.1 depicts X3,2 , note that (1) X3,2 is 2-connected and (2) ecc(x0,0 ) = 3. Corollary 3.3.6 generalizes 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. In Corollary 3.3.5, Basavaraju et al. showed that for every bridgeless graph G with radius r, rc(G) ≤ r(r + 2), and the bound is tight. As one can see, they did not consider graphs with bridges. Since bridges are important things in a rainbow coloring (any two different bridges must receive distinct colors), Dong and Li [30] considered graphs with bridges. They upper-bounded rc(G) by the number of bridges and radius of a graph G. Theorem 3.3.7. 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 , · · · , D1 such that Dr ⊂ Dr−1 ⊂ Dr−2 · · · ⊂ D1 ⊂ D0 = V (G) and rc(G) ≤ ∑ri=1 max{2i + 1, bi}, where bi is the number of bridges in E[Di , N(Di )] for 1 ≤ i ≤ r, and the number of bridges in G is equal to ∑ri=1 bi . Note that if bi ≤ 2i + 1 for all 1 ≤ i ≤ r, then rc(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 rc(G) = ∑ri=1 bi , the number of bridges of G. So, this generalizes Corollary 3.3.5. Dong and Li [30] also gave two examples, one of which shows a graph G with radius r, such that the number of bridges is not more than r(r + 2) and rc(G) = r(r + 2), whereas the other one shows a graph G with radius r, such that the number of bridges b is at least r(r + 2) + 1 and rc(G) = b. 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. [50] generalized Theorem 3.3.4 in the following result.

3.4 Complementary Graphs

47

Theorem 3.3.8. For every bridgeless graph G with radius r, r

rc(G) ≤ ∑ min{2i + 1, η (G)} ≤ rη (G). i=1

They also gave upper bounds of the rainbow connection numbers for plane graphs, edge-transitive graphs and bipartite graphs.

3.4 Complementary Graphs In [80], Li and Sun investigated 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 rc(G) is bounded by a constant. By using the fact that rc(G) ≤ rc(H) where H is a connected spanning subgraph of a connected graph G, and the structure of its complement graph as well as Propositions 1.3.4 and 1.3.5, they derived the following result. Theorem 3.4.1 ([80]). For a connected graph G, if 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 rc(G) ≤ 4. Furthermore, this bound is best possible. The following result is an important ingredient in the proof of Theorem 3.4.1: If G is a connected graph with diam(G) ≥ 4, then rc(G) ≤ 4. The sketch of its proof is as follows. Clearly, we see that G must be connected. We choose a vertex x with eccG (x) = diam(G) = d ≥ 4. Let NGi (x) = {v : dist(x, v) = i} where  0 ≤ i ≤ d. So NG0 (x) = {x}, NG1 (x) = NG (x) as usual. Then, 0≤i≤d NGi (x) is a vertex   partition of V (G) with |NGi (x)| = ni . Let A = i is even NGi (x), B = i is odd NGi (x). For example, see Fig. 3.2, a graph with diam(G) = 4. So, if d = 2k(k ≥ 2)   then A = 0≤i≤d is even NGi (x), B = 1≤i≤d−1 is odd NGi (x); if d = 2k + 1(k ≥ 2)   then A = 0≤i≤d−1 is even NGi (x), B = 1≤i≤d is odd NGi (x). Then by the definition of complement graphs, we know that G[A](G[B]) contains a spanning complete d k1 -partite subgraph (complete k2 -partite subgraph) where k1 =  d+1 2 (k2 =  2 ). x N G0 (x) N G1 (x) N G2 (x) N G3 (x)

Fig. 3.2 Graph for the example with d = 4

N G4 (x) A

G

B

48

3 Upper Bounds for Rainbow Connection Numbers

For example, see Fig. 3.2, G[A] contains a spanning complete tripartite subgraph Kn0 ,n2 ,n4 , G[B] contains a spanning complete bipartite subgraph Kn1 ,n3 . Then, we need to consider two cases: d ≥ 5 and d = 4. For the remaining cases, rc(G) can be very large as discussed in [80]. So, they add a constraint: if G is triangle-free, then G is claw-free, and they then derived the following result. In their argument, Theorem 5.2.1 is useful. Theorem 3.4.2 ([80]). For a connected graph G, if G is triangle-free, then rc(G) ≤ 6. The readers may consider the rainbow connection number of a graph G according to some other conditions to its complement graph. Nordhaus–Gaddum-type results are related to complementary graphs. Chen et al. [20] investigated Nordhaus–Gaddum-type results. A Nordhaus–Gaddum-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 [84] who first established the following type of inequalities for chromatic numbers of graphs in 1956. Theorem 3.4.3 ([20]). Let G and G be connected with n ≥ 4, then 4 ≤ rc(G) + rc(G) ≤ n + 2. Furthermore, the upper bound is sharp for n ≥ 4 and the low bound is sharp for n ≥ 8. Proof. We first give the upper bound. The following claim is easy. Claim 6. rc(G) + rc(G) ≤ n + 2 for n = 4, 5, and the bound is sharp. We also need the following claim. Claim 7. Let G be a nontrivial connected graph of order n, and rc(G) = k. Let c : E(G) → {1, 2, · · · , k} be a rainbow k-coloring of G. Add a new vertex w to G, w is adjacent to q vertices of G, the resulting graph is denoted by G . Then if q ≥ n + 1 − k, we have rc(G ) ≤ k. Proof of Claim 7. Let X = {x1 , x2 , · · · , xq } be the vertices adjacent to P, V \X = {y1 , y2 , · · · , yn−q }. If q ≥ n + 1 − k, n − q ≤ k − 1. Since G is rainbow connected under the coloring c, for any yi , i ∈ {1, 2, · · · , n − q}, there is a rainbow x1 − yi path, say Px1 y1 , Px1 y2 , · · · , Px1 yn−q . For each Px1 yi , we find out the last vertex on the path that belongs to X, and the subpath between this vertex to yi of Px1 yi is denoted by Pi . Then Pi is a rainbow path whose vertices are in Y except the first vertex. Let Gxi be the union of the paths in P1 , P2 , · · · , Pn−q whose origin vertex is xi , 1 ≤ i ≤ q. If there is no path with origin vertex xi , let Gxi be a trivial graph with the vertex xi . Then Gxi is a subgraph of G, and |V (Gxi )| ≤ n − q + 1 ≤ k. First, we consider the subgraph Gx1 , and let V (Gx1 ) = {x1 , yi1 , yi2 , · · · , yi }.

3.4 Complementary Graphs

49

Case 1. The number of colors appeared in Gx1 is k. Then |E(Gx1 )| ≥ k. Subcase 1.1. |E(Gx1 )| = k ≥ |V (Gx1 )|. In this case, Gx1 contains a cycle, and no two edges of Gx1 are colored the same. Thus, Gx1 is rainbow connected. Let e be an edge in the cycle. Then, by deleting e and coloring the edge wx1 with color c(e), we get that, for any j ∈ {1, 2, · · · , }, there is a rainbow w − yi j path. Subcase 1.2. |E(Gx1 )| > k ≥ |V (Gx1 )|. In this case, Gx1 contains a cycle, and there are two edges e1 , e2 with c(e1 ) = c(e2 ). If one of the edges, say e1 , is contained in a cycle of Gx1 . Then, by deleting it, we obtain a spanning subgraph G x1 of Gx1 with the same number of colors appearing in it, but |E(G x1 )| = |E(Gx1 )| − 1. If |E(G x1 )| = k, by a similar operation as in Subcase 1.1, we can obtain a coloring of wx1 such that for any j ∈ {1, 2, · · · , }, there is a rainbow w − yi j path. If |E(G x1 )| > k, we consider the graph G x1 other than Gx1 . If both e1 , e2 are not in a cycle, they must be cut edges of Gx1 . Then, contract one of them, say e1 , and denote the resulting graph by G x1 . The number of colors appeared in Gx1 is still k, and |V (G x1 )| = |V (Gx1 )| − 1, |E(G x1 )| = |E(Gx1 )| − 1. If |E(G x1 )| = k, by a same operation as in Subcase 1.1, we can obtain a coloring of wx1 such that for any yk in G x1 , there is a rainbow w − yk path. It is easy to check that there still exists a rainbow w − yi j path in Gx1 for any j ∈ {1, 2, · · · , }. If |E(G x1 )| > k, we consider the graph G x1 other than Gx1 . Case 2. The number of colors appeared in Gx1 is less than k. Then we color the edge wx1 with a color not appeared in Gx1 . No matter which cases happen, we can always color the edge wx1 with one of the colors {1, 2, · · · , k}, such that for any j ∈ {1, 2, · · · , }, there is a rainbow w − yi j path. For Gx2 , Gx3 , · · · , Gxq , we use the same way to color the edges wx2 , wx3 , · · · , wxq . Then we get a k-coloring of G . Since for each yi , there is an x j , such that yi ∈ Gx j , then the path wx j Pi is a rainbow path connecting w and yi . Thus in this coloring, G is rainbow connected. Therefore, rc(G ) ≤ k. This completes the proof of Claim 7. Now we continue to prove the upper bound. We use induction on n. From Claim 6, the result is true for n = 4, 5. We assume that rc(G) + rc(G) ≤ n + 2 holds for complementary graphs on n vertices. To the union of connected graphs G and G, a complete graph on the n vertices, we adjoin a new vertex w. Let q be the number of vertices of G which are adjacent to w, then the number of vertices of G which are adjacent to w is n − q. If G and G are the resultant graphs (each of order n + 1), then rc(G ) ≤ rc(G) + 1, rc(G ) ≤ rc(G) + 1. These inequalities are evident from the fact that if given a rainbow rc(G)-coloring (rc(G)-coloring) of G (G), we assign a new color to the edges added from P to G (G), the resulting coloring makes G (G ) rainbow connected. Then rc(G ) + rc(G ) ≤ rc(G) + rc(G) + 2 ≤ n + 4. And rc(G ) + rc(G ) ≤ n + 3 except possibly when rc(G ) = rc(G) + 1, rc(G ) = rc(G) + 1.

50

3 Upper Bounds for Rainbow Connection Numbers

Fig. 3.3 rc(G) = rc(G) = 2 for n = 8

In this case, by Claim 7, q ≤ n − rc(G), n − q ≤ n − rc(G), thus rc(G) + rc(G) ≤ n, from which rc(G ) + rc(G ) ≤ n + 2. This completes the induction. We now give an example showing that the upper bound can be reached when n ≥ 4: let G be a tree obtained by joining the centers of two stars S p and Sq by an edge uv, where u and v are the centers of S p and Sq , and p + q = n. Then rc(G) = n − 1. To compute the rainbow connection number of the complement graph of G, we assume that X = V (S p \u) ∪ {v}, Y = V (Sq \v) ∪ {u}. Then G is a bipartite graph with bipartition (X,Y ). Thus G[X], G[Y ] is complete. We assign color 1 to G[X], 2 to G[Y ] and 3 to the edges between X and Y . The resulting coloring makes G rainbow connected, thus rc(G) ≤ 3. On the other hand diam(G) = dG (u, v) = 3, it follows that rc(G) = 3. Then we have rc(G ) + rc(G ) = n + 2. Next, we will prove the lower bound. Since rc(G) = 1 if and only if G is a complete graph, then G is not connected. Thus, if both G and G are connected, then rc(G) ≥ 2 and rc(G) ≥ 2, and so rc(G) + rc(G) ≥ 4. The following claim is not hard and we omit the proof. Claim 8. For 4 ≤ n ≤ 7, there are no graphs G and G on n vertices, such that rc(G) = rc(G) = 2. We now consider the case n ≥ 8. For n = 8, see Fig. 3.3, colored with two colors, the heavy line with color 2, the others with color 1. It is easy to check that they are rainbow connected. If n = 4k, let G be the graph with vertex set X ∪Y ∪ {v}, where X = (x1 , x2 , · · · , x2k−1 ), Y = {y1 , y2 , · · · , y2k }, such that N(v) = X, X is an independent set, G[Y ] is a clique, and for each xi , xi is adjacent to yi , yi+1 , · · · , yi+k , where the sum is taken modulo 2k. We define a coloring c for the graph G by the following rules: ⎧ ⎨ 2 if e = vxi for k + 1 ≤ i ≤ 2k − 1, c(e) = 2 if e = xi yi for 1 ≤ i ≤ 2k − 1, and e = xk yk+1 , ⎩ 1 otherwise. Then c is a rainbow 2-coloring. And it is easy to check that G can also be colored by two colors and make it rainbow connected. If n = 4k + 1, G can be obtained by adding a vertex x2k to the vertex set X in the case n = 4k, and joined x2k to v, y2k , y1 , · · · , yk−1 . With the coloring c defined above, in addition with c(vx2k ) = c(x2k y2k ) = 2, G is rainbow connected. If n = 4k + 2, G can be obtained by adding two vertices x2k , y2k+1 to the vertex set X and Y , respectively, in the case n = 4k, and joined x2k to v, y2k+1 to each

3.5 Miscellaneous Bounds

51

vertex in Y . And for each xi , xi is adjacent to yi , yi+1 , · · · , yi+k , where the sum is taken modulo 2k + 1. With the coloring c defined above, in addition with c(vx2k ) = c(x2k y2k ) = 2, G is rainbow connected. If n = 4k + 3, G can be obtained by adding two vertices x2k+1 , y2k+1 to the vertex set X and Y , respectively, in the case n = 4k + 1, and joined x2k+1 to v, y2k+1 to every vertex in Y . And for each xi , xi is adjacent to yi , yi+1 , · · · , yi+k , where the sum is taken modulo 2k + 1, we also join xk+1 to y2k+1 . With the coloring c defined above, in addition with c(vx2k+1 ) = c(x2k+1 y2k+1 ) = 2, G is rainbow connected.

 The authors of [20] also proved that rc(G) + rc(G) ≥ 6 for n = 4, 5; and rc(G) + rc(G) ≥ 5 for n = 6, 7 and these bounds are best possible.

3.5 Miscellaneous Bounds In [11], Caro et al. also derived a result which gives an upper bound for rainbow connection number according to the order and the number of vertex-disjoint cycles. Here, χ (G) is the chromatic index of G. Theorem 3.5.1 ([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 rc(G) < 3n/4 + s/4 − 1/2. In particular: (i) If G has a 2-factor then rc(G) < 3n/4. (ii) If G is k-regular and k is even then rc(G) < 3n/4. (iii) If G is k-regular and χ (G) = k then rc(G) < 3n/4. In terms of minimum degree, they also obtained the following result: Theorem 3.5.2 ([11, 67]). If G is a connected graph of order n with minimum degree δ , then rc(G) ≤ n − δ . As a consequence they got the following Corollary 3.5.3 ([11]). If G is a connected graph of order n with average degree d ≥ 2, then rc(G) ≤ n − d/2 − 1. Schiermeyer [90] got a few results on other graph parameters. Theorem 3.5.4 ([90]). If G is a connected graph of order n with circumference c(G), then rc(G) ≤ n −  c(G) 2 . Theorem 3.5.5 ([90]). If G is a graph with a connected complement G with chromatic number χ (G), then rc(G) ≤ 2 χ (G) − 1. The toughness parameter is important in the structure of a graph, for example, if G is 2-tough then G has a 2-factor. So the following problem might be interesting. Problem 3.3. What happens with the value rc(G) for graphs with higher toughness parameter?

52

3 Upper Bounds for Rainbow Connection Numbers

3.6 Bound for Strong Rainbow Connection Number From the above, one can see that there have been so much work on upper bounds for the rainbow connection number. We now turn to the strong rainbow connection number. From the definition, the investigation of this number is more challenging than that of the rainbow connection number. However, there are very few papers that have been published about it. In [15], Chartrand et al. determined the precise values of the strong rainbow connection numbers for some special graph classes including trees, complete graphs, wheels, and complete bipartite (multipartite) graphs as shown in Sect. 1.3. However, for a general graph G, it is almost impossible to give the precise value of src(G). So, we try to give upper bounds for it according to some graph parameters. Li and Sun [79] derived a sharp upper bound for src(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. Recall that a block of a connected graph G is a maximal connected subgraph without any 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: 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 2 in G. By the definition, each graph G ∈ G t is formed by (edge-disjoint) triangles and paths (may be trivial), 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. 3.4, here t = 2, and u1 , u2 and u6 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 a D2 -tree of G, denoted by TG . For example, in Fig. 3.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 u1 instead of u2 . 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. u1

u1 u3

T1

u4 T2

Fig. 3.4 An example of G ∈ G t with t = 2

u5

u6 G

u7

u2 u4

u8

u3

u5 TG

u7

u8

3.6 Bound for Strong Rainbow Connection Number

53

Li and Sun derived the following result: Theorem 3.6.1 ([79]). If G is a graph with m edges and t edge-disjoint triangles, then src(G) ≤ m − 2t, the equality holds if and only if G ∈ G t . Proof. Let T = {Ti : 1 ≤ i ≤ t} be a set of t edge-disjoint triangles in G. We color each triangle with a fresh color, that is, the three edges of each triangle receive a same color. Then, we give each other edge a fresh color. For any two vertices u, v of G, let P be any u − v geodesic. Then clearly P contains at most one edge from each triangle. So P is rainbow under the above coloring. As this procedure costs m − 2t colors totally, we have src(G) ≤ m − 2t. The following claim is clear. Claim 9. If the equality holds, then for any set T of edge-disjoint triangles of G, we have |T | ≤ t. Claim 10. If the equality holds, then G contains no cycle but the above t (edgedisjoint) triangles. Proof. We suppose that there is at least one cycle distinct from the above t triangles. Let C be the set of these cycles and C1 be the smallest element of C with |C1 | = k. We will consider two cases: / that is, C1 is edge-disjoint with each of the above t Case 1. E(C1 ) ∩ E(T ) = 0, triangles. Clearly, C1 has at most one common vertex with each of the above t triangles. In this case, k ≥ 4 by Claim 9. We give G an edge-coloring as follows. We first color the edges of cycle C1 the same as in [15]: let |C1 | = k. If k is even, let k = 2 for some integer  ≥ 3, c(ei ) = i for 1 ≤ i ≤  and c(ei ) = i −  for  + 1 ≤ i ≤ k; If k is odd, let k = 2 + 1 for some integer  ≥ 3, c(ei ) = i for 1 ≤ i ≤  + 1 and c(ei ) = i −  − 1 for  + 2 ≤ i ≤ k; then we color each triangle with a fresh color; for the remaining edges, we give each one a fresh color. Recall the fact that any geodesic contains at most one edge from each triangle. It is easy to show that the above coloring is strongly rainbow. As this procedure costs  2k  + t + (m − k − 3t) = (m − 2t) + ( 2k  − k) < m − 2t colors totally, we have src(G) < m − 2t, which produces a contradiction. / that is, C1 has common edges with the above t triangles, Case 2. E(C1 )∩E(T ) = 0, in this case k ≥ 3. By the choice of C1 , we know that |E(C1 )∩E(Ti )| ≤ 1 for each 1 ≤ i ≤ t. We only consider the case for k even, since for k odd, the proof is similar. Let k = 2 for some  ≥ 2. For example, see graph (α ) of Fig. 3.5, here T = {T1 , T2 , T3 }, V (C1 ) = {ui : 1 ≤ i ≤ 6}, E(C1 )∩E(T1 ) = {u1 u2 }, E(C1 )∩E(T2 ) = {u4 u5 }. Without loss of generality, we assume that there exists a triangle, say T1 , which contains the edge u1 u2 , and let V (T1 ) = {u1 , u2 , w1 }, G = G\E(T1 ). If there exists some triangle, say T2 , which contains the edge u+1 u+2 , we let V (T2 ) = {u+1 , u+2, w2 }. At first we consider the case for  = 2, see the graph (β ) of Fig. 3.5. We first give each triangle of G a fresh color; for the remaining edges of G , we give each of them a fresh color; for the edges of T1 , let c(u1 w1 ) = c(u2 u3 ), c(u2 w1 ) = c(u1 u4 ),

54

3 Upper Bounds for Rainbow Connection Numbers

Fig. 3.5 Graphs of Theorem 3.6.1

u6 u5

u1

T1

T w2 2 u u3 4 C1 T3 (α)

w1 u2

w1 1 T 2 u1 1 u2 3 1 2 C1 u4

3

u3

(β )

c(u1 u2 ) = c(u3 u4 ). Then we can show that there is a u − v geodesic which contains at most one edge from any two edges with the same color for u, v ∈ G, and so the above coloring is strongly rainbow. As this procedure costs m − 2t − 1 < m − 2t colors totally, we have src(G) < m − 2t, a contradiction. We next consider the case for  ≥ 3. Let G = G\(E(T1 ) ∪ E(T2 )). We give G an edge-coloring as follows: we first give each triangle of G a fresh color; then we give a fresh color to each of the remaining edges of G ; for the edges of T1 and T2 , let c(u1 w1 ) = c(u2 u3 ), c(u2 w1 ) = c(u1 uk ), c(u1 u2 ) = c(u+1 u+2 ) = c, c(w2 u+1) = c(u+2 u+3), c(w2 u+2) = c(u u+1 ) where c is a new color. Then we can show that there is a u − v geodesic which contains at most one edge from any two edges with the same color for u, v ∈ G, and so the above coloring is strongly rainbow. As this procedure costs m − 2t − 1 < m − 2t colors totally, we have src(G) < m − 2t, a contradiction. Claim 11. If the equality holds, then G ∈ G t . Proof. If the equality holds, to show G ∈ G t , it suffices to show that each triangle contains at least one vertex of degree 2 in G. Suppose that it does not hold, without loss of generality, let T1 be the triangle with degG (vi ) ≥ 3, where V (T1 ) = {vi : 1 ≤ i ≤ 3}. By Claim 10, it is easy to show that E(T1 ) is an edge-cut of G. Let Hi be the subgraph of G\E(T1 ) containing the vertex vi (1 ≤ i ≤ 3). By the assumption of T1 , we know that each Hi is nontrivial. We now give G an edge-coloring: for the t − 1 (edge-disjoint) triangles of G\E(T1 ), we give each of them a fresh color; for the remaining edges of G\E(T1 ) (by Claim 10, each of them must be a cut-edge), we give each of them a fresh color; for the edges of E(T1 ), let c(v1 v3 ) ∈ c(H2 ), c(v1 v2 ) ∈ c(H3 ), c(v2 v3 ) ∈ c(H1 ). It is easy to show that, with the above coloring, G is strongly rainbow connected, and we have src(G) < m − 2t, a contradiction, so the claim holds. Claim 12. If G ∈ G t , then the equality holds. Proof. Let TG be a D2 -tree of G. The result clearly holds for the case |E(TG )| = 1. Now we assume |E(TG )| ≥ 2. We will show that, for any strong rainbow coloring of G, c(e1 ) = c(e2 ) where e1 , e2 ∈ TG , that is, each edge of TG receives a distinct color. So the edges of TG cost m − 2t colors totally. Recall that |E(TG )| = m − 2t, then src(G) ≥ m − 2t, by the above claim, Claim 12 holds. For any two edges, say e1 , e2 , of TG , let e1 = u1 u2 , e2 = v1 v2 . Without loss of generality, we assume that dTG (u1 , v2 ) = max{dTG (ui , v j ) : 1 ≤ i, j ≤ 2} where

3.6 Bound for Strong Rainbow Connection Number

55

dTG (u, v) denotes the distance between u and v in TG . As TG is a tree, the (unique) u1 − v2 geodesic, say P, in TG must contain the edges e1 , e2 . Moreover, it is easy to show that P is also a unique u1 − v2 geodesic in G, and so c(e1 ) = c( e2 ) under any strong rainbow coloring. By Claims 11 and 12, the equality holds if and only if G ∈ G t . Then our result holds. 

In [1], Ahadi and Dehghan also derived an upper bound for strongly regular 1

graph: if G is an SRG(n, r, λ , μ ), then src(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 the paragraph below Problem 1.1 for an example). The investigation of strong rainbow connection number is much harder than that of rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster gave the following conjecture. Conjecture 3.6.2 ([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 ε .

Chapter 4

Dense and Sparse Graphs

For any given graph G, we know that 1 ≤ rc(G) ≤ src(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 1.3.1, the cases that rc(G) = 1, src(G) = 1 and rc(G) = m, src(G) = m are clear. So what we want to investigate are the other cases.

4.1 Dense Graphs In [11], Caro et al. investigated graphs with small rainbow connection numbers and they gave a sufficient condition that guarantees rc(G) = 2. Theorem 4.1.1 ([11]). Any noncomplete graph with δ (G) ≥ n/2 + log n has rc(G) = 2. Proof. Given a graph G with n vertices and δ (G) ≥ n/2 + logn, we randomly color the edges with two colors, red and blue. We show that with positive probability, such a random coloring makes G rainbow connected. Consider two nonadjacent vertices x, y. The minimum degree requirement forces x and y to have more than 2 log n common neighbors. Now, for each such common neighbor z, the probability that the path x, z, y is not a rainbow path is precisely 1/2. Since the paths corresponding to distinct common neighbors are edge-disjoint, the probability that all  these paths are not rainbow is less than (1/2)2 logn . Since there are less than n2 pairs x, y to consider, it follows from the union bound that with positive probability, each pair of nonadjacent vertices are connected by a rainbow path.   We know that having diameter 2 is a necessary requirement for having rc(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 rc(G) = 2. Theorem 4.1.1 asserts that minimum degree n/2 + logn guarantees rc(G) = 2. Clearly, minimum X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 4, © Xueliang Li, Yuefang Sun 2012

57

58

4 Dense and Sparse Graphs

degree n/2−1 does not, as there are connected graphs with minimum 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 the following Problem 4.1 ([11]). Determine the minimum degree threshold that guarantees that rc(G) = 2. In particular, Can δ (G) ≥ n/2 guarantees rc(G) = 2? or find a graph G with δ (G) ≥ n/2 but rc(G) ≥ 3. The following might also be an interesting problem. Problem 4.2. Give a degree-sum condition to guarantee that rc(G) = 2. Following the same idea of Caro et al. as in [11], Dong and Li [33] got the following results. Theorem 4.1.2 ([33]). Let k ≥ 2 be an integer. If G is a noncomplete graph of order n with δ (G) ≥ n2 − 1 + logkn, then rc(G) ≤ k. Theorem 4.1.3 ([33]). Let k ≥ 2 be an integer. If G is a noncomplete graph of order n with minimum degree-sum σ2 (G) ≥ n − 2 + 2logkn, then rc(G) ≤ k. Kemnitz and Schiermeyer [53] gave a sufficient condition to guarantee rc(G) = 2 according to the number m of edges.   Theorem4.1.4 ([53]). Let G be a connected graph of order n and size m. If n−1 2 +  1 ≤ m ≤ n2 − 1, then rc(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, 40]). Since having rc(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 4.1.5 ([11]). The probability p = log n/n is a sharp threshold function for the graph property rc(G(n, p)) ≤ 2. Proof. For the first part of the theorem, we need to prove  that for a sufficiently large constant C, the random graph G(n, p) with p = C log n/n almost surely has rc(G(n, p)) = 2. By the proof of Theorem 4.1.1, it suffices to show that almost surely any two vertices of G(n, p) have at least 2 log n common neighbors. By the union bound, it suffices to prove that a fixed pair of vertices does not have at least 2 log n common neighbors with probability o(1/n2). Fixing a pair x, y, the probability of the event that z is a common neighbor is C2 log n/n. Thus, the expected 2 2 number of common neighbors is n−2 n (C log n) > 0.5c log n, and this is the sum of n − 2 indicator random variables of independent events. By the standard Chernoff

4.1 Dense Graphs

59

estimates (see [3]), the probability that the number of common neighbors is less than half of its expectation (in this case, less than 0.25c2 log n) is o(1/n2) for C sufficiently large. For the other direction, it suffices  to prove that for a sufficiently small constant c, the random graph G(n, p) with p = c log n/n almost surely does not have diameter 2. Fix a set X of n1/5 vertices (we may and will assume that n1/5 is an even integer), and let Y be the remaining n − n1/5 vertices. Let A be the event that X induces an independent set, and let B be the event that there exists a pair of vertices of X with no common neighbor in Y . Clearly, if both A and B occur, then the diameter is at least 3. Hence, it suffices to prove (separately) that for a small c, A occurs with probability approaching 1 and B occurs with probability approaching 1. We start with A first. For c sufficiently small, we indeed have:  n1/5 n1/5 Pr[A ] = (1 − p)( 2 ) = (1 − c log n/n)( 2 ) = 1 − on(1). To estimate B, let us first partition X into n1/5 /2 pairs, arbitrarily. For a pair x, y, the probability that x, y have a common neighbor in Y is precisely  n−n1/5 c2 log n . 1− 1− n Thus, for c sufficiently small, the probability that all |X|/2 pairs have a common neighbor is ⎛ ⎞ 1/5   1/5 n /2 2 log n n−n c ⎝1 − 1 − ⎠ = on (1). n We use here the fact that the event that a pair x, y has a common neighbor in Y is independent of all the events that other pairs have common neighbors in Y . Since the last inequality is on (1) we have that with probability 1 − on(1) at least one of the pairs does not have a common neighbor in Y , and, in particular, B holds.   Li et al. in [59] investigated a new parameter concerning the rainbow connection number. Let k and n be natural numbers with k < n. Denote by Gk (n) the set of all graphs of order n with rainbow connection number at most k. Define t(n, k) = min{e(G) | G ∈ Gk (n)}, where e(G) denotes the number of edges in G. They derived a result corresponding to graphs G with rc(G) = 2. Theorem 4.1.6 ([59]). lim

n→∞

t(n, 2) = 1. n log2 n

60

4 Dense and Sparse Graphs

Schiermeyer [91] derived the following more general result. Theorem 4.1.7 ([91]). Let k and n be natural numbers with k < n. Then we have   n t(n, 1) = , 2 t(n, 2) ≤ log2 n (n + 1) − 2log2 n +1 + 2, t(n, 3) ≤ 2n − 5, t(n, k) ≤ n − 1 +

n−1 n−2 for4 ≤ k ≤ , k−2 2

n t(n, k) = nfor ≤ k ≤ n − 2, 2 t(n, n − 1) = n − 1. Kemnitz and Schiermeyer in [53] considered Erd˝os-Gallai type problem for rainbow connection number, and introduced a parameter s(n, k) for graphs of order n, which is the smallest number with the property that if a graph G has |E(G)| ≥ s(n, k), then rc(G) ≤ k. Obviously, s(n, k) ≥ t(n, k). They proposed the following problem. Problem 4.3 ([53]). For every k with 1 ≤ k ≤ n − 1, compute the function s(n, k). Kemnitz and Schiermeyer [53], and Li et al. [68] obtained the following results. Theorem4.1.8 ([53, 68]). Let k and n be natural numbers with k ≤ n. Then s(n, k) ≥ n−k+1 + (k − 1), where equality holds for k = 1, 2, 3, 4, n − 1, n. 2 A natural question is: Does the above equality hold for any 1 ≤ k ≤ n. It seems that the method used in [53,68] cannot be used for general k, for which new method is needed. Let G be a graph G with rainbow connection number k. An edge e of G is called removable if rc(G − e) = rc(G) = k. We call G k-rainbow minimal if for any edge e of G, rc(G − e) > rc(G) = k, and k-rainbow maximal if for any nonadjacent vertices u and v of G, rc(G + uv) < rc(G) = k. The following problem may be more challenging. Problem 4.4. Let G be a graph G with rainbow connection number k. Characterize the removable edges of G. Characterize those graphs that are k-minimal (k-maximal). Especially, for k = 2, 3 or 4, try to solve the problem. By Proposition 1.3.1, we know that the problem of considering graphs with rc(G) = 2 is equivalent to that of considering graphs with src(G) = 2. A bipartite graph which is not complete has diameter at least 3. A proof similar to that of Theorem 4.1.5 gives the following result. Theorem 4.1.9 ([11]). Let c = 1/log(9/7). If G is a noncomplete bipartite graph with n vertices and any two vertices in the same vertex class have at least 2clog n common neighbors in the other vertex class, then rc(G) = 3.

4.1 Dense Graphs

61

A similar result was obtained by Dong and Li in [33]. Theorem 4.1.10 ([33]). Let k ≥ 3 be an integer. If G is a noncomplete bipartite graph of order n and any two vertices in the same vertex class have at least 2log k2 klogk n common neighbors in the other class, then rc(G) ≤ k. 3k−2

The following theorem asserts however that having diameter 2 and only logarithmic minimum degree suffices to guarantee rainbow connection 3. Theorem 4.1.11 ([12]). If G is a graph of order n with diameter 2 and minimum degree at least 8 log n, then rc(G) ≤ 3. A similar result was also obtained by Dong and Li in [33]. Theorem 4.1.12 ([33]). Let k ≥ 3 be an integer. If G is a graph of order n with diameter 2 and δ (G) ≥ 2(1 + log k2 k)logk n, then rc(G) ≤ k. 3k−2

Since a graph with minimum degree n/2 is connected and has diameter 2, the following corollary is immediate. Corollary 4.1.13 ([12]). If G is an n-vertex graph with minimum degree at least n/2, then rc(G) ≤ 3. We know that graphs with rc(G) = 2 belong to the graph class with diam(G) = 2. By Corollary 3.3.5, we know that for a bridgeless graph with diam(G) = 2, rc(G) ≤ r(r + 2) ≤ 8. As rc(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 1.4.1. So there is an interesting problem. For any bridgeless graph G with diam(G) = 2, determine the smallest constant c such that rc(G) ≤ c. Li et al. in [58] derived that c ≤ 5 by showing the following result. Theorem 4.1.14 ([58]). If G is a bridgeless graph with diameter 2, then rc(G) ≤ 5. If G is a connected graph of diameter 2 and k bridges with k ≥ 1, then rc(G) ≤ k + 2. In the proof, Li, Li and Liu showed that if G is a bridgeless graph of order n with diameter 2, then it is either 2-connected or has only one cut vertex v; furthermore, v is the center of G with radius 1. They showed that 5 is almost best possible since there are infinitely many bridgeless bipartite graphs with diameter 2 whose rainbow connection numbers are 4; however, they did not find an example of such graph G with rainbow connection number 5. Dong and Li in [31] settled this problem by showing a family of graphs G of diameter 2 with rc(G) = 5, and moreover, they gave another proof for the upper bound 5. Their graphs are described as follows: Let P1 = u, v1 , w1 , P2 = u, v2 , w2 , · · · , Pk = u, vk , wk be k internally disjoint paths of length 2 with k ≥ 17, and when i = j, wi = w j , 1 ≤ i, j ≤ k. For any two different vertices wi , w j , we join wi to w j . Thus, we get a graph G. Let V = {v1 , v2 , · · · , vk } and W = {w1 , w2 , · · · , wk }. We know that V is an independent set and G[W ] is a complete subgraph of G. So the diameter of G is 2. In any edge-coloring c : E(G) → {1, 2, 3, 4} of G, each u − wi path of length 2 can be colored in at most 16 different ways. By the Pigeonhole Principle, there exist integers i and j with 1 ≤ i = j ≤ k such

62

4 Dense and Sparse Graphs

that c(uvi ) = c(uv j ), c(vi wi ) = c(v j w j ). Consider any rainbow path R between vi and v j . We know that R can contain only two edges of {uvi , uv j , vi wi , v j w j }, and R must pass through another path P ( = i, j) and one edge of {wi w , w j w }. That is, R = vi , wi , w , v , u, v j or R = v j , w j , w , v , u, vi . Hence, rc(G) ≥ 5. Now, we color the edges of G in the following way: Let c(uv1 ) = 1, c(v1 , w1 ) = 2, c(uvi ) = 3, c(vi , wi ) = 4, 2 ≤ i ≤ k, for any edge e ∈ E(G[W ]), c(e) = 5. It is easy to check that for any two vertices v1 , v2 of G, there is a rainbow path connecting them. Hence rc(G) ≤ 5 and so rc(G) = 5. The bound k + 2 is also sharp since there are infinitely many graphs with diameter 2 and k bridges whose rainbow connection numbers attain this bound [58]. For example, the rainbow connection number of the graph (kK1 ∪ rK2 ) ∨ K1 achieves this upper bound, where k ≥ 1, r ≥ 2. For bridgeless graphs with diameter 3, Li et al. [61] got the following upper bound: Theorem 4.1.15 ([61]). If G is a bridgeless graph with diameter 3, then rc(G) ≤ 9. They gave examples showing that rc(G) = 7 can be reached by bridgeless graphs G with diameter 3. However, they could not show that the upper bound 9 is reachable by such graphs.

4.2 Sparse Graphs In [78, 79], Li and Sun investigated graphs with large rainbow connection numbers and strong rainbow connection numbers, respectively. They derived the following two results. Note that each path Pj in the member of graph class Gi (1 ≤ i ≤ 4) of Fig. 4.1 may be trivial. Theorem 4.2.1 ([78]). For a connected graph G with m edges, we have rc(G) = m − 1; and rc(G) = m − 2 if and only if G is a 5-cycle or belongs to one of four graph classes Gi ’s (1 ≤ i ≤ 4) shown in Fig. 4.1. We now introduce two graph classes. Let C be the cycle of a unicyclic graph G, V (C) = {v1 , · · · , vk } and TG = {Ti : 1 ≤ i ≤ k} where Ti is the unique tree containing

P1 P3

Fig. 4.1 The figure for the four graph classes

P1

P2 P4 G1

P5 P6

P2

P3 G2

P1

P4 P2

P1 G3

P2 G4

4.2 Sparse Graphs

63

vertex vi in the subgraph G\E(C). We say that Ti and T j are ad jacent (nonad jacent) if vi and v j are adjacent (nonadjacent) in the cycle 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}. Theorem 4.2.2 ([79]). For a connected graph G with m edges, src(G) = m − 1; src(G) = m − 2 if and only if G is a 5-cycle or belongs to one of the sets Gi (i = 5, 6). Recall that rc(G) = m (or src(G) = m) if and only if G is a tree. Theorems 4.2.1 and 4.2.2 show the graphs with rc(G) ≥ m − 2 (src(G) ≥ m − 2). Furthermore, we raise the following problem. Problem 4.5. Determine the graphs with rc(G) ≥ m − k (src(G) ≥ m − k), where k is a small integer.

Chapter 5

Rainbow Connection Numbers of Some Graph Classes

5.1 Line Graphs 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, 69], Caro et al. and Li and Liu derived Theorem 3.2.1 and Theorem 3.2.6, respectively, according to the ear decomposition of a 2-connected graph. In this subsection, we will introduce some results on the rainbow connection numbers of line graphs, etc. In [74, 75], Li and Sun studied the rainbow connection numbers of line graphs in the light of particular properties of line graphs shown in [47, 48]. 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. We need the following new terminology. For a connected graph G, we call G a clique-tree-structure, if it satisfies the following condition: each block is a maximal clique. We call a graph H a clique-forest-structure, 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 size of a clique-tree(forest)-structure is the number of its maximal cliques. An example of clique-forest-structure is shown in Fig. 5.1. If each block of a clique-tree-structure is a triangle, we call it a triangle-tree-structure. Let  be the size of a triangletree-structure. Then, by definition, it is easy to see 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. The following observation is obvious. Observation 5.1.1 ([75]). If G is a connected graph and {Ei }i∈[t] is a partition of the edge set of G into connected subgraphs Gi = G[Ei ], then rc(G) ≤ ∑ti=1 rc(Gi ).

X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 5, © Xueliang Li, Yuefang Sun 2012

65

66

5 Rainbow Connection Numbers of Some Graph Classes

Fig. 5.1 A clique-foreststructure with size 6 and two components

Fig. 5.2 Graph G is obtained from G by applying Operation 5.1 at edge e

u

e

G

Operation 1 v

u

v

ue

ve G

Let G be a connected graph, and X a proper subset of V (G). To shrink X is to delete all the edges between vertices of X and then identify the vertices of X into a single vertex, namely w. We denote the resulting graph by G/X. Observation 5.1.2 ([74]). Let G and G be two connected graphs, where G is obtained from G by shrinking a proper subset X of V (G), that is, G = G/X, such that any two vertices of X have no common adjacent vertex in V \ X. Then rc(G ) ≤ rc(G). Now we introduce a graph operation and the corresponding result which will be used later. Operation 5.1. As shown in Fig. 5.2, for any edge e = uv ∈ G with min{degG (u), degG (v)} ≥ 2, we first subdivide e and then replace the new vertex with two new vertices ue , ve with degG (ue ) = degG (ve ) = 1 where G is the new graph. Since degG (ue ) = degG (ve ) = 1 in G , and by the definition of a line graph, it is easy to show that L(G) can be obtained from L(G ) by shrinking a vertex set of two nonadjacent vertices (these two vertices correspond to edges uue , vve ). So by Observation 5.1.2, we have Observation 5.1.3. If a connected graph G is obtained from a connected graph G by applying Operation 5.1 at some edge e ∈ G, then rc(L(G)) ≤ rc(L(G )). An inner vertex of a graph is a vertex with degree at least 2. For a graph G, we use V2 to denote the set of all inner vertices of G. Let n1 = |{v : degG (v) = 1}|, n2 = |V2 |. Denote by S(v) the set of edges incident with a vertex v of G, and by S(v) the subgraph of L(G) induced by S(v), which is a clique of L(G). Let K0 = {S(v) : v ∈ V (G)}, K = {S(v) : v ∈ V2 }. It is easy to show that K0 is a clique decomposition of L(G) (see [47, 48]) and each vertex of the line graph belongs to at most two elements of K0 . We know that each element S(v) of K0 \ K , a single vertex of L(G), is contained in the clique induced by u that is adjacent to v in G. So K is a clique decomposition of L(G).

5.1 Line Graphs

67

Fig. 5.3 An example of Theorem 5.1.4

w u2

u4

T2,1

T1,1

u3

v3

T1,3

T1,2 u5

v2

v1

u1

u6

u7 v4

T2,3 T2,2 v5 v6

v7

G

Theorem 5.1.4 ([75]). 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-foreststructure, then rc(L(G)) ≤ n2 − t. Moreover, the bound is sharp. 



Proof. Let T = ci=1 Ti = ci=1 {Ti, ji is a triangle of G : 1 ≤ ji ≤ ti }(∑ci=1 ti = t) be a set of t edge-disjoint triangles of G such that the subgraph of G, G[E(Ti )], induced by each E(Ti ), is a component of the subgraph G[E(T )], that is, a triangle-treestructure of size ti . In G, for each 1 ≤ i ≤ c let Gi = G[E(Ti )] with Vi = V (Gi ) and Ei = E(Ti ), and let Ei0 = E(Vi ) ∪ ∂ (Vi ) ⊇ Ei and G0i = G[Ei0 ]. We then obtain a new graph G from G by applying Operation 5.1 at each edge e ∈ E(Vi )\Ei for 1 ≤ i ≤ c (Note that here any edge e ∈ E(Vi )\Ei cannot be a bridge and so the graph obtained from G by applying Operation 5.1 at one such edge is still connected). We denote by Gi the new subgraph (of G ) corresponding to G0i . Applying Observation 5.1.3 repeatedly, we get that rc(L(G)) ≤ rc(L(G )). For example, see Fig. 5.3, here c = 2, t1 = t2 = 3, t = t1 + t2 = 6, and   T = 2i=1 Ti = 2i=1 {Ti, ji : 1 ≤ ji ≤ 3} is a set of six edge-disjoint triangles of G. Clearly, the subgraph G[E(Ti )] of G induced by each E(Ti ) is a triangletree-structure of size 3. So G[E(T )] is a triangle-forest-structure with size 6 and two components. Then G1 = G[E(T1 )] with V1 = V (G1 ) = {ui : 1 ≤ i ≤ 7} and E1 = E(T1 ) = {u1 u2 , u2 u3 , u1 u3 , u2 u4 , u4 u5 , u2 u5 , u3 u6 , u6 u7 , u3 u7 }, and G01 = G[E10 ] where E10 = E(V1 ) ∪ ∂ (V1 ) = E1 ∪ {u3 u5 } ∪ {wu1 , u1 v3 } with E(V1 ) = E1 ∪ {u3u5 } and ∂ (V1 ) = {wu1 , u1 v3 }. The edge u3 u5 ∈ E(V1 )\E1 cannot be a bridge. Similarly, v2 v7 ∈ E(V2 )\E2 cannot be a bridge. We then obtain G from G by applying Operation 5.1 at edges u3 u5 and v2 v7 , where the new subgraph Gi (of G ) corresponding to G0i contains exactly ti = 3 (edge-disjoint) triangles: {Ti, ji } with i = 1, 2 and 1 ≤ ji ≤ 3. Next we will show that rc(L(G )) ≤ n2 −t. By previous discussion, we know that K = {S(v) : v ∈ V2 } =

c 

{S(v) : v ∈ Vi }

i=1



 S(v) : v ∈ V2 \

c  i=1

 Vi

68

5 Rainbow Connection Numbers of Some Graph Classes

is a clique decomposition of L(G). So {E(S(v)) : v ∈ Vi }ci=1



 E(S(v)) : v ∈ V2 \

c 

 Vi ,

i=1

that is,

  c     0  c  E L Gi E(S(v)) : v ∈ V2 \ Vi i=1 i=1

is an edge partition of L(G). So {E(L(Gi ))}ci=1



 E(S(v)) : v ∈ V2 \

c 

 Vi

i=1

is an edge partition of L(G ). By Observation 5.1.1, we have c

rc(L(G )) ≤ ∑ rc(L(Gi )) + i=1

∑

 v∈V2 \ ci=1 Vi

rc(S(v)).

We know |Vi | = 2ti + 1 since the triangle-tree-structure Gi has size ti . So c

rc(L(G )) ≤ ∑ rc(L(Gi )) + (n2 − 2t − c). i=1

rc(L(G ))

In order to get ≤ n2 − t, it suffices to show that rc(L(Gi )) ≤ ti + 1. In  fact, since the graph Gi is obtained from Gi by applying Operation 5.1 at each edge e ∈ E(Vi )\Ei , Gi contains exactly ti triangles: {Ti, ji ∈ Ti : 1 ≤ ji ≤ ti }. We will show that there is a (ti + 1)-rainbow coloring of L(Gi ) by induction on ti . For ti = 1, Gi contains exactly one triangle and we give its line graph a 2-rainbow coloring as shown in Fig. 5.4. We assign color 1 to the edges of S(u) incident with vertex e1 except for the edges e1 e2 , e2 e3 , e3 e1 and the edges of S(v) incident with vertex e2 except for the edges e1 e2 , e2 e3 , e3 e1 as well as the edges of S(w) incident with vertex e3 except for the edges e1 e2 , e2 e3 , e3 e1 . We then assign color 2 to the edges of S(u) incident with vertex e3 except for the edges e1 e2 , e2 e3 , e3 e1 and the edges of S(v) incident with vertex e1 except for the edges e1 e2 , e2 e3 , e3 e1 as well as the edges of S(w) incident with vertex e2 except for the edges e1 e2 , e2 e3 , e3 e1 . Finally, we assign color 2 to the rest of the edges. It is easy to check that this is a rainbow coloring. So, the above conclusion holds for the case ti = 1. We assume that the conclusion holds for the case ti = h − 1(h ≥ 2), and now show that it holds for the case ti = h. By the definition of triangle-tree-structure, there must exist one triangle T = {u, v, w}, which has exactly one common vertex, namely u, with other triangles and v, w do not belong to any other triangle. We now obtain a new graph Gi from Gi by doing Operation 5.1 at edges e1 and e2 . This produces two subgraphs

5.1 Line Graphs

69

Fig. 5.4 The 2-rainbow coloring of the line graph of a graph with exactly one triangle

2

u e3

1

w

u e2 v Gi

e1

e2 w

e2

e1 v

e2

2

1

2

Fig. 5.5 Graph Gi is obtained from Gi by applying Operation 5.1 at edges e1 and e2

1

H1

u e1 e1 w

v

H2

Gi

Fig. 5.6 The tight example of Theorem 5.1.4 G

H1 and H2 (see Fig. 5.5). It is clear that L(Gi ) can be obtained from L(Gi ) by subdividing vertex e1 into two vertices {e1 , e1 } and e2 into two vertices {e2 , e2 }. Since H1 has h − 1 (edge-disjoint) triangles, by induction hypothesis, rc(L(H1 )) ≤ h. Since the subgraph of L(Gi ) induced by {S(v) : v ∈ Vi \{v, w}} is isomorphic to L(H1 ), it also has a rainbow h-coloring. The remaining edges of L(Gi ) belong to S(v) and S(w) and we color them as follows: Let e3 = vw. We then assign a new color to the edges of S(w) incident with vertex e1 except for the edges e1 e2 , e2 e3 , e3 e1 and the edges of S(v) incident with vertex e2 except for the edges e1 e2 , e2 e3 , e3 e1 . We then assign any color, say c1 , of the former h colors to the edges of S(w) incident with vertex e3 except for the edges e1 e2 , e2 e3 , e3 e1 and assign a color from the former h colors, say c2 , distinct from c1 , to the edges of S(v) incident with vertex e3 except for the edges e1 e2 , e2 e3 , e3 e1 . It is easy to check that, with the above coloring, L(Gi ) is rainbow connected and so L(Gi ) ≤ ti + 1 holds for ti = h. For the sharpness of the upper bound, see the following example. Let G consist of t triangles and t − 1 edges which do not belong to any triangles, as shown in Fig. 5.6. Since G has 3t inner vertices, by Theorem 5.1.4, we know rc(L(G)) ≤ 2t; on the other hand, it is easy to show that the diameter of the line graph L(G) is 2t and so we have rc(L(G)) = 2t. Then the bound of the above theorem is sharp. 

Li and Sun also derived the following two upper bounds according to the particular properties of line graphs.

70

5 Rainbow Connection Numbers of Some Graph Classes

Theorem 5.1.5 ([75]). If G is a connected graph, T is a set of t edge-disjoint triangles that cover all but n2 inner vertices of G and c is the number of components of the subgraph G[E(T )], then rc(L(G)) ≤ t + n2 + c. Moreover, the bound is sharp. Theorem 5.1.6 ([75]). Let G be a connected graph with m edges and m1 pendant paths of length 2. Then rc(L2 (G)) ≤ m − m1. The equality holds if and only if G is a path of length at least 3. The above three theorems give upper bounds for the rainbow connection number of Lk (G)(k = 1, 2) according to some parameters of G. One may consider the relationship between rc(G) and rc(L(G)). Problem 5.1. Determine the relationship between rc(G) and rc(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 Lk (G) when k is sufficiently large. Problem 5.2. Consider the value of rc(Lk (G)) as k → ∞. Is it bounded by a constant? or, does it convergence to a function of some graph parameters, such as the order n of G? For Problem 5.2, we know that if G is a cycle Cn (n ≥ 4), then Lk (G) = G, so rc(Lk (G)) = n2 . But for many graphs, we know, as k grows, Lk (G) will become more dense and rc(Lk (G)) may decrease. From an algorithmic point of view, a natural problem is the following Problem 5.3. Given the line graph L(G) of a graph G, determine the complexity of computing rc(L(G)).

5.2 Other Graph Classes In [13], Chandran et al. investigated the rainbow connection numbers of several special graph classes. They first showed a result concerning the connected two-way dominating sets. Theorem 5.2.1 ([13]). If D is a connected two-way dominating set in a graph G, then rc(G) ≤ rc(G[D]) + 3. From Theorem 5.2.1, the following result can be derived.

5.2 Other Graph Classes

71

Theorem 5.2.2 ([13]). Let G be a connected graph with δ (G) ≥ 2. Then: (i) If G is an interval graph, diam(G) ≤ rc(G) ≤ diam(G) + 1. In particular, if G is a unit interval graph, then rc(G) = diam(G). (ii) If G is AT -free, diam(G) ≤ rc(G) ≤ diam(G) + 3. (iii) If G is a threshold graph, diam(G) ≤ rc(G) ≤ 3. (iv) If G is a chain graph, diam(G) ≤ rc(G) ≤ 4. (v) If G is a circular arc graph, diam(G) ≤ rc(G) ≤ diam(G) + 4. (vi) If G is a bridgeless chordal graph, then rc(G) ≤ 3rad(G). Moreover, there exist threshold graphs and chain graphs with minimum degree at least 2 and rainbow connection numbers equal to the corresponding upper bound above. There exists an AT -free graph G with minimum degree at least 2 and rc(G) = diam(G) + 2, which is 1 less than the upper bound above. And there is a bridgeless chordal graph G with rc(G) = 3rad(G). Note that the upper bounds follow from Theorem 5.2.1 since (1) every interval graph G which is not isomorphic to a complete graph has a dominating path of length at most diam(G) − 2, (2) every AT -free graph G has a dominating path of length at most diam(G), (3) a maximum weight vertex in a connected threshold graph G is a dominating vertex, (4) every connected chain graph G has a dominating edge, and (5) every circular arc graph G, which is not an interval graph, has a dominating cycle of diameter at most diam(G). An interesting question is the following: Question 5.2.3. Is there any polynomial time algorithm to determine the rainbow connection number for any of the above graph classes? or, what is the complexity of computing the rainbow connection number for any of the above graph classes? 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. Li et al. [57] investigated the rainbow connection numbers of Cayley graphs on Abelian groups. Theorem 5.2.4 ([57]). Given an Abelian group Γ and an inverse closed set (a set X ∪ X −1 , where X −1 = {x−1 | x ∈ X}) S ⊆ Γ \ {1}, we have the following results: (i) The rainbow connection number rc(C(Γ, S)) ≤ min{∑a∈S∗ |a|/2 | S∗ ⊆ S is a minimal generating set o f Γ} (a generating set X such that no proper subset of X is a generating set of Γ).

72

5 Rainbow Connection Numbers of Some Graph Classes

(ii) If S is an inverse closed minimal generating set of Γ (a set X ∪ X −1 such that X is a minimal generating set of Γ), then

∑ |a|/2 ≤ rc(C(Γ, S)) ≤ src(C(Γ, S)) ≤ ∑∗ |a|/2,

a∈S∗

a∈S

S∗

where ⊆ S is a minimal generating set of Γ. Moreover, if every element a ∈ S has even order, then rc(C(Γ, S)) = src(C(Γ, S)) =

∑ |a|/2.

a∈S∗

They also investigated the rainbow connection numbers of recursive circulants (see [86] for an introduction to recursive circulants). By definition, a strongly regular graph with parameters (v, k, λ , μ ) is connected if and only if μ ≥ 1. In [1], Ahadi and Dehghan derived the following result: For every connected strongly regular graph G, rc(G) ≤ 600. As each strongly regular graph is a graph with diam(G) = 2, from Theorem 4.1.14 we know that rc(G) ≤ 5 if G is a strongly regular graph with parameters (v, k, λ , μ ), other than a star [58]. But 5 may not be the optimal upper bound, so one may consider to determine the maximum value of rc(G) among strongly regular graphs G with parameters (v, k, λ , μ ). There are other results on some special graph classes. In [17], Chartrand et al. investigated the rainbow connection numbers of cages, and in [52], Johns et al. investigated the rainbow connection numbers of small cubic graphs. The details are omitted. Planar graphs are a very large graph class, and it is interesting to consider the rainbow connection of a planar graph. Problem 5.4. Given a planar graph G, find good upper bounds for the rainbow connection number rc(G), in terms of its other parameters, such as number of edges, number of faces, etc. For a maximal outerplanar graph G, Deng et al. [27] gave a polynomial time algorithm to find an upper bound of rc(G). Huang et al. [49] obtained the following result. Theorem 5.2.5 ([49]). Let G be a bridgeless outerpalnar graph of order n. (1) If diam(G) = 2, then rc(G) ≤ 3 and the bound is tight. (2) If diam(G) = 3, then rc(G) ≤ 6.

Chapter 6

Rainbow Connection Numbers of Graph Products

Products of graphs occur naturally in discrete mathematics as tools in combinatorial constructions and give rise to important classes of graphs and deep structural problems. The extensive literature on products that has evolved over the years presents a wealth of profound and beautiful results, see [51]. In [78], Li and Sun obtained some results on the rainbow connection numbers of products of graphs, including Cartesian product, composition (lexicographic product) and join of graphs, etc. We first consider the Cartesian product of some graphs. By definition, the graph G1 G2 is the spanning subgraph of the graph G1  G2 . By using the definition and structure of Cartesian product, Li and Sun derived the following: Theorem 6.0.1 ([78]). Let G = G1 G2  · · · Gk (k ≥ 2), where each Gi (1 ≤ i ≤ k) is connected. Then rc(G) ≤ ∑ki=1 rc(Gi ). Moreover, if diam(Gi ) = rc(Gi ) for each Gi , then equality holds. Therefore, for the Cartesian product Pn1  · · · Pnt  Cnt+1  · · · Cnk of some paths and even cycles, equality also holds, where t or k − t could be 0. We know that there are also infinitely many nontrivial graphs H with diam(H) = rc(H), such as the unit interval graphs shown in Theorem 5.2.2 and many Cayley graphs [57]. The following problem could be interesting but may be difficult. Problem 6.1. Characterize those graphs H with rc(H) = diam(H) or determine sufficient conditions to guarantee that rc(H) = diam(H). Similar problems for src(G) can be considered. As one can see in Sect. 1.3 that for trees (but not paths), odd cycles, and many complete bipartite and multipartite graphs, the equality does not hold. For graphs H with diam(H) = 2, to give a polynomial-time checkable characterization of the graphs with rc(H) = diam(H) should be NP-complete, since, from Theorem 2.0.1, deciding if rc(H) = 2 is NPcomplete and deciding if diam(H) = 2 is polynomial-time checkable. Let G∗ = G1  G2  · · ·  Gk (k ≥ 2), where each Gi (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∗ . We have the following result. X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 6, © Xueliang Li, Yuefang Sun 2012

73

74

6 Rainbow Connection Numbers of Graph Products

Corollary 6.0.2 ([78]). Let G∗ = G1  G2  · · ·  Gk (k ≥ 2), where each Gi (1 ≤ i ≤ k) is connected. Then rc(G∗ ) ≤ ∑ki=1 rc(Gi ). For i = 1, 2, · · · , r, let mi ≥ 2 be given integers. Consider the graph G whose vertices are the r-tuples b1 b2 · · · br with bi ∈ {0, 1, · · · , mi − 1}, and let two vertices be adjacent if the corresponding tuples differ in precisely one place. 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 = Km1 Km2 · · · Kmr for some r ≥ 1, where mi ≥ 2 for all i. So we call G a Hamming graph with r factors. A Hamming graph is a hypercube (or r-cube) [45], denoted by Qr , if and only mi = 2 for all i. Hamming graphs are useful in communication networks [51]. Corollary 6.0.3 ([78]). If G is a Hamming graph with r factors, then rc(G) = r. In particular, rc(Qr ) = r. By the definition of composition (lexicographic product), 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 that 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 6.0.4 ([78]). Let G and H be graphs where G is connected. (1) If H is complete, then rc(G[H]) ≤ rc(G). In particular, if diam(G) = rc(G), then rc(G[H]) = rc(G). (2) If H is not complete, then rc(G[H]) ≤ rc(G) + 1. In particular, if diam(G) = rc(G), then rc(G[H]) = 2 for a complete graph G and rc(G) ≤ rc(G[H]) ≤ rc(G) + 1 for a noncomplete graph G. In [78], Li and Sun also investigated other graph products, such as the join of graphs, which we will not introduce here. 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 6.0.5. For a connected graph G, let Gk be the k-th power of G. Then r(Gk ) ≤ rc(Gk ) ≤ 2r(Gk ) + 1 for k ≥ 2. Moreover, the upper bound is tight up to an additive constant 1. (Note that r(Gk ) =  r(G) k ). Theorem 6.0.6. If G and H are connected nontrivial graphs, then r(GH) ≤ rc(GH) ≤ 2r(GH). Moreover, the bounds are tight. (Note that r(GH) = r(G) + r(H)). Theorem 6.0.7. Let G and H be nontrivial graphs. If G is a connected, then r(G[H]) ≤ rc(G[H]) ≤ 2r(G[H]) if r(G[H]) ≥ 2, and 1 ≤ rc(G[H]) ≤ 3 if r(G[H]) =1. Moreover, the bounds are tight.

6 Rainbow Connection Numbers of Graph Products

75

Theorem 6.0.8. If G and H are connected nontrivial graphs, then r(G  H) ≤ rc(G  H) ≤ 2r(G  H) + 2. The upper bound is tight up to an additive constant 2. Gologranca et al. in [44] investigated the (strong) rainbow connection number on direct, strong, and lexicographic product. To state them, we need to introduce the following new notions. For an edge-colored graph G (not to be properly edge-colored), we say that G is odd–even rainbow connected if there exists a rainbow-colored odd walk and a rainbow-colored even walk between every pair of (not necessarily different) vertices of G. Clearly, on such a walk a fixed edge can appear only once. The odd–even rainbow connection number oerc(G) of a graph G is the smallest number of colors needed for G to be odd–even rainbow connected and it equals infinity if no such coloring exists. A bipartite graph has either only even or only odd walks between two fixed vertices, thus there is no odd–even rainbow coloring of such a graph. On the other hand, let G be a graph in which every edge lies on some odd cycle. Then oerc(G) is finite since coloring every edge with its own color produces an odd–even rainbow coloring of G. An odd cycle is an example where this coloring is optimal. In this case, if we would have two consecutive edges of the same color, then there is no even rainbow walk between the diametrical endvertices of these two edges, and in the case of two nonincident edges of the same color there is no even rainbow walk between endvertices of any different colored edge. Let G be a graph. We split G into two spanning subgraphs OG and BG , where the set E(OG ) consists of all edges of G that lie on some odd cycle of G, and the set E(BG ) = G G E(G) \ E(OG ). Clearly, OG and BG are not always connected. Let OG 1 , O2 , · · · , Ok G , · · · , BG be components of OG and BG , respectively, each one containing and BG , B 1 2  G G more than one vertex. Denote o(G) = oerc(OG 1 ) + oerc(O2 ) + · · · + oerc(Ok ) and G ) + · · · + rc(BG ). Note that o(G) is finite since it is defined b(G) = rc(BG ) + rc(B 1 2  on nontrivial components OG i , i ∈ {1, 2, · · · , k}. Then we have Theorem 6.0.9 ([44]). Let G and H be two nonbipartite noncomplete connected graphs. Then rc(G × H) ≤ min{rc(H)(o(G) + b(G)), rc(G)(o(H) + b(H))}. As a consequence, they got the following Corollary 6.0.10 ([44]). Let G and H be noncomplete connected graphs, where G is nonbipartite and H is bipartite. Then rc(G × H) ≤ min{rc(H)(o(G) + b(G))}. They also got the following Theorem 6.0.11 ([44]). Let n, m ≥ 3. Then (a) rc(Kn × Km ) = 2 = src(Kn × Km ); (b) rc(K2 × Km ) = 3 = src(K2 × Km ); (c) if G is a nonbipartite connected graph, then rc(G × K2) ≤ o(G) + 2b(G). For the strong product, they obtained the following Theorem 6.0.12 ([44]). Let G and H be connected graphs. Then (a) rc(G  H) ≤ max{rc(G), rc(H)}; (b) src(G  H) ≤ max{src(G), src(H)}.

76

6 Rainbow Connection Numbers of Graph Products

This bound is much better than Corollary 6.0.2. As consequences, they got the following result. Corollary 6.0.13 ([44]). (a) If G and H are connected graphs with rc(G) ≤ rc(H) = diam(H), then rc(G  H) = diam(H); (b) For every connected graph G there exists an integer n0 such that rc(G  Pn) = n − 1 for every n > n0 . They also got some results for special graphs: For integers m, n, p, q with n, q > 1, we have 2 ≤ rc(Km,n  K p,q ) ≤ 3; for 2 ≤ m ≤ n ≤ 2m and 2 ≤ p ≤ q ≤ 2n , we have rc(Km,n  K p,q ) = 2; for n, q ≥ 3, we have rc(K1,n  K1,q ) = 3 and src(K1,n  K1,n ) = n. For the composition or lexicographic product, they obtained the following result, which is better than Theorem 6.0.4. Theorem 6.0.14 ([44]). Let G and H be connected graphs. Then (a) rc(G[H]) ≤ max{rc(G), 2}; (b) src(G[H]) ≤ max{src(G), 2}. A vertex-cover of a graph G is a vertex set S ⊆ V (G) such that S contains at least one end-vertex of every edge of G. Let β (G) denote the cardinality of a minimum vertex-cover of G. Then they obtained the following Theorem 6.0.15 ([44]). Let G be a connected graph, and H a graph of order at least 2 without isolated vertices. Then rc(G[H]) ≤ 2β (G) + 1, They also obtained the following Theorem 6.0.16 ([44]). Let T be a tree with diam(T ) > 2 and H a graph of order ) . Then diam(T ) ≤ rc(G[H]) ≤ diam(T ) + 1. at least  diam(T 2 As a consequence, they got the following Corollary 6.0.17 ([44]). Let G be a connected graph with diam(G) > 2 and H a graph of order at least diam(G). Then rc(G[H]) ≤ 2diam(G) + 1. Since all of the results in this chapter can be deduced by routing methods, we omit their proofs. For readers interested in them, references are given.

Chapter 7

Rainbow Connectivity

7.1 Rainbow k-Connectivity In this chapter, we survey the results on rainbow k-connectivity. An example, the graph H = K3 K2 , in [16] is given to illustrate this concept, see Fig. 7.1. Because the diameter of H is 2 and there is a 2-rainbow-coloring of H, we have rc1 (H) = rc(H) = 2. Because H = K3 K2 has connectivity 3, the numbers rc2 (H) and rc3 (H) are also defined. We first establish the value of rc2 (H). Consider the 3-edge-coloring of H shown in Fig. 7.1. We claim that for every two distinct vertices x and y of H, there exist two internally disjoint x− y rainbow paths. This is obvious if x and y belong to the same triangle. Suppose that x and y belong to distinct triangles. There are three different cases, which are represented by (1) x = u and y = u , (2) x = u and y = w , and (3) x = u and y = v . For (1), the paths u, u and u, w, w , u are internally disjoint u − u rainbow paths; for (2), the paths u, w, w and u, u , w are internally disjoint u − w rainbow paths; while for (3), the paths u, w, v, v and u, u , w , v are internally disjoint u − v rainbow paths. Thus, rc2 (H) ≤ 3. On the other hand, if a 2-edge-coloring of H is given, then at least two edges of the triangle u, v, w, u are assigned the same color, say uv and vw. However then, there do not exist two internally disjoint u − w rainbow paths. Thus, rc2 (H) ≥ 3 and so rc2 (H) = 3. Finally, we determine the value of rc3 (K3 K2 ). Again, let H = K3 K2 . In the 6-edge-coloring of H shown in Fig. 7.2, every two distinct vertices of H are connected by three internally disjoint rainbow paths. Therefore, rc3 (H) ≤ 6. One property possessed by K3 K2 is that for every two distinct vertices x and y belonging to different triangles, there exists a unique set of three internally disjoint x − y paths. Let an rc3 (H)-edge-coloring c of H be given such that every two vertices of H are connected by three internally disjoint rainbow paths and let x and y be two distinct vertices of H belonging to a common triangle of H. Because two of every three internally disjoint x − y paths in H have lengths 1 and 2, the three edges of each triangle must be assigned different colors by c. Assume that uv is colored 1, uw is colored 2, and vw is colored 3, see Fig. 7.3a.

X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 7, © Xueliang Li, Yuefang Sun 2012

77

78

7 Rainbow Connectivity u

Fig. 7.1 The rainbow 2-connectivity of K3 K2

w

2 1

u

1

v

u

1

v

w

3

b 1 2

w

6

1

u

w

v

3

u

w

2 v

u

3

3 3 2

1 w

v

1 2

3 3

u

v

1 2

w

v

c

u

3

2 5

w

u

v

3 1

4

u

1 2

w

2

a

3 1

3

Fig. 7.2 A 6-edge-coloring of K3 K2

v

1

w 1

1 3

2 v

Fig. 7.3 Steps in determining rc3 (K3 K2 )

By considering the three internally disjoint u − v paths in H, we see that uu is not colored by 1 (denoted by ∼1) and neither ww nor u w is colored 3 (see Fig. 7.3b). Similarly, by considering the pairs {u, v }, {u, u }, and {v, v } of vertices of H, we have the following conditions on the coloring c shown in Fig. 7.3c. Then by considering the pairs {u, w }, {v, w }, {w, u }, and {w, v } of vertices of H, we have the added conditions on c shown in Fig. 7.4. This shows that none of the edges of the triangle with vertices u , v , and w can be assigned any of the colors 1, 2, 3. Because no two edges belonging to a triangle can be colored the same, at least six colors are required to color the edges of H in order for every two distinct vertices of H to be connected by three internally disjoint rainbow paths. Thus, rc3 (H) ≥ 6 and so rc3 (H) = 6.

7.1 Rainbow k-Connectivity

79

Fig. 7.4 A final step in determining rc3 (K3 K2 )

u

v

1 w

2

3 3 2

1 2

1 u

2

3

1

w 2

1 3 3

3

2

1 v

By its definition, we know that it is difficult to derive the exact value or a nice upper bound of the rainbow k-connectivity for a general graph. Chartrand et al. [16] 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 Kn for various pairs k, n of integers, and derived the following result: Theorem 7.1.1 ([16]). For every integer k ≥ 2, there exists an integer f (k) such that if n ≥ f (k), then rck (Kn ) = 2. Proof. The case for 2 ≤ k ≤ 4 is easy, in fact, f (2) = 4, f (3) = 5, and f (4) = 8, and we omit the details. Hence, we may assume that k ≥ 5. First, we show that rck (K(k+1)2 ) = 2. Let G1 , G2 , · · · , Gk+1 be mutually vertexdisjoint graphs, where V (Gi ) = Vi , such that Gi = Kk+1 for 1 ≤ i ≤ k + 1. Let Vi = {vi,1 , vi,2 , · · · , vi,k+1 } for 1 ≤ i ≤ k + 1. Let G be the join of the graphs G1 , G2 , · · · , Gk+1 . Thus, G = K(k+1)2 and V (G) = ∪k+1 i=1 Vi . We assign the edge uv of G the color 1 if either uv ∈ E(Gi ) for some i (1 ≤ i ≤ k + 1) or if uv = vi, v j, for some i, j,  with 1 ≤ i, j,  ≤ k + 1 and i = j. All other edges of G are assigned the color 2. We now show that each pair x, y of distinct vertices of G are connected by k internally disjoint x − y rainbow paths. We consider two cases. Case 1. x, y ∈ Vi for some i with 1 ≤ i ≤ k + 1. We may assume that x = v1,1 and y = v1,2 . Then G contains the x − y path x, y as well as the x − y rainbow paths v1,1 , va,1 , v1,2 (2 ≤ a ≤ k + 1). Case 2. x ∈ Vi and y ∈ V j , where i with 1 ≤ i, j ≤ k + 1 and i = j. We may assume, that x ∈ V1 and y ∈ V2 . Hence, we may further assume that x = v1,1 and that either y = v2,1 or y = v2,2 . If y = v2,1 , then G contains the x − y path x, y together with the x − y rainbow paths v1,1 , v1,a , v2,1 (2 ≤ a ≤ k + 1); while if y = v2,2 , then G contains the x − y path x, y together with the x − y rainbow paths v1,1 , v1,a , v2,2 (3 ≤ a ≤ k + 1). Since each pair of distinct vertices of G are connected by k internally disjoint x − y rainbow paths, then rck (K(k+1)2 ) = 2. Suppose next that n ≥ (k + 1)2 . By the division algorithm, we may write n n n = (k + 1)q + r, where q ≥ k + 1 and 0 ≤ r ≤ k. Then, q = k+1

and let s =  k+1 .

80

7 Rainbow Connectivity

We construct the graph G as before, where r of the graphs G1 , G2 , · · · , Gk+1 are Ks and k + 1 − r of these graphs are Kq . For each graph Gi of order p, where p is either s or q and 1 ≤ i ≤ k + 1, let V (Gi ) = {vi, j : 1 ≤ j ≤ p}. We color the edge joining va,b and vc,d with the color 1 if a = c or if a = c and b = d. All other edges are colored 2. 

They obtained an upper bound (k + 1)2 for f (k), namely f (k) ≤ (k + 1)2 . Li and Sun [76] continued their investigation, and derived the following result: 3

Theorem 7.1.2 ([76]). For every integer k ≥ 2, there exists an integer f (k) = ck 2 + 3 C(k) where c is a constant and C(k) = o(k 2 ) such that if n ≥ f (k), then rck (Kn ) = 2. Let K[r] (r ≥ 2) denote the complete -partite graph each part of which con  tains r elements and 0 = max{ 2k + 1, k−1 r + 2} (≥3). Let V = s=1 Vs where Vs = {us,1 , us,2 , · · · , us,r } (1 ≤ s ≤ ) is the vertex set of each part, and U j = {u1, j , u2, j , · · · , ul, j } (1 ≤ j ≤ r). Then their proof is divided into four steps: Step 1. We will show that for every integer k ≥ 5, if ξ ≥ 0 , then rck (Kξ 2 [r] ) = 2, which gives a result on the rainbow k-connectivity of complete -partite graph K[r] where the number  of parts is the square of an integer ξ , i.e.,  = ξ 2 . Step 2. We will obtain a similar result for the general complete -partite graph K[r] using the result in Step 1: for every integer k ≥ 5, if  ≥ 0 2 , then rck (K[r] ) = 2. Here the number  of parts is not always the square of an integer. Step 3. Let G be a complete ( + 1)-partite graph with  parts of order r and a part of order p where 0 ≤ p ≤ r − 1, that is, G is obtained from K[r] by adding a new part with p vertices. We will obtain a similar result: for every integer k ≥ 5, if  ≥ 0 2 , then rck (G ) = 2. We can see that the result of Step 2 is a special case (when p = 0) of it. Step 4. We derive Theorem 7.1.2 from the result in Step 3. 3

From Theorem 7.1.2, we can obtain an upper bound ck 2 + C(k) for f (k), where 3 c is a constant and C(k) = o(k 2 ), that is, we improved the upper bound of f (k) from 3 O(k2 ) to O(k 2 ). Dellamonica et al. [26] got the best possible upper bound 2k, which is linear in k (see Theorem 7.1.3). However, the proof of Theorem 7.1.2 is more structural or constructive, and informative. In the argument of [26], Dellamonica et al. proposed a new concept, the rainbow (k, )-connectivity. Given an edge-colored simple graph G, let  ≤ k be integers. Suppose the edges of G are k-colored. For a, b ∈ V (G), denote by p(a, b) the maximum number of internally disjoint rainbow paths of length  having endpoints a and b. The rainbow (k, )-connectivity of G is the minimum p(a, b) among all distinct a, b ∈ V (G). Note that this new defined rainbow (k, )-connectivity computes the number of internally disjoint rainbow paths with the same length  (this is distinct from the rainbow k-connectivity which, as mentioned above, computes the number of colors); and by the definition, for different edge-colorings, the values of rainbow (k, )-connectivity could be different.

7.1 Rainbow k-Connectivity

81

From Theorem 7.1.1, we know that for any r, there exists an explicit 2-coloring of Kr in which√ the number of bichromatic 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 Kr . In [26], Dellamonica et al. 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 7.1.3 ([26]). For any k ≥ 2 and r ≥ r0 = r0 (k) there exists an explicit k-coloring of the edges of Kr having rainbow (k, 2)-connectivity 

 k−1 − o(1) r. k

More generally, they considered the problem of finding longer rainbow paths. Theorem 7.1.4 ([26]). For any 3 ≤  ≤ k, there exists r0 = r0 (k) such that for every r ≥ r0 , there is an explicit k-coloring of the edges of Kr having rainbow (k, 2)connectivity r . (1 − o(1)) −1 This result is also asymptotically best possible, since any collection of internally r disjoint paths of length  can contain at most −1 paths. Their proof employed a very recent breakthrough due to Bourgain [10, 87], 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 [93] for a good but somewhat outdated survey on extractors.) Chartrand et al. [16] also investigated the rainbow k-connectivity of r-regular complete bipartite graphs for some pairs k, r of integers with 2 ≤ k ≤ r, and they obtained the following result: Theorem 7.1.5 ([16]). For every integer k ≥ 2, there exists an integer r such that rck (Kr,r ) = 3. Proof. The case for k = 2, 3 is not hard. Thus, we may assume that k ≥ 4. We show that rck (K2k k ,2k k ) = 3. 2

2

We first assume that k is even. Then, 2k 2k = k2 . Let G = Kk2 ,k2 with partite sets U and W . Suppose that U = U1 ∪ U2 ∪ · · · ∪ Uk and W = W1 ∪ W2 ∪ · · · ∪ Wk , where Ui = {ui,1 , ui,2 , · · · , ui,k } and W j = {w j,1 , w j,2 , · · · , w j,k } for 1 ≤ i, j ≤ k. Let G1 be the spanning subgraph of G such that E(G1 ) = {ui,p w j,p : 1 ≤ i, j, p ≤ k, i and j are o f the same parity}. See Fig. 7.5 for an example with k = 6. Let G2 be the spanning subgraph of G such that G2 = H1 ∪ H2 ∪ · · · ∪ Hk , where Hi = Kk,k (1 ≤ i ≤ k) and H1 has partite sets U1 and Wk and Hi (2 ≤ i ≤ k) has partite sets Ui and Wi−1 (see Fig. 7.5 for k = 6). Finally, let G3 = G − (E(G1 ) ∪ E(G2 )).

82

7 Rainbow Connectivity U1

U2

H1 H2

W1

H3

U3 W3

H4

W2 U4 W4

U5

H5

U6

W5

H6

W6

Fig. 7.5 The spanning subgraphs G1 and G2 of G for k = 6

Assign each edge of Gi (1 ≤ i ≤ 3) the color i. Then we can show that every two distinct vertices x and y of G are connected by k internally disjoint rainbow paths (we omit the details). The case that k is odd is similar. 

However, they could not show a result similar to that for complete graphs, and therefore they left an open question. For every integer k ≥ 2, determine an integer (function) g(k), for which rck (Kr,r ) = 3 for every integer r ≥ g(k), that is, the rainbow k-connectivity of the complete bipartite graph Kr,r is essentially 3. In [77], Li and Sun settled this question by using a similar method to but more complicated than that used for Theorem 7.1.5. Theorem 7.1.6 ([77]). For every integer k ≥ 2, there exists an integer g(k) = 2k 2k such that rck (Kr,r ) = 3 for any r ≥ g(k). With a random method, Fujita et al. [42] improved the result to g(k) = 2k + o(k), as follows. Theorem 7.1.7 ([42]). Let 0 < ε < 12 and k ≥ 12 (θ −1)(1−2ε )+2, where θ = θ (ε ) 2 2k−4 is the largest solution of 2x2 e−ε (x−2) = 1. If r ≥ 1−2 ε + 1, then rck (Kr,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 7.1.8 ([42]). For any 3-coloring of the edges of Kr,r , there exist u, v ∈ V (Kr,r ) where the number of internally vertex-disjoint rainbow u − v paths is 2r2 at most 3(r−1) . They extended this to complete multipartite graphs with equipartitions. Let Kt×r denote the complete multipartite graph with t classes of size r. For k ≥ 2, when

7.1 Rainbow k-Connectivity

83

considering bipartite graph Kr,r , we cannot achieve rck (Kr,r ) = 2. However, we may hope for rck (Kt×r ) = 2. Using a similar random method, Fujita, Liu and Magnant got the following Theorem 7.1.9 ([42]). Let 0 < ε < 12 , t ≥ 3, and k ≥ 12 θ (t − 2)(1 − 2ε ) + 1, where 2 2k−2 θ = θ (ε ,t) is the largest solution of 12 t 2 x2 e−(t−2)ε x = 1. If r ≥ (t−2)(1−2 ε ) , then rck (Kt×r ) = 2. Again, going in the other direction, the following result shows that the best lower 2k bound for r would be approximately r ≥ t−1 . Theorem 7.1.10 ([42]). Let t ≥ 3. For any 2-coloring of the edges of Kt×r , there exist u, v ∈ V (Kt×r ) where the number of internally vertex-disjoint rainbow u − v paths is at most

(t−1)r2 . 2(r−1)

In [76], Li and Sun 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 rck (Kt×r ) = 2. In [77], the same authors showed that for any t ≥ 2 there is an integer h(k) such that if r ≥ h(k), then rck (Kt×r ) ≤ 3. More generally, we have the following question. Question 7.1.11 ([42]). For integers k,t ≥ 2 and n1 ≤ n2 ≤ · · · ≤ nt , is there an integer h(k,t) such that if n1 ≥ h(k,t), we have rck (Kn1 ,n2 ,··· ,nt ) = 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. [16]. It is surprising that this particular case is still open, since complete bipartite graphs are very basic graphs. He and Liang in [46] investigated the rainbow k-connectivity in the setting of random graphs. They determined a sharp threshold function for the property rck (G(n, p)) ≤ d for every fixed integer d ≥ 2. This substantially generalizes a result due to Caro, Lev, Roditty, Tuza and Yuster (see Theorem 4.1.5). Their main result is as follows. Theorem 7.1.12 ([46]). 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 rck (G(n, p)) ≤ d.

The key ingredient of their proof is the following result: with probability at least 1/d

n) ) are connected by at least 1 − n−Ω (1), every two different vertices of G(n, C(log n(d−1)/d 10d 2 c0 log n internally disjoint paths of length exactly d. He and Liang [46] also investigated the rainbow k-connectivity from an algorithmic point of view. The NP-hardness of determining rc(G) was shown by Chakraborty et al. as shown in Chap. 2. However, He and Liang showed that the problem (even the search version) becomes easy in random graphs.

Theorem 7.1.13 ([46]). For any constant ε ∈ [0, 1), p = n−ε (1±o(1)) and k ≤ O (log n), there is a randomized polynomial time algorithmthat, with probability 1 − o(1), makes G(n, p) rainbow-k-connected using at most one more than the optimal number of colors.

84

7 Rainbow Connectivity

Since almost all natural edge probability functions p encountered in various scenarios have such a form, their result is quite strong. Note that G(n, n−ε ) is almost surely disconnected when ε > 1 [37], which makes the problem become trivial. Therefore, they ignored these cases. Fujita et al. [42] proved the following result.  Theorem 7.1.14 ([42]). The probability p = log n/n is a sharp threshold function for the property rck (Gn,p ) ≤ 2 for all k ≥ 1. They also considered other random graph models. Let Gn,m,p be the random bipartite graph with class sizes n and m, and edge probability p. Let Gn,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 7.1.15 ([42]). The probability p = log n/n is a sharp threshold function for the property rck (Gn,n,p ) ≤ 3 for all k ≥ 1.  Theorem 7.1.16 ([42]). The probability p = n3 log n is a sharp threshold function for the property rck (Gn,M ) ≤ 2 for all k ≥ 1. Finally, for random graphs we can obviously raise the following Problem 7.1. For d ≥ 2, determine a sharp threshold function for the property rck (G) ≤ d, where G is another random graph model. In particular, an answer for random regular graphs would be interesting. Fujita et al.[42] also considered rc2 (G) when G has fixed vertex-connectivity. By using the Fan Lemma [9], they obtained the following result. Theorem 7.1.17 ([42]). If  ≥ 2 and G is an -connected graph on n ≥  + 1 vertices, then rc2 (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 K3 , 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. Theorem 7.1.18 ([42]). If G is a 2-connected series-parallel graph on n ≥ 3 vertices, then rc2 (G) ≤ n. Since any 3-connected planar graph contains a 2-connected series-parallel spanning subgraph, see [35], as a consequence one can get that if G is a 3-connected planar graph of order n, then rc2 (G) ≤ n. Note that the bound presented in Theorem 7.1.18 is sharp when G is a generalized Θ-graph, that is, G = Θq1 ,··· ,qt is the union of t ≥ 2 paths with lengths

7.2 k-Rainbow Index

85

q1 ≥ · · · ≥ qt ≥ 1, where qt−1 ≥ 2, and the paths are pairwise internally vertexdisjoint with the same two end-vertices, as we know that if G = Θq1 ,··· ,qt , then rc2 (G) = n when t = 2; n − 1 or n − 2 when t ≥ 3. These results naturally lead to the following question. Problem 7.2. What is the minimum constant c > 0 such that for all 2-connected graphs G on n vertices, we have rc2 (G) ≤ cn? By the above results, we have 1 ≤ c ≤ 32 and Theorem 7.1.18 suggests that c = 1 may possibly be the correct answer. Clearly, there are many additional things that one can do with this concept. As mentioned above, it is difficult to derive the precise value or a nice upper bound for rck (G) of a κ -connected graph G, where 2 ≤ k ≤ κ . More generally, one may consider the following problem. Problem 7.3 ([42]). 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 rck (G) ≤ cn. Note that a result of Mader [82] 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 rck (G) ≤ κ n.

7.2 k-Rainbow Index The concept of k-rainbow coloring as defined above is another generalization of rainbow coloring. In [18], Chartrand et al. did some basic research on this topic. There is a rather simple upper bound for rxk (G) in terms of the order of G, regardless of the value of k. Proposition 7.2.1 ([18]). Let G be a nontrivial connected graph of order n ≥ 3. For each integer k with 3 ≤ k ≤ n − 1, rxk (G) ≤ n − 1 while rxn (G) = n − 1. There is a class of graphs of order n ≥ 3 whose k-rainbow index attains the upper bound of Proposition 7.2.1, it is an immediate consequence of Observation 1.4.1. Proposition 7.2.2 ([18]). Let T be a tree of order n ≥ 3. For each integer k with 3 ≤ k ≤ n, rxk (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 sdiamk (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 sdiam2 (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, rxk (G) ≥ sdiamk (G) ≥ k − 1.

86

7 Rainbow Connectivity

a

Fig. 7.6 Rainbow colorings of C4 and the corona of C4

b u1

6

1 2

c u2

v1

v2

2

2 1

1

v4

v3

5 u4

3 2

1

4

u3

The following two graphs G are given in [18] to illustrate the concepts, for which the k-rainbow index of G for all integers k with 3 ≤ k ≤ |V (G)| are found. We begin with the 4-cycle C4 . Clearly, rx3 (C4 ) ≥ sdiam3 (C4 ) = 2. The edge-coloring of C4 in Fig. 7.6a shows that rx3 (C4 ) = 2. By Proposition 7.2.1, rx4 (C4 ) = 3. Next let G denote the corona of C4 shown in Fig. 7.6b. The graph G therefore has order 8. We first consider rx3 (G). Let c be a 3-rainbow coloring of G, where c(u1 v1 ) = a say. Assume that some edge of the 4-cycle of G is also colored a. Suppose first that either v1 v2 or v1 v4 is also colored a, say v1 v4 is colored a. Then any rainbow tree of G containing S = {u1 , u3 , u4 } has size at least 6. Suppose next that either v2 v3 or v3 v4 is also colored a, say c(v2 v3 ) = a. Then any rainbow tree of G containing S = {u1 , u2 , u3 } has size at least 6. Thus rx3 (G) ≥ 6. On the other hand, if no edge of the 4-cycle of G is colored the same as a bridge, then rx3 (G) ≥ 6 because rx3 (C4 ) = 2. Hence in any case, rx3 (G) ≥ 6. That rx3 (G) = 6 follows from the edge-coloring of G in Fig. 7.6c. If 4 ≤ k ≤ 8, then every tree containing a set S of k vertices of G where {u1 , u2 , u3 , u4 } ⊆ S has size at least 7 and so rxk (G) = 7 by Proposition 7.2.1. The two graphs that we just considered are unicyclic graphs (connected graphs containing a unique cycle) and we saw that for each of these graphs G, either rxk (G) = |V (G)| − 2 or rxk (G) = |V (G)| − 1. This is true for all unicyclic graphs. Theorem 7.2.3 ([18]). If G is a unicyclic graph of order n ≥ 3 and girth g ≥ 3, then  rxk (G) =

n − 2 if k = 3 and g ≥ 4, n − 1 if g = 3 or 4 ≤ k ≤ n.

The investigation of rxk (G) for a general k and a general graph G is rather difficult. So one may consider rxk (G) for a special graph (see [41] for small cubic graphs) or for a general graph and small k, such as k = 3. Problem 7.4. Derive a sharp upper bound for rx3 (G). Problem 7.5. For k ≥ 3, characterize the graphs with rxk (G) = n − 1. Problem 7.6. Consider the relationship between rxk (G) and rxk (L(G)).

7.3 (k, )-Rainbow Index

87

7.3 (k, )-Rainbow Index There is also a generalization of the k-rainbow index, say (k, )-rainbow index rxk, , of G which is mentioned in [18]. The concepts and problems concerning rainbow trees suggest a concept that generalizes the connectivity using trees with the aid of factorizations. Recall that the connectivity κ (G) of a graph G is the minimum cardinality of a set S of vertices of G such that G\ S is disconnected or trivial. A well-known theorem of Menger [83] provides an equivalent definition of the connectivity. For each two-element subset S = {u, v} of vertices of G, let κ (S) denote the maximum number of internally disjoint u − v paths in G. Then κ (G) = min{κ (S)}, where the minimum is taken over all 2-element subsets S of V (G). Let G be a nontrivial connected graph of order n and let k be an integer with 2 ≤ k ≤ n. For a set S of k vertices of G, let κ (S) denote the maximum number  of pairwise edge-disjoint trees T1 , T2 , · · · , T in G such that V (Ti ) ∩ V (T j ) = S for every pair i, j of distinct integers with 1 ≤ i, j ≤ . A collection {T1 , T2 , · · · , T } of trees in G with this property is called an internally disjoint set o f trees connecting S. The k-connectivity κk (G) of G is then defined by κk (G) = min{κ (S)}, where the minimum is taken over all k-element subsets S of V (G). Thus κ2 (G) = κ (G). There already have been many results on the generalized connectivity in the literature, see [60, 62, 63, 65, 66, 85] for example. For a connected graph G and an integer  with 1 ≤  ≤ κ (G), the parameter rc (G) described in the last section is the smallest number of colors needed in an edge-coloring of G such that for every two distinct vertices u and v of G, there exist at least  internally disjoint u − v rainbow paths. Let G be a connected graph and let k ≥ 2 and  be integers with 1 ≤  ≤ κk (G). The (k, )-rainbow index rxk, (G) of G is the smallest number of colors needed in an edge-coloring of G such that for every set S of k vertices of G, there exist  internally disjoint rainbow trees connecting S. Hence, rxk,1 (G) = rxk (G). It is not hard to check that rx3 (Kn ) = rx3,1 (Kn ) = 2 for 3 ≤ n ≤ 5, rx3,1 (K6 ) = 3, and rx3,2 (Kn ) = 3 for k = 4, 5, 6, and rx3,3 (K5 ) = 4, rx3,3 (K6 ) = 3, rx3,4 (K6 ) = 4. In [18], Chartrand et al. investigated the rainbow indices rx3, (G) where n ≥ 3 and 1 ≤  ≤ κ3 (G). The following result is about complete graphs: Theorem 7.3.1 ([18]). For every integer n ≥ 6, rx3, (Kn ) = 3 for  = 1, 2. Proof. We need the following claim. Clam 1. Let G be a connected graph of order n ≥ 6. For each integer k with 3 ≤ k ≤ n, rxk (G) ≥ 3. Proof of Claim 1. If G is a tree, then rxk (G) = n − 1 ≥ 5 by Proposition 7.2.2. Similarly, if G is a cycle, then rxk (G) ≥ n − 2 ≥ 4 by Theorem 7.2.3. Thus, we may, assume that G is neither a tree nor a cycle and so the maximum degree Δ(G) of G is at least 3. Assume, to the contrary, that there is a rainbow 2-coloring c of G using the colors 1 and 2. Therefore, every three vertices belong to a rainbow path of length

88

7 Rainbow Connectivity

2, implying that there is no monochromatic triangle. We also show that there is no monochromatic K1,3 . If c(uv1 ) = c(uv2 ) = c(uv3 ) = 1, say, where u, v1 , v2 , v3 are four distinct vertices in G, then consider the three vertices v1 , v2 and v3 . As the three vertices must belong to a rainbow path of length 2, we may assume, without loss of generality, that c(v1 v2 ) = 1 and c(v2 v3 ) = 2. However, then, the triangle u, v1 , v2 , u is monochromatic, which is impossible. Therefore, each vertex can be incident with at most two edges that are colored the same and consequently, 3 ≤ Δ(G) ≤ 4. Suppose that deg(u) = Δ(G) and let {v1 , v2 , v3 } be a subset of the neighborhood of u. Then we may assume, without loss of generality, that c(uv1 ) = c(uv2 ) = 1. We may further assume that c(v1 v2 ) = 2. As G is of order at least 6, let w be a vertex with d(u, w) = 2. Then w is adjacent to each of v1 and v2 since the three vertices u, vi and w must belong to a rainbow path of length 2 for i = 1, 2 and uw ∈ E(G). Furthermore, in order for these paths to be rainbow, c(wv1 ) = c(wv2 ) = 2. However, this produces a monochromatic triangle w, v1 , v2 , w, which is a contradiction. Then the claim holds. We consider six cases according to the congruence class to which n belongs modulo 6. We always assume that V (Kn ) = {v1 , v2 , · · · , vn } and that S = {u, v, w} is an arbitrary set of three vertices of Kn . We only consider the case that n ≡ 1 (mod 6). The other five cases can be dealt with similarly. Let n = 6b + 1 where b is a positive integer. For each integer i with 1 ≤ i ≤ 6b + 1, define the color c(vi v j ) of the edge vi v j as follows: if j ∈ {i ± 1, i ± 2, · · · , i ± b}, c(vi v j ) = 1; if j ∈ {i ± (b + 1), i ± (b + 2), · · · , i ± (2b)}, c(vi v j ) = 2; if j ∈ {i ± (2b + 1), i ± (2b + 2), · · · , i ± (3b)}, c(vi v j ) = 3, where addition and subtraction are performed modulo 6b + 1. We may assume that u = v1 , v = v p and w = vq , where 1 < p < q ≤ 6b + 1. Then it can be shown that there are two internally disjoint rainbow trees connecting the set S. Then by the above claim, the conclusion holds. 

From the results obtained, we are led to the following conjectures. Conjecture 7.3.2 ([18]). For every positive integer , there exists a positive integer N such that rx3, (Kn ) = 3 for every integer n ≥ N. Conjecture 7.3.3 ([18]). For every pair k,  of positive integers with k ≥ 3, there exists a positive integer N such that rxk, (Kn ) = k for every integer n ≥ N. To end this chapter, we propose the following general problem. Problem 7.7. Similar to the rainbow k-connectivity and (k, )-rainbow index, one can define the so-called rainbow k-edge-connectivity rcek (G) and (k, )-rainbow edge-index rxek, (G) of a graph G. Compute the values of rcek (G) and rxek, (G) for a given (special) graph G, or find good bounds of rcek (G) and rxek, (G) for a general graph G in terms of other parameters, such as minimum degree, connectivity, edgeconnectivity, etc.

Chapter 8

Rainbow Vertex-Connection Number

All the above parameters on rainbow connections involved edge-colorings of graphs. A natural idea is to introduce a similar parameter involving vertex-colorings of graphs. It is, as mentioned above, a vertex version of the rainbow connection number. Krivelevich and Yuster [55] is the first to propose this new concept and proved a theorem analogous to the result of Theorem 3.1.10. Theorem 8.0.1 ([55]). A connected graph G with n vertices has rvc(G) <

11n δ (G) .

Recall that a set S of vertices of a graph G is called a two-step dominating set if every vertex of V (G) \ S has either a neighbor in S or a common neighbor with a vertex in S. In [55], the authors used the concept of a special type of two-step dominating set, the k-strong two-step dominating set. A two-step dominating set is k-strong if every vertex that is not dominated by it has at least k neighbors that are dominated by it. A two-step dominating set S is called connected if the subgraph induced by S is connected. Similarly, one can define the concept of connected k-strong two-step dominating set. 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 δ2n +2 . 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´asz Local Lemma (see later). Motivated by the method of Theorem 8.0.1, Li and Shi derived a result, which greatly improved Theorem 8.0.1. Theorem 8.0.2 ([72]). A connected graph √ G of order n with minimum degree δ has rvc(G) ≤ 3n/(δ + 1)√+ 5 for δ ≥ n − 1 − 1, n ≥ 290, while rvc(G) ≤ 4n/ (δ + 1) + 5 for 16 ≤ δ ≤ n − 1 − 2, rvc(G) ≤ 4n/(δ + 1) + C(δ ) for 6 ≤ δ ≤ 16 3 log(δ 3 +2δ 2 +3)−3(log 3−1)

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

X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0 8, © Xueliang Li, Yuefang Sun 2012

89

90

8 Rainbow Vertex-Connection Number

Now we state some lemmas that are needed to prove Theorem 8.0.2. The first lemma is from [55]. Lemma 8.0.3. If G is a connected graph with minimum degree δ , then it has a connected spanning subgraph with minimum degree δ and with less than n(δ + 1/(δ + 1)) edges. Lemma 8.0.4. If G is a graph of order n with minimum degree δ ≥ 2, then G has a connected δ /3-strong two-step dominating set S whose size is at most 3n/(δ + 1) − 2. Proof. For any T ⊆ V (G), denote by N k (T ) the set of all vertices with distance exactly k from T . We construct a connected δ /3-strong two-step dominating set S as follows: / take Procedure 1. Initialize S = {u} for some u ∈ V (G). As long as N 3 (S ) = 0, a vertex v ∈ N 3 (S ) and add vertices v, x1 , x2 to S , where vx2 x1 x0 is a shortest path from v to S and x0 ∈ S . Procedure 2. Initialize S = S obtained from Procedure 1. As long as there exists a vertex v ∈ N 2 (S) such that |N(v) ∩ N 2 (S)| ≥ 2δ /3 + 1, add vertices v, y1 to S, where vy1 y0 is a shortest path from v to S and y0 ∈ S. Clearly, S remains connected after every iteration in Procedure 1. Therefore, when Procedure 1 ends, S is a connected two-step dominating set. Let k1 be the number of iterations executed in Procedure 1. Observe that when a new vertex from N 3 (S ) is added to S , |S ∪ N 1 (S )| increases by at least δ + 1 in each iteration. Thus,  1 (S )| 2 (S )| 3(n−|N 2 (S )|)  we have k1 +1 ≤ |S ∪N = n−|N − δ +1 δ +1 . Furthermore, |S | = 3k1 +1 ≤ δ +1 2 since three more vertices are added in each iteration. Notice that S also remains connected after every iteration in Procedure 2. When Procedure 2 ends, each v ∈ N 2 (S) has at most 2δ /3 neighbors in N 2 (S), i.e., has at least δ /3 neighbors in N 1 (S), so S is a connected δ /3-strong two-step dominating set. Let k2 be the number of iterations executed in Procedure 2. Observe that when a new vertex from N 2 (S) is added to S, |N 2 (S)| reduces by at least 2δ /3 + 2 in each iteration. Thus, we have k2 ≤

|N 2 (S )| 2δ /3+2

=

3|N 2 (S )| 2δ +6 .

Furthermore,

  3 n − |N 2 (S )| 6|N 2 (S )| 3n −2+ < − 2. |S| = |S | + 2k2 ≤ δ +1 2δ + 6 δ +1 



Before proceeding further, we first recall the Lov´asz Local Lemma. For examples and applications of this lemma, we refer to Chap. 5 of book [3]. The Lov´asz Local Lemma (Symmetric Case). Let A1 , A2 , . . . , An be the events in an arbitrary probability space. Suppose that each event Ai is mutually independent of a set of all the other events A j but at most d, and that P[Ai ] ≤ p for all 1 ≤ i ≤ n.  If ep(d + 1) < 1, then Pr[ ni=1 Ai ] > 0.

8 Rainbow Vertex-Connection Number

91

Actually, this is an improvement to the original Lov´asz local lemma, which was published in 1977 and attributed to Lov´asz by Spencer in [94]. Proof of Theorem 8.0.2 Suppose G is a connected graph of order n with minimum degree δ . By Lemma 8.0.3, we may assume that G has less than n(δ + 1/(δ + 1)) edges. Let S be a connected δ /3-strong two-step dominating set of G with at most 3n/(δ + 1) − 2 vertices. √ Suppose δ ≥ n − 1 − 1. Observe that each vertex v of N 1 (S) has less than (δ + 1)2 neighbors in N 2 (S), since (δ + 1)2 ≥ n − 1 and v has another neighbor in S. We assign colors to the graph G as follows: distinct colors to each vertex of S and seven new colors to vertices of N 1 (S) such that each vertex of N 1 (S) chooses its color randomly and independently from all other vertices of N 1 (S). Hence, the total color we used is at most |S| + 7 ≤

3n 3n −2+7= + 5. δ +1 δ +1

For each vertex u of N 2 (S), let Au be the event that all the neighbors of u in N 1 (S), denoted by N1 (u), are assigned at least two distinct colors. Now we will prove Pr[Au ] > 0 for each u ∈ N 2 (S). Notice that each vertex u ∈ N 2 (S) has at least δ /3 neighbors in N 1 (S) since S is a connected δ /3-strong two-step dominating set of G. Therefore, we fix a set X(u) ⊂ N 1 (S) of neighbors of u with |X(u)| = δ /3. Let Bu be the event that all of the vertices in X(u) receive the same color. Thus, Pr[Bu ] ≤ 7−δ /3+1 . As each vertex of N 1 (S) has less than (δ + 1)2 neighbors in N 2 (S), we have that the event Bu is independent of all √ other events Bv for v = u but at most ((δ + 1)2 − 1)δ /3 of them. Since for δ ≥ n − 1 − 1 and n ≥ 290,   e · 7 −δ /3+1 ((δ + 1)2 − 1)δ /3 + 1 < 1, by the Lov´asz Local Lemma, we have Pr[Au ] > 0 for each u ∈ N 2 (S). Therefore, for N 1 (S), there exists one coloring with seven colors such that every vertex of N 2 (S) has at least two neighbors in N 1 (S) colored differently. It remains to show that the graph G is rainbow vertex-connected. Let u, v be a pair of vertices such that u, v ∈ N 2 (S). If u and v have a common neighbor in N 1 (S), then we are done. Denote by x1 , y1 and x2 , y2 , respectively, the two neighbors of u and v in N 1 (S) such that the colors of xi and yi are different for i = 1, 2. Without loss of generality, suppose that the colors of x1 and x2 are also different. Indeed, there exists a required path between u and v: ux1 w1 Pw2 x2 v, where wi is the neighbor of xi in S and P is the path connected w1 and w2 in S. All other √cases of u, v can be checked easily. From now on, we assume δ ≤ n − 1 − 2. We partition N 1 (S) into two subsets D1 = {v ∈ N 1 (S) : v has at least (δ + 1)2 neighbors in N 2 (S)} and D2 = N 1 (S)\ D1 . Since G has less than n(δ + 1/(δ + 1)) edges, we have |D1 | ≤ n/(δ + 1). Let L1 = {v ∈ N 2 (S) : v has at least one√ neighbor in D1 } and L2 = N 2 (S) \ L1. Let C(δ ) = 5 for 16 ≤ δ ≤ n − 1 − 2 and C(δ ) = e

3 log(δ 3 +2δ 2 +3)−3(log 3−1) δ −3

−2

92

8 Rainbow Vertex-Connection Number

for 6 ≤ δ ≤ 15. We assign colors to graph G as follows: distinct colors to each vertex of S ∪ D1 and C(δ ) + 2 new colors to vertices of D2 such that each vertex of D2 chooses its color randomly and independently from all other vertices of D2 . Hence, the total number of colors we used is at most |S| + |D1| + C(δ ) + 2 ≤

n 3n 4n −2+ + C(δ ) + 2 = + C(δ ). δ +1 δ +1 δ +1

For each vertex u of L2 , let Au be the event that all of the neighbors of u in D2 are assigned at least two distinct colors. Now we will prove Pr[Au ] > 0 for each u ∈ L2 . Notice that each vertex u ∈ L2 has at least δ /3 neighbors in D1 . Therefore, we fix a set X(u) ⊂ D1 of neighbors of u with |X(u)| = δ /3. Let Bu be the event that all of the vertices in X(u) receive the same color. Thus, Pr[Bu ] ≤ (C(δ ) + 2)−δ /3+1 . As each vertex of D2 has less than (δ + 1)2 neighbors in N 2 (S), we have that the event Bu is independent of all other events Bv for v = u but at most ((δ + 1)2 − 1)δ /3 of them. Since   e · (C(δ ) + 2)−δ /3+1 ((δ + 1)2 − 1)δ /3 + 1 < 1, by the Lov´asz Local Lemma, we have Pr[Au ] > 0 for each u ∈ L2 . Therefore, for D2 , there exists one coloring with C(δ ) + 2 colors such that each vertex of L2 has at least two neighbors in D2 colored differently. Similarly, we can check that the graph G is also rainbow vertex-connected in this case. The proof is thus complete.  Motivated by the method of Theorem 8.0.1, Dong and Li [28] also obtained a result analogous to Theorem 3.1.13 for the rainbow vertex-connection version according to the degree-sum condition σ2 , which is stated as the following theorem. Theorem 8.0.5 ([28]). Let G a connected graph of order n. Then rvc(G) ≤ σ28n+2 +8 for 2 ≤ σ2 ≤ 6 and σ2 ≥ 28, rvc(G) ≤ σ10n +8 for 7 ≤ σ2 ≤ 8 and 16 ≤ σ2 ≤ 27, and 2 +2 10n rvc(G) ≤ σ2 +2 + A(σ2 ) for 9 ≤ σ2 ≤ 15, where A(σ2 ) = 63, 41, 27, 20, 16, 13, 11, respectively. Dong and Li in [29] also showed a theorem for the rainbow vertex-connection number according to the degree-sum condition σk , which is stated as follows. Theorem 8.0.6. Let G is a connected graph of order n with k independent 2 )n vertices. Then, rvc(G) ≤ (4k+2k σk +k + 5k if σk ≤ 7k and σk ≥ 8k; whereas rvc(G) ≤ 2 ( 38k 9 +2k )n σk +k

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

In [70], Li and Liu employed a concept of revised rainbow vertex-connection number and determined the rainbow vertex-connection number of a cycle Cn first, and then gave a sharp upper bound for the rainbow vertex-connection number of 2-connected graphs.

8 Rainbow Vertex-Connection Number

93

Theorem 8.0.7 ([70]). Let G be a 2-connected graph of order n(n ≥ 3). Then rvc(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 . Chen et al. [22] also investigated the Nordhaus–Gaddum-type result for the rainbow vertex-connection number. Theorem 8.0.8. When G and G are both connected, then 2 ≤ rvc(G) + rvc(G) ≤ n − 1. Both the upper and the lower bounds are best possible for all n ≥ 5. The complexity of determining rainbow vertex-connection of a given graph was settled by Chen et al. [23]. Motivated by the proofs of Theorems 2.0.1 and 2.0.8, they derived two corresponding results to the rainbow vertex-connection. At first, they defined the following three problems: Subset rainbow vertex-connection 2: Given a graph G = (V, E) and a set of pairs P ⊆ V (G) × V (G), decide whether there is a vertex-coloring of G with two colors such that all pairs (u, v) ∈ P are rainbow vertex-connected? Rainbow vertex-connection 2: Given a graph G = (V, E), decide whether there is a vertex-coloring of G with two colors such that all pairs (u, v) ∈ V (G) × V (G) are rainbow vertex-connected? Different subsets rainbow vertex-connection 2: Given a graph G = (V, E) and two disjoint subsets V1 , V2 of V with a one to one corresponding f : V1 → V2 , decide whether there is a vertex-coloring of G with two colors such that G is rainbow vertex-connected and for each v ∈ V1 , v and f (v) are assigned different colors. For two problems A and B, we write A ∝ B, if problem A is polynomially reducible to problem B. Then the authors of [23] proved the following theorem by showing that problem Subset rainbow vertex-connection 2 ∝ problem Rainbow vertex-connection 2, then problem Different subsets rainbow vertex-connection 2 ∝ problem Subset rainbow vertex-connection 2, and finally 3-SAT problem ∝ problem Different subsets rainbow vertex-connection 2. Theorem 8.0.9 ([23]). Given a graph G, deciding if rvc(G) = 2 is NP-complete. In particular, computing rvc(G) is NP-hard. We will give a detailed proof of the following result, which uses a similar idea of [12], but differently by reducing the problem of 3-SAT to some other new problems. Theorem 8.0.10 ([23]). The following problem is NP-complete: given a vertexcolored graph G, check whether the given coloring makes G rainbow vertexconnected. Now we define Problem 8.1 and Problem 8.2 in the following. We will prove Theorem 8.0.10 by reducing Problem 8.1 to Problem 8.2, and then the problem of 3-SAT to Problem 8.1.

94

8 Rainbow Vertex-Connection Number

Problem 8.1 (s − t rainbow vertex-connection). Given a vertex-colored graph G and two specified vertices s and t of G, decide if there is a rainbow vertex-connected path connecting s and t? Problem 8.2 (Rainbow vertex-connection). Given a vertex-colored graph G, decide if G is rainbow vertex-connected under the vertex-coloring? Lemma 8.0.11. Problem 8.1 ∝ Problem 8.2. Proof. Given a vertex-colored graph G with two specified vertices s and t. We want to construct a new graph G with a vertex-coloring such that G is rainbow vertexconnected if and only if there is a rainbow vertex-connected path connecting s and t in G. Let V = {v1 , v2 , . . . , vn−1 , vn } be the vertices of G, where v1 = s and vn = t. We construct a new graph G = (V  , E  ) as follows. Set V  = V ∪ {s ,t  , a, b},

E  = E ∪ {s s,t t} ∪ {avi, bvi : i ∈ [n]}.

Let c be the vertex-coloring of G. We define the vertex-coloring c of G as follows: c (vi ) = c(vi ) for i ∈ {2, 3, . . . , n − 1}; c (s) = c (a) = c1 , c (t) = c (b) = c2 , where c1 , c2 are two new colors; and the vertices s and t  are assigned any colors already used. Then, it is not difficult to check that c makes G rainbow vertex-connected if and only if there is a rainbow vertex-connected path connecting s and t in G under the vertex-coloring c.  Lemma 8.0.12. 3-SAT ∝ Problem 8.1. Proof. Let φ be an instance of the 3-SAT with clauses c1 , c2 , . . . , cm and variables x1 , x2 , . . . , xn . We construct a graph Gφ with two specified vertices s and t. Let k ≥ m and  ≥ m be two integers. First, we introduce k new vertices vi,1 j , vi,2 j , . . . , vi,k j for each x j ∈ ci and  new i, j i, j i, j vertices v1 , v2 , . . . , v for each x j ∈ ci . i, j Next, for each va with a ∈ [k], where and in what follows [k] denotes the set i, j i, j i, j {1, 2, · · · , k}, we introduce  new vertices va1 , va2 , . . . , va , which form a path in i, j i, j this order (we call va1 and va the initial vertex and the terminal vertex of the path, respectively). Similarly, for each vi,b j with b ∈ [], we introduce k new vertices vi,1bj , vi,2bj , . . . , vi,kbj , which form a path in that order (we call vi,1bj and vi,kbj the initial vertex and the terminal vertex of the path, respectively). Therefore, for x j ∈ ci there are k paths of length  − 1, and for x j ∈ ci there are  paths of length k − 1. We use Si to denote the set of all the paths corresponding to the three variables in ci for 1 ≤ i ≤ m, and define S0 = {s}. For each path P in Si (i ∈ [m]), we join the initial vertex of P to the terminal vertices of all the paths in Si−1 . And for each path in Sm , we join its terminal vertex to t. Thus, we obtain a new graph Gφ . Now we define a vertex-coloring of Gφ . For every variable x j , we introduce j j j k ×  distinct colors α1,1 , α1,2 , . . . , αk, . For all i ∈ [m], we color the vertices

8 Rainbow Vertex-Connection Number

95

j j j vi,a1j , vi,a2j , . . . , vi,aj with colors αa,1 , αa,2 , . . . , αa, , respectively, and color vi,1bj , vi,2bj , . . . ,

vkb with colors α1,b , α2,b , . . . , αk,b , respectively, where a ∈ [k] and b ∈ []. Then, it is not difficult to verify that Gφ contains a rainbow vertex-connected path Q connecting s and t if and only if φ is a YES instance of the 3-SAT in this assignment.  i, j

j

j

j

Like the NP-hardness results in [4], Chen et al. in [21] got similar result for the rainbow vertex-connection number. Theorem 8.0.13 ([21]). For every integer k ≥ 2, deciding whether a graph has rvc(G) ≤ k is NP-hard. And for any fixed k ≥ 2, the problem becomes NP-complete. Using the NP-completeness of deciding if a given edge-colored graph is rainbow connected, and by some reduction, Huang et al. obtained the following result for line graphs. Theorem 8.0.14 ([49]). Deciding if a given vertex-colored line graph is rainbow vertex-connected is NP-complete. A natural question is the following Question 8.0.15. Given an edge-colored line graph, is it NP-complete to decide if it is rainbow connected? Denote by Gk (n) the set of graphs of order n with rainbow vertex-connection number at most k, and define t  (n, k) = min{e(G) | G ∈ Gk (n)}. Li et al. [59] got the following result, which is much better than Theorems 4.1.6 and 4.1.7 for edge case. Theorem 8.0.16 ([59]). Let k be a positive integer. Then t  (n, k) = n − 1, and the equality holds if and only if G is such a graph that deleting all leaves of G results in ba tree of order k. We end this chapter with the following open problems. Problem 8.3. Given a 2-connected graph G with diameter 3, is there a constant C such that rvc(G) ≤ C? Problem 8.4. Given a κ (or λ -edge)-connected graph G, find good upper bounds for the rainbow vertex-connection number rvc(G) in terms of κ (or λ ). If G is a graph with many cut vertices, then from the examples in paragraph two of Sect. 1.4 one can see that the difference |rc(G) − rvc(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 |rc(G) − rvc(G)| is very small. So we have the following problem.

96

8 Rainbow Vertex-Connection Number

Problem 8.5. For a 2-connected graph G, find good bounds to the difference |rc(G) − rvc(G)|. Is this difference a very small constant? Another problem is the following Problem 8.6. Is it true that for any 2-connected graph G, rvc(G) ≤ rc(G)?

References

1. A. Ahadi, A. Dehghan, On rainbow connection of strongly regular graphs, arXiv:1001.3413v1 [math.CO] 2010. 2. N. Alon, R. Duke, H. Lefmann, V. R¨odl, R. Yuster, The algorithmic aspects of the Regularity Lemma, J. Algorithms 16 (1994), 80–109. 3. N. Alon, J. Spencer, The Probabilistic Method, Third Edition, Wiley, New York, 2008. 4. P. Ananth, M. Nasre, New hardness results in rainbow connectivity, arXiv:1104.2074v1 [cs.CC] 2011. 5. M. Basavaraju, L.S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number and radius, arXiv:1011.0620 [math.CO] 2010. 6. M. Basavaraju, L.S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number of graph power and graph products, arXiv:1104.4190v1 [math.CO] 2011. ˜ 3/14 )-coloring algorithm for 3-colorable graphs, Infor. Process. 7. A. Blum, D. Karger, An O(n Lett. 61(1) (1997), 49–53. 8. B. Bollob´as, A. Thomason, Threshold functions, Combinatorica 7 (1986), 35–38. 9. J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, Berlin, 2008. 10. J. Bourgain, More on the sum-product phenomenon in prime fields and its applications, Intern. J. Number Theory 1 (2005) 1–32. 11. Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), R57. 12. S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connectivity, 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009), 243-254. Also, see J. Combin. Optim. 21 (2011), 330–347. 13. L.S. Chandran, A. Das, D. Rajendraprasad, N.M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory, in press, doi:10.1002/jgt20643. 14. L.S. Chandran, R. Mathew, D. Rajendraprasad, On rainbow connection number and connectivity, arXiv:1105.5704v1 [math.CO] 2011. 15. G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008), 85–98. 16. G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54(2) (2009), 75–81. 17. G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, On the rainbow connectivity of cages, Congr. Numer. 184 (2007), 209-222. 18. G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010), 360–367. 19. G. Chartrand, P. Zhang, Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL, 2009.

X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0, © Xueliang Li, Yuefang Sun 2012

97

98

References

20. L. Chen, X. Li, H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, arXiv:1012.2641v2 [math.CO] 2010. 21. L. Chen, X. Li, H. Lian, Further hardness results on the rainbow vertex-connection number of graphs, arXiv:1110.1915v1 [math.CO] 2011. 22. L. Chen, X. Li, M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph, Util. Math. 86 (2011), 335–340. 23. L. Chen, X. Li, Y. Shi, The complexity of determining the rainbow vertex-connection of graphs, Theoretical Computer Science 412 (2011), 4531–4535. 24. X. Chen, X. Li, A solution to a conjecture on the rainbow connection number, Ars Combin. 104 (2012). 25. D. Corneil, S. Olariu, L. Stewart, Asteroidal triple-free graphs, SIAM J. Discrete Math. 10(3) (1997), 399–430. 26. D. Dellamonica Jr., C. Magnant, D. Martin, Rainbow paths, Discrete Math. 310 (2010), 774–781. 27. X. Deng, K. Xiang, B. Wu, Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs, Appl. Math. Lett. 25 (2012), 237–244. 28. J. Dong, X. Li, Upper bounds involving parameter σ2 for the rainbow connection, arXiv:1101.3119v1 [math.CO] 2011, also see Acta Math. Appl. Sin., to appear. 29. J. Dong, X. Li, Two rainbow connection numbers and the parameter σk , arXiv:1102.5149v2 [math.CO] 2011. 30. J. Dong, X. Li, Rainbow connection number, bridges and radius, arXiv:1105.0790v1 [math.CO] 2011. 31. J. Dong, X. Li, Sharp upper bound for the rainbow connection number of a graph with diameter 2, arXiv:1106.1258v3 [math.CO] 2011. 32. J. Dong, X. Li, On a question on graphs with rainbow connection number 2, arXiv:1109.5004v2 [math.CO] 2011. 33. J. Dong, X. Li, Note on rainbow connection number of dense graphs, arXiv:1110.1268v1 [math.CO] 2011. 34. J. Ekstein, P. Holub, T. Kaiser, M. Kochy, S.M. Camachoy, Z. Ryja´cek, ˇ I. Schiermeyer, The rainbow connection number of 2-connected graphs, arXiv:1110.5736v1 [math.CO] 2011. 35. E.S. Elmallah, C.J. Colbourn, Series-parallel subgraphs of planar graphs, Networks 22(6) (1992), 607–614. 36. P. Erd˝os, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory, Ser.B, 47(1) (1989), 73–79. 37. P. Erd˝os, A. R´enyi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17–61. 38. A. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007), 24–28. 39. E. Fischer, A. Matsliah, A. Shapira, Approximate hypergraph partitioning and applications, In: Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS) (2007), 579–589. 40. E. Friedgut, G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), 2993–3002. 41. F. Fujie-Okamoto, J. Lin, P. Zhang, Rainbow trees in small cubic graphs, J. Combin. Math. Combin. Comput. 78 (2011), 33-47. 42. S. Fujita, H. Liu, C. Magnant, Rainbow k-connection in dense graphs, preprint, available at www.cantab.net/users/henry.liu/maths.htm. Extended abstract in Proceedings of EuroComb’11, Electron. Notes Discrete Math., to appear. 43. M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. 44. T. Gologranca, G. Mekiˇs, I. Peterin, Rainbow connection and graph products, submitted. 45. F. Harary, J. Hayes, H. Wu, A survey of the theory of hypercube graphs, Comput. & Math. Appl. 15 (1988), 277–289. 46. J. He, H. Liang, On rainbow-k-connectivity of random graphs, arXiv:1012.1942v1 [math.CO] 2010.

References

99

47. S.T. Hedetniemi, P.J. Slater, Line graphs of triangleless graphs and iterated clique graphs, in Graph Theory and Applications, Lecture Notes in Math. 303 (ed. Y. Alavi et al.), SpringerVerlag, Berlin, Heidelberg, New York, 1972, pp. 139–147; MR49#151. 48. R. Hemminger, L. Beineke, Line graphs and line digraphs, in Selected Topics in Graph Theory (ed. L. Beineke et al.), Academic Press, London, New York, San Francisco, 1978, pp. 271–305. 49. X. Huang, X. Li, Y. Shi, Rainbow connections for planar graphs and line graphs, arXiv:1110.3147v2 [cs.CC] 2011. 50. X. Huang, H. Li, X. Li, Y. Sun, Oriented diameter and rainbow connection number of a graph, arXiv:1111.3480v1 [math.CO] 2011. 51. W. Imrich, S. Klavzar, Product Graphs–Structure and Recognition, Wiley, New York, 2000. 52. G.L. Johns, F. Okamoto, P. Zhang, The rainbow connectivities of small cubic graphs, Ars Combin., to appear. 53. A. Kemnitz, I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory, 31(2) (2011), 313–320. 54. J. Koml´os, M. Simonovits, Szemer´edi’s Regularity Lemma and its applications in graph theory, In: D. Mikl´os, VT. S´os, T. Sz¨onyi, (eds) Combinatorics, Paul Erd˝o is Eighty. Bolyai society mathematical studies, Budapest, 2 (1996), 295–352. 55. M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63(3) (2009), 185–191. 56. V. Le, Z. Tuza, Finding optimal rainbow connection is hard, Preprint 2009. 57. H. Li, X. Li, S. Liu, The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. & Math. Appl. 62(11) (2011), 4082–4088. 58. H. Li, X. Li, S. Liu, Rainbow connection in graphs with diameter 2, arXiv:1101.2765v1 [math.CO] 2011. Discrete Math., to appear. 59. H. Li, X. Li, Y. Sun, Asymptotic value of the minimal size of a graph with rainbow connection number 2, arXiv:1105.4314v1 [math.CO] 2011. 60. H. Li, X. Li, Y. Sun, The generalized 3-connectivity of Cartesian product graphs, arXiv:1103.6095v4 [math.CO] 2011. 61. H. Li, X. Li, Y. Sun, Upper bound for the rainbow connection number of bridgeless graphs with diameter 3, arXiv:1109.2769v1 [math.CO] 2011. 62. S. Li, W. Li, X. Li, The generalized connectivity of complete bipartite graphs, Ars Combin. 104 (2012). 63. S. Li, X. Li, Note on the hardness of generalized connectivity, J. Combin. Optimization, in press. 64. S. Li, X. Li, Note on the complexity of deciding the rainbow connectedness for bipartite graphs, arXiv:1109.5534v2 [cs.CC] 2011. 65. S. Li, X. Li, Y. Shi, The minimal size of a graph with generalized connectivity κ3 = 2, Australasian J. Combin. 51 (2011), 209–220. 66. S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity κ3 (G), Discrete Math. 310 (2010), 2147–2163. 67. W. Li, X. Li, Note on two results on the rainbow connection number of graphs, arXiv:1110.5017v1 [math.CO] 2011. 68. X. Li, M. Liu, I. Schiermeyer, Rainbow connection number of dense graphs, arXiv:1110.5772v1 [math.CO] 2011. 69. X. Li, S. Liu, Sharp upper bound for the rainbow connection numbers of 2-connected graphs, arXiv:1105.4210v2 [math.CO] 2011. 70. X. Li, S. Liu, Rainbow vertex-connection number of 2-connected graphs, arXiv:1110.5770v1 [math.CO] 2011. 71. X. Li, S. Liu, L.S. Chandran, R. Mathew, D. Rajendraprasad, Rainbow connection number and connectivity, Electron. J. Combin. 19 (2012), P20. 72. X. Li, Y. Shi, On the rainbow vertex-connection, arXiv:1012.3504v1 [math.CO] 2010. 73. X. Li, Y. Shi, Rainbow connection in 3-connected graphs, arXiv:1010.6131v1 [math.CO] 2010. 74. X. Li, Y. Sun, Rainbow connection numbers of line graphs, Ars Combin. 100 (2011), 449–463.

100

References

75. X. Li, Y. Sun, Upper bounds for the rainbow connection numbers of line graphs, Graphs & Combin., in press. 76. X. Li, Y. Sun, On the rainbow k-connectivity of complete graphs, Australasian J. Combin. 49 (2011), 217–226. 77. X. Li, Y. Sun, Note on the rainbow k-connectivity of regular complete bipartite graphs, Ars Combin. 101 (2011), 513–518. 78. X. Li, Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, Discrete Math., to appear. 79. X. Li, Y. Sun, On the strong rainbow connection of a graph, Bull. Malays. Math. Sci. Soc., in press. 80. X. Li, Y. Sun, Rainbow connection numbers of complementary graphs, Util. Math. 86 (2011), 23–31. 81. X. Li, Y. Sun, Rainbow connections of graphs- A survey, arXiv:1101.5747v2 [math.CO] 2011. 82. W. Mader, Ecken vom Grad n in minimalen n-fach zusammenh¨angenden Graphen, Arch. Math. 23 (1972), 219–224. 83. K. Menger, Zur allgemeinen kurventheorie, Fund. Math. 10 (1927), 96–115. 84. E.A. Nordhaus, J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175–177. 85. F. Okamoto, P. Zhang, The tree connectivity of regular complete bipartite graphs, J. Combin. Math. Combin. Comput. 74 (2010), 279–293. 86. J.H. Park, K.Y. Chwa, Recursive circulants and their embeddings among hypercubes, Theoret. Computer Science 244 (2000), 35–62. 87. A. Rao, An exposition of Bourgain’s 2-source extractor, in: ECCCTR: Electronic Colloquium on Computational Complexity, Technical Reports, 2007. 88. J.J. Rotman, An Introduction to the Theory of Groups, GTM 148, Springer, New York, 1994. 89. I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, LNCS 5874 (2009), 435–437. 90. I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory 31(2) (2011), 387–395. 91. I. Schiermeyer, On mininally rainbow k-connected graphs, Discrete Appl. Math., in press. 92. I. Schiermeyer, Rainbow connection and minimum degree, Discrete Appl. Math., to appear. 93. R. Shaltiel, Recent developments in explicit constructions of extractors, Bull. EATCS 77 (2002), 67–95. 94. J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977), 69–76. 95. E. Szemer´edi, Regular partitions of graphs, In: Proc. colloque inter. CNRS 260. CNRS, Paris, 399–401. 96. M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Alg. & Discrete Methods 3(3) (1982), 351–358.

Index

Symbols (k, )-rainbow edge-index, 88 (k, )-rainbow index, 87 BFS algorithm, 32 D-ear, 43, 44 D2 -tree, 52 NP class, 22 NP-complete, 15, 17, 22, 23, 93, 95 NP-hard, 15, 17–19, 21, 22, 93, 95 ε -regular pair, 28 k-Steiner diameter, 85 k-connectivity, 87 k-edge-connectivity, 88 k-iterated line graph, 1 k-rainbow coloring, 12, 85 k-rainbow connected problem, 19 k-rainbow index, 12, 85 k-rainbow maximal graph, 60 k-rainbow minimal graph, 60 k-step dominating set, 2 k-step open neighborhood, 2 k-strong two-step dominating set, 2, 89 k-subset rainbow connected problem, 17–19, 21 k-subset strong rainbow connected problem, 20, 21 k-vertex-coloring problem, 20, 21 r-cube, 74 s − t rainbow vertex-connection problem, 94 2-factor, 51 2-subset rainbow connected problem, 18 3-SAT problem, 15, 17, 93–95 3CNF formula, 17 A Abelian group, 2, 71 acceptable D-ear, 43

almost surely, 58 approximate algorithm, 22 asteroidal triple (AT) graph, 2 AT-free graph, 2, 71 average degree, 51

B block, 26, 27, 52, 65 block tree, 27 bridge, 1, 43, 46, 52, 61 bridgeless graph, 1, 41, 43, 45, 61, 62, 71

C cage, 72 Cartesian product, 3, 73 Cayley graph, 2, 10, 71, 73 central vertex, 45 chain graph, 2, 71 chordal graph, 3, 42, 46, 71 chordality, 3, 45, 46 chromatic index, v, 4, 5, 51 chromatic number, 48, 51 circular arc graph, 2, 71 circumference, 51 claw-free graph, 48 clique, 1 clique decomposition, 66, 68 clique-forest-structure, 65 clique-tree-structure, 65 communication networks, 71, 74 complement graph, 47, 50, 51 complete bipartite graph, 1, 6, 81, 82 complete graph, 6, 79 complete multipartite graph, 6, 8, 47, 80, 82 complete rainbow coloring, 37

X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics, DOI 10.1007/978-1-4614-3119-0, © Xueliang Li, Yuefang Sun 2012

101

102

Index

complete rainbow path, 37 composition of graphs, 3, 73, 74, 76 connected k-step dominating set, 2, 41, 42, 44 connected k-step domination number, 2 connected k-strong two-step dominating set, 89 connected two-dominating set, 28 connected two-step dominating set, 33, 89, 90 connected two-way dominating set, 2, 70 connected two-way two-step dominating set, 2, 33, 35 connectivity, 3, 12, 25, 26, 36, 41, 43, 46 cubic graph, 72 cut vertex, 26, 27 cycle, 1, 6, 51, 73

I incomplete rainbow coloring, 37–40 incomplete rainbow path, 37–41 inner vertex, 66, 70 intersection graph, 1 interval graph, 1, 71 inverse closed set, 71 isometric cycle, 3, 43 isometric subgraph, 3 iterated line graph, 1, 65, 70

D degree-sum condition, 35, 58, 92 dense graph, 57 diameter, 2, 43, 57, 61, 62 different subsets rainbow vertex-connection 2 problem, 93 direct product, 3, 75 distance, 2 dominating set, 2

L lexicographic product, 3, 73–76 line graph, 1, 65, 69, 70, 95 Lov´asz Local Lemma, 89–92

E ear, 2 ear decomposition, 3, 37, 38, 40, 41 eccentricity, 2 edge density, 28 edge-connectivity, 12, 43 edge-disjoint triangles, 52, 53, 67, 69, 70 equipartition, 28 Erd˝os-Gallai type problem, 60 evenly colored Dk -ear, 44 extending to rainbow connection number 2 problem, 15 extractor, 81

J join, 3, 73, 74

M maximal clique, 1 Menger’s Theorem, 12, 87 minimal generating set, 71 minimum k-rainbow coloring, 12 minimum degree, 3, 25, 51, 57, 58, 61 minimum rainbow k-coloring, 12 minimum rainbow coloring, v, 4 minimum rainbow vertex-coloring, 11 minimum strong rainbow coloring, 5 minimum vertex-cover, 76 multicomputer networks, 71

N nested sequence of graphs, 2 network, 4 non-Hamiltonian graph, 37, 38, 40 Nordhaus–Gaddum-type result, 48, 93

F Fan Lemma, 41

G girth, 3, 42 graph power, 74

O odd-even rainbow connected graph, 75 odd-even rainbow connection number, 75 order of a graph, 25 outerplanar graph, 72

H Hamiltonian graph, 37 Hamming graph, 74 hypercube, 10, 74

P path, 1, 73 pendant, 1 pendant k-length path, 1

Index pendant edge, 1 Petersen graph, 5 planar graph, 23, 72, 84 polynomial time algorithm, 17, 22, 71, 72, 83

R radius, 2, 43, 45, 46, 74 rainbow (k, )-connectivity, 80 rainbow k-coloring, 12 rainbow k-connection number, 12 rainbow k-connectivity, 12, 77 rainbow coloring, v, 4 rainbow connected graph, v, 4 rainbow connection number, v, 4 rainbow connection number 2 problem, 15 rainbow diameter number, 5 rainbow geodesic, 4 rainbow path, v, 4 rainbow tree, 12 rainbow vertex-coloring, 11 rainbow vertex-connected graph, 11 rainbow vertex-connection 2 problem, 93 rainbow vertex-connection number, 11, 89 rainbow vertex-connection problem, 94 random graph, 58, 59, 83, 84 recursive circulant, 72 refinement of a coloring, 30 regular graph, 51 removable edge, 60 revised rainbow vertex-connection number, 92

S series-parallel graph, 84 sharp threshold function, 58, 84 shrink, 66 size of clique-forest-structure, 65 size of clique-tree-structure, 65 sparse graph, 57, 62 Steiner distance, 85

103 Steiner tree, 85 strong product, 3, 73, 75 strong rainbow coloring, 4 strong rainbow connection number, 5, 19, 52 strongly rainbow connected graph, 4 strongly regular graph, 2, 55, 72 subset rainbow connection number 2 problem, 15 subset rainbow vertex-connection 2 problem, 93 subset strong rainbow connected problem, 20 Szemer´edi Regularity Lemma, 22, 28, 29

T threshold function, 83 threshold graph, 2, 71 toughness, 51 tower function, 33 tree, 6 triangle, 52 triangle-forest-structure, 65, 67 triangle-free graph, 48 triangle-tree-structure, 65, 67, 68 two-step dominating set, 33, 89 two-way dominating set, 2 two-way two-step dominating set, 34

U unicyclic graph, 62, 63, 86 union of graphs, 1 unit interval graph, 2, 71, 73

V vertex-cover, 76

W wheel, 1, 6