Contents
Preface in Chinese iii
Chapter 1 Basic concepts 1
1.1 Graph and simple graph 1
1.2 Graph operations 3
1.3 Isomorphism 7
1.4 Incident and adjacent matrix 7
1.5 The spectrum of graph 10
1.6 The spectrum of several graphs 16
1.7 Results from matrix theory 19
1.8 About the largest zero of characteristic polynomials 22
1.9 Spectrum radius 28
Chapter 2 path and cycle 30
2.1 The path 30
2.2 The cycle 33
2.3 The diameter of a graph and its complement graph 36
Chapter 3 Tree 39
3.1 Tree 39
3.2 Spanning tree 41
3.3 A bound for the tree number of regular graphs 47
3.4 Cycle space and bound space of a graph 48
Chapter 4 Connectivity 51
4.1 Cut edges 51
4.2 Cut vertex 52
4.3 Block 55
4.4 Connectivity 57
Chapter 5 Euler and Hamilton graphs 60
5.1 Euler path and circuits 60
i
ii The Fundamental Theory Of Graphs
5.2 Hamilton graph 62
Chapter 6 Matching and matching polynomial 66
6.1 Matching 66
6.2 Bipartite graph and perfect matching 67
6.3 Matching polynomial 69
6.4 The relation between spectrum and matching polynomial 72
6.5 Relation between several graphs 74
6.6 Several matching equivalent and matching unique graphs 75
6.7 The Hosoya index of several graphs 76
6.8 Two trees with minimal Hosoya index 79
6.9 Recent results in matching 83
Chapter 7 Laplacian and Quasi-Laplacian spectrum 85
7.1 Sigma function 85
7.2 The spanning tree and sigma function 87
7.3 Quasi-Laplacian Spectrum 88
7.4 Basic lemmas 89
7.5 Main results 90
7.6 Three di?erent spectrum of regular graphs 96
Chapter 8 More theorems form matrix theory 100
8.1 The irreducible matrix 100
8.2 Cauchy's interlacing theorem 102
8.3 The eigenvalues of A(G) and graph structure 103
Chapter 9 Chromatic polynomial 105
9.1 Induction 105
9.2 Two di?erent formula for chromatic polynomial 107
9.3 Chromatic polynomials for several type of graphs 109
9.4 Estimate the color number 110
References 112
Bibliography 115
