Graphs & Digraphs, Fourth EditionWith a growing range of applications in fields from computer science to chemistry and communications networks, graph theory has enjoyed a rapid increase of interest and widespread recognition as an important area of mathematics. Through more than 20 years of publication, Graphs & Digraphs has remained a popular point of entry to the field, and through its various editions, has evolved with the field from a purely mathematical treatment to one that also addresses the mathematical needs of computer scientists. Carefully updated, streamlined, and enhanced with new features, Graphs & Digraphs, Fourth Edition reflects many of the developments in graph theory that have emerged in recent years. The authors have added discussions on topics of increasing interest, deleted outdated material, and judiciously augmented the Exercises sections to cover a range of problems that reach beyond the construction of proofs. New in the Fourth Edition: Every edition of Graphs & Digraphs has been unique in its reflection the subject as one that is important, intriguing, and most of all beautiful. The fourth edition continues that tradition, offering a comprehensive, tightly integrated, and up-to-date introduction that imparts an appreciation as well as a solid understanding of the material. |
Contents
The structure of graphs | 33 |
Trees and connectivity | 55 |
Eulerian and hamiltonian graphs and digraphs | 85 |
Directed graphs | 111 |
Planar graphs | 127 |
Graph embeddings | 161 |
Graph colorings | 193 |
Matchings factors and decompositions | 233 |
Domination in graphs | 273 |
Extremal graph theory | 293 |
Ramsey theory | 317 |
The probabilistic method in graph theory | 333 |
Glossary of symbols | 347 |
| 359 | |
| 379 | |
Common terms and phrases
1-factor 2-cell embedding 2-connected adjacent Assume automorphism B₁(G bipartite graph chordal graph chromatic number complete graph components conjecture connected graph Corollary cubic graph D₁ define denote digraph dominating set domination number edges of G embedding of G eulerian graph follows G contains G of Figure G of order genus graph G graph of order Graph Theory H₁ hamiltonian cycle hamiltonian graphs hamiltonian path Hence implies incident independent set induced subgraph integer internally disjoint isolated vertices isomorphic Let G Math minimum number Moore graph multigraph nonadjacent vertices nonplanar number of edges number of vertices orbits Petersen graph planar graph plane positive integer Proof Let proof of Theorem Prove r-regular graph R₁ Ramsey number result S₁ score sequence set of G set of vertices Show shown in Figure subgraph of G subset tree of order u-v path u₁ v₁ vertex set vertices of G w₁ w₂