Several Problems On Expansion Properties And Rainbow Connection Numbers Of Graphs

This thesis studies some problems on expansion properties and rainbow connec-tion numbers of graphs:(1) By Azuma’s inequality and representation theory of fi-nite groups, we investigate concentration properties of semi-vertex-transitive graphsand random bi-coset graphs.(2) We answer affirmatively an open problem on semi-coloring of graphs proposed by Daniely and Linial [21], and get an upper bound foredge-coloring number of regular graphs by the probabilistic method.(3) We designa polynomial time algorithm for a sharp upper bound of rainbow connection numberof maximal outerplanar graphs by the maximal FAN partition.(4) For graphs withbounded tree widths, we give a linear time algorithm for a sharp upper bound of theirrainbow connection numbers, and can judge whether the bound is good or not in poly-nomial time.In Chapter1, we introduce some preliminaries on expansion-like property andrainbow connection number of graphs.In Chapter2, based on the relation between bounded strong concentrator and itseigenvalues (Tanner [56]), by Azuma’s inequality and representation theory of finitegroups, we prove almost all semi-vertex-transitive graphs are bounded strong concen-trators. In addition, we construct the following semi-vertex-transitive bounded strongconcentrators: the generalized hexagon of order (2,2), the corresponding graphs XMiof the unique design given by large Mathieu groups Mi(i∈{22,23,24}),the cor-responding graphs XDiof the unique design given by small Mathieu groups Di(i∈{9,10,11,12}),and a sequence of bounded strong concentrators constructed by sym-metric groups.Recall Daniely and Linial [21](Tight products and graph expansion) defined a newproduct, tight product, of graphs by the concept of lift on graphs; and in the process ofproving the existence of such a product, they proposed a new edge-coloring (i.e., semi-coloring) of graphs and a problem: does every graph have a semi-coloring? In Chapter3, we answer affirmatively this problem, and also get an upper bound for edge-coloring number of regular graphs by the probabilistic method.In Chapter4, after obtaining the rainbow connection number and a rainbow color-ing for every maximal FAN and defining the maximal FAN decomposition for maximalouterplanar graphs, by the algorithm of maximal cardinality search and maximal FANdecomposition, we design a polynomial time algorithm computing a sharp upper boundof rainbow connection number for maximal outerplanar graphs and also give an exam-ple reaching the sharp bound.In Chapter5, based on the“divide and conquer”method, which is widely usedin algorithm design (especially approximation algorithm design), we give a basic resultlike“divide and conquer”on rainbow connection number and a linear time algorithmcomputing a sharp upper bound of rainbow connection number for graphs with boundedtree width by the result and the spirit of Ford algorithm; and also take an example thatreaches the sharp bound by the algorithm. Moreover, we could judge whether theobtained bound is good or not in polynomial time.