# Book:J.A. Bondy/Graph Theory With Applications

## J.A. Bondy and U.S.R. Murty: Graph Theory With Applications

Published $\text {1976}$, Elsevier Science Ltd/North-Holland

ISBN 978-0444194510

### Contents

Preface
1 Graphs and Subgraphs
1.1 Graphs and Simple Graphs
1.2 Graph Isomorphism
1.3 The Incidence and Adjacency Matrices
1.4 Subgraphs
1.5 Vertex Degrees
1.6 Paths and Connection
1.7 Cycles
Applications
1.8 The Shortest Path Problem
1.9 Sperner's Lemma
2 Trees
2.1 Trees
2.2 Cut Edges and Bonds
2.3 Cut Vertices
2.4 Cayley's Formula
Applications
2.5 The Connector Problem
3 Connectivity
3.1 Connectivity
3.2 Blocks
Applications
3.3 Construction of Reliable Communication Networks
4 Euler Tours and Hamilton Cycles
4.1 Euler Tours
4.2 Hamilton Cycles
Applications
4.3 The Chinese Postman Problem
4.4 The Travelling Salesman Problem
5 Matchings
5.1 Matchings
5.2 Matchings and Coverings in Bipartite Graphs
5.3 Perfect Matchings
Applications
5.4 The Personnel Assignment Problem
5.5 The Optimal Assignment Problem
6 Edge Colourings
6.1 Edge Chromatic Number
6.2 Vizing's Theorem
Applications
6.3 The Timetabling Problem
7 Independent Sets and Cliques
7.1 Independent Sets
7.2 Ramsey's Theorem
7.3 Turán's Theorem
Applications
7.4 Schur's Theorem
7.5 A Geometry Problem
8 Vertex Colourings
8.1 Chromatic Number
8.2 Brooks' Theorem
8.3 Hajós' Conjecture
8.4 Chromatic Polynomials
8.5 Girth and Chromatic Number
Applications
8.6 A Storage Problem
9 Planar Graphs
9.1 Plane and Planar Graphs
9.2 Dual Graphs
9.3 Euler's Formula
9.4 Bridges
9.5 Kuratowski's Theorem
9.6 The Five-Colour Theorem and the Four-Colour Conjecture
9.7 Nonhamiltonian Planar Graphs
Applications
9.8 A Planarity Algorithm
10 Directed Graphs
10.1 Directed Graphs
10.2 Directed Paths
10.3 Directed Cycles
Applications
10.4 A Job Sequencing Problem
10.5 Designing an Efficient Computer Drum
10.6 Making a Road System One-Way
10.7 Ranking the Participants in a Tournament
11 Networks
11.1 Flows
11.2 Cuts
11.3 The Max-Flow Min-Cut Theorem
Applications
11.4 Menger's Theorems
11.5 Feasible Flows
12 The Cycle Space and Bond Space
12.1 Circulations and Potential Differences
12.2 The Number of Spanning Trees
Applications
12.3 Perfect Squares
Appendix I: Hints to Starred Exercises
Appendix II: Four Graphs and a Table of their Properties
Appendix III: Some Interesting Graphs
Appendix IV: Unsolved Problems
Appendix V: Suggestions for Further Reading
Glossary of Symbols
Index