| 摘要 | 第1-7页 |
| Abstract | 第7-10页 |
| Contents | 第10-12页 |
| Chapter 1 Introduction | 第12-24页 |
| ·Background | 第12-14页 |
| ·Definition and Notation | 第14-18页 |
| ·Overview of Results | 第18-24页 |
| ·Upper bounds for the rainbow (vertex-) connection num-bers of graphs | 第18-20页 |
| ·Rainbow (vertex-) connection numbers on complementary graphs | 第20-22页 |
| ·Complexity for rainbow (vertex-) connection numbers of graphs | 第22-24页 |
| Chapter 2 Nordhaus-Gaddum Type Bounds | 第24-46页 |
| ·Nordhaus-Gaddum Type Bounds for Rainbow Connection Number of Graphs | 第24-40页 |
| ·Upper bound on rc(G)+rc(G) | 第25-29页 |
| ·Lower bound on rc(G)+rc(G) | 第29-40页 |
| ·Concluding remark | 第40页 |
| ·Nordhaus-Gaddum Type Bounds for Rainbow Vertex-Connection Number of Graphs | 第40-46页 |
| ·upper bound on rvc(G)+rvc(G) | 第41-44页 |
| ·Lower bound on rvc(G)+rvc(G) | 第44-46页 |
| Chapter 3 Complexity for Rainbow Vertex-Connection Number of Graphs | 第46-70页 |
| ·Preliminaries | 第46-49页 |
| ·The Complexity of Determining the Rainbow Vertex-Connection Namber of a Graph | 第49-58页 |
| ·Rainbow vertex-connection 2 | 第49-55页 |
| ·Rainbow vertex-connection | 第55-58页 |
| ·Further Hardness Results on the Rainbow Vertex-Connection Num-ber of a Graph | 第58-68页 |
| ·Concluding and Open Problems | 第68-70页 |
| Biblography | 第70-76页 |
| 致谢 | 第76-78页 |
| 个人简介 | 第78页 |
