Graph Theory

by Ronald Gould

Overview

This introduction to graph theory focuses on well-established topics, covering primary techniques and including both algorithmic and theoretical problems. The algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as advanced undergraduates and graduate students of topology, algebra, and matrix theory.
Fundamental concepts and notation and elementary properties and operations are the first subjects, followed by examinations of paths and searching, trees, and networks. Subsequent chapters explore cycles and circuits, planarity, matchings, and independence. The text concludes with considerations of special topics and applications and extremal theory. Exercises appear throughout the text.

Product Details

ISBN-13:	9780486498065
Publisher:	Dover Publications
Publication date:	11/21/2012
Series:	Dover Books on Mathematics
Edition description:	Reprint
Pages:	350
Product dimensions:	9.00(w) x 6.10(h) x 0.80(d)

About the Author

Ronald Gould is Professor of Mathematics and Computer Science at Emory University. He specializes in combinatorics and graph theory and is most noted for his work in Hamiltonian graph theory.

Table of Contents

Chapter 1 Graphs

1.0 Introduction 1

1.1 Fundamental Concepts and Notation 1

1.2 Elementary Properties and Operations 8

1.3 Alternate Representations for Graphs 14

1.4 Algorithms 16

1.5 Degree Sequences 19

1.6 Fundamental Counting 25

Chapter 2 Paths and Searching

2.1 Distance 33

2.2 Connectivity 47

2.3 Digraph Connectivity 56

2.4 Problem Solving and Heuristics 59

Chapter 3 Trees

3.1 Fundamental Properties of Trees 69

3.2 Minimal Weight Spanning Trees 71

3.3 Counting Trees 76

3.4 Directed Trees 80

3.5 Optimal Directed Subgraphs 86

3.6 Binary Trees 90

3.7 More About Counting-Using Generating Functions 99

Chapter 4 Networks

4.1 Flows 105

4.2 The Ford and Fulkerson Approach 107

4.3 The Dinic Algorithm and Layered Networks 114

4.4 Layered Networks and Potential 118

4.5 Variations on Networks 119

4.6 Connectivity and Networks 124

Chapter 5 Cycles and Circuits

5.1 Eulerian Graphs 131

5.2 Adjacency Conditions for Hamiltonian Graphs 137

5.3 Related Hamiltonian-like Properties 146

5.4 Forbidden Subgraphs 149

5.5 Other Types of Hamiltonian Results 153

5.6 The Traveling Salesman Problem 155

5.7 Short Cycles and Girth 157

5.8 Disjoint Cycles 160

Chapter 6 Planarity

6.1 Euler's Formula 171

6.2 Characterizations of Planar Graphs 174

6.3 A Planarity Algorithm 184

6.4 The Hopcroft-Tarjan Planarity Algorithm 188

6.5 Hamiltonian Planar Graphs 196

Chapter 7 Matchings

7.0 Introduction 201

7.1 Matchings and Bipartite Graphs 201

7.2 Matching Algorithms and Marriage 207

7.3 Factoring 219

7.4 Degrees and 2-Factors 225

Chapter 8 Independence

8.1 Vertex Independence and Coverings 233

8.2 Vertex Colorings 235

8.3 Approximate Coloring Algorithms 240

8.4 Edge Colorings 246

8.5 The Four Color Theorem 250

8.6 Chromatic Polynomials 252

8.7 Perfect Graphs 254

Chapter 9 Special Topics and Applications

9.1 Graphs and Ordered Sets 261

9.2 Random Graphs 266

9.3 Ramsey Theory 272

9.4 Finite State Machines 278

9.5 Scheduling 283

9.6 Tournaments 289

Chapter 10 Extremal Theory

10.0 Introduction 301

10.1 Complete Subgraphs 302

10.2 Cycles in Graphs 310

10.3 On the Structure of Extremal Graphs 315

Appendix 327

Index 329