Part 1: Graph Models and Routes
1. Eulerian Tours
1.1 Königsberg Bridge Problem
1.2 Introduction to Graph Models
1.3 Touring a Graph
1.4 Eulerian Circuit Algorithms
1.5 Eulerization
1.6 Exercises
2. Hamiltonian Cycles
2.1 Existence of a Hamiltonian Cycle
2.2 Traveling Salesman Problem
2.3 Digraphs
2.4 Exercises
3. Paths
3.1 Shortest Paths
3.2 Project Scheduling
3.3 Exercises
4. Additional Topics in Graph Routes
4.1 Tournaments
4.2 Flow and Capacity
4.3 Matrix Representation
4.4 Algorithm Efficiency
4.5 Exercises
Part 2: Graph Structure
5. Trees and Networks
5.1 Trees
5.2 Spanning Trees
5.3 Shortest Networks
5.4 Traveling Salesman Problem Revisited
5.5 Exercises
6. Matching
6.1 Bipartite Graphs
6.2 Matching Terminology and Strategies
6.3 Stable Matching
6.4 Matchings in Non-Bipartite Graphs
6.5 Exercises
7. Graph Coloring
7.1 Four Color Theorem
7.2 Coloring Bounds
7.3 Coloring Strategies
7.4 Perfect Graphs
7.5 Weighted Coloring
7.6 Exercises
8. Additional Topics in Graph Structure
8.1 Graph Isomorphism
8.2 Rooted Trees
8.3 Planarity
8.4 Edge-Coloring
8.5 Exercises
Appendix
A Set Theory
B Functions
C Matrix Operations
Selected Answers and Solutions
Biography
Karin R. Saoub is the M. Paul Capp and Constance Whitehead Professor of Mathematics and Dean of the School of Health, Science, and Sustainability at Roanoke College, Salem, VA. She earned her PhD in mathematics from Arizona State University and a BA from Wellesley College. Her research focuses on graph coloring and online algorithms applied to tolerance graphs. She is also the author of Graph Theory: An Introduction to Proofs, Algorithms, and Applications, published by CRC Press.
