Book description
With 34 new contributors, this best-selling handbook provides comprehensive coverage of the main topics in pure and applied graph theory. This second edition incorporates 14 new sections. Each chapter includes lists of essential definitions and facts, accompanied by examples, tables, remarks, and, in some cases, conjectures and open problems.
Table of contents
- Preliminaries
- Discrete Mathematics and its Applications
- Dedication
- Preface
- About the Editors
- Contributors
-
Chapter 1 Introduction to Graphs
- Section 1.1 Fundamentals of Graph Theory
- References
- Section 1.2 Families of Graphs and Digraphs
- References
- Section 1.3 History of Graph Theory
- References
- Glossary for Chapter 1
-
- Figure 1.1.1
- Figure 1.1.2
- Figure 1.1.3
- Figure 1.1.4
- Figure 1.1.5
- Figure 1.1.6
- Figure 1.1.7
- Figure 1.1.8
- Figure 1.1.9
- Figure 1.1.10
- Figure 1.1.11
- Figure 1.1.12
- Figure 1.1.13
- Figure 1.1.14
- Figure 1.1.15
- Figure 1.1.16
- Figure 1.1.17
- Figure 1.1.18
- Figure 1.1.19
- Figure 1.1.20
- Figure 1.1.21
- Figure 1.1.22
- Figure 1.2.1
- Figure 1.2.2
- Figure 1.2.3
- Figure 1.2.4
- Figure 1.2.5
- Figure 1.2.6
- Figure 1.2.7
- Figure 1.2.8
- Figure 1.2.9
- Figure 1.2.10
- Figure 1.3.1
- Figure 1.3.2
- Figure 1.3.3
- Figure 1.3.4
- Figure 1.3.5
- Figure 1.3.6
- Figure 1.3.7
- Figure 1.3.8
- Figure 1.3.9
- Figure 1.3.10
- Figure 1.3.11
- Figure 1.3.12
- Figure 1.3.13
-
Chapter 2 Graph Representation
- Section 2.1 Computer Representations of Graphs
- References
- Section 2.2 Graph Isomorphism
- References
- Section 2.3 The Reconstruction Problem
- References
- Section 2.4 Recursively Constructed Graphs
- References
-
Section 2.5 Structural Graph Theory
- 2.5.1 Perfect Graphs
- 2.5.2 Other Decomposition Theorems
- 2.5.3 Structure Theorems
- 2.5.4 Trigraphs
- 2.5.5 Recognition Algorithms
- 2.5.6 Erdős-Hajnal Conjecture and χ-Boundedness
- 2.5.7 Well-Quasi-Ordering and Rao's Conjecture
- 2.5.8 Tournament Immersion
- 2.5.9 Topological Containment in Tournaments
- 2.5.10 Disjoint Paths Problems in Tournaments
- 2.5.11 Acknowledgment
- References
- Glossary for Chapter 2
-
- Figure 2.1.1
- Figure 2.2.1
- Figure 2.2.2
- Figure 2.2.3
- Figure 2.2.4
- Figure 2.3.1
- Figure 2.4.1
- Figure 2.4.2
- Figure 2.4.3
- Figure 2.4.4
- Figure 2.4.5
- Figure 2.4.6
- Figure 2.4.7
- Figure 2.4.8
- Figure 2.4.9
- Figure 2.4.10
- Figure 2.4.11
- Figure 2.4.12
- Figure 2.4.13
- Figure 2.4.14
- Figure 2.4.15
- Figure 2.4.16
- Figure 2.4.17
- Figure 2.5.1
-
Chapter 3 Directed Graphs
-
Section 3.1 Basic Digraph Models and Properties
- 3.1.1 Terminology and Basic Facts
-
3.1.2 A Sampler of Digraph Models
- Markov Chains and Markov Digraphs
- Equipment-Replacement Policy
- The Digraph of a Relation and the Transitive Closure
- Constructing the Transitive Closure of a Digraph: Algorithm
- Activity-Scheduling Networks
- Scheduling the Matches in a Round-Robin Tournament
- Flows in Networks
- Software Testing and the Chinese Postman Problem
- Lexical Scanners
- 3.1.3 Binary Trees
- References
- Section 3.2 Directed Acyclic Graphs
- References
- Section 3.3 Tournaments
- References
- Glossary for Chapter 3
-
- Figure 3.1.1
- Figure 3.1.2
- Figure 3.1.3
- Figure 3.1.4
- Figure 3.1.5
- Figure 3.1.6
- Figure 3.1.7
- Figure 3.1.8
- Figure 3.1.9
- Figure 3.1.10
- Figure 3.1.11
- Figure 3.1.12
- Figure 3.2.1
- Figure 3.2.2
- Figure 3.2.3
- Figure 3.2.4
- Figure 3.2.5
- Figure 3.2.6
- Figure 3.2.7
- Figure 3.2.8
- Figure 3.2.9
- Figure 3.2.10
- Figure 3.2.11
- Figure 3.2.12
- Figure 3.2.13
- Figure 3.2.14
- Figure 3.3.1
- Figure 3.3.2
- Figure 3.3.3
- Figure 3.3.4
- Figure 3.3.5
- Figure 3.3.6
- Figure 3.3.7
- Figure 3.3.8
- Figure 3.3.9
- Figure 3.3.10
-
Section 3.1 Basic Digraph Models and Properties
-
Chapter 4 Connectivity and Traversability
- Section 4.1 Connectivity: Properties and Structure
- References
- Section 4.2 Eulerian Graphs
- References
- Section 4.3 Chinese Postman Problems
- References
- Section 4.4 DeBruijn Graphs and Sequences
- References
- Section 4.5 Hamiltonian Graphs
- References
- Section 4.6 Traveling Salesman Problems
- References
- Section 4.7 Further Topics in Connectivity
- References
- Glossary for Chapter 4
-
- Figure 4.1.1
- Figure 4.1.2
- Figure 4.2.1
- Figure 4.2.2
- Figure 4.2.3
- Figure 4.2.4
- Figure 4.2.5
- Figure 4.2.6
- Figure 4.2.7
- Figure 4.2.8
- Figure 4.2.9
- Figure 4.2.10
- Figure 4.3.1
- Figure 4.3.2
- Figure 4.3.3
- Figure 4.3.4
- Figure 4.3.5
- Figure 4.3.6
- Figure 4.3.7
- Figure 4.3.8
- Figure 4.3.9
- Figure 4.4.1
- Figure 4.4.2
- Figure 4.4.3
- Figure 4.5.1
- Figure 4.5.2
- Figure 4.5.3
- Figure 4.6.1
- Figure 4.6.2
- Figure 4.6.3
- Figure 4.6.4
- Figure 4.6.5
- Figure 4.6.6
- Figure 4.7.1
- Figure 4.7.2
- Figure 4.7.3
- Figure 4.7.4
- Figure 4.7.5
- Figure 4.7.6
-
Chapter 5 Colorings and Related Topics
- Section 5.1 Graph Coloring
- References
- Section 5.2 Further Topics in Graph Coloring
- References
- Section 5.3 Independence and Cliques
- References
- Section 5.4 Factors and Factorization
- References
-
Section 5.5 Applications to Timetabling
- 5.5.1 Specification of Timetabling Problems
- 5.5.2 Class-Teacher Timetabling
- 5.5.3 University Course Timetabling
- 5.5.4 University Examination Timetabling
-
5.5.5 Sports Timetabling
- A Simple Graph Model
- Profiles, Breaks, and Home-Away Patterns of a Schedule
- A Lower Bound on the Number of Breaks
- Irreducible and Compact Schedules
- Complementarity
- Constructing a Compact Schedule with a Minimum Number of Breaks
- An Alternate View of the Canonical Factorization
- Some Characterization Results
- Feasible Sequences
- References
- Section 5.6 Graceful Labelings
- References
- Glossary for Chapter 5
-
Chapter 6 Algebraic Graph Theory
- Section 6.1 Automorphisms
- References
- Section 6.2 Cayley Graphs
- References
- Section 6.3 Enumeration
- References
-
Section 6.4 Graphs and Vector Spaces
- 6.4.1 Basic Concepts and Definitions
- 6.4.2 Circuit Subspace of an Undirected Graph
- 6.4.3 Cutset Subspace of an Undirected Graph
- 6.4.4 Relationship between Circuit and Cutset Subspaces
- 6.4.5 Circuit and Cutset Spaces in a Directed Graph
- 6.4.6 Two Circ/Cut-Based Tripartitions of a Graph
- 6.4.7 Realization of Circuit and Cutset Spaces
- 6.4.8 An Application: Cross-Layer Survivability in a Layered Network
- References
- Section 6.5 Spectral Graph Theory
- References
-
Section 6.6 Matroidal Methods in Graph Theory
- 6.6.1 Matroids: Basic Definitions and Examples
- 6.6.2 Alternative Axiom Systems
- 6.6.3 The Greedy Algorithm
- 6.6.4 Duality
- 6.6.5 Matroid Union and Its Consequences
- 6.6.6 Fundamental Operations
- 6.6.7 Connectedness, 2- and 3-Connectedness for Graphs and Matroids
- 6.6.8 Graphs and Totally Unimodular Matrices
- 6.6.9 Excluded-Minor Characterizations
- 6.6.10 Wheels, Whirls, and the Splitter Theorem
- 6.6.11 Removable Circuits
- 6.6.12 Minimally k-connected Graphs and Matroids
- 6.6.13 Conclusion
- References
- Glossary for Chapter 6
-
- Figure 6.1.1
- Figure 6.1.2
- Figure 6.2.1
- Figure 6.2.2
- Figure 6.3.1
- Figure 6.3.2
- Figure 6.3.3
- Figure 6.3.4
- Figure 6.3.5
- Figure 6.3.6
- Figure 6.3.7
- Figure 6.3.8
- Figure 6.3.9
- Figure 6.4.1
- Figure 6.4.2
- Figure 6.4.3
- Figure 6.4.4
- Figure 6.4.5
- Figure 6.4.6
- Figure 6.4.7
- Figure 6.4.8
- Figure 6.4.9
- Figure 6.4.10
- Figure 6.4.11
- Figure 6.5.1
- Figure 6.5.2
- Figure 6.5.3
- Figure 6.5.4
- Figure 6.5.5
- Figure 6.5.6
- Figure 6.6.1
- Figure 6.6.2
- Figure 6.6.3
- Figure 6.6.4
- Figure 6.6.5
- Figure 6.6.6
- Figure 6.6.7
- Figure 6.6.8
-
Chapter 7 Topological Graph Theory
- Section 7.1 Graphs on Surfaces
- References
- Section 7.2 Minimum Genus and Maximum Genus
- References
-
Section 7.3 Genus Distributions
- 7.3.1 Ranges and Distributions of Imbeddings
- 7.3.2 Counting Noncellular Imbeddings
- 7.3.3 Partitioned Genus Distributions
- 7.3.4 Graph Amalgamations
- 7.3.5 Genus Distribution Formulas for Special Classes
- 7.3.6 Other Imbedding Distribution Calculations
- 7.3.7 The Unimodality Problem
- 7.3.8 Average Genus
- 7.3.9 Stratification of Imbeddings
- References
-
Section 7.4 Voltage Graphs
- 7.4.1 Regular Voltage Graphs
- 7.4.2 Local Group and Natural Automorphisms
- 7.4.3 Permutation Voltage Graphs
- 7.4.4 Representing Coverings with Voltage Graphs
- 7.4.5 The Kirchhoff Voltage Law
- 7.4.6 Imbedded Voltage Graphs
- 7.4.7 Topological Current Graphs
- 7.4.8 Lifting Voltage Graph Mappings
- 7.4.9 Applications of Voltage Graphs
- References
- Section 7.5 The Genus of a Group
- References
- Section 7.6 Maps
- References
- Section 7.7 Representativity
- References
- Section 7.8 Triangulations
- References
- Section 7.9 Graphs and Finite Geometries
- References
-
Section 7.10 Crossing Numbers
- 7.10.1 Drawings of Graphs and Crossing Numbers
- 7.10.2 General Techniques and Bounds
- 7.10.3 Crossing Numbers of Some Families of Graphs
- 7.10.4 Crossing-Critical Graphs
- 7.10.5 Algorithmical Aspects
- 7.10.6 Other Definitions of Crossing Number
- 7.10.7 Crossing Sequences
- 7.10.8 Applications of Crossing Numbers
- 7.10.9 Suggestions for Further Reading
- References
- Glossary for Chapter 7
-
- Figure 7.1.1
- Figure 7.1.2
- Figure 7.1.3
- Figure 7.1.4
- Figure 7.1.5
- Figure 7.1.6
- Figure 7.1.7
- Figure 7.1.8
- Figure 7.1.9
- Figure 7.1.10
- Figure 7.1.11
- Figure 7.1.12
- Figure 7.1.13
- Figure 7.2.1
- Figure 7.2.2
- Figure 7.2.3
- Figure 7.3.1
- Figure 7.3.2
- Figure 7.3.3
- Figure 7.3.4
- Figure 7.3.5
- Figure 7.3.6
- Figure 7.3.7
- Figure 7.3.8
- Figure 7.3.9
- Figure 7.3.10
- Figure 7.3.11
- Figure 7.3.12
- Figure 7.3.13
- Figure 7.3.14
- Figure 7.3.15
- Figure 7.3.16
- Figure 7.4.1
- Figure 7.4.2
- Figure 7.4.3
- Figure 7.4.4
- Figure 7.4.5
- Figure 7.4.6
- Figure 7.4.7
- Figure 7.4.8
- Figure 7.6.1
- Figure 7.6.2
- Figure 7.6.3
- Figure 7.6.4
- Figure 7.6.5
- Figure 7.6.6
- Figure 7.6.7
- Figure 7.6.8
- Figure 7.6.9
- Figure 7.6.10
- Figure 7.6.11
- Figure 7.6.12
- Figure 7.6.13
- Figure 7.6.14
- Figure 7.6.15
- Figure 7.6.16
- Figure 7.6.17
- Figure 7.6.18
- Figure 7.6.19
- Figure 7.7.1
- Figure 7.7.2
- Figure 7.7.3
- Figure 7.8.1
- Figure 7.8.2
- Figure 7.8.3
- Figure 7.8.4
- Figure 7.8.5
- Figure 7.8.6
- Figure 7.8.7
- Figure 7.8.8
- Figure 7.8.9
- Figure 7.8.10
- Figure 7.8.11
- Figure 7.8.12
- Figure 7.8.13
- Figure 7.9.1
- Figure 7.9.2
- Figure 7.9.3
- Figure 7.9.4
- Figure 7.9.5
- Figure 7.10.1
- Figure 7.10.2
- Figure 7.10.3
-
Chapter 8 Analytic Graph Theory
-
Section 8.1 Extremal Graph Theory
- 8.1.1 Turán-Type Problems
- 8.1.2 The Number of Complete Graphs
- 8.1.3 Erdős–Stone Theorem and Its Extensions
- 8.1.4 Zarankiewicz Problem and Related Questions
- 8.1.5 Paths and Trees
- 8.1.6 Circumference
- 8.1.7 Hamiltonian Cycles
- 8.1.8 Cycle Lengths
- 8.1.9 Szemerédi's Uniformity Lemma
- 8.1.10 Asymptotic Enumeration
- 8.1.11 Graph Minors
- 8.1.12 Ramsey–Turán Problems
- References
- Section 8.2 Random Graphs
- References
- Section 8.3 Ramsey Graph Theory
- References
- Section 8.4 The Probabilistic Method
- References
-
Section 8.5 Graph Limits
- 8.5.1 Graphs, Weighted Graphs, and Graphons
- 8.5.2 Homomorphism Density
- 8.5.3 Convergent Sequences of Graphs and Graphons
- 8.5.4 Metric Space Topology on Graphs and Graphons
- 8.5.5 Regularity Lemma and Approximation of Graphons by Weighted Graphs
- 8.5.6 W-Random Graphs
- 8.5.7 Graph Parameters and Connection Matrices
- 8.5.8 Extremal Graph Theory and the Algebra of Quantum Graphs
- References
- Glossary for Chapter 8
-
Section 8.1 Extremal Graph Theory
-
Chapter 9 Graphical Measurement
- Section 9.1 Distance in Graphs
- References
- Section 9.2 Domination in Graphs
- References
- Section 9.3 Tolerance Graphs
- References
- Section 9.4 Bandwidth
- References
- Section 9.5 Pursuit-Evasion Problems
- References
- Glossary for Chapter 9
-
- Figure 9.1.1
- Figure 9.1.2
- Figure 9.1.3
- Figure 9.1.4
- Figure 9.1.5
- Figure 9.1.6
- Figure 9.1.7
- Figure 9.1.8
- Figure 9.1.9
- Figure 9.1.10
- Figure 9.1.11
- Figure 9.1.12
- Figure 9.1.13
- Figure 9.1.14
- Figure 9.1.15
- Figure 9.1.16
- Figure 9.1.17
- Figure 9.2.1
- Figure 9.2.2
- Figure 9.2.3
- Figure 9.2.4
- Figure 9.2.5
- Figure 9.2.6
- Figure 9.2.7
- Figure 9.2.8
- Figure 9.2.9
- Figure 9.2.10
- Figure 9.2.11
- Figure 9.2.12
- Figure 9.4.1
- Figure 9.4.2
- Figure 9.4.3
- Figure 9.4.4
- Figure 9.4.5
- Figure 9.4.6
- Figure 9.4.7
- Figure 9.4.8
- Figure 9.4.9
- Figure 9.4.10
- Figure 9.5.1
- Figure 9.5.2
- Figure 9.5.3
- Figure 9.5.4
- Figure 9.5.5
- Figure 9.5.6
- Figure 9.5.7
- Figure 9.5.8
-
Chapter 10 Graphs in Computer Science
- Section 10.1 Searching
- References
-
Section 10.2 Dynamic Graph Algorithms
- 10.2.1 Basic Terminology
- 10.2.2 Dynamic Problems on Undirected Graphs
-
10.2.3 Dynamic Problems on Directed Graphs
- General Techniques for Directed Graphs
- Path Problems and Kleene Closures
- Locally Shortest Paths
- Long Paths Property
- Reachability Trees
- Matrix Data Structures
- Dynamic Transitive Closure
- King's O(n2 log n) Update Algorithm
- Demetrescu and Italiano's O(n2) Update Algorithm
- Dynamic Shortest Paths
- King's On2.5 C log n Update Algorithm
- Demetrescu and Italiano's O(n2 log3 n) Update Algorithm
- 10.2.4 Research Issues
- References
-
Section 10.3 Drawings of Graphs
- 10.3.1 Types of Graphs and Drawings
- 10.3.2 Combinatorics of Some Geometric Graphs
- 10.3.3 Properties of Drawings and Bounds
- 10.3.4 Complexity of Graph Drawing Problems
- 10.3.5 Example of a Graph Drawing Algorithm
- 10.3.6 Techniques for Drawing Graphs
- 10.3.7 Selected Topics
- 10.3.8 Sources and Related Material
- References
- Section 10.4 Algorithms on Recursively Constructed Graphs
- References
-
Section 10.5 Fuzzy Graphs
- 10.5.1 Definitions and Basic Properties
- 10.5.2 Paths and Connectedness
- 10.5.3 Forests and Trees
- 10.5.4 Fuzzy Cut Sets
- 10.5.5 Fuzzy 1-Chain with Boundary 0, Fuzzy Coboundary, and Fuzzy Cocycles
- 10.5.6 Fuzzy Line Graphs
- 10.5.7 Fuzzy Interval Graphs
- 10.5.8 Operations on Fuzzy Graphs
- 10.5.9 Clusters
- 10.5.10 Application to Cluster Analysis
- 10.5.11 Fuzzy Graphs in Database Theory
- 10.5.12 Strengthening and Weakening Members of a Group
- 10.5.13 Network Analysis of Fuzzy Graphs
- 10.5.14 Intuitionistic Fuzzy Graphs and Group Decision-Making
- References
- Section 10.6 Expander Graphs
- References
- Section 10.7 Visibility Graphs
- References
- Glossary for Chapter 10
-
- Figure 10.1.1
- Figure 10.1.2
- Figure 10.1.3
- Figure 10.1.4
- Figure 10.1.5
- Figure 10.1.6
- Figure 10.1.7
- Figure 10.1.8
- Figure 10.1.9
- Figure 10.1.10
- Figure 10.1.11
- Figure 10.1.12
- Figure 10.1.13
- Figure 10.1.14
- Figure 10.1.15
- Figure 10.1.16
- Figure 10.1.17
- Figure 10.1.18
- Figure 10.1.19
- Figure 10.1.20
- Figure 10.1.21
- Figure 10.1.22
- Figure 10.1.23
- Figure 10.1.24
- Figure 10.2.1
- Figure 10.2.2
- Figure 10.2.3
- Figure 10.2.4
- Figure 10.3.1
- Figure 10.3.2
- Figure 10.3.3
- Figure 10.4.1
- Figure 10.4.2
- Figure 10.4.3
- Figure 10.4.4
- Figure 10.4.5
- Figure 10.4.6
- Figure 10.6.1
- Figure 10.6.2
- Figure 10.7.1
- Figure 10.7.2
- Figure 10.7.3
- Figure 10.7.4
- Figure 10.7.5
- Figure 10.7.6
- Figure 10.7.7
- Figure 10.7.8
-
Chapter 11 Networks and Flows
- Section 11.1 Maximum Flows
- References
- Section 11.2 Minimum Cost Flows
- References
- Section 11.3 Matchings and Assignments
- References
- Section 11.4 Graph Pebbling
- References
- Glossary for Chapter 11
-
- Figure 11.1.1
- Figure 11.1.2
- Figure 11.1.3
- Figure 11.1.4
- Figure 11.1.5
- Figure 11.1.6
- Figure 11.1.7
- Figure 11.2.1
- Figure 11.2.2
- Figure 11.2.3
- Figure 11.2.4
- Figure 11.3.1
- Figure 11.3.2
- Figure 11.3.3
- Figure 11.3.4
- Figure 11.3.5
- Figure 11.3.6
- Figure 11.3.7
- Figure 11.3.8
- Figure 11.3.9
- Figure 11.3.10
- Figure 11.3.11
- Figure 11.3.12
- Figure 11.4.1
- Figure 11.4.2
- Figure 11.4.3
- Figure 11.4.4
- Figure 11.4.5
- Figure 11.4.6
- Figure 11.4.7
- Figure 11.4.8
- Figure 11.4.9
-
Chapter 12 Communication Networks
-
Section 12.1 Complex Networks
- 12.1.1 Examples of Complex Networks
- 12.1.2 Properties of Complex Networks
- 12.1.3 Random Graphs with General Degree Distributions
- 12.1.4 On-Line Models of Complex Networks
- 12.1.5 Geometric Models for Complex Networks
- 12.1.6 Percolation in a General Host Graph
- 12.1.7 PageRank for Ranking Nodes
- 12.1.8 Network Games
- References
- Section 12.2 Broadcasting and Gossiping
- References
- Section 12.3 Communication Network Design Models 1495
- References
- Section 12.4 Network Science for Graph Theorists
- References
- Glossary for Chapter 12
-
Section 12.1 Complex Networks
- Chapter 13 Natural Science & Processes
Product information
- Title: Handbook of Graph Theory, 2nd Edition
- Author(s):
- Release date: December 2013
- Publisher(s): Chapman and Hall/CRC
- ISBN: 9781498761369
You might also like
book
Algorithmic Graph Theory and Perfect Graphs, 2nd Edition
Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to …
book
Essentials of Discrete Mathematics, 3rd Edition
Written for the one-term course, the Third Edition of Essentials of Discrete Mathematics is designed to …
book
Handbook of Data Structures and Applications, 2nd Edition
This book provides a comprehensive survey of data structures of various types. The second edition has …
book
Guide to Essential Math, 2nd Edition
This book reminds students in junior, senior and graduate level courses in physics, chemistry and engineering …