| 中文摘要 | 第1-7页 |
| Abstract | 第7-11页 |
| Chapter 1 Introduction | 第11-25页 |
| ·Probabilistic methods versus explicit constructions on expander graphs | 第13-16页 |
| ·Cayley graphs and expander graphs | 第16-20页 |
| ·Lift of graph | 第20-22页 |
| ·Ramanujan graphs and expander graphs | 第22-23页 |
| ·Rainbow connection number of graphs on algorithm | 第23-25页 |
| Chapter 2 Concentration properties of semi-vertex transitive graphs and random bi-coset graphs | 第25-45页 |
| ·Introduction | 第25-30页 |
| ·Preliminaries from representation theory | 第30-32页 |
| ·Proof of Theorem 2.1.8 | 第32-34页 |
| ·Bsc and semi-vertex transitive graph from generalized polygons | 第34-35页 |
| ·Bsc and semi-vertex transitive graph from designs of the Mathieu groups | 第35-38页 |
| ·Symmetric group and a sequence of concentrators | 第38-40页 |
| ·Concluding remarks | 第40页 |
| ·Irregular ramanujan graphs and unbalanced expander graphs | 第40-45页 |
| Chapter 3 Tight products, graph expansion and semi-coloring of graphs35 | 第45-53页 |
| ·Introduction | 第45-48页 |
| ·The proof | 第48-50页 |
| ·A partial result | 第50-53页 |
| Chapter 4 Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs | 第53-65页 |
| ·Introduction | 第53-54页 |
| ·Rainbow connection numbers of Fan structures | 第54-56页 |
| ·Maximal Fan partition properties of MOP | 第56-60页 |
| ·The computation of the upper bound of MOPs | 第60-63页 |
| ·An example | 第63-64页 |
| ·Concluding remarks | 第64-65页 |
| Chapter 5 Parameterized Algorithm for A Sharp Upper Bound of Rain-bow Connection Numbers of Graphs | 第65-77页 |
| ·Introduction | 第65-66页 |
| ·A basic property of rainbow connection numbers | 第66-69页 |
| ·Upper bound of rc(G)for G with bounded treewidth | 第69-77页 |
| References | 第77-81页 |
| 致谢 | 第81-83页 |
| 个人简历 | 第83-84页 |
