Graphs and Networks (eBook)

S. R. Kingan is an Associate Professor of Mathematics at Brooklyn College and the Graduate Center of The City University of New York. Dr. Kingan's research interests include graph theory, matroid theory, combinatorial algorithms, and their applications.

List of Figures iv

Preface viii

Chapter 1. From Königsberg to Connectomes 1

1.1. Introduction 1

1.2. Isomorphism 18

1.3. Minors and Constructions 25

Chapter 2. Fundamental Topics 39

2.1. Trees 39

2.2. Distance 44

2.3. Degree Sequences 52

2.4. Matrices 56

Chapter 3. Similarity and Centrality 70

3.1. Similarity Measures 70

3.2. Centrality Measures 74

3.3. Eigenvector and Katz Centrality 78

3.4. PageRank 84

Chapter 4. Types of Networks 91

4.1. Small-World Networks 91

4.2. Scale-Free Networks 95

4.3. Assortative Mixing 97

4.4. Covert Networks 102

Chapter 5. Graph Algorithms 107

5.1. Traversal Algorithms 107

5.2. Greedy Algorithms 113

5.3. Shortest Path Algorithms 118

Chapter 6. Structure, Coloring, Higher Connectivity 126

6.1. Eulerian Circuits 126

6.2. Hamiltonian Cycles 131

6.3. Coloring 136

6.4. Higher Connectivity 142

6.5. Menger's Theorem 148

Chapter 7. Planar Graphs 159

7.1. Properties of Planar Graphs 159

7.2. Euclid's Theorem on Regular Polyhedra 167

7.3. The Five Color Theorem 172

7.4. Invariants for Non-Planar Graphs 174

Chapter 8. Flows and Matchings 182

8.1. Flows in Networks 182

8.2. Stable Sets, Matchings, Coverings 188

8.3. Min-Max Theorems 192

8.4. Maximum Matching Algorithm 196

Appendix A. Linear Algebra 211

Appendix B. Probability and Statistics 215

Appendix C. Complexity of Algorithms 218

Appendix D. Stacks and Queues 222

Appendix. Bibliography 226