Contents
Preface
Chapter 1 Introduction 1
1.1 Basic concepts 1
1.2 Basic results 5
Chapter 2 Rainbow Connection Number， Order and
Minimum Degree (sum) 14
2.1 Rainbow connection number， order and minimum degree (sum) 14
2.2 Rainbow vertex-connection number and minimum degree (sum) 27
Chapter 3 Rainbow Connection Number， Radius and Diameter 38
3.1 Rainbow connection number and radius with bridgeless 38
3.2 Rainbow connection number and radius with bridges 43
Chapter 4 Rainbow Connection Number and Independence
Number 52
4.1 Tight example 52
4.2 Lemma and observation 53
4.3 Theorem and proof 54
Chapter 5 Rainbow Connection Number of Dense， Sparse and
Random Graphs 69
5.1 Definitions of dense， sparse and random graphs 69
5.2 Rainbow connection number of dense graphs 69
5.3 Rainbow connection number of sparse and random graphs 74
Chapter 6 Computational Complexity 84
6.1 Conjecture of NP-hard and NP-complete 84
6.2 NP-hard and NP-complete 85
Reference 101
Index 106