《THEORY OF GRAPHS》

Chapter 1FUNDAMENTAL CONCEPTS1

1．1 Graph definitions1

1．2 Local degrees7

1．3 Subgraphs12

1．4 Binary relations13

1．5 Incidence matrices18

Chapter 2CONNECTEDNESS22

2．1 Sequences,paths and arcs22

2．2 Connected components23

2．3 One-to-one correspondences25

2．4 Distances27

2．5 Elongations31

2．6 Matrices and paths．Product graphs33

2．7 Puzzles36

Chapter 3PATH PROBLEMS38

3．1 Euler paths38

3．2 Euler paths in infinite graphs42

3．3 An excursion into labyrinths47

3．4 Hamilton circuits52

Chapter 4TREES58

4．1 Properties of trees58

4．2 Centers in trees62

4．3 The circuit rank67

4．4 Many-to-one correspondences68

4．5 Arbitrarily traceable graphs74

Chapter 5LEAVES AND LOBES78

5．1 Edges and vertices of attachment78

5．2 Leaves81

5．3 Homomorphic graph images83

5．4 Lobes85

5．5 Maximal circuits89

Chapter 6THE AXIOM OF CHOICE92

6．1 Well-ordering92

6．2 The maximal principles94

6．3 Chain sum properties96

6．4 Maximal exclusion graphs100

6．5 Maximal trees101

6．6 Interrelations between maximal graphs103

Chapter 7MATCHING THEOREMS106

7．1 Bipartite graphs106

7．2 Deficiencies108

7．3 The matching theorems110

7．4 Mutual matchings113

7．5 Matchings in special graphs117

7．6 Bipartite graphs with positive deficiencies121

7．7 Applications to matrices125

7．8 Alternating paths and maximal matchings132

7．9 Separating sets138

7．10 Simultaneous matchings139

Chapter 8DIRECTED GRAPHS145

8．1 The inclusion relation and accessible sets145

8．2 The homomorphism theorem149

8．3 Transitive graphs and embedding in order relations150

8．4 Basis graphs152

8．5 Alternating paths156

8．6 Subgraphs of first degree159

Chapter 9ACYCLIC GRAPHS162

9．1 Basis graphs162

9．2 Deformations of paths163

9．3 Reproduction graphs166

Chapter 10PARTIAL ORDER170

10．1 Graphs of partial order170

10．2 Representations as sums of ordered sets170

10．3 Lattices and lattice operations．Closure relations175

10．4 Dimension in partial order178

Chapter 11BINARY RELATIONS AND GALOIS CORRESPONDENCES183

11．1 Galois correspondences183

11．2 Galois connections for binary relations187

11．3 Alternating product relations191

11．4 Ferrers relations193

Chapter 12CONNECTING PATHS197

12．1 The cross-path theorem197

12．2 Vertex separation200

12．3 Edge separation202

12．4 Deficiency203

Chapter 13DOMINATING SETS,COVERING SETS AND INDEPENDENT SETS206

13．1 Dominating sets206

13．2 Covering sets and covering graphs208

13．3 Independent sets210

13．4 The theorem of Turan214

13．5 The theorem of Ramsey216

13．6 A problem in information theory220

Chapter 14CHROMATIC GRAPHS224

14．1 The chromatic number224

14．2 Sums of chromatic graphs227

14．3 Critical graphs229

14．4 Coloration polynomials234

Chapter 15GROUPS AND GRAPHS239

15．1 Groups of automorphisms239

15．2 Cayley＇s color graphs for groups242

15．3 Graphs with prescribed groups244

15．4 Edge correspondences245

BIBLIOGRAPHY250

LIST OF CONCEPTS265

INDEX OF NAMES269