Handbook of Graph Theory, 2nd Edition

Handbook of Graph Theory, 2nd Edition

by Jonathan L. Gross, Jay Yellen, Ping Zhang
Released December 2013
Publisher(s): Chapman and Hall/CRC
ISBN: 9781498761369

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

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

  1. Preliminaries
  2. Discrete Mathematics and its Applications
  3. Dedication
  4. Preface
    1. Format
    2. Terminology and Notation
    3. Acknowledgments
  5. About the Editors
  6. Contributors
  7. Chapter 1 Introduction to Graphs
    1. Section 1.1 Fundamentals of Graph Theory
      1. 1.1.1 Graphs and Digraphs
        1. Basic Terminology
        2. Simple Graphs
        3. Edge Notation for Simple Adjacencies and for Multi-Edges
        4. General Graphs
        5. Attributes
        6. Digraphs
        7. Ordered-Pair Representation of Arcs
        8. Vertex-Coloring
      2. 1.1.2 Degree and Distance
        1. Degree
        2. Walks, Trails, and Paths
        3. Distance and Connectivity
      3. 1.1.3 Basic Structural Concepts
        1. Isomorphism
        2. Automorphisms
        3. Subgraphs
        4. Graph Operations
      4. 1.1.4 Trees
        1. Acyclic Graphs
        2. Trees as Subgraphs
        3. Basic Tree-Growing Algorithm
        4. Prioritizing the Edge Selection
    2. References
    3. Section 1.2 Families of Graphs and Digraphs
      1. 1.2.1 Building Blocks
      2. 1.2.2 Symmetry
        1. Local Symmetry: Regularity
        2. Global Symmetry: Vertex-Transitivity
      3. 1.2.3 Integer-Valued Invariants
        1. Cycle Rank
        2. Chromatic Number and k-Partite Graphs
        3. K-Connectivity and K-Edge-Connectivity
        4. Minimum Genus
      4. 1.2.4 Criterion Qualification
    4. References
    5. Section 1.3 History of Graph Theory
      1. 1.3.1 Traversability
        1. The Königsberg Bridges Problem
        2. Diagram-Tracing Puzzles
        3. Hamiltonian Graphs
      2. 1.3.2 Trees
        1. Counting Trees
        2. Chemical Trees
      3. 1.3.3 Topological Graphs
        1. Euler's Polyhedron Formula
        2. Planar Graphs
        3. Graphs on Higher Surfaces
      4. 1.3.4 Graph Colorings
        1. The Four-Color Problem
        2. Other Graph Coloring Problems
        3. Factorization
      5. 1.3.5 Graph Algorithms
    6. References
    7. Glossary for Chapter 1
      1. Figure 1.1.1
      2. Figure 1.1.2
      3. Figure 1.1.3
      4. Figure 1.1.4
      5. Figure 1.1.5
      6. Figure 1.1.6
      7. Figure 1.1.7
      8. Figure 1.1.8
      9. Figure 1.1.9
      10. Figure 1.1.10
      11. Figure 1.1.11
      12. Figure 1.1.12
      13. Figure 1.1.13
      14. Figure 1.1.14
      15. Figure 1.1.15
      16. Figure 1.1.16
      17. Figure 1.1.17
      18. Figure 1.1.18
      19. Figure 1.1.19
      20. Figure 1.1.20
      21. Figure 1.1.21
      22. Figure 1.1.22
      23. Figure 1.2.1
      24. Figure 1.2.2
      25. Figure 1.2.3
      26. Figure 1.2.4
      27. Figure 1.2.5
      28. Figure 1.2.6
      29. Figure 1.2.7
      30. Figure 1.2.8
      31. Figure 1.2.9
      32. Figure 1.2.10
      33. Figure 1.3.1
      34. Figure 1.3.2
      35. Figure 1.3.3
      36. Figure 1.3.4
      37. Figure 1.3.5
      38. Figure 1.3.6
      39. Figure 1.3.7
      40. Figure 1.3.8
      41. Figure 1.3.9
      42. Figure 1.3.10
      43. Figure 1.3.11
      44. Figure 1.3.12
      45. Figure 1.3.13
  8. Chapter 2 Graph Representation
    1. Section 2.1 Computer Representations of Graphs
      1. 2.1.1 Basic Representations for Graphs
      2. 2.1.2 Graph Traversal Algorithms
        1. Depth-First Search
        2. Breadth-First Search
      3. 2.1.3 All-Pairs Problems
        1. All-Pairs Shortest-Paths Algorithm
        2. Transitive Closure
      4. 2.1.4 Applications to Pattern Matching
        1. Kleene's Algorithm
    2. References
    3. Section 2.2 Graph Isomorphism
      1. 2.2.1 Isomorphisms and Automorphisms
        1. Basic Terminology
        2. Related Isomorphism Problems
      2. 2.2.2 Complexity Theory
      3. 2.2.3 Algorithms
        1. Search Tree
        2. Software
    4. References
    5. Section 2.3 The Reconstruction Problem
      1. 2.3.1 Two Reconstruction Conjectures
        1. Decks and Edge-Decks
        2. Reconstructibility
        3. The Reconstruction Conjecture
        4. The Edge-Reconstruction Conjecture
        5. Comparing Reconstruction with Edge-Reconstruction
        6. Reconstruction and Graph Symmetries
      2. 2.3.2 Some Reconstructible Parameters and Classes
        1. Reconstructible Parameters
        2. Reconstructible Classes
      3. 2.3.3 Reconstructing from Less than the Full Deck
        1. Endvertex-Reconstruction
        2. Reconstruction Numbers
        3. Set Reconstruction
        4. Reconstruction from the Characteristic Polynomial Deck
        5. Reconstructing from k-Vertex-Deleted Subgraphs
      4. 2.3.4 Tutte's and Kocay's Results
        1. Kocay's Parameter
        2. Characteristic and Chromatic Polynomials
      5. 2.3.5 Lovász's Method and Nash–Williams's Lemma
        1. The Nash–Williams Lemma
        2. Structures Other than Graphs
        3. The Reconstruction Index of Groups
      6. 2.3.6 Digraphs
      7. 2.3.7 Illegitimate Decks
      8. 2.3.8 Recent Results
    6. References
    7. Section 2.4 Recursively Constructed Graphs
      1. 2.4.1 Some Parameterized Families of Graph Classes
        1. Trees
        2. Series-Parallel Graphs
        3. k-Trees and Partial k-Trees
        4. Halin Graphs
        5. Bandwidth-k Graphs
        6. Treewidth-k Graphs
        7. Pathwidth-k Graphs
        8. Branchwidth-k Graphs
        9. k-Terminal Graphs
        10. Cographs
        11. Cliquewidth-k Graphs
        12. k-NLC Graphs
        13. k-HB Graphs
      2. 2.4.2 Equivalences and Characterizations
        1. Relationships between Recursive Classes
        2. Characterizations
      3. 2.4.3 Recognition
        1. Recognition of Recursive Classes
    8. References
    9. Section 2.5 Structural Graph Theory
      1. 2.5.1 Perfect Graphs
        1. ANOTHER FACT, ALSO FIRST CONJECTURED BY BERGE
        2. Outline of the Proof of the Strong Perfect Graph Theorem
      2. 2.5.2 Other Decomposition Theorems
      3. 2.5.3 Structure Theorems
        1. Claw-Free Graphs
        2. Quasi-Line Graphs
        3. Bull-Free Graphs
        4. INFORMAL DEFINITIONS
      4. 2.5.4 Trigraphs
        1. Using Trigraphs: Structure Theorems
        2. Using Trigraphs: Algorithms
      5. 2.5.5 Recognition Algorithms
        1. Testing for Pyramids: the Shortest Paths Detector
        2. Easily Detectable Configurations; Cleaning; Finding Odd Holes
        3. Testing for Even Holes
        4. More Algorithms
        5. The Three-in-a-Tree Problem
      6. 2.5.6 Erdős-Hajnal Conjecture and χ-Boundedness
        1. Tournaments
        2. χ-Boundedness
      7. 2.5.7 Well-Quasi-Ordering and Rao's Conjecture
        1. Outline of the Proof of Fact F40
      8. 2.5.8 Tournament Immersion
        1. On the Proof of Fact F46
      9. 2.5.9 Topological Containment in Tournaments
      10. 2.5.10 Disjoint Paths Problems in Tournaments
        1. The Edge-Disjoint Paths Problem
        2. The Vertex-Disjoint Paths Problem
      11. 2.5.11 Acknowledgment
    10. References
    11. Glossary for Chapter 2
      1. Figure 2.1.1
      2. Figure 2.2.1
      3. Figure 2.2.2
      4. Figure 2.2.3
      5. Figure 2.2.4
      6. Figure 2.3.1
      7. Figure 2.4.1
      8. Figure 2.4.2
      9. Figure 2.4.3
      10. Figure 2.4.4
      11. Figure 2.4.5
      12. Figure 2.4.6
      13. Figure 2.4.7
      14. Figure 2.4.8
      15. Figure 2.4.9
      16. Figure 2.4.10
      17. Figure 2.4.11
      18. Figure 2.4.12
      19. Figure 2.4.13
      20. Figure 2.4.14
      21. Figure 2.4.15
      22. Figure 2.4.16
      23. Figure 2.4.17
      24. Figure 2.5.1
  9. Chapter 3 Directed Graphs
    1. Section 3.1 Basic Digraph Models and Properties
      1. 3.1.1 Terminology and Basic Facts
        1. Reachability and Connectivity
        2. Measures of Digraph Connectivity
        3. Directed Trees
        4. Tree-Growing in a Digraph
        5. Oriented Graphs
        6. Adjacency Matrix of a Digraph
      2. 3.1.2 A Sampler of Digraph Models
        1. Markov Chains and Markov Digraphs
        2. Equipment-Replacement Policy
        3. The Digraph of a Relation and the Transitive Closure
        4. Constructing the Transitive Closure of a Digraph: Algorithm
        5. Activity-Scheduling Networks
        6. Scheduling the Matches in a Round-Robin Tournament
        7. Flows in Networks
        8. Software Testing and the Chinese Postman Problem
        9. Lexical Scanners
      3. 3.1.3 Binary Trees
        1. Rooted Tree Terminology
        2. Binary Search
    2. References
    3. Section 3.2 Directed Acyclic Graphs
      1. 3.2.1 Examples and Basic Facts
      2. 3.2.2 Rooted Trees
        1. Definitions for Rooted Trees
        2. Spanning Directed Trees
        3. Functional Graphs
      3. 3.2.3 DAGs and Posets
      4. 3.2.4 Topological Sort and Optimization
        1. Optimization
    4. References
    5. Section 3.3 Tournaments
      1. 3.3.1 Basic Definitions and Examples
        1. Regular Tournaments
        2. Arc Reversals
      2. 3.3.2 Paths, Cycles, and Connectivity
        1. Condensation and Transitive Tournaments
        2. Cycles and Paths in Tournaments
        3. Hamiltonian Cycles and Kelly’s Conjecture
        4. Higher Connectivity
        5. Anti-Directed Paths
      3. 3.3.3 Scores and Score Sequences
        1. The Second Neighborhood of a Vertex
      4. 3.3.4 Transitivity, Feedback Sets, and Consistent Arcs
        1. Smallest Feedback Sets
        2. Acyclic Subdigraphs and Transitive Sub-Tournaments
        3. Arc-Disjoint Cycles
      5. 3.3.5 Kings, Oriented Trees, and Reachability
        1. Tournaments Containing Oriented Trees
        2. Arc-Colorings and Monochromatic Paths
      6. 3.3.6 Domination
      7. 3.3.7 Tournament Matrices
      8. 3.3.8 Voting
        1. Deciding Who Won
        2. Tournaments That Are Majority Digraphs
        3. Agendas
        4. Division Trees and Sophisticated Decisions
        5. Inductively Determining the Sophisticated Decision
    6. References
    7. Glossary for Chapter 3
      1. Figure 3.1.1
      2. Figure 3.1.2
      3. Figure 3.1.3
      4. Figure 3.1.4
      5. Figure 3.1.5
      6. Figure 3.1.6
      7. Figure 3.1.7
      8. Figure 3.1.8
      9. Figure 3.1.9
      10. Figure 3.1.10
      11. Figure 3.1.11
      12. Figure 3.1.12
      13. Figure 3.2.1
      14. Figure 3.2.2
      15. Figure 3.2.3
      16. Figure 3.2.4
      17. Figure 3.2.5
      18. Figure 3.2.6
      19. Figure 3.2.7
      20. Figure 3.2.8
      21. Figure 3.2.9
      22. Figure 3.2.10
      23. Figure 3.2.11
      24. Figure 3.2.12
      25. Figure 3.2.13
      26. Figure 3.2.14
      27. Figure 3.3.1
      28. Figure 3.3.2
      29. Figure 3.3.3
      30. Figure 3.3.4
      31. Figure 3.3.5
      32. Figure 3.3.6
      33. Figure 3.3.7
      34. Figure 3.3.8
      35. Figure 3.3.9
      36. Figure 3.3.10
  10. Chapter 4 Connectivity and Traversability
    1. Section 4.1 Connectivity: Properties and Structure
      1. 4.1.1 Connectivity Parameters
        1. Preliminaries
        2. Vertex- and Edge-Connectivity
        3. Relationships Among the Parameters
        4. Some Simple Observations
        5. Internally-Disjoint Paths and Whitney's Theorem
        6. Strong Connectivity in Digraphs
        7. An Application to Interconnection Networks
      2. 4.1.2 Characterizations
        1. Menger's Theorems
        2. Other Versions and Generalizations of Menger's Theorem
        3. Another Menger-Type Theorem
        4. Whitney's Theorem
        5. Other Characterizations
      3. 4.1.3 Structural Connectivity
        1. Cycles Containing Prescribed Vertices
        2. The Lovász—Woodall Conjecture
        3. Paths with Prescribed Initial and Final Vertices
        4. Subgraphs
      4. 4.1.4 Analysis and Synthesis
        1. Contractions and Splittings
        2. Subgraph Contraction
        3. Edge Deletion
        4. Vertex Deletion
        5. Products of Graphs
        6. Minimality and Criticality
        7. Vertex-Minimal Connectivity — Criticality
        8. Connectivity Augmentation
    2. References
    3. Section 4.2 Eulerian Graphs
      1. 4.2.1 Basic Definitions and Characterizations
        1. Some Basic Characterizations
        2. Characterizations Based on Partition Cuts
      2. 4.2.2 Algorithms to Construct Eulerian Tours
        1. The Splitting and Detachment Operations
      3. 4.2.3 Eulerian-Tour Enumeration and Other Counting Problems
      4. 4.2.4 Applications to General Graphs
        1. Covering Walks and Double Tracings
        2. Maze Searching
        3. Covers, Double Covers, and Packings
        4. Three Optimization Problems
        5. Nowhere-Zero Flows
      5. 4.2.5 Various Types of Eulerian Tours and Cycle Decompositions
        1. Incidence-Partition and Transition Systems
        2. Orderings of the Incidence Set, Non-Intersecting Tours, and A-Trails
      6. 4.2.6 Transforming Eulerian Tours
        1. The Kappa Transformations
        2. Splicing the Trails in a Trail Decomposition
    4. References
    5. Section 4.3 Chinese Postman Problems
      1. 4.3.1 The Basic Problem and Its Variations
        1. The Eulerian Case
        2. Variations of CPP
      2. 4.3.2 Undirected Postman Problems
      3. 4.3.3 Directed Postman Problems
        1. Producing an Eulerian Tour in a Symmetric (Multi)Digraph
      4. 4.3.4 Mixed Postman Problems
        1. Deciding if a Mixed Graph Is Eulerian
        2. The Postman Problem for Mixed Graphs
        3. Approximation Algorithm ES
        4. Approximate Algorithm SE
        5. Some Performance Bounds
      5. 4.3.5 Recent Research
    6. References
    7. Section 4.4 DeBruijn Graphs and Sequences
      1. 4.4.1 DeBruijn Graph Basics
        1. DeBruijn Sequences
        2. DeBruijn Graphs
      2. 4.4.2 Generating deBruijn Sequences
        1. Algorithm
        2. Necklaces and Lyndon Words
      3. 4.4.3 Pseudorandom Numbers
      4. 4.4.4 A Genetics Application
    8. References
    9. Section 4.5 Hamiltonian Graphs
      1. 4.5.1 History
      2. 4.5.2 The Classic Attacks
        1. Degrees
        2. Other Counts
        3. Powers and Line Graphs
        4. Planar Graphs
      3. 4.5.3 Extending the Classics
        1. Adding Toughness
        2. More Than Hamiltonian
      4. 4.5.4 More Than One Hamiltonian Cycle
        1. A Second Hamiltonian Cycle
        2. Many Hamiltonian Cycles
        3. Uniquely Hamiltonian Graphs
        4. Products and Hamiltonian Decompositions
      5. 4.5.5 Random Graphs
      6. 4.5.6 Spectral Attacks
      7. 4.5.7 Forbidden Subgraphs
    10. References
    11. Section 4.6 Traveling Salesman Problems
      1. 4.6.1 The Traveling Salesman Problem
        1. Symmetric and Asymmetric TSP
        2. Matrix Representation of TSP
        3. Algorithmic Complexity
        4. Exact and Approximate Algorithms
        5. The Euclidean TSP
      2. 4.6.2 Exact Algorithms
        1. Integer Programming Approaches
      3. 4.6.3 Construction Heuristics
        1. Greedy-Type Algorithms
        2. Insertion Algorithms
        3. Minimum Spanning Tree Heuristics
        4. Worst Case Analysis of Heuristics
      4. 4.6.4 Improvement Heuristics
        1. Exponential Neighborhoods
      5. 4.6.5 The Generalized TSP
        1. Transforming Generalized TSP to TSP
        2. Exact Algorithms
        3. Approximate Algorithms
      6. 4.6.6 The Vehicle Routing Problem
        1. Exact Algorithms
        2. Heuristics for CVRP
        3. Savings Heuristics
        4. Insertion Heuristics
        5. Two-phase Heuristics
    12. References
    13. Section 4.7 Further Topics in Connectivity
      1. 4.7.1 High Connectivity
        1. Minimum Degree and Diameter
        2. Degree Sequence
        3. Distance
        4. Super Edge-Connectivity
        5. Digraphs
        6. Oriented Graphs
        7. Semigirth
        8. Line Digraphs
        9. Girth
        10. Girth Pair
        11. Cages
        12. Large Digraphs
        13. Large Graphs
      2. 4.7.2 Bounded Connectivity
        1. π-Semigirth
        2. Imbeddings
        3. Adjacency Spectrum
        4. Laplacian Spectrum
      3. 4.7.3 Symmetry and Regularity
        1. Boundaries, Fragments, and Atoms
        2. Fragments and Atoms in Undirected Graphs
        3. Fragments and Atoms in Digraphs
        4. Graphs with Symmetry
        5. Cayley Graphs
        6. Circulant Graphs
        7. Distance-Regular Graphs
      4. 4.7.4 Generalizations of Connectivity Parameters
        1. Conditional Connectivity
        2. Restricted Connectivity
        3. Distance Connectivity
        4. High Distance Connectivity
        5. Maximal Connectivity
        6. Hamiltonian Connectivity
    14. References
    15. Glossary for Chapter 4
      1. Figure 4.1.1
      2. Figure 4.1.2
      3. Figure 4.2.1
      4. Figure 4.2.2
      5. Figure 4.2.3
      6. Figure 4.2.4
      7. Figure 4.2.5
      8. Figure 4.2.6
      9. Figure 4.2.7
      10. Figure 4.2.8
      11. Figure 4.2.9
      12. Figure 4.2.10
      13. Figure 4.3.1
      14. Figure 4.3.2
      15. Figure 4.3.3
      16. Figure 4.3.4
      17. Figure 4.3.5
      18. Figure 4.3.6
      19. Figure 4.3.7
      20. Figure 4.3.8
      21. Figure 4.3.9
      22. Figure 4.4.1
      23. Figure 4.4.2
      24. Figure 4.4.3
      25. Figure 4.5.1
      26. Figure 4.5.2
      27. Figure 4.5.3
      28. Figure 4.6.1
      29. Figure 4.6.2
      30. Figure 4.6.3
      31. Figure 4.6.4
      32. Figure 4.6.5
      33. Figure 4.6.6
      34. Figure 4.7.1
      35. Figure 4.7.2
      36. Figure 4.7.3
      37. Figure 4.7.4
      38. Figure 4.7.5
      39. Figure 4.7.6
  11. Chapter 5 Colorings and Related Topics
    1. Section 5.1 Graph Coloring
      1. 5.1.1 General Concepts
        1. Proper Vertex-Coloring and Chromatic Number
        2. List Coloring and Choice Number
        3. The Hajós Construction
        4. Lovász's Topological Lower Bound
        5. Alon and Tarsi's Graph Polynomial Characterization
        6. List Reduction
      2. 5.1.2 Vertex Degrees
      3. 5.1.3 Critical Graphs and Uniquely Colorable Graphs
        1. Uniquely Colorable Graphs
      4. 5.1.4 Girth and Clique Number
        1. The Conjectures of Hadwiger and Hajós
      5. 5.1.5 Edge-Coloring and χ-Binding Functions
        1. Snarks
        2. Uniquely Edge-Colorable Graphs
        3. Further χ-Bound Graph Classes
      6. 5.1.6 Coloring and Orientation
        1. Paths and Cycles
        2. Eulerian Subgraphs
        3. Choosability and Orientations with Kernels
        4. Acyclic Orientations
      7. 5.1.7 Colorings of Infinite Graphs
        1. Coloring Euclidean Spaces and Distance Graphs
    2. References
    3. Section 5.2 Further Topics in Graph Coloring
      1. 5.2.1 Multicoloring and Fractional Coloring
      2. 5.2.2 Graphs on Surfaces
        1. Heawood Number and the Empire Problem
        2. Nowhere-Zero Flows
        3. Chromatic Polynomials
      3. 5.2.3 Some Further Types of Coloring Problems
        1. Variants of Proper Coloring
        2. Graph Homomorphisms
        3. Coloring with Costs
        4. Vertex Ranking
        5. Non-Repetitive (Thue) Colorings
        6. Partial Colorings and Extensions
        7. Coloring Cubic Graphs with Triple Systems
        8. Neighbor-Distinguishing Colorings
        9. Maximizing the Number of Colors
        10. Partitions with Weaker Requirements
      4. 5.2.4 Colorings of Hypergraphs
        1. Clique Hypergraphs
      5. 5.2.5 Algorithmic Complexity
        1. Approximation
    4. References
    5. Section 5.3 Independence and Cliques
      1. 5.3.1 Basic Definitions and Applications
        1. Some Combinatorial Optimization Problems
        2. Vertex-Weighted Graphs
        3. Applications Involving Hamming Distance
      2. 5.3.2 Integer Programming Formulations
        1. Two More Formulations of the Maximum-Clique Problem
      3. 5.3.3 Hardness Results
      4. 5.3.4 Bounds on Independence and Clique Numbers
        1. Lower Bounds
        2. Upper bounds
      5. 5.3.5 Exact Algorithms
        1. Clique Enumeration
        2. Maximum-Clique and Maximum-Weight-Clique Algorithms
      6. 5.3.6 Heuristics
        1. Construction Heuristics and Local Search
        2. Tabu Search
    6. References
    7. Section 5.4 Factors and Factorization
      1. 5.4.1 Preliminaries
      2. 5.4.2 1-Factors
        1. Conditions for a Graph to Have a 1-Factor
        2. The Number of 1-Factors: Bounds
        3. 1-Factors in Bipartite Graphs
        4. The Number of 1-Factors: Exact Counting
      3. 5.4.3 Degree Factors
        1. k-factors
        2. f-factors
        3. [a,b]-factors
        4. (g,f)-factors
        5. Factors in Random Graphs
      4. 5.4.4 Component Factors
      5. 5.4.5 Graph Factorization
        1. Edge Partitions
        2. Vertex Partitions
        3. Factor Algorithms and Complexity
        4. Subgraph Problems
    8. References
    9. Section 5.5 Applications to Timetabling
        1. Automated Timetabling: Historical Perspective
      2. 5.5.1 Specification of Timetabling Problems
        1. The General Problem
        2. Times
        3. Resources
        4. Meetings
        5. Constraints
      3. 5.5.2 Class-Teacher Timetabling
        1. The Basic Class-Teacher Timetabling Problem
        2. Extensions to the Basic Class-Teacher Problem
        3. Graph Models for Subproblems of the Class-Teacher Problem
      4. 5.5.3 University Course Timetabling
        1. Basic Model
        2. A Graph Formulation
        3. Scheduling Multi-Section Courses
      5. 5.5.4 University Examination Timetabling
        1. Basic Model
        2. A More Compact Schedule
        3. The Breadth and Variation of Exam Timetabling Constraints
        4. Heuristic Methods
        5. Two Different Random-Selection Strategies
        6. Hybrid Graph-Coloring/Meta-Heuristic Approaches
      6. 5.5.5 Sports Timetabling
        1. A Simple Graph Model
        2. Profiles, Breaks, and Home-Away Patterns of a Schedule
        3. A Lower Bound on the Number of Breaks
        4. Irreducible and Compact Schedules
        5. Complementarity
        6. Constructing a Compact Schedule with a Minimum Number of Breaks
        7. An Alternate View of the Canonical Factorization
        8. Some Characterization Results
        9. Feasible Sequences
    10. References
    11. Section 5.6 Graceful Labelings
      1. 5.6.1 Trees
      2. 5.6.2 Cycle-Related Graphs
      3. 5.6.3 Product-Related Graphs
      4. 5.6.4 Complete Graphs
      5. 5.6.5 Disconnected Graphs
      6. 5.6.6 Joins of Graphs
      7. 5.6.7 α-labelings
    12. References
    13. Glossary for Chapter 5
      1. Figure 5.3.1
      2. Figure 5.5.1
      3. Figure 5.5.2
      4. Figure 5.5.3
      5. Figure 5.5.4
      6. Figure 5.5.5
      7. Figure 5.5.6
      8. Figure 5.5.7
      9. Figure 5.5.8
      10. Figure 5.5.9
      11. Figure 5.5.10
      12. Figure 5.5.11
      13. Figure 5.5.12
  12. Chapter 6 Algebraic Graph Theory
    1. Section 6.1 Automorphisms
      1. 6.1.1 The Automorphism Group of a Graph
      2. 6.1.2 Graphs with Given Group
          1. Further Reading
      3. 6.1.3 Groups of Graph Products
          1. Further Reading
      4. 6.1.4 Transitivity
          1. Further Reading
      5. 6.1.5 s-Regularity and s-Transitivity
      6. 6.1.6 Graphical Regular Representations
      7. 6.1.7 Primitivity
      8. 6.1.8 More Automorphisms of Infinite Graphs
        1. Strips
        2. Automorphisms and Distance
      9. 6.1.9 Distinguishability
          1. Further Reading
        2. Distinguishing Number of Graph Products
        3. More Distinguishing Number Results for Infinite Graphs
    2. References
    3. Section 6.2 Cayley Graphs
      1. 6.2.1 Construction and Recognition
      2. 6.2.2 Prevalence
      3. 6.2.3 Isomorphism
      4. 6.2.4 Subgraphs
      5. 6.2.5 Factorization
      6. 6.2.6 Miscellaneous
          1. Embeddings
          2. Applications
          3. Further Reading
    4. References
    5. Section 6.3 Enumeration
      1. 6.3.1 Counting Simple Graphs and Multigraphs
        1. Labeled Graphs
        2. Unlabeled Graphs
      2. 6.3.2 Counting Digraphs and Tournaments
        1. Labeled Digraphs
        2. Unlabeled Digraphs
      3. 6.3.3 Counting Generic Trees
      4. 6.3.4 Counting Trees in Chemistry
      5. 6.3.5 Counting Trees in Computer Science
    6. References
    7. Section 6.4 Graphs and Vector Spaces
      1. 6.4.1 Basic Concepts and Definitions
        1. Subgraphs and Complements
        2. Components, Spanning Trees, and Cospanning Trees
        3. Cuts and Cutsets
        4. Vector Space of a Graph under Ring Sum of Its Edge Subsets
      2. 6.4.2 Circuit Subspace of an Undirected Graph
        1. Fundamental Circuits and the Dimension of the Circuit Subspace
      3. 6.4.3 Cutset Subspace of an Undirected Graph
        1. Fundamental Cutsets and the Dimension of the Cutset Subspace
      4. 6.4.4 Relationship between Circuit and Cutset Subspaces
        1. Orthogonality of Circuit and Cutset Subspaces
        2. Circ/Cut-Based Decomposition of Graphs and Subgraphs
      5. 6.4.5 Circuit and Cutset Spaces in a Directed Graph
        1. Circuit and Cut Vectors and Matrices
        2. Fundamental Circuit, Fundamental Cutset, and Incidence Matrices
        3. Orthogonality and the Matrix Tree Theorem
        4. Minty’s Painting Theorem
      6. 6.4.6 Two Circ/Cut-Based Tripartitions of a Graph
        1. Bicycle-Based Tripartition
        2. A Tripartition Based on Maximally Distant Spanning Trees
      7. 6.4.7 Realization of Circuit and Cutset Spaces
        1. Whitney and Kuratowski
      8. 6.4.8 An Application: Cross-Layer Survivability in a Layered Network
    8. References
    9. Section 6.5 Spectral Graph Theory
      1. 6.5.1 Basic Matrix Properties
      2. 6.5.2 Walks and the Spectrum
        1. Walks and the Coefficients of the Characteristic Polynomial
        2. Walks and the Minimal Polynomial
        3. Regular Graphs
      3. 6.5.3 Line Graph, Root System, Eigenvalue Bounds
        1. Line Graphs and Generalized Line Graphs
        2. Root Systems
        3. Eigenvalue Bounds
          1. Further Reading
      4. 6.5.4 Distance-Regular Graphs
        1. Distance-Regular Graphs and the Hoffman Polynomial
        2. Strongly Regular Graphs
          1. Further Reading
      5. 6.5.5 Spectral Characterization
        1. Eigenvalues and Graph Operations
      6. 6.5.6 The Laplacian
        1. Further Reading
    10. References
    11. Section 6.6 Matroidal Methods in Graph Theory
      1. 6.6.1 Matroids: Basic Definitions and Examples
      2. 6.6.2 Alternative Axiom Systems
      3. 6.6.3 The Greedy Algorithm
      4. 6.6.4 Duality
      5. 6.6.5 Matroid Union and Its Consequences
      6. 6.6.6 Fundamental Operations
      7. 6.6.7 Connectedness, 2- and 3-Connectedness for Graphs and Matroids
        1. Bounds on the number of elements
        2. 2-sums and 3-sums
      8. 6.6.8 Graphs and Totally Unimodular Matrices
      9. 6.6.9 Excluded-Minor Characterizations
      10. 6.6.10 Wheels, Whirls, and the Splitter Theorem
      11. 6.6.11 Removable Circuits
      12. 6.6.12 Minimally k-connected Graphs and Matroids
      13. 6.6.13 Conclusion
    12. References
    13. Glossary for Chapter 6
      1. Figure 6.1.1
      2. Figure 6.1.2
      3. Figure 6.2.1
      4. Figure 6.2.2
      5. Figure 6.3.1
      6. Figure 6.3.2
      7. Figure 6.3.3
      8. Figure 6.3.4
      9. Figure 6.3.5
      10. Figure 6.3.6
      11. Figure 6.3.7
      12. Figure 6.3.8
      13. Figure 6.3.9
      14. Figure 6.4.1
      15. Figure 6.4.2
      16. Figure 6.4.3
      17. Figure 6.4.4
      18. Figure 6.4.5
      19. Figure 6.4.6
      20. Figure 6.4.7
      21. Figure 6.4.8
      22. Figure 6.4.9
      23. Figure 6.4.10
      24. Figure 6.4.11
      25. Figure 6.5.1
      26. Figure 6.5.2
      27. Figure 6.5.3
      28. Figure 6.5.4
      29. Figure 6.5.5
      30. Figure 6.5.6
      31. Figure 6.6.1
      32. Figure 6.6.2
      33. Figure 6.6.3
      34. Figure 6.6.4
      35. Figure 6.6.5
      36. Figure 6.6.6
      37. Figure 6.6.7
      38. Figure 6.6.8
      1. Table 6.3.1
      2. Table 6.3.2
      3. Table 6.3.3
      4. Table 6.3.4
      5. Table 6.3.5
      6. Table 6.3.6
      7. Table 6.3.7
      8. Table 6.3.8
      9. Table 6.3.9
      10. Table 6.3.10
      11. Table 6.3.11
      12. Table 6.3.12
      13. Table 6.3.13
      14. Table 6.3.14
      15. Table 6.6.1
      16. Table 6.6.2
      17. Table 6.6.3
      18. Table 6.6.4
      19. Table 6.6.5
      20. Table 6.6.6
  13. Chapter 7 Topological Graph Theory
    1. Section 7.1 Graphs on Surfaces
      1. 7.1.1 Surfaces
        1. 2-Manifolds and 2-Pseudomanifolds
        2. Some Standard Surfaces
        3. Surface Operations and Classification
      2. 7.1.2 Polygonal Complexes
      3. 7.1.3 Imbeddings
      4. 7.1.4 Combinatorial Descriptions of Maps
          1. Algorithm
    2. References
    3. Section 7.2 Minimum Genus and Maximum Genus
      1. 7.2.1 Definitions and Basic Facts
        1. Ear Decomposition
        2. Edge Insertion and Deletion
      2. 7.2.2 Kuratowski-Type Theorems
        1. Minimum Genus
        2. Maximum Genus
      3. 7.2.3 Planarity and Upper-Embeddability
      4. 7.2.4 Lower Bounds
        1. Lower Bounds on Minimum Genus
        2. Lower Bounds on Maximum Genus
      5. 7.2.5 Algorithmic Issues
        1. Minimum Genus Algorithms
        2. Maximum Genus Algorithms
    4. References
    5. Section 7.3 Genus Distributions
      1. 7.3.1 Ranges and Distributions of Imbeddings
      2. 7.3.2 Counting Noncellular Imbeddings
      3. 7.3.3 Partitioned Genus Distributions
      4. 7.3.4 Graph Amalgamations
        1. Bar Amalgamations
        2. Vertex Amalgamations
      5. 7.3.5 Genus Distribution Formulas for Special Classes
      6. 7.3.6 Other Imbedding Distribution Calculations
      7. 7.3.7 The Unimodality Problem
      8. 7.3.8 Average Genus
      9. 7.3.9 Stratification of Imbeddings
    6. References
    7. Section 7.4 Voltage Graphs
      1. 7.4.1 Regular Voltage Graphs
        1. Fibers
        2. Bouquets and Dipoles
        3. Net Voltages
      2. 7.4.2 Local Group and Natural Automorphisms
        1. The Local Group
        2. Natural Automorphisms
      3. 7.4.3 Permutation Voltage Graphs
      4. 7.4.4 Representing Coverings with Voltage Graphs
        1. Coverings and Branched Coverings of Surfaces
        2. Using Voltage Graph Constructions
        3. Action of the Group of Covering Transformations
      5. 7.4.5 The Kirchhoff Voltage Law
      6. 7.4.6 Imbedded Voltage Graphs
      7. 7.4.7 Topological Current Graphs
      8. 7.4.8 Lifting Voltage Graph Mappings
      9. 7.4.9 Applications of Voltage Graphs
        1. Applications of Imbedded Voltage Graphs and Topological Current Graphs
    8. References
    9. Section 7.5 The Genus of a Group
      1. 7.5.1 Symmetric Imbeddings of Cayley Graphs
      2. 7.5.2 Riemann—Hurwitz Equation; Hurwitz’s Theorem
      3. 7.5.3 Groups of Low Genus
      4. 7.5.4 Genus for Families of Groups
      5. 7.5.5 Non-Orientable Surfaces
    10. References
    11. Section 7.6 Maps
      1. 7.6.1 Maps and Polyhedral Maps
      2. 7.6.2 Existence and Realizations of Polyhedral Maps
      3. 7.6.3 Paths and Cycles in Maps
      4. 7.6.4 Map Coloring
      5. 7.6.5 Combinatorial Schemes
      6. 7.6.6 Maps and Universal Tessellations
      7. 7.6.7 Highly Symmetrical Maps
      8. 7.6.8 Enumeration of Maps
    12. References
    13. Section 7.7 Representativity
      1. 7.7.1 Basic Concepts
      2. 7.7.2 Coloring Densely Imbeddable Graphs
        1. Coloring with Few Colors
        2. Coloring Graphs that Quadrangulate
        3. Coloring Graphs That Triangulate
      3. 7.7.3 Finding Cycles, Walks, and Spanning Trees
      4. 7.7.4 Re-Imbedding Properties
        1. LEW-Imbeddings
        2. Imbeddings and Connectivity
        3. Imbeddings and Genus
        4. Re-Imbedding Results
      5. 7.7.5 Minors of Imbedded Graphs
        1. Surface Minors
        2. Finding Imbedded Cycles
      6. 7.7.6 Minor-Minimal Maps
        1. Similarity Classes on the Torus
        2. Kernels
    14. References
    15. Section 7.8 Triangulations
      1. 7.8.1 Basic Concepts
          1. Notations
      2. 7.8.2 Constructing Triangulations
        1. Triangulations with Complete Graphs
        2. Minimum Triangulations
        3. Covering Constructions
      3. 7.8.3 Irreducible Triangulations
        1. Edge Contraction
        2. Classification and Finiteness in Number
        3. Other Irreducibility
      4. 7.8.4 Diagonal Flips
        1. Estimating Bounds
        2. Catalan Triangulations
        3. Preserving Properties
      5. 7.8.5 Rigidity and Flexibility
        1. Equivalence over Imbeddings
        2. Uniqueness of Imbeddings
        3. Re-Imbedding Structures
        4. Imbeddings into Other Surfaces
    16. References
    17. Section 7.9 Graphs and Finite Geometries
      1. 7.9.1 Finite Geometries
      2. 7.9.2 Associated Graphs
      3. 7.9.3 Surface Models
    18. References
    19. Section 7.10 Crossing Numbers
      1. 7.10.1 Drawings of Graphs and Crossing Numbers
        1. Embeddings
        2. Drawings
        3. Crossing Numbers
      2. 7.10.2 General Techniques and Bounds
        1. The Crossing Lemma
        2. Crossing Numbers, Bisection Width, and Cutwidth
        3. Crossing Numbers, Immersion, and Congestion
      3. 7.10.3 Crossing Numbers of Some Families of Graphs
        1. Complete Bipartite Graphs
        2. Complete Graphs
        3. Other Families of Graphs
      4. 7.10.4 Crossing-Critical Graphs
      5. 7.10.5 Algorithmical Aspects
      6. 7.10.6 Other Definitions of Crossing Number
      7. 7.10.7 Crossing Sequences
      8. 7.10.8 Applications of Crossing Numbers
      9. 7.10.9 Suggestions for Further Reading
    20. References
    21. Glossary for Chapter 7
      1. Figure 7.1.1
      2. Figure 7.1.2
      3. Figure 7.1.3
      4. Figure 7.1.4
      5. Figure 7.1.5
      6. Figure 7.1.6
      7. Figure 7.1.7
      8. Figure 7.1.8
      9. Figure 7.1.9
      10. Figure 7.1.10
      11. Figure 7.1.11
      12. Figure 7.1.12
      13. Figure 7.1.13
      14. Figure 7.2.1
      15. Figure 7.2.2
      16. Figure 7.2.3
      17. Figure 7.3.1
      18. Figure 7.3.2
      19. Figure 7.3.3
      20. Figure 7.3.4
      21. Figure 7.3.5
      22. Figure 7.3.6
      23. Figure 7.3.7
      24. Figure 7.3.8
      25. Figure 7.3.9
      26. Figure 7.3.10
      27. Figure 7.3.11
      28. Figure 7.3.12
      29. Figure 7.3.13
      30. Figure 7.3.14
      31. Figure 7.3.15
      32. Figure 7.3.16
      33. Figure 7.4.1
      34. Figure 7.4.2
      35. Figure 7.4.3
      36. Figure 7.4.4
      37. Figure 7.4.5
      38. Figure 7.4.6
      39. Figure 7.4.7
      40. Figure 7.4.8
      41. Figure 7.6.1
      42. Figure 7.6.2
      43. Figure 7.6.3
      44. Figure 7.6.4
      45. Figure 7.6.5
      46. Figure 7.6.6
      47. Figure 7.6.7
      48. Figure 7.6.8
      49. Figure 7.6.9
      50. Figure 7.6.10
      51. Figure 7.6.11
      52. Figure 7.6.12
      53. Figure 7.6.13
      54. Figure 7.6.14
      55. Figure 7.6.15
      56. Figure 7.6.16
      57. Figure 7.6.17
      58. Figure 7.6.18
      59. Figure 7.6.19
      60. Figure 7.7.1
      61. Figure 7.7.2
      62. Figure 7.7.3
      63. Figure 7.8.1
      64. Figure 7.8.2
      65. Figure 7.8.3
      66. Figure 7.8.4
      67. Figure 7.8.5
      68. Figure 7.8.6
      69. Figure 7.8.7
      70. Figure 7.8.8
      71. Figure 7.8.9
      72. Figure 7.8.10
      73. Figure 7.8.11
      74. Figure 7.8.12
      75. Figure 7.8.13
      76. Figure 7.9.1
      77. Figure 7.9.2
      78. Figure 7.9.3
      79. Figure 7.9.4
      80. Figure 7.9.5
      81. Figure 7.10.1
      82. Figure 7.10.2
      83. Figure 7.10.3
      1. Table 7.1
  14. Chapter 8 Analytic Graph Theory
    1. Section 8.1 Extremal Graph Theory
      1. 8.1.1 Turán-Type Problems
        1. Turán's Theorem and Its Extensions
        2. Structural Properties of the Graphs G(n, tr(n) + 1)
        3. Books and Generalized Books
        4. Vertex-Disjoint Cliques
      2. 8.1.2 The Number of Complete Graphs
      3. 8.1.3 Erdős–Stone Theorem and Its Extensions
        1. The Structure of Extremal Graphs
      4. 8.1.4 Zarankiewicz Problem and Related Questions
        1. κr-Free Graphs with Large Minimal Degree
      5. 8.1.5 Paths and Trees
      6. 8.1.6 Circumference
      7. 8.1.7 Hamiltonian Cycles
      8. 8.1.8 Cycle Lengths
        1. Cycles of Consecutive Lengths
        2. Pancyclicity and Weak Pancyclicity
      9. 8.1.9 Szemerédi's Uniformity Lemma
        1. Applications of the Uniformity and Blow-up lemmas
      10. 8.1.10 Asymptotic Enumeration
      11. 8.1.11 Graph Minors
      12. 8.1.12 Ramsey–Turán Problems
    2. References
    3. Section 8.2 Random Graphs
      1. 8.2.1 Random Graph Models
        1. Asymptotics
      2. 8.2.2 Threshold Functions
      3. 8.2.3 Small Subgraphs and the Degree Sequence
      4. 8.2.4 Phase Transition
      5. 8.2.5 Many More Properties of Random Graphs
      6. 8.2.6 Random Regular Graphs
      7. 8.2.7 Other Random Graph Models
      8. 8.2.8 Random Graph Processes
    4. References
    5. Section 8.3 Ramsey Graph Theory
      1. 8.3.1 Ramsey’s Theorem
        1. Ramsey Numbers for Arbitrary Graphs
      2. 8.3.2 Fundamental Results
      3. 8.3.3 Classical Ramsey Numbers
        1. Ramsey Numbers for Small Graphs
        2. Asymptotic Results
      4. 8.3.4 Generalized Ramsey Numbers
        1. Initial Generalized Ramsey Results
        2. Ramsey Numbers for Trees
        3. Cycle Ramsey Numbers
        4. Good Results
        5. Small Order Graphs
        6. Linear Bounds
      5. 8.3.5 Size Ramsey Numbers
        1. General Bounds
        2. Linear Bounds
        3. Bipartite Graphs
        4. Small Order Graphs
      6. 8.3.6 Ramsey Minimal Graphs
      7. 8.3.7 Generalizations and Variations
        1. Graphs
        2. Hypergraphs
    6. References
    7. Section 8.4 The Probabilistic Method
      1. 8.4.1 The First Moment Method
        1. Ramsey Numbers
      2. 8.4.2 Alterations
      3. 8.4.3 The Lovász Local Lemma
      4. 8.4.4 The Rödl Nibble
      5. 8.4.5 Bounds on Tails of Distributions
      6. 8.4.6 Dependent Random Choice
    8. References
    9. Section 8.5 Graph Limits
      1. 8.5.1 Graphs, Weighted Graphs, and Graphons
      2. 8.5.2 Homomorphism Density
      3. 8.5.3 Convergent Sequences of Graphs and Graphons
      4. 8.5.4 Metric Space Topology on Graphs and Graphons
      5. 8.5.5 Regularity Lemma and Approximation of Graphons by Weighted Graphs
      6. 8.5.6 W-Random Graphs
      7. 8.5.7 Graph Parameters and Connection Matrices
      8. 8.5.8 Extremal Graph Theory and the Algebra of Quantum Graphs
    10. References
    11. Glossary for Chapter 8
      1. Figure 8.2.1
      2. Figure 8.2.2
      3. Figure 8.3.1
      4. Figure 8.3.2
      5. Figure 8.3.3
      6. Figure 8.3.4
      7. Figure 8.3.5
      8. Figure 8.3.6
      9. Figure 8.5.1
      10. Figure 8.5.2
  15. Chapter 9 Graphical Measurement
    1. Section 9.1 Distance in Graphs
      1. 9.1.1 Standard Distance in Graphs
        1. Distance and Eccentricity
        2. Radius and Diameter
        3. Center and Periphery
        4. Self-Centered Graphs
      2. 9.1.2 Geodetic Parameters
        1. Geodetic Sets and Geodetic Numbers
        2. Convex Sets and Hull Sets
      3. 9.1.3 Total Distance and Medians of Graphs
        1. Total Distance of a Vertex
        2. The Median of a Connected Graph
        3. Centers and Medians of a Connected Graph
      4. 9.1.4 Steiner Distance in Graphs
        1. Steiner Radius and Steiner Diameter
        2. Steiner Centers
      5. 9.1.5 Distance in Digraphs
        1. Radius and Diameter in Strong Digraphs
        2. The Center of a Strong Digraph
        3. Strong Distance in Strong Digraphs
        4. Strong Centers of Strong Digraphs
    2. References
    3. Section 9.2 Domination in Graphs
      1. 9.2.1 Dominating Sets in Graphs
        1. Equivalent Definitions of a Dominating Set
        2. Applications of Domination
      2. 9.2.2 Minimality Conditions
        1. The Domination Chain
      3. 9.2.3 Domination Perfect Graphs
      4. 9.2.4 Bounds on the Domination Number
        1. Bounds in Terms of Order and Minimum Degree
        2. Minimum Degree Two
        3. Minimum Degree Three
        4. Cubic Graphs
        5. More Bounds Involving Minimum Degree
        6. Bounds in Terms of Size and Degree
        7. Bounds in Terms of Order and Maximum Degree
        8. Bounds in Terms of Order and Size
        9. Bounds in Terms of Packing
        10. Bounds in Terms of Radius
      5. 9.2.5 Nordhaus-Gaddum-Type Results
      6. 9.2.6 Domination in Planar Graphs
      7. 9.2.7 Vizing's Conjecture
      8. 9.2.8 Domination Critical Graphs
      9. 9.2.9 Domination Parameters
    4. References
    5. Section 9.3 Tolerance Graphs
      1. 9.3.1 Intersection Graphs and Their Applications
        1. Containment Graphs
      2. 9.3.2 The Classical Model of Interval Tolerance
      3. 9.3.3 The Algorithmics of Tolerance Graphs
      4. 9.3.4 Variations of Tolerance on Intervals
        1. ɸ-Tolerance Graphs
        2. Threshold Tolerance and coTT Graphs
        3. Bounded Bitolerance Graphs and Ordered Sets
      5. 9.3.5 Rank-Tolerance Graphs
        1. Background
      6. 9.3.6 Intersection and Tolerance Graphs on Trees
        1. The (h, s, t) Graphs: Degree Constrained Representations
    6. References
    7. Section 9.4 Bandwidth
      1. 9.4.1 Fundamentals
        1. The Bandwidth Concept
        2. Applications
          1. Efficient Matrix Storage
          2. VLSI Layout
          3. Interconnection Networks
          4. Binary Constraint Satisfaction Problem
        3. Algorithms
      2. 9.4.2 Elementary Results
        1. The Bandwidth of Some Common Families of Graphs
        2. A Few Basic Relations
        3. On the Bandwidth of Trees
        4. Alternative Interpretations of Bandwidth
      3. 9.4.3 Bounds on Bandwidth
        1. Two General Bounds
        2. Subdivisions, Mergers, Contractions, and Edge Additions
        3. Nordhaus-Gaddum Types of Bounds
        4. Other Bounds
      4. 9.4.4 On the Bandwidth of Combinations of Graphs
        1. Cartesian Product
        2. Sum of Two Graphs
        3. Corona and Composition
        4. Strong Product and Tensor Product
      5. 9.4.5 Bandwidth and Its Relationship to Other Invariants
        1. Vertex Degree
        2. Number of Vertices and Edges for Arbitrary Graphs
        3. Number of Vertices and Edges for Graphs with no κ3
        4. Radius and Diameter
        5. Vertex and Edge Chromatic Number
        6. Vertex Independence and Vertex Cover Numbers
        7. Girth, Vertex Arboricity, and Thickness
      6. 9.4.6 Related Concepts
        1. Bandsize
        2. Edgesum (Bandwidth Sum)
        3. Cyclic Bandwidth
        4. Edge-Bandwidth
        5. Profile
        6. Cutwidth
        7. Topological Bandwidth
        8. Additive Bandwidth
    8. References
    9. Section 9.5 Pursuit-Evasion Problems
      1. 9.5.1 Sweeping and Edge Search
      2. 9.5.2 Node Search and Mixed Search
      3. 9.5.3 Cops-and-Robbers
      4. 9.5.4 Additional Variations
    10. References
    11. Glossary for Chapter 9
      1. Figure 9.1.1
      2. Figure 9.1.2
      3. Figure 9.1.3
      4. Figure 9.1.4
      5. Figure 9.1.5
      6. Figure 9.1.6
      7. Figure 9.1.7
      8. Figure 9.1.8
      9. Figure 9.1.9
      10. Figure 9.1.10
      11. Figure 9.1.11
      12. Figure 9.1.12
      13. Figure 9.1.13
      14. Figure 9.1.14
      15. Figure 9.1.15
      16. Figure 9.1.16
      17. Figure 9.1.17
      18. Figure 9.2.1
      19. Figure 9.2.2
      20. Figure 9.2.3
      21. Figure 9.2.4
      22. Figure 9.2.5
      23. Figure 9.2.6
      24. Figure 9.2.7
      25. Figure 9.2.8
      26. Figure 9.2.9
      27. Figure 9.2.10
      28. Figure 9.2.11
      29. Figure 9.2.12
      30. Figure 9.4.1
      31. Figure 9.4.2
      32. Figure 9.4.3
      33. Figure 9.4.4
      34. Figure 9.4.5
      35. Figure 9.4.6
      36. Figure 9.4.7
      37. Figure 9.4.8
      38. Figure 9.4.9
      39. Figure 9.4.10
      40. Figure 9.5.1
      41. Figure 9.5.2
      42. Figure 9.5.3
      43. Figure 9.5.4
      44. Figure 9.5.5
      45. Figure 9.5.6
      46. Figure 9.5.7
      47. Figure 9.5.8
      1. Table 9.1
  16. Chapter 10 Graphs in Computer Science
    1. Section 10.1 Searching
      1. 10.1.1 Breadth-First Search
        1. Ordered Trees
      2. 10.1.2 Depth-First Search
        1. Discovery Order
      3. 10.1.3 Topological Order
      4. 10.1.4 Connectivity Properties
        1. Strong Components of a Directed Graph
        2. Bridges and Cutpoints of an Undirected Graph
      5. 10.1.5 DFS as a Proof Technique
      6. 10.1.6 More Graph Properties
        1. Planarity Testing
        2. Triconnectivity
        3. Ear Decomposition and st-numbering
        4. Reducibility
        5. Two Directed Spanning Trees
        6. Dominators
        7. Facts About Semidominators
      7. 10.1.7 Approximation Algorithms
        1. Algorithm
    2. References
    3. Section 10.2 Dynamic Graph Algorithms
      1. 10.2.1 Basic Terminology
      2. 10.2.2 Dynamic Problems on Undirected Graphs
        1. General Techniques for Undirected Graphs
        2. Topology Trees
          1. Assumption
          2. Approach
        3. ET Trees
          1. Approach
        4. Top Trees
          1. Approach
        5. Clustering
        6. Sparsification
          1. Approach
          2. Notation
        7. Randomization
          1. Approach
        8. Connectivity
          1. Invariants
        9. Minimum Spanning Trees
        10. Decremental Minimum Spanning Tree
          1. Approach
          2. Invariant
        11. Fully Dynamic Minimum Spanning Tree
      3. 10.2.3 Dynamic Problems on Directed Graphs
        1. General Techniques for Directed Graphs
        2. Path Problems and Kleene Closures
        3. Locally Shortest Paths
        4. Long Paths Property
        5. Reachability Trees
        6. Matrix Data Structures
        7. Dynamic Transitive Closure
        8. King's O(n2 log n) Update Algorithm
          1. Approach
        9. Demetrescu and Italiano's O(n2) Update Algorithm
          1. Approach
          2. Notation
        10. Dynamic Shortest Paths
          1. Notation
        11. King's On2.5 C log n Update Algorithm
          1. Approach
        12. Demetrescu and Italiano's O(n2 log3 n) Update Algorithm
          1. Approach
      4. 10.2.4 Research Issues
        1. Further Information
        2. Acknowledgments
    4. References
    5. Section 10.3 Drawings of Graphs
      1. 10.3.1 Types of Graphs and Drawings
        1. Types of Graphs
        2. Types of Drawings
      2. 10.3.2 Combinatorics of Some Geometric Graphs
        1. Delaunay Triangulations
        2. β-drawings and Rectangle of Influence Drawings
        3. Minimum Spanning Trees
        4. Minimum Weight Triangulations
      3. 10.3.3 Properties of Drawings and Bounds
        1. Properties of Drawings
        2. Bounds on the Area
        3. Bounds on the Angular Resolution
        4. Bounds on the Number of Bends
        5. Tradeoff Between Area and Aspect Ratio
        6. Tradeoff between Area and Angular Resolution
      4. 10.3.4 Complexity of Graph Drawing Problems
      5. 10.3.5 Example of a Graph Drawing Algorithm
      6. 10.3.6 Techniques for Drawing Graphs
        1. Planarization
        2. Layering
        3. Physical Simulation
      7. 10.3.7 Selected Topics
        1. Point-Set Embeddings and Universal Point Sets
        2. Simultaneous Embeddings
        3. Lombardi Drawings
        4. Drawings with Large Crossing Angles
        5. Drawings with Few Slopes
        6. Witness Proximity and Approximate Proximity Drawings
        7. Cluster Planarity
      8. 10.3.8 Sources and Related Material
    6. References
    7. Section 10.4 Algorithms on Recursively Constructed Graphs
        1. Algorithm Design Strategy
      2. 10.4.1 Algorithms on Trees
        1. Maximum-Cardinality Independent Set in a Tree
        2. Maximum-Weight Independent Set in a Tree
      3. 10.4.2 Algorithms on Series-Parallel Graphs
        1. Maximum-Cardinality Independent Set in a Series-Parallel Graph
        2. Multiplication Tables for Series, Parallel, and Jacknife Operations
      4. 10.4.3 Algorithms on Treewidth-k Graphs
        1. Maximum-Cardinality Independent Set in a Treewidth-k Graph
        2. Monadic Second-Order Logic Expressions for a Graph
        3. MSOL-Expressible Graph Problems
      5. 10.4.4 Algorithms on Cographs
        1. Three More Algorithms for Cographs
      6. 10.4.5 Algorithms on Cliquewidth-k Graphs
        1. Maximum-Cardinality Independent Set of a Cliquewidth-k Graph
        2. A Subset of the MSOL Expressions for a Graph
      7. 10.4.6 Algorithms on k-HB Graphs
        1. Maximum-Cardinality Independent Set in a k-HB Graph
        2. A Subset of the MSOL' Expressions
    8. References
    9. Section 10.5 Fuzzy Graphs
      1. 10.5.1 Definitions and Basic Properties
      2. 10.5.2 Paths and Connectedness
      3. 10.5.3 Forests and Trees
      4. 10.5.4 Fuzzy Cut Sets
      5. 10.5.5 Fuzzy 1-Chain with Boundary 0, Fuzzy Coboundary, and Fuzzy Cocycles
      6. 10.5.6 Fuzzy Line Graphs
      7. 10.5.7 Fuzzy Interval Graphs
      8. 10.5.8 Operations on Fuzzy Graphs
      9. 10.5.9 Clusters
      10. 10.5.10 Application to Cluster Analysis
      11. 10.5.11 Fuzzy Graphs in Database Theory
      12. 10.5.12 Strengthening and Weakening Members of a Group
      13. 10.5.13 Network Analysis of Fuzzy Graphs
      14. 10.5.14 Intuitionistic Fuzzy Graphs and Group Decision-Making
    10. References
    11. Section 10.6 Expander Graphs
      1. 10.6.1 Foundational Definitions and Results
        1. Isoperimetric Constants and Expander Families
        2. Relationship to Graph Spectra
        3. Ramanujan Graphs and the Alon–Boppana Theorem
        4. Group Representations and Kazhdan Constants
      2. 10.6.2 Major Results and Open Problems
        1. Existence and Construction of Expander Families
        2. Ramanujan Graphs and Zeta Functions
        3. Group Structure and Expansion
        4. Random Graphs and Expansion Definitions
      3. 10.6.3 Other Surveys and General Sources
    12. References
    13. Section 10.7 Visibility Graphs
      1. 10.7.1 Bar-Visibility Graphs
      2. 10.7.2 Rectangle-Visibility Graphs
      3. 10.7.3 Visibility Representations in ℝ3
      4. 10.7.4 Box-Visibility Graphs
      5. 10.7.5 Bar k-Visibility Graphs
      6. 10.7.6 Bar Visibility Number
      7. 10.7.7 Other Visibility Graphs
    14. References
    15. Glossary for Chapter 10
      1. Figure 10.1.1
      2. Figure 10.1.2
      3. Figure 10.1.3
      4. Figure 10.1.4
      5. Figure 10.1.5
      6. Figure 10.1.6
      7. Figure 10.1.7
      8. Figure 10.1.8
      9. Figure 10.1.9
      10. Figure 10.1.10
      11. Figure 10.1.11
      12. Figure 10.1.12
      13. Figure 10.1.13
      14. Figure 10.1.14
      15. Figure 10.1.15
      16. Figure 10.1.16
      17. Figure 10.1.17
      18. Figure 10.1.18
      19. Figure 10.1.19
      20. Figure 10.1.20
      21. Figure 10.1.21
      22. Figure 10.1.22
      23. Figure 10.1.23
      24. Figure 10.1.24
      25. Figure 10.2.1
      26. Figure 10.2.2
      27. Figure 10.2.3
      28. Figure 10.2.4
      29. Figure 10.3.1
      30. Figure 10.3.2
      31. Figure 10.3.3
      32. Figure 10.4.1
      33. Figure 10.4.2
      34. Figure 10.4.3
      35. Figure 10.4.4
      36. Figure 10.4.5
      37. Figure 10.4.6
      38. Figure 10.6.1
      39. Figure 10.6.2
      40. Figure 10.7.1
      41. Figure 10.7.2
      42. Figure 10.7.3
      43. Figure 10.7.4
      44. Figure 10.7.5
      45. Figure 10.7.6
      46. Figure 10.7.7
      47. Figure 10.7.8
  17. Chapter 11 Networks and Flows
    1. Section 11.1 Maximum Flows
      1. 11.1.1 The Basic Maximum Flow Problem
      2. 11.1.2 Minimum Cuts and Duality
        1. Cuts in a Network
        2. Weak Duality
      3. 11.1.3 Max-Flow Min-Cut Theorem
        1. The Residual Network and Flow-Augmenting Paths
      4. 11.1.4 Algorithms for Maximum Flow
        1. Ford–Fulkerson Algorithm
        2. Preflow-Push Algorithms
      5. 11.1.5 Variants and Extensions of Maximum Flow
        1. Multicommodity Flow
        2. Variants of Multicommodity Flow Problems
    2. References
    3. Section 11.2 Minimum Cost Flows
      1. 11.2.1 The Basic Model and Definitions
        1. Residual Networks
      2. 11.2.2 Optimality Conditions
        1. A Basic Cycle-Canceling Algorithm
      3. 11.2.3 The Dual Problem
      4. 11.2.4 Algorithms for Minimum Cost Flow
        1. A Transshipment Problem Associated with a Minimum Cost Flow Problem
        2. A Primal-Dual Algorithm
        3. A Push-Relabel Algorithm
        4. Strongly Polynomial Algorithms
      5. 11.2.5 Extensions to Minimum Cost Flow
        1. Convex Cost Flows
        2. Flows Over Time
        3. Flows with Losses and Gains
    4. References
    5. Section 11.3 Matchings and Assignments
      1. 11.3.1 Matchings
        1. Basic Terminology
        2. Some Fundamental Results
      2. 11.3.2 Matchings in Bipartite Graphs
        1. Bipartite Maximum-Size Matching Algorithm
        2. Bipartite Maximum-Weight Matching Algorithm
      3. 11.3.3 Matchings in Nonbipartite Graphs
      4. 11.3.4 Stable Matchings
        1. Gale–Shapley Algorithm
    6. References
    7. Section 11.4 Graph Pebbling
      1. 11.4.1 Solvability
        1. NOTATION
        2. Weight Functions
        3. Complexity
      2. 11.4.2 Pebbling Numbers
        1. Diameter, Connectivity, and Class 0
        2. Complexity
      3. 11.4.3 Optimal Pebbling
        1. Complexity
      4. 11.4.4 Thresholds
        1. NOTATION
      5. 11.4.5 Other Variations
        1. NOTATION
      6. 11.4.6 Applications
    8. References
    9. Glossary for Chapter 11
      1. Figure 11.1.1
      2. Figure 11.1.2
      3. Figure 11.1.3
      4. Figure 11.1.4
      5. Figure 11.1.5
      6. Figure 11.1.6
      7. Figure 11.1.7
      8. Figure 11.2.1
      9. Figure 11.2.2
      10. Figure 11.2.3
      11. Figure 11.2.4
      12. Figure 11.3.1
      13. Figure 11.3.2
      14. Figure 11.3.3
      15. Figure 11.3.4
      16. Figure 11.3.5
      17. Figure 11.3.6
      18. Figure 11.3.7
      19. Figure 11.3.8
      20. Figure 11.3.9
      21. Figure 11.3.10
      22. Figure 11.3.11
      23. Figure 11.3.12
      24. Figure 11.4.1
      25. Figure 11.4.2
      26. Figure 11.4.3
      27. Figure 11.4.4
      28. Figure 11.4.5
      29. Figure 11.4.6
      30. Figure 11.4.7
      31. Figure 11.4.8
      32. Figure 11.4.9
  18. Chapter 12 Communication Networks
    1. Section 12.1 Complex Networks
      1. 12.1.1 Examples of Complex Networks
      2. 12.1.2 Properties of Complex Networks
      3. 12.1.3 Random Graphs with General Degree Distributions
      4. 12.1.4 On-Line Models of Complex Networks
        1. Preferential Attachment Model
        2. The Copying Model
        3. Iterated Local Transitivity Model
      5. 12.1.5 Geometric Models for Complex Networks
      6. 12.1.6 Percolation in a General Host Graph
      7. 12.1.7 PageRank for Ranking Nodes
      8. 12.1.8 Network Games
    2. References
    3. Section 12.2 Broadcasting and Gossiping
      1. 12.2.1 Broadcasting
        1. Minimum Broadcast Trees
        2. B(n) and Minimum Broadcast Graphs
        3. Construction of Sparse Broadcast Graphs
        4. Bounded Degree Broadcast Graphs
      2. 12.2.2 Gossiping
        1. Optimal Gossip Graphs
        2. Minimum Gossip Graphs
      3. 12.2.3 Other Variations of Broadcasting and Gossiping
    4. References
    5. Section 12.3 Communication Network Design Models 1495
      1. 12.3.1 General Network Design Model
        1. Preliminaries
          1. SUMMARY OF NOTATION
        2. General Edge-Based Flow Model
        3. General Model: Edge-Flow [GM:EF]
        4. General Path-Flow Model
        5. General Model: Path-Flow [GM:PF]
      2. 12.3.2 Uncapacitated Network Design
        1. Uncapacitated Network Design [UND]
          1. ASSUMPTIONS
        2. Multi-Level Network Design
        3. Multi-Level Network Design Model [MLND]
        4. MLND Composite Heuristic
      3. 12.3.3 Survivable Network Design (SND)
        1. Uncapacitated Survivable Network Design [SNDUnc]
        2. Cut-Based Formulation of SND [SND-CUT]
        3. SND Iterative Rounding Heuristic
        4. Flow-Based Formulation of SND [SND-FLOW]
        5. Survivable Network Design: Bounded Cycles
      4. 12.3.4 Capacitated Network Design
        1. Network Loading Problem [NLP]
        2. Capacitated Concentrator Location [CCL]
        3. Capacitated Concentrator Location Model [CCL]
        4. Survivable Network Design (Capacitated)
        5. Diversification and Reservation Model [DR]
        6. p-Cycle Protection Model [PP]
    6. References
    7. Section 12.4 Network Science for Graph Theorists
      1. 12.4.1 Network Measures and Properties
        1. Structural Measures: Centrality
      2. 12.4.2 Other Structural Measures
        1. Reciprocity on Dyads
        2. Transitivity on Triads
        3. Balance on Triads
        4. Communities and Partitions
      3. 12.4.3 Attribute or Data Measures
        1. Similarity
        2. Homophily
      4. 12.4.4 Process Measures
      5. 12.4.5 Modeling with Networks
      6. 12.4.6 Process Dynamics
      7. 12.4.7 Structural Classification
      8. 12.4.8 Future Directions
    8. References
    9. Glossary for Chapter 12
      1. Figure 12.2.1
      2. Figure 12.2.2
      3. Figure 12.2.3
      4. Figure 12.2.4
      5. Figure 12.2.5
      6. Figure 12.2.6
      7. Figure 12.2.7
      8. Figure 12.2.8
      9. Figure 12.3.1
      10. Figure 12.3.2
      11. Figure 12.3.3
      12. Figure 12.3.4
      13. Figure 12.3.5
      14. Figure 12.3.6
      15. Figure 12.4.1
      16. Figure 12.4.2
      17. Figure 12.4.3
      18. Figure 12.4.4
      19. Figure 12.4.5
      1. Table 12.1
      2. Table 12.2
      3. Table 12.3
  19. Chapter 13 Natural Science & Processes
    1. Section 13.1 Chemical Graph Theory
      1. 13.1.1 Basic Definitions
      2. 13.1.2 Molecular Energy
      3. 13.1.3 Graph Nullity and Zero-Energy States
      4. 13.1.4 Graph-Based Molecular Descriptors
      5. 13.1.5 Walk-Based Molecular Parameters
      6. 13.1.6 Vibrational Analysis of Graphs
    2. References
    3. Section 13.2 Ties between Graph Theory and Biology
      1. 13.2.1 Biological Primer
      2. 13.2.2 Graphs in Sequencing and Mapping
        1. Interval Graphs in DNA Mapping
        2. Adjoint Graphs in DNA Sequencing
        3. Quasi-Adjoint Graphs in DNA Sequencing
        4. Labeled Graphs in DNA Assembling
      3. 13.2.3 Probabilistics and Graphs
        1. Graphical Models of TF Binding
        2. Learning Graphical Models
      4. 13.2.4 Hypergraphs in Biology
      5. Acknowledgments
    4. References
    5. Glossary for Chapter 13
      1. Figure 13.2.1
      2. Figure 13.2.2
      3. Figure 13.2.3
      4. Figure 13.2.4
      5. Figure 13.2.5
      6. Figure 13.2.6
      7. Figure 13.2.7
      8. Figure 13.2.8
      9. Figure 13.2.9
      10. Figure 13.2.10
      11. Figure 13.2.11
      12. Figure 13.2.12

Product information

  • Title: Handbook of Graph Theory, 2nd Edition
  • Author(s): Jonathan L. Gross, Jay Yellen, Ping Zhang
  • Release date: December 2013
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781498761369