图论基础PDF电子书下载

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

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 different 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 different 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