| A communication network is usually modeled by a graph in which vertices rep-resent the switching elements or processors and edges represent the communication links. In order to prevent hackers, one can set a password in each link. To facilitate the management, one can require that the number of passwords is small enough such that any two nodes can exchange information by a sequence of links which have different passwords. This problem can be modeled by a graph and studied by means of rainbow connection number. The rainbow connection number was introduced by Chartrand et al. in2008.A k-edge-colouring of a graph G=(V,E) is a mapping c:E→S, where S is a set of k colours, in other words, an assignment of k colours to the edges of G. Usually, the set of colours S is taken to be{1,2,...,k}. A path in an edge-colored graph G, where adjacent edges may have the same color, is a rainbow path if no two edges of the path are colored the same. A k-edge-coloring is k-rainbow-coloring if there exists a rainbow path for any two vertices of G. A graph is k-rainbow connected if G has a k-rainbow-coloring. The rainbow connection number rc(G) of G is the minimum integer k such that the graph G has k-rainbow-coloring. For integers n and k let t(n,k) denote the minimum size (number of edges) in k-rainbow connected graphs of order n.This thesis includes seven chapters. In chapter1. we first introduce the definition and background of rainbow connection number. Then, we present an overview of our main results.Since the diameter of a graph is a natural lower bound of the rainbow connection number of the graph, we focus on the relation between rainbow connection number and diameter (radius). It is clear that each bridge must be assigned different colors, and this case is trivial, we put our attention on bridgeless graphs. The radius and diameter of a graph G have the following close relation:rad(G)<diam(G)<2rad(G). In chapter1, we investigate the relation between rainbow connection number and radius, and show that for every bridgeless graph G, rc{G)≤∑i=1rad(G)min{2i+1,η(G)}≤rad(G)η(G), where η (G) is the smallest integer number such, that every edge of G is contained in a cycle of length at most η(G).The relation between rainbow connection number and radius was studied in chap-ter2. Unlike radius, it is very different to study the relation between rainbow connec-tion number and diameter. But we know that almost all graphs have diameter two, so the small diameter graphs are very interesting.In chapter3and4, we will study the upper bound of rainbow connection number of a graph with small diameter, and get the following results:for a bridgeless graph G with diameter2, rc(G)<5, and for a bridgeless graph G with diameter3, rc(G)<9.Hypercubes and recursive circulants are the two networks which were studied by many researchers in the past decades. Since hypercubes and recursive circulants are Cayley graphs on Abelian groups. In Chapter5, we study the rainbow connection number of Cayley graphs on Abelian groups by using the property of commutativ-ity, and get that for an Abelian group F and an inverse closed set S(?)Γ{1},(ⅰ) rc(C(Γ,S))<min{∑a∈S*(?)|S*(?)S is a minimal generating set of Γ}.(ⅱ) if S is an inverse closed minimal generating set of Γ, then∑a∈S*(?)≤rc(C(Γ,S))≤src(C(F,S))≤∑a∈S*(?),,where S*(?)S is a minimal generating set of Γ. Moreover, if every element∈has an even order, then rc(C(Γ,S))=src(C(Γ,S))=∑a∈S*(?)In chapter6, we study minimally k-rainbow connected graphs for k≥3, and show that (i) for sufficiently large n, t(n,2)≥nlog2n-4nlog2log2n-2n;(ii) for3<k<(?).n-k-3+(?)≤t(n,k)≤k(n-2)/k-1In chapter7,based on our results in this thesis, we discuss some interesting prob-lems. |
