| |
| |
| Preface | |
| |
| |
| |
| Introduction to Graph Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Why Study Graphs? | |
| |
| |
| |
| Mathematical Preliminaries | |
| |
| |
| |
| The Definition of a Graph | |
| |
| |
| |
| Examples of Common Graphs | |
| |
| |
| |
| Degrees and Regular Graphs | |
| |
| |
| |
| Subgraphs | |
| |
| |
| |
| The Definition of a Directed Graph | |
| |
| |
| |
| Indegrees and Outdegrees in a Digraph | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Basic Concepts in Graph Theory | |
| |
| |
| |
| Paths and Cycles | |
| |
| |
| |
| Connectivity | |
| |
| |
| |
| Homomorphisms and Isomorphisms of Graphs | |
| |
| |
| |
| More on Isomorphisms on Simple Graphs | |
| |
| |
| |
| Formations and Minors of Graphs | |
| |
| |
| |
| Homomorphisms and Isomorphisms for Digraphs | |
| |
| |
| |
| Digraph Connectivity | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Trees and Forests | |
| |
| |
| |
| Trees and Some of Their Basic Properties | |
| |
| |
| |
| Characterizations of Trees | |
| |
| |
| |
| Inductive Proofs on Trees | |
| |
| |
| |
| Erdos-Szekeres Theorem on Sequences | |
| |
| |
| |
| Centers in Trees | |
| |
| |
| |
| Rooted Trees | |
| |
| |
| |
| Binary Trees | |
| |
| |
| |
| Levels in Rooted and Binary Trees | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Spanning Trees | |
| |
| |
| |
| Spanning Trees and Forests | |
| |
| |
| |
| Spanning Trees of the Complete Graph | |
| |
| |
| |
| The Adjacency Matrix of a Graph | |
| |
| |
| |
| The Incidence Matrix of a Graph | |
| |
| |
| |
| The Matrix-Tree Theorem | |
| |
| |
| |
| An Application to Electrical Networks | |
| |
| |
| |
| Minimum Cost Spanning Trees | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Fundamental Properties of Graphs and Digraphs | |
| |
| |
| |
| Bipartite Graphs | |
| |
| |
| |
| Eulerian Graphs | |
| |
| |
| |
| Hamiltonian Graphs | |
| |
| |
| |
| Hamiltonian Cycles in Weighted Graphs | |
| |
| |
| |
| Eulerian and Hamiltonian Digraphs | |
| |
| |
| |
| Tournament Digraphs | |
| |
| |
| |
| On the Adjacency Matrix of a Digraph | |
| |
| |
| |
| Acyclic Digraphs and Posets | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Connectivity and Flow | |
| |
| |
| |
| Edge Cuts | |
| |
| |
| |
| Edge Connectivity and Connectivity | |
| |
| |
| |
| Blocks in Separable Graphs | |
| |
| |
| |
| Flows in Networks | |
| |
| |
| |
| The Theorems of Menger | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Planar Graphs | |
| |
| |
| |
| Embeddings in Surfaces | |
| |
| |
| |
| More on Planar Embeddings | |
| |
| |
| |
| Euler's Formula and Consequences | |
| |
| |
| |
| Characterization of Planar Graphs | |
| |
| |
| |
| Kuratowski and Wagner's Theorem | |
| |
| |
| |
| Plane Duality | |
| |
| |
| |
| Higher Genus | |
| |
| |
| |
| Generalization of Euler's Formula | |
| |
| |
| |
| Crossing Number | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Graph Coloring | |
| |
| |
| |
| The Chromatic Number of a Graph | |
| |
| |
| |
| Multipartite Graphs | |
| |
| |
| |
| Results for General Graphs | |
| |
| |
| |
| Planar Graphs and Other Surface Graphs | |
| |
| |
| |
| Edge Coloring of a Graph | |
| |
| |
| |
| Tait's Theorem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Coloring Enumerations and Chordal Graphs | |
| |
| |
| |
| The Chromatic Polynomial of a Graph | |
| |
| |
| |
| Basic Properties of the Chromatic Polynomial | |
| |
| |
| |
| Interval and Intersection Graphs | |
| |
| |
| |
| Chordal Graphs | |
| |
| |
| |
| Powers of Graphs | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Independence, Dominance, and Matchings | |
| |
| |
| |
| Independence of Vertices | |
| |
| |
| |
| Domination of Vertices | |
| |
| |
| |
| Matchings in a Graph | |
| |
| |
| |
| Hall's Marriage Theorem | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Cover Parameters and Matching Polynomials | |
| |
| |
| |
| Covers and Related Parameters | |
| |
| |
| |
| Rook Polynomials and Bipartite Graphs | |
| |
| |
| |
| The Matching Defect Polynomial | |
| |
| |
| |
| Matching Algorithms | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Graph Counting | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Basic Counting Results | |
| |
| |
| |
| Generating Functions | |
| |
| |
| |
| Partitions of a Finite Set | |
| |
| |
| |
| The Labeled Counting Lemma | |
| |
| |
| |
| The Exponential Formula | |
| |
| |
| |
| The Number Two and Related Graphs | |
| |
| |
| |
| Two-Regular Graphs | |
| |
| |
| |
| Two-Colorable Graphs | |
| |
| |
| |
| Even Graphs | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Graph Algorithms | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Recap of Algorithms Already Presented | |
| |
| |
| |
| Algorithm Efficiency | |
| |
| |
| |
| Breadth-First Search | |
| |
| |
| |
| Depth-First Search | |
| |
| |
| |
| Connected Components | |
| |
| |
| |
| Dijkstra's Shortest Path Algorithm | |
| |
| |
| |
| Java Source Code | |
| |
| |
| |
| Exercises | |
| |
| |
| Appendices | |
| |
| |
| |
| Greek Alphabet | |
| |
| |
| |
| Notation | |
| |
| |
| |
| Top Ten Online References | |
| |
| |
| Bibliography | |
| |
| |
| Index | |