Handbook of Graph Theory, 2nd Edition

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.

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.

Show and hide more Table of contents Product information

Preliminaries
Discrete Mathematics and its Applications
Dedication
Preface
1. Format
2. Terminology and Notation
3. Acknowledgments
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
    1. Degree
    2. Walks, Trails, and Paths
    3. Distance and Connectivity
    1. Isomorphism
    2. Automorphisms
    3. Subgraphs
    4. Graph Operations
    1. Acyclic Graphs
    2. Trees as Subgraphs
    3. Basic Tree-Growing Algorithm
    4. Prioritizing the Edge Selection
    1. 1.2.1 Building Blocks
    2. 1.2.2 Symmetry
      1. Local Symmetry: Regularity
      2. Global Symmetry: Vertex-Transitivity
      1. Cycle Rank
      2. Chromatic Number and k-Partite Graphs
      3. K-Connectivity and K-Edge-Connectivity
      4. Minimum Genus
      1. 1.3.1 Traversability
        
        The Königsberg Bridges Problem
        
        Diagram-Tracing Puzzles
        
        Hamiltonian Graphs
        
        Counting Trees
        
        Chemical Trees
        
        Euler's Polyhedron Formula
        
        Planar Graphs
        
        Graphs on Higher Surfaces
        
        The Four-Color Problem
        
        Other Graph Coloring Problems
        
        Factorization
        
        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
        
        Section 2.1 Computer Representations of Graphs
        
        2.1.1 Basic Representations for Graphs
        
        2.1.2 Graph Traversal Algorithms
        
        Depth-First Search
        
        Breadth-First Search
        
        All-Pairs Shortest-Paths Algorithm
        
        Transitive Closure
        
        Kleene's Algorithm
        
        2.2.1 Isomorphisms and Automorphisms
        
        Basic Terminology
        
        Related Isomorphism Problems
        
        Search Tree
        
        Software
        
        2.3.1 Two Reconstruction Conjectures
        
        Decks and Edge-Decks
        
        Reconstructibility
        
        The Reconstruction Conjecture
        
        The Edge-Reconstruction Conjecture
        
        Comparing Reconstruction with Edge-Reconstruction
        
        Reconstruction and Graph Symmetries
        
        Reconstructible Parameters
        
        Reconstructible Classes
        
        Endvertex-Reconstruction
        
        Reconstruction Numbers
        
        Set Reconstruction
        
        Reconstruction from the Characteristic Polynomial Deck
        
        Reconstructing from k-Vertex-Deleted Subgraphs
        
        Kocay's Parameter
        
        Characteristic and Chromatic Polynomials
        
        The Nash–Williams Lemma
        
        Structures Other than Graphs
        
        The Reconstruction Index of Groups
        
        2.4.1 Some Parameterized Families of Graph Classes
        
        Trees
        
        Series-Parallel Graphs
        
        k-Trees and Partial k-Trees
        
        Halin Graphs
        
        Bandwidth-k Graphs
        
        Treewidth-k Graphs
        
        Pathwidth-k Graphs
        
        Branchwidth-k Graphs
        
        k-Terminal Graphs
        
        Cographs
        
        Cliquewidth-k Graphs
        
        k-NLC Graphs
        
        k-HB Graphs
        
        Relationships between Recursive Classes
        
        Characterizations
        
        Recognition of Recursive Classes
        
        2.5.1 Perfect Graphs
        
        ANOTHER FACT, ALSO FIRST CONJECTURED BY BERGE
        
        Outline of the Proof of the Strong Perfect Graph Theorem
        
        Claw-Free Graphs
        
        Quasi-Line Graphs
        
        Bull-Free Graphs
        
        INFORMAL DEFINITIONS
        
        Using Trigraphs: Structure Theorems
        
        Using Trigraphs: Algorithms
        
        Testing for Pyramids: the Shortest Paths Detector
        
        Easily Detectable Configurations; Cleaning; Finding Odd Holes
        
        Testing for Even Holes
        
        More Algorithms
        
        The Three-in-a-Tree Problem
        
        Tournaments
        
        χ-Boundedness
        
        Outline of the Proof of Fact F40
        
        On the Proof of Fact F46
        
        The Edge-Disjoint Paths Problem
        
        The Vertex-Disjoint Paths Problem
        
        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
        
        Section 3.1 Basic Digraph Models and Properties
        
        3.1.1 Terminology and Basic Facts
        
        Reachability and Connectivity
        
        Measures of Digraph Connectivity
        
        Directed Trees
        
        Tree-Growing in a Digraph
        
        Oriented Graphs
        
        Adjacency Matrix of a Digraph
        
        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
        
        Rooted Tree Terminology
        
        Binary Search
        
        3.2.1 Examples and Basic Facts
        
        3.2.2 Rooted Trees
        
        Definitions for Rooted Trees
        
        Spanning Directed Trees
        
        Functional Graphs
        
        Optimization
        
        3.3.1 Basic Definitions and Examples
        
        Regular Tournaments
        
        Arc Reversals
        
        Condensation and Transitive Tournaments
        
        Cycles and Paths in Tournaments
        
        Hamiltonian Cycles and Kelly’s Conjecture
        
        Higher Connectivity
        
        Anti-Directed Paths
        
        The Second Neighborhood of a Vertex
        
        Smallest Feedback Sets
        
        Acyclic Subdigraphs and Transitive Sub-Tournaments
        
        Arc-Disjoint Cycles
        
        Tournaments Containing Oriented Trees
        
        Arc-Colorings and Monochromatic Paths
        
        Deciding Who Won
        
        Tournaments That Are Majority Digraphs
        
        Agendas
        
        Division Trees and Sophisticated Decisions
        
        Inductively Determining the Sophisticated Decision
        
        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 4.1 Connectivity: Properties and Structure
        
        4.1.1 Connectivity Parameters
        
        Preliminaries
        
        Vertex- and Edge-Connectivity
        
        Relationships Among the Parameters
        
        Some Simple Observations
        
        Internally-Disjoint Paths and Whitney's Theorem
        
        Strong Connectivity in Digraphs
        
        An Application to Interconnection Networks
        
        Menger's Theorems
        
        Other Versions and Generalizations of Menger's Theorem
        
        Another Menger-Type Theorem
        
        Whitney's Theorem
        
        Other Characterizations
        
        Cycles Containing Prescribed Vertices
        
        The Lovász—Woodall Conjecture
        
        Paths with Prescribed Initial and Final Vertices
        
        Subgraphs
        
        Contractions and Splittings
        
        Subgraph Contraction
        
        Edge Deletion
        
        Vertex Deletion
        
        Products of Graphs
        
        Minimality and Criticality
        
        Vertex-Minimal Connectivity — Criticality
        
        Connectivity Augmentation
        
        4.2.1 Basic Definitions and Characterizations
        
        Some Basic Characterizations
        
        Characterizations Based on Partition Cuts
        
        The Splitting and Detachment Operations
        
        Covering Walks and Double Tracings
        
        Maze Searching
        
        Covers, Double Covers, and Packings
        
        Three Optimization Problems
        
        Nowhere-Zero Flows
        
        Incidence-Partition and Transition Systems
        
        Orderings of the Incidence Set, Non-Intersecting Tours, and A-Trails
        
        The Kappa Transformations
        
        Splicing the Trails in a Trail Decomposition
        
        4.3.1 The Basic Problem and Its Variations
        
        The Eulerian Case
        
        Variations of CPP
        
        Producing an Eulerian Tour in a Symmetric (Multi)Digraph
        
        Deciding if a Mixed Graph Is Eulerian
        
        The Postman Problem for Mixed Graphs
        
        Approximation Algorithm ES
        
        Approximate Algorithm SE
        
        Some Performance Bounds
        
        4.4.1 DeBruijn Graph Basics
        
        DeBruijn Sequences
        
        DeBruijn Graphs
        
        Algorithm
        
        Necklaces and Lyndon Words
        
        4.5.1 History
        
        4.5.2 The Classic Attacks
        
        Degrees
        
        Other Counts
        
        Powers and Line Graphs
        
        Planar Graphs
        
        Adding Toughness
        
        More Than Hamiltonian
        
        A Second Hamiltonian Cycle
        
        Many Hamiltonian Cycles
        
        Uniquely Hamiltonian Graphs
        
        Products and Hamiltonian Decompositions
        
        4.6.1 The Traveling Salesman Problem
        
        Symmetric and Asymmetric TSP
        
        Matrix Representation of TSP
        
        Algorithmic Complexity
        
        Exact and Approximate Algorithms
        
        The Euclidean TSP
        
        Integer Programming Approaches
        
        Greedy-Type Algorithms
        
        Insertion Algorithms
        
        Minimum Spanning Tree Heuristics
        
        Worst Case Analysis of Heuristics
        
        Exponential Neighborhoods
        
        Transforming Generalized TSP to TSP
        
        Exact Algorithms
        
        Approximate Algorithms
        
        Exact Algorithms
        
        Heuristics for CVRP
        
        Savings Heuristics
        
        Insertion Heuristics
        
        Two-phase Heuristics
        
        4.7.1 High Connectivity
        
        Minimum Degree and Diameter
        
        Degree Sequence
        
        Distance
        
        Super Edge-Connectivity
        
        Digraphs
        
        Oriented Graphs
        
        Semigirth
        
        Line Digraphs
        
        Girth
        
        Girth Pair
        
        Cages
        
        Large Digraphs
        
        Large Graphs
        
        π-Semigirth
        
        Imbeddings
        
        Adjacency Spectrum
        
        Laplacian Spectrum
        
        Boundaries, Fragments, and Atoms
        
        Fragments and Atoms in Undirected Graphs
        
        Fragments and Atoms in Digraphs
        
        Graphs with Symmetry
        
        Cayley Graphs
        
        Circulant Graphs
        
        Distance-Regular Graphs
        
        Conditional Connectivity
        
        Restricted Connectivity
        
        Distance Connectivity
        
        High Distance Connectivity
        
        Maximal Connectivity
        
        Hamiltonian Connectivity
        
        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
        
        Section 5.1 Graph Coloring
        
        5.1.1 General Concepts
        
        Proper Vertex-Coloring and Chromatic Number
        
        List Coloring and Choice Number
        
        The Hajós Construction
        
        Lovász's Topological Lower Bound
        
        Alon and Tarsi's Graph Polynomial Characterization
        
        List Reduction
        
        Uniquely Colorable Graphs
        
        The Conjectures of Hadwiger and Hajós
        
        Snarks
        
        Uniquely Edge-Colorable Graphs
        
        Further χ-Bound Graph Classes
        
        Paths and Cycles
        
        Eulerian Subgraphs
        
        Choosability and Orientations with Kernels
        
        Acyclic Orientations
        
        Coloring Euclidean Spaces and Distance Graphs
        
        5.2.1 Multicoloring and Fractional Coloring
        
        5.2.2 Graphs on Surfaces
        
        Heawood Number and the Empire Problem
        
        Nowhere-Zero Flows
        
        Chromatic Polynomials
        
        Variants of Proper Coloring
        
        Graph Homomorphisms
        
        Coloring with Costs
        
        Vertex Ranking
        
        Non-Repetitive (Thue) Colorings
        
        Partial Colorings and Extensions
        
        Coloring Cubic Graphs with Triple Systems
        
        Neighbor-Distinguishing Colorings
        
        Maximizing the Number of Colors
        
        Partitions with Weaker Requirements
        
        Clique Hypergraphs
        
        Approximation
        
        5.3.1 Basic Definitions and Applications
        
        Some Combinatorial Optimization Problems
        
        Vertex-Weighted Graphs
        
        Applications Involving Hamming Distance
        
        Two More Formulations of the Maximum-Clique Problem
        
        Lower Bounds
        
        Upper bounds
        
        Clique Enumeration
        
        Maximum-Clique and Maximum-Weight-Clique Algorithms
        
        Construction Heuristics and Local Search
        
        Tabu Search
        
        5.4.1 Preliminaries
        
        5.4.2 1-Factors
        
        Conditions for a Graph to Have a 1-Factor
        
        The Number of 1-Factors: Bounds
        
        1-Factors in Bipartite Graphs
        
        The Number of 1-Factors: Exact Counting
        
        k-factors
        
        f-factors
        
        [a,b]-factors
        
        (g,f)-factors
        
        Factors in Random Graphs
        
        Edge Partitions
        
        Vertex Partitions
        
        Factor Algorithms and Complexity
        
        Subgraph Problems
        
        Automated Timetabling: Historical Perspective
        
        The General Problem
        
        Times
        
        Resources
        
        Meetings
        
        Constraints
        
        The Basic Class-Teacher Timetabling Problem
        
        Extensions to the Basic Class-Teacher Problem
        
        Graph Models for Subproblems of the Class-Teacher Problem
        
        Basic Model
        
        A Graph Formulation
        
        Scheduling Multi-Section Courses
        
        Basic Model
        
        A More Compact Schedule
        
        The Breadth and Variation of Exam Timetabling Constraints
        
        Heuristic Methods
        
        Two Different Random-Selection Strategies
        
        Hybrid Graph-Coloring/Meta-Heuristic Approaches
        
        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
        
        5.6.1 Trees
        
        5.6.2 Cycle-Related Graphs
        
        5.6.3 Product-Related Graphs
        
        5.6.4 Complete Graphs
        
        5.6.5 Disconnected Graphs
        
        5.6.6 Joins of Graphs
        
        5.6.7 α-labelings
        
        Figure 5.3.1
        
        Figure 5.5.1
        
        Figure 5.5.2
        
        Figure 5.5.3
        
        Figure 5.5.4
        
        Figure 5.5.5
        
        Figure 5.5.6
        
        Figure 5.5.7
        
        Figure 5.5.8
        
        Figure 5.5.9
        
        Figure 5.5.10
        
        Figure 5.5.11
        
        Figure 5.5.12
        
        Section 6.1 Automorphisms
        
        6.1.1 The Automorphism Group of a Graph
        
        6.1.2 Graphs with Given Group
        
        Further Reading
        
        Further Reading
        
        Further Reading
        
        Strips
        
        Automorphisms and Distance
        
        Further Reading
        
        6.2.1 Construction and Recognition
        
        6.2.2 Prevalence
        
        6.2.3 Isomorphism
        
        6.2.4 Subgraphs
        
        6.2.5 Factorization
        
        6.2.6 Miscellaneous
        
        Embeddings
        
        Applications
        
        Further Reading
        
        6.3.1 Counting Simple Graphs and Multigraphs
        
        Labeled Graphs
        
        Unlabeled Graphs
        
        Labeled Digraphs
        
        Unlabeled Digraphs
        
        6.4.1 Basic Concepts and Definitions
        
        Subgraphs and Complements
        
        Components, Spanning Trees, and Cospanning Trees
        
        Cuts and Cutsets
        
        Vector Space of a Graph under Ring Sum of Its Edge Subsets
        
        Fundamental Circuits and the Dimension of the Circuit Subspace
        
        Fundamental Cutsets and the Dimension of the Cutset Subspace
        
        Orthogonality of Circuit and Cutset Subspaces
        
        Circ/Cut-Based Decomposition of Graphs and Subgraphs
        
        Circuit and Cut Vectors and Matrices
        
        Fundamental Circuit, Fundamental Cutset, and Incidence Matrices
        
        Orthogonality and the Matrix Tree Theorem
        
        Minty’s Painting Theorem
        
        Bicycle-Based Tripartition
        
        A Tripartition Based on Maximally Distant Spanning Trees
        
        Whitney and Kuratowski
        
        6.5.1 Basic Matrix Properties
        
        6.5.2 Walks and the Spectrum
        
        Walks and the Coefficients of the Characteristic Polynomial
        
        Walks and the Minimal Polynomial
        
        Regular Graphs
        
        Line Graphs and Generalized Line Graphs
        
        Root Systems
        
        Eigenvalue Bounds
        
        Further Reading
        
        Distance-Regular Graphs and the Hoffman Polynomial
        
        Strongly Regular Graphs
        
        Further Reading
        
        Eigenvalues and Graph Operations
        
        Further Reading
        
        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
        
        Bounds on the number of elements
        
        2-sums and 3-sums
        
        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
        
        Table 6.3.1
        
        Table 6.3.2
        
        Table 6.3.3
        
        Table 6.3.4
        
        Table 6.3.5
        
        Table 6.3.6
        
        Table 6.3.7
        
        Table 6.3.8
        
        Table 6.3.9
        
        Table 6.3.10
        
        Table 6.3.11
        
        Table 6.3.12
        
        Table 6.3.13
        
        Table 6.3.14
        
        Table 6.6.1
        
        Table 6.6.2
        
        Table 6.6.3
        
        Table 6.6.4
        
        Table 6.6.5
        
        Table 6.6.6
        
        Section 7.1 Graphs on Surfaces
        
        7.1.1 Surfaces
        
        2-Manifolds and 2-Pseudomanifolds
        
        Some Standard Surfaces
        
        Surface Operations and Classification
        
        Algorithm
        
        7.2.1 Definitions and Basic Facts
        
        Ear Decomposition
        
        Edge Insertion and Deletion
        
        Minimum Genus
        
        Maximum Genus
        
        Lower Bounds on Minimum Genus
        
        Lower Bounds on Maximum Genus
        
        Minimum Genus Algorithms
        
        Maximum Genus Algorithms
        
        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
        
        Bar Amalgamations
        
        Vertex Amalgamations
        
        7.4.1 Regular Voltage Graphs
        
        Fibers
        
        Bouquets and Dipoles
        
        Net Voltages
        
        The Local Group
        
        Natural Automorphisms
        
        Coverings and Branched Coverings of Surfaces
        
        Using Voltage Graph Constructions
        
        Action of the Group of Covering Transformations
        
        Applications of Imbedded Voltage Graphs and Topological Current Graphs
        
        7.5.1 Symmetric Imbeddings of Cayley Graphs
        
        7.5.2 Riemann—Hurwitz Equation; Hurwitz’s Theorem
        
        7.5.3 Groups of Low Genus
        
        7.5.4 Genus for Families of Groups
        
        7.5.5 Non-Orientable Surfaces
        
        7.6.1 Maps and Polyhedral Maps
        
        7.6.2 Existence and Realizations of Polyhedral Maps
        
        7.6.3 Paths and Cycles in Maps
        
        7.6.4 Map Coloring
        
        7.6.5 Combinatorial Schemes
        
        7.6.6 Maps and Universal Tessellations
        
        7.6.7 Highly Symmetrical Maps
        
        7.6.8 Enumeration of Maps
        
        7.7.1 Basic Concepts
        
        7.7.2 Coloring Densely Imbeddable Graphs
        
        Coloring with Few Colors
        
        Coloring Graphs that Quadrangulate
        
        Coloring Graphs That Triangulate
        
        LEW-Imbeddings
        
        Imbeddings and Connectivity
        
        Imbeddings and Genus
        
        Re-Imbedding Results
        
        Surface Minors
        
        Finding Imbedded Cycles
        
        Similarity Classes on the Torus
        
        Kernels
        
        7.8.1 Basic Concepts
        
        Notations
        
        Triangulations with Complete Graphs
        
        Minimum Triangulations
        
        Covering Constructions
        
        Edge Contraction
        
        Classification and Finiteness in Number
        
        Other Irreducibility
        
        Estimating Bounds
        
        Catalan Triangulations
        
        Preserving Properties
        
        Equivalence over Imbeddings
        
        Uniqueness of Imbeddings
        
        Re-Imbedding Structures
        
        Imbeddings into Other Surfaces
        
        7.9.1 Finite Geometries
        
        7.9.2 Associated Graphs
        
        7.9.3 Surface Models
        
        7.10.1 Drawings of Graphs and Crossing Numbers
        
        Embeddings
        
        Drawings
        
        Crossing Numbers
        
        The Crossing Lemma
        
        Crossing Numbers, Bisection Width, and Cutwidth
        
        Crossing Numbers, Immersion, and Congestion
        
        Complete Bipartite Graphs
        
        Complete Graphs
        
        Other Families of Graphs
        
        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
        
        Table 7.1
        
        Section 8.1 Extremal Graph Theory
        
        8.1.1 Turán-Type Problems
        
        Turán's Theorem and Its Extensions
        
        Structural Properties of the Graphs G(n, tr(n) + 1)
        
        Books and Generalized Books
        
        Vertex-Disjoint Cliques
        
        The Structure of Extremal Graphs
        
        κr-Free Graphs with Large Minimal Degree
        
        Cycles of Consecutive Lengths
        
        Pancyclicity and Weak Pancyclicity
        
        Applications of the Uniformity and Blow-up lemmas
        
        8.2.1 Random Graph Models
        
        Asymptotics
        
        8.3.1 Ramsey’s Theorem
        
        Ramsey Numbers for Arbitrary Graphs
        
        Ramsey Numbers for Small Graphs
        
        Asymptotic Results
        
        Initial Generalized Ramsey Results
        
        Ramsey Numbers for Trees
        
        Cycle Ramsey Numbers
        
        Good Results
        
        Small Order Graphs
        
        Linear Bounds
        
        General Bounds
        
        Linear Bounds
        
        Bipartite Graphs
        
        Small Order Graphs
        
        Graphs
        
        Hypergraphs
        
        8.4.1 The First Moment Method
        
        Ramsey Numbers
        
        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
        
        Figure 8.2.1
        
        Figure 8.2.2
        
        Figure 8.3.1
        
        Figure 8.3.2
        
        Figure 8.3.3
        
        Figure 8.3.4
        
        Figure 8.3.5
        
        Figure 8.3.6
        
        Figure 8.5.1
        
        Figure 8.5.2
        
        Section 9.1 Distance in Graphs
        
        9.1.1 Standard Distance in Graphs
        
        Distance and Eccentricity
        
        Radius and Diameter
        
        Center and Periphery
        
        Self-Centered Graphs
        
        Geodetic Sets and Geodetic Numbers
        
        Convex Sets and Hull Sets
        
        Total Distance of a Vertex
        
        The Median of a Connected Graph
        
        Centers and Medians of a Connected Graph
        
        Steiner Radius and Steiner Diameter
        
        Steiner Centers
        
        Radius and Diameter in Strong Digraphs
        
        The Center of a Strong Digraph
        
        Strong Distance in Strong Digraphs
        
        Strong Centers of Strong Digraphs
        
        9.2.1 Dominating Sets in Graphs
        
        Equivalent Definitions of a Dominating Set
        
        Applications of Domination
        
        The Domination Chain
        
        Bounds in Terms of Order and Minimum Degree
        
        Minimum Degree Two
        
        Minimum Degree Three
        
        Cubic Graphs
        
        More Bounds Involving Minimum Degree
        
        Bounds in Terms of Size and Degree
        
        Bounds in Terms of Order and Maximum Degree
        
        Bounds in Terms of Order and Size
        
        Bounds in Terms of Packing
        
        Bounds in Terms of Radius
        
        9.3.1 Intersection Graphs and Their Applications
        
        Containment Graphs
        
        ɸ-Tolerance Graphs
        
        Threshold Tolerance and coTT Graphs
        
        Bounded Bitolerance Graphs and Ordered Sets
        
        Background
        
        The (h, s, t) Graphs: Degree Constrained Representations
        
        9.4.1 Fundamentals
        
        The Bandwidth Concept
        
        Applications
        
        Efficient Matrix Storage
        
        VLSI Layout
        
        Interconnection Networks
        
        Binary Constraint Satisfaction Problem
        
        The Bandwidth of Some Common Families of Graphs
        
        A Few Basic Relations
        
        On the Bandwidth of Trees
        
        Alternative Interpretations of Bandwidth
        
        Two General Bounds
        
        Subdivisions, Mergers, Contractions, and Edge Additions
        
        Nordhaus-Gaddum Types of Bounds
        
        Other Bounds
        
        Cartesian Product
        
        Sum of Two Graphs
        
        Corona and Composition
        
        Strong Product and Tensor Product
        
        Vertex Degree
        
        Number of Vertices and Edges for Arbitrary Graphs
        
        Number of Vertices and Edges for Graphs with no κ3
        
        Radius and Diameter
        
        Vertex and Edge Chromatic Number
        
        Vertex Independence and Vertex Cover Numbers
        
        Girth, Vertex Arboricity, and Thickness
        
        Bandsize
        
        Edgesum (Bandwidth Sum)
        
        Cyclic Bandwidth
        
        Edge-Bandwidth
        
        Profile
        
        Cutwidth
        
        Topological Bandwidth
        
        Additive Bandwidth
        
        9.5.1 Sweeping and Edge Search
        
        9.5.2 Node Search and Mixed Search
        
        9.5.3 Cops-and-Robbers
        
        9.5.4 Additional Variations
        
        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
        
        Table 9.1
        
        Section 10.1 Searching
        
        10.1.1 Breadth-First Search
        
        Ordered Trees
        
        Discovery Order
        
        Strong Components of a Directed Graph
        
        Bridges and Cutpoints of an Undirected Graph
        
        Planarity Testing
        
        Triconnectivity
        
        Ear Decomposition and st-numbering
        
        Reducibility
        
        Two Directed Spanning Trees
        
        Dominators
        
        Facts About Semidominators
        
        Algorithm
        
        10.2.1 Basic Terminology
        
        10.2.2 Dynamic Problems on Undirected Graphs
        
        General Techniques for Undirected Graphs
        
        Topology Trees
        
        Assumption
        
        Approach
        
        Approach
        
        Approach
        
        Approach
        
        Notation
        
        Approach
        
        Invariants
        
        Approach
        
        Invariant
        
        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
        
        Approach
        
        Approach
        
        Notation
        
        Notation
        
        Approach
        
        Approach
        
        Further Information
        
        Acknowledgments
        
        10.3.1 Types of Graphs and Drawings
        
        Types of Graphs
        
        Types of Drawings
        
        Delaunay Triangulations
        
        β-drawings and Rectangle of Influence Drawings
        
        Minimum Spanning Trees
        
        Minimum Weight Triangulations
        
        Properties of Drawings
        
        Bounds on the Area
        
        Bounds on the Angular Resolution
        
        Bounds on the Number of Bends
        
        Tradeoff Between Area and Aspect Ratio
        
        Tradeoff between Area and Angular Resolution
        
        Planarization
        
        Layering
        
        Physical Simulation
        
        Point-Set Embeddings and Universal Point Sets
        
        Simultaneous Embeddings
        
        Lombardi Drawings
        
        Drawings with Large Crossing Angles
        
        Drawings with Few Slopes
        
        Witness Proximity and Approximate Proximity Drawings
        
        Cluster Planarity
        
        Algorithm Design Strategy
        
        Maximum-Cardinality Independent Set in a Tree
        
        Maximum-Weight Independent Set in a Tree
        
        Maximum-Cardinality Independent Set in a Series-Parallel Graph
        
        Multiplication Tables for Series, Parallel, and Jacknife Operations
        
        Maximum-Cardinality Independent Set in a Treewidth-k Graph
        
        Monadic Second-Order Logic Expressions for a Graph
        
        MSOL-Expressible Graph Problems
        
        Three More Algorithms for Cographs
        
        Maximum-Cardinality Independent Set of a Cliquewidth-k Graph
        
        A Subset of the MSOL Expressions for a Graph
        
        Maximum-Cardinality Independent Set in a k-HB Graph
        
        A Subset of the MSOL' Expressions
        
        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
        
        10.6.1 Foundational Definitions and Results
        
        Isoperimetric Constants and Expander Families
        
        Relationship to Graph Spectra
        
        Ramanujan Graphs and the Alon–Boppana Theorem
        
        Group Representations and Kazhdan Constants
        
        Existence and Construction of Expander Families
        
        Ramanujan Graphs and Zeta Functions
        
        Group Structure and Expansion
        
        Random Graphs and Expansion Definitions
        
        10.7.1 Bar-Visibility Graphs
        
        10.7.2 Rectangle-Visibility Graphs
        
        10.7.3 Visibility Representations in ℝ3
        
        10.7.4 Box-Visibility Graphs
        
        10.7.5 Bar k-Visibility Graphs
        
        10.7.6 Bar Visibility Number
        
        10.7.7 Other Visibility Graphs
        
        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
        
        Section 11.1 Maximum Flows
        
        11.1.1 The Basic Maximum Flow Problem
        
        11.1.2 Minimum Cuts and Duality
        
        Cuts in a Network
        
        Weak Duality
        
        The Residual Network and Flow-Augmenting Paths
        
        Ford–Fulkerson Algorithm
        
        Preflow-Push Algorithms
        
        Multicommodity Flow
        
        Variants of Multicommodity Flow Problems
        
        11.2.1 The Basic Model and Definitions
        
        Residual Networks
        
        A Basic Cycle-Canceling Algorithm
        
        A Transshipment Problem Associated with a Minimum Cost Flow Problem
        
        A Primal-Dual Algorithm
        
        A Push-Relabel Algorithm
        
        Strongly Polynomial Algorithms
        
        Convex Cost Flows
        
        Flows Over Time
        
        Flows with Losses and Gains
        
        11.3.1 Matchings
        
        Basic Terminology
        
        Some Fundamental Results
        
        Bipartite Maximum-Size Matching Algorithm
        
        Bipartite Maximum-Weight Matching Algorithm
        
        Gale–Shapley Algorithm
        
        11.4.1 Solvability
        
        NOTATION
        
        Weight Functions
        
        Complexity
        
        Diameter, Connectivity, and Class 0
        
        Complexity
        
        Complexity
        
        NOTATION
        
        NOTATION
        
        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
        
        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
        
        Preferential Attachment Model
        
        The Copying Model
        
        Iterated Local Transitivity Model
        
        12.2.1 Broadcasting
        
        Minimum Broadcast Trees
        
        B(n) and Minimum Broadcast Graphs
        
        Construction of Sparse Broadcast Graphs
        
        Bounded Degree Broadcast Graphs
        
        Optimal Gossip Graphs
        
        Minimum Gossip Graphs
        
        12.3.1 General Network Design Model
        
        Preliminaries
        
        SUMMARY OF NOTATION
        
        Uncapacitated Network Design [UND]
        
        ASSUMPTIONS
        
        Uncapacitated Survivable Network Design [SNDUnc]
        
        Cut-Based Formulation of SND [SND-CUT]
        
        SND Iterative Rounding Heuristic
        
        Flow-Based Formulation of SND [SND-FLOW]
        
        Survivable Network Design: Bounded Cycles
        
        Network Loading Problem [NLP]
        
        Capacitated Concentrator Location [CCL]
        
        Capacitated Concentrator Location Model [CCL]
        
        Survivable Network Design (Capacitated)
        
        Diversification and Reservation Model [DR]
        
        p-Cycle Protection Model [PP]
        
        12.4.1 Network Measures and Properties
        
        Structural Measures: Centrality
        
        Reciprocity on Dyads
        
        Transitivity on Triads
        
        Balance on Triads
        
        Communities and Partitions
        
        Similarity
        
        Homophily
        
        Figure 12.2.1
        
        Figure 12.2.2
        
        Figure 12.2.3
        
        Figure 12.2.4
        
        Figure 12.2.5
        
        Figure 12.2.6
        
        Figure 12.2.7
        
        Figure 12.2.8
        
        Figure 12.3.1
        
        Figure 12.3.2
        
        Figure 12.3.3
        
        Figure 12.3.4
        
        Figure 12.3.5
        
        Figure 12.3.6
        
        Figure 12.4.1
        
        Figure 12.4.2
        
        Figure 12.4.3
        
        Figure 12.4.4
        
        Figure 12.4.5
        
        Table 12.1
        
        Table 12.2
        
        Table 12.3
        
        Section 13.1 Chemical Graph Theory
        
        13.1.1 Basic Definitions
        
        13.1.2 Molecular Energy
        
        13.1.3 Graph Nullity and Zero-Energy States
        
        13.1.4 Graph-Based Molecular Descriptors
        
        13.1.5 Walk-Based Molecular Parameters
        
        13.1.6 Vibrational Analysis of Graphs
        
        13.2.1 Biological Primer
        
        13.2.2 Graphs in Sequencing and Mapping
        
        Interval Graphs in DNA Mapping
        
        Adjoint Graphs in DNA Sequencing
        
        Quasi-Adjoint Graphs in DNA Sequencing
        
        Labeled Graphs in DNA Assembling
        
        Graphical Models of TF Binding
        
        Learning Graphical Models
        
        Figure 13.2.1
        
        Figure 13.2.2
        
        Figure 13.2.3
        
        Figure 13.2.4
        
        Figure 13.2.5
        
        Figure 13.2.6
        
        Figure 13.2.7
        
        Figure 13.2.8
        
        Figure 13.2.9
        
        Figure 13.2.10
        
        Figure 13.2.11
        
        Figure 13.2.12
        
        Show and hide more
        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