You are previewing Topics in Structural Graph Theory.
O'Reilly logo
Topics in Structural Graph Theory

Book Description

The rapidly expanding area of structural graph theory uses ideas of connectivity to explore various aspects of graph theory and vice versa. It has links with other areas of mathematics, such as design theory and is increasingly used in such areas as computer networks where connectivity algorithms are an important feature. Although other books cover parts of this material, none has a similarly wide scope. Ortrud R. Oellermann (Winnipeg), internationally recognised for her substantial contributions to structural graph theory, acted as academic consultant for this volume, helping shape its coverage of key topics. The result is a collection of thirteen expository chapters, each written by acknowledged experts. These contributions have been carefully edited to enhance readability and to standardise the chapter structure, terminology and notation throughout. An introductory chapter details the background material in graph theory and network flows and each chapter concludes with an extensive list of references.

Table of Contents

  1. Cover
  2. Copyright
  3. Contents
  4. Foreword by Ortrud R. Oellermann
  5. Preface
  6. Preliminaries
    1. 1. Graph theory
    2. 2. Connectivity
    3. 3. Flows in networks
  7. 1 Menger’s theorem
    1. 1. Introduction
    2. 2. Vertex-connectivity
    3. 3. Edge-connectivity
    4. 4. Mixed connectivity
    5. 5. Average connectivity
    6. 6. Menger results for paths of bounded length
    7. 7. Connectivity of sets
    8. 8. Connecting with trees
  8. 2 Maximally connected graphs
    1. 1. Introduction
    2. 2. Maximally edge-connected graphs
    3. 3. Maximally edge-connected digraphs
    4. 4. Maximally locally edge-connected graphs and digraphs
    5. 5. Maximally connected and maximally locally connected graphs and digraphs
    6. 6. Restricted edge-connectivity
    7. 7. Conditional vertex-connectivity and edge-connectivity
  9. 3 Minimal connectivity
    1. 1. Introduction
    2. 2. Edge-deletion
    3. 3. Vertex-deletion
    4. 4. Edge-contraction
    5. 5. Generalized criticality
    6. 6. Reduction methods
    7. 7. Subgraph-deletion
    8. 8. Partitions under connectivity constraints
    9. 9. Line graphs
  10. 4 Contractions of k-connected graphs
    1. 1. Introduction
    2. 2. Contractible edges in 3-connected graphs
    3. 3. Contractible edges in 4-connected graphs
    4. 4. Contractible edges in k-connected graphs
    5. 5. Contraction-critical 5-connected graphs
    6. 6. Local structure and contractible edges
    7. 7. Concluding remarks
  11. 5 Connectivity and cycles
    1. 1. Introduction
    2. 2. Generalizations of classical results
    3. 3. Relative lengths of paths and cycles
    4. 4. Regular graphs
    5. 5. Bipartite graphs
    6. 6. Claw-free graphs
    7. 7. Planar graphs
    8. 8. The Chvátal–Erdős condition
    9. 9. Ordered graphs
    10. 10. Numbers of cycles
  12. 6 H-linked graphs
    1. 1. Introduction
    2. 2. k-linked graphs
    3. 3. Weak linkage
    4. 4. Digraphs
    5. 5. Modulo and parity linkage
    6. 6. Disjoint connected subgraphs
    7. 7. The disjoint paths problem
    8. 8. H-linked graphs
    9. 9. H-extendible graphs
  13. 7 Tree-width and graph minors
    1. 1. Introduction
    2. 2. Subtree intersection representation
    3. 3. Tree decomposition and tree-width
    4. 4. Tree decompositions decompose
    5. 5. Excluding planar minors
    6. 6. Wagner’s conjecture
    7. 7. The dual of tree-width
    8. 8. A canonical tree decomposition
    9. 9. Wagner’s conjecture for arbitrary graphs
    10. 10. Efficient characterization of H-minor-free graphs
  14. 8 Toughness and binding numbers
    1. 1. Introduction
    2. 2. Toughness and connectivity
    3. 3. Toughness and cycles
    4. 4. Toughness and k-factors
    5. 5. Binding number
    6. 6. Binding number and k-factors
    7. 7. Binding numbers and cycles
    8. 8. Other measures of vulnerability
  15. 9 Graph fragmentability
    1. 1. Introduction
    2. 2. Values and bounds for fragmentability
    3. 3. Reduction and separation
    4. 4. Bounded degree classes
    5. 5. Planarization
    6. 6. Applications
    7. 7. Monochromatic components
    8. 8. Open problems
  16. 10 The phase transition in random graphs
    1. 1. Introduction
    2. 2. The Erdős–Rényi theorem: the double jump
    3. 3. Correction: no double jump
    4. 4. The phase transition – simple results
    5. 5. Exploring components
    6. 6. The phase transition – finer results
    7. 7. The young giant
    8. 8. Final words
  17. 11 Network reliability and synthesis
    1. 1. Introduction
    2. 2. Domination in digraphs
    3. 3. Coherent systems and domination in graphs
    4. 4. Computational complexity of reliability
    5. 5. Synthesis of reliable networks
    6. 6. Other measures of vulnerability
  18. 12 Connectivity algorithms
    1. 1. Introduction
    2. 2. Computing the edge-connectivity
    3. 3. Computing the arc-connectivity
    4. 4. Computing the vertex-connectivity
    5. 5. Concluding remarks
  19. 13 Using graphs to find the best block designs
    1. 1. What makes a block design good?
    2. 2. Graphs from block designs
    3. 3. Statistical issues
    4. 4. Highly patterned block designs
    5. 5. D-optimality
    6. 6. A-optimality
    7. 7. E-optimality
    8. 8. Some history
    9. 9. Block size 2
    10. 10. Low average replication
    11. 11. Further reading
  20. Notes on contributors
  21. Index