Some Topics On Rainbow Connections Of Graphs

The concept of rainbow connection of a graph was first introduced by Chartrand,Johns, McKeon and Zhang in2006. Let G be a nontrivial connected graph on which anedge-coloring c: E(G)â†'{1,2,···,n}, n∈N, is defined, where adjacent edges may becoloredthesame. Apathisrainbowifnotwoedgesofitarecoloredthesame. Anedge-colored graph G is rainbow connected if every two distinct vertices are connected by arainbowpath. Anedge-coloringunderwhichGisrainbowconnectediscalledarainbowcoloring. 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 bycoloring edges with distinct colors. Thus, we define the rainbow connection numberof a connected graph G, denoted by rc(G), as the smallest number of colors that areneeded in order to make G rainbow connected.The rainbow connection number is not only a natural combinatorial measure, butalso has applications to the secure transfer of classified information between agencies.In addition, the rainbow connection number can also be motivated by its interestinginterpretation in the area of networking: Suppose that G represents a network (e.g., acellular 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 thepath) is assigned a distinct channel (e.g. a distinct frequency). Clearly, we want tominimize the number of distinct channels that we use in our network. This number isprecisely rc(G).Let c be a rainbow coloring of a connected graph G. For any two vertices u andv of G, a rainbow u v geodesic in G is a rainbow u v path of length d(u, v). Agraph G is strongly rainbow connected if there exists a rainbow u v geodesic forevery pair of distinct vertices u and v in G. In this case, the coloring c is called astrong rainbow coloring of G. Similarly, we define the strong rainbow connectionnumber ofaconnectedgraph G,denotedby src(G),asthesmallestnumberofcolorsthatare needed in order to make G strong rainbow connected. 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.A natural generalization of rainbow coloring is as follows: the number of rainbowpaths between any two vertices is at least an integer k with k≥1in some edge-coloring.Awell-knowntheoremofMengershowsthatineveryκ-connectedgraphGwithκ≥1,there are k internally disjoint u v paths connecting every two distinct vertices u andv for every integer k with1≤k≤κ. Similar to rainbow coloring, we call an edge-coloring a rainbow k-coloring if there are at least k internally disjoint rainbow u vpaths connecting any two distinct vertices u and v. Chartrand, Johns, McKeon andZhangdefinedtherainbowk-connectivityrck(G) of G tobetheminimuminteger j suchthat there exists a j-edge-coloring which is a rainbow k-coloring. By definition, rck(G)is a generalization of rc(G) and rc1(G)=rc(G) is the rainbow connection number ofG. By coloring the edges of G with distinct colors, we see that every two vertices of Gare connected by k internally disjoint rainbow paths and that rck(G) is defined for every1≤k≤κ. So rck(G) is well-defined. Furthermore, rck(G)≤rcj(G) for1≤k≤j≤κ.This thesis consists of two parts. The first part, including Chapters2,3,4and5,contributestotheconceptofrainbowconnectionnumberandstrongrainbowconnectionnumber of a graph. While the second part, Chapter6, contributes to the concept ofrainbow k-connectivity of a graph.In Chapter2, we consider the upper bounds for rainbow connection number andstrong rainbow connection number of a graph. We first investigate the rainbow connec-tion number of a graph G according to some constraints to its complement graph G andderive two sufficient conditions to guarantee that rc(G) is bounded by a constant. Thefirst result is that for a connected graph G, if G does not belong to the following twocases:(i) diam(G)=2,3,(ii) G contains exactly two connected components and oneof them is trivial, then rc(G)≤4, where diam(G) is the diameter of G. Examples aregiven to show that this bound is best possible. The second result is that for a connectedgraph G, if G is triangle-free, then rc(G)≤6. Next, we obtain a sharp upper boundfor src(G) according to the number of edge-disjoint triangles in a graph G: If G is agraph with m edges and t edge-disjoint triangles, then src(G)≤m2t. We then give anecessary and sufficient condition for the sharpness.In Chapter3, we investigate graphs with (strong) large rainbow connection num- bers, we derived that rc(G)=m1, src(G)=m1, and characterize graphs withrc(G)=m2(src(G)=m2).In chapter4, We investigate an important graph class, line graph. We first considerthe rainbow connection numbers of line graphs of triangle-free graphs and derive twoupperboundsaccordingtosomeparametersofthelinegraphortheoriginalgraph. Next,we consider the rainbow connection numbers of line graphs of graphs containing trian-gles and derive two sharp upper bounds according to some parameters of the originalgraph. The first result is that for any set T of t edge-disjoint triangles of a connectedgraph G, if the subgraph induced by the edge set E(T) is a triangle-forest-structure,then rc(L(G))≤n2t; moreover, the bound is sharp. The next result is as follows: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)], thenrc(L(G))≤t+n′2+c; moreover, the bound is sharp. We also investigate the rainbowconnection number for iterated line graphs and obtain that let G be a connected graphwith m edges and m1pendent2-length paths, then rc(L2(G))≤m m1, the equalityholds if and only if G is a path of length at least3.In chapter5, we study the behavior of rainbow connection number under graphoperations. FortheCartesianproduct,wegiveasharpupperbound: IfGistheCartesianproduct of connected graphs G1,···, Gk, then rc(G)≤∑ki=1rc(Gi), with equality whenrc(Gi)=diam(Gi) for each i. We also consider also graph graph operations, such as,composition(lexicographicproduct),joinoperationsontwographs, vertexsplittingandedge subdivision on a single graph.In chapter6, we investigate the rainbow k-connectivity of two special graph class-es: complete graph and regular complete bipartite graph. For complete graph, we showthat for every integer k≥2, there exists an integer f(k)=ck23+C(k) where c is aconstant and C(k)=o(k23) such that if n≥f (k), then rck(Kn)=2. Chartrand, Johns,McKeon and Zhang obtained an upper bound (k+1)2for f(k), namely f(k)≤(k+1)2.Weimprovetheupperboundof f(k)fromO(k2) to O(k23),aconsiderableimprovement.For regular complete bipartite graph, we derive that for every integer k≥2, there ex-ists an integer g(k) such that rck(Kr,r)=3for any r≥g(k). This result settle an openquestion of [1].