You are here

Home » MAA Publications » MAA Reviews » Graph Theory and Its Applications

Graph Theory and Its Applications

Jonathn L. Gross, Jay Yellen, and Mark Anderson
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2018
Number of Pages: 
577
Format: 
Hardcover
Edition: 
3
Series: 
Textbooks in Mathematics
Price: 
99.95
ISBN: 
9781482249484
Category: 
Textbook
[Reviewed by
Fernando Q. Gouvêa
, on
12/6/2018
]

The authors describe this book as

a collection of topics drawn from the second edition of Graph Theory and its Applications, written by the first two authors of this book.

See Bill Satzer’s review of that second edition, in which he comments on its enormous size but also points out its many strengths. That edition had 779 pages; the third edition has “only” 577. Comparing the tables of contents one sees that

  • Several chapters have been omitted: “Drawing Graphs and Maps”, “Measurement and Mappings”, “Analytic Graph Theory”, “Algebraic Specification of Graphs”, and “Non-Planar Layouts”.
  • The chapter on “Graphical Enumeration” has been slimmed down and renamed “Graph Colorings and Symmetry” to reflect that.

The first six chapters, which have a foundational role, seem to be unchanged. The first two authors have a web site with supporting material and corrections, but (as I write) it does not seem to have been updated to reflect the new edition.

Unless an instructor intends to focus on the materials that are no longer included, this remains a strong contender for a serious introduction to graph theory.

Fernando Q. Gouvêa is the editor of MAA Reviews. For now.

Introduction to Graph Models

Graphs and Digraphs
Common Families of Graphs
Graph Modeling Applications
Walks and Distance
Paths, Cycles, and Trees
Vertex and Edge Attributes

Structure and Representation

Graph Isomorphism
Automorphism and Symmetry
Subgraphs
Some Graph Operations
Tests for Non-Isomorphism
Matrix Representation
More Graph Operations

Trees

Characterizations and Properties of Trees
Rooted Trees, Ordered Trees, and Binary Trees
Binary-Tree Traversals
Binary-Search Trees
Huffman Trees and Optimal Prefix Codes
Priority Trees
Counting Labeled Trees
Counting Binary Trees

Spanning Trees

Tree Growing
Depth-First and Breadth-First Search
Minimum Spanning Trees and Shortest Paths
Applications of Depth-First Search
Cycles, Edge-Cuts, and Spanning Trees
Graphs and Vector Spaces
Matroids and the Greedy Algorithm

Connectivity

Vertex and Edge-Connectivity
Constructing Reliable Networks
Max-Min Duality and Menger’s Theorems
Block Decompositions

Optimal Graph Traversals

Eulerian Trails and Tours
DeBruijn Sequences and Postman Problems
Hamiltonian Paths and Cycles
Gray Codes and Traveling Salesman Problems

Planarity and Kuratowski’s Theorem

Planar Drawings and Some Basic Surfaces
Subdivision and Homeomorphism
Extending Planar Drawings
Kuratowski’s Theorem
Algebraic Tests for Planairty
Planarity Algorithm
Crossing Numbers and Thickness

Graph Colorings

Vertex-Colorings
Map-Colorings
Edge-Colorings
Factorization

Special Digraph Models

Directed Paths and Mutual Reachability
Digraphs as Models for Relations
Tournaments
Project Scheduling
Finding the Strong Components of a Digraph

Network Flows and Applications

Flows and Cuts in Networks
Solving the Maximum-Flow Problem
Flows and Connectivity
Matchings, Transversals, and Vertex Covers

Graph Colorings and Symmetry

Automorphisms of Simple Graphs
Equivalence Classes of Colorings

Appendix

Tags: 
Graph Theory