Graph Theory : Modeling, Applications, and Algorithms

Preface ix Introduction to Graph Theory 1(30) Introduction 1(1) Why Study Graphs? 1(5) Mathematical Preliminaries 6(4) The Definition of a Graph 10(3) Examples of Common Graphs 13(2) Degrees and Regular Graphs 15(4) Subgraphs 19(2) The Definition of a Directed Graph 21(3) Indegrees and Outdegrees in a Digraph 24(2) Exercises 26(5) Basic Concepts in Graph Theory 31(35) Paths and Cycles 31(4) Connectivity 35(4) Homomorphisms and Isomorphisms of Graphs 39(6) More on Isomorphisms on Simple Graphs 45(3) Formations and Minors of Graphs 48(7) Homomorphisms and Isomorphisms for Digraphs 55(3) Digraph Connectivity 58(3) Exercises 61(5) Trees and Forests 66(32) Trees and Some of Their Basic Properties 66(4) Characterizations of Trees 70(1) Inductive Proofs on Trees 71(3) Erdos-Szekeres Theorem on Sequences 74(3) Centers in Threes 77(4) Rooted Trees 81(2) Binary Trees 83(5) Levels in Rooted and Binary Trees 88(5) Exercises 93(5) Spanning Trees 98(34) Spanning Trees and Forests 98(3) Spanning Trees of the Complete Graph 101(3) The Adjacency Matrix of a Graph 104(4) The Incidence Matrix of a Graph 108(4) The Matrix-Tree Theorem 112(5) An Application to Electrical Networks 117(4) Minimum Cost Spanning Trees 121(5) Exercises 126(6) Fundamental Properties of Graphs and Digraphs 132(28) Bipartite Graphs 132(3) Eulerian Graphs 135(4) Hamiltonian Graphs 139(5) Hamiltonian Cycles in Weighted Graphs 144(1) Eulerian and Hamiltonian Digraphs 145(2) Tournament Digraphs 147(3) On the Adjacency Matrix of a Digraph 150(2) Acyclic Digraphs and Posets 152(3) Exercises 155(5) Connectivity and Flow 160(35) Edge Cuts 160(3) Edge Connectivity and Connectivity 163(5) Blocks in Separable Graphs 168(5) Flows in Networks 173(12) The Theorems of Menger 185(5) Exercises 190(5) Planar Graphs 195(37) Embeddings in Surfaces 195(4) More on Planar Embeddings 199(2) Euler's Formula and Consequences 201(4) Characterization of Planar Graphs 205(5) Kuratowski and Wagner's Theorem 210(4) Plane Duality 214(6) Higher Genus 220(4) Generalization of Euler's Formula 224(3) Crossing Number 227(1) Exercises 228(4) Graph Coloring 232(35) The Chromatic Number of a Graph 232(4) Multipartite Graphs 236(5) Results for General Graphs 241(4) Planar Graphs and Other Surface Graphs 245(7) Edge Coloring of a Graph 252(5) Tait's Theorem 257(2) Exercises 259(8) Coloring Enumerations and Chordal Graphs 267(32) The Chromatic Polynomial of a Graph 267(5) Basic Properties of the Chromatic Polynomial 272(3) Interval and Intersection Graphs 275(9) Chordal Graphs 284(6) Powers of Graphs 290(6) Exercises 296(3) Independence, Dominance, and Matchings 299(28) Independence of Vertices 299(6) Domination of Vertices 305(7) Matchings in a Graph 312(6) Hall's Marriage Theorem 318(5) Exercises 323(4) Cover Parameters and Matching Polynomials 327(29) Covers and Related Parameters 327(6) Rook Polynomials and Bipartite Graphs 333(7) The Matching Defect Polynomial 340(3) Matching Algorithms 343(8) Exercises 351(5) Graph Counting 356(36) Introduction 356(2) Basic Counting Results 358(7) Generating Functions 365(6) Partitions of a Finite Set 371(3) The Labeled Counting Lemma 374(4) The Exponential Formula 378(3) The Number Two and Related Graphs 381(5) Two-Regular Graphs 381(1) Two-Colorable Graphs 382(2) Even Graphs 384(2) Exercises 386(6) Graph Algorithms 392(39) Introduction 392(1) Recap of Algorithms Already Presented 393(1) Algorithm Efficiency 394(2) Breadth-First Search 396(4) Depth-First Search 400(3) Connected Components 403(4) Dijkstra's Shortest Path Algorithm 407(4) Java Source Code 411(5) Exercises 416(5) APPENDICES A. Greek Alphabet 421(2) B. Notation 423(6) C. Top Ten Online References 429(2) Bibliography 431(4) Index 435