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

Subject Matter

• Graph Theory

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