You are previewing Circuit Double Cover of Graphs.
O'Reilly logo
Circuit Double Cover of Graphs

Book Description

The famous Circuit Double Cover conjecture (and its numerous variants) is considered one of the major open problems in graph theory owing to its close relationship with topological graph theory, integer flow theory, graph coloring and the structure of snarks. It is easy to state: every 2-connected graph has a family of circuits covering every edge precisely twice. C.-Q. Zhang provides an up-to-date overview of the subject containing all of the techniques, methods and results developed to help solve the conjecture since the first publication of the subject in the 1940s. It is a useful survey for researchers already working on the problem and a fitting introduction for those just entering the field. The end-of-chapter exercises have been designed to challenge readers at every level and hints are provided in an appendix.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright
  4. Dedication Page
  5. Contents
  6. Foreword (by Brian Alspach)
  7. Foreword (by Michael Tarsi)
  8. Preface
  9. Chapter 1: Circuit Double Cover
    1. 1.1 Circuit Double Cover Conjecture
    2. 1.2 Minimal Counterexamples
    3. 1.3 3-Edge-Coloring and Even Subgraph Cover
    4. 1.4 Circuit Double Covers and Graph Embeddings
    5. 1.5 Open Problems
    6. 1.6 Exercises
  10. Chapter 2: Faithful Circuit Cover
    1. 2.1 Faithful Circuit Cover
    2. 2.2 3-Edge-Coloring and Faithful Cover
    3. 2.3 Construction of Contra Pairs
    4. 2.4 Open Problems
    5. 2.5 Exercises
  11. Chapter 3: Circuit Chain and Petersen Minor
    1. 3.1 Weight Decomposition and Removable Circuit
    2. 3.2 Cubic Minimal Contra Pair
    3. 3.3 Minimal Contra Pair
    4. 3.4 Structure of Circuit Chain
    5. 3.5 Open Problems
    6. 3.6 Exercises
  12. Chapter 4: Small Oddness
    1. 4.1 k-Even Subgraph Double Covers
    2. 4.2 Small oddness
    3. 4.3 Open Problems
    4. 4.4 Exercises
  13. Chapter 5: Spanning Minor, Kotzig Frames
    1. 5.1 Spanning Kotzig Subgraphs
    2. 5.2 Kotzig Frames
    3. 5.3 Construction of Kotzig Graphs
    4. 5.4 Three-Hamilton Circuit Double Covers
    5. 5.5 Open Problems
    6. 5.6 Exercises
  14. Chapter 6: Strong Circuit Double Cover
    1. 6.1 Circuit Extension and Strong CDC
    2. 6.2 Thomason’s Lollipop Method
    3. 6.3 Stable Circuits
    4. 6.4 Extension-Inheritable Properties
    5. 6.5 Extendable Circuits
    6. 6.6 Semi-Extension of Circuits
    7. 6.7 Circumferences
    8. 6.8 Open Problems
    9. 6.9 Exercises
  15. Chapter 7: Spanning Trees, Supereulerian Graphs
    1. 7.1 Jaeger Theorem: 2-Even Subgraph Covers
    2. 7.2 Jaeger Theorem: 3-Even Subgraph Covers
    3. 7.3 Even Subgraph 2k-Covers
    4. 7.4 Catlin’s Collapsible Graphs
    5. 7.5 Exercises
  16. Chapter 8: Flows and Circuit Covers
    1. 8.1 Jaeger Theorems: 4-Flow and 8-Flow
    2. 8.2 4-Flows
    3. 8.3 Seymour Theorem: 6-Flow
    4. 8.4 Contractible Configurations for 4-Flow
    5. 8.5 Bipartizing Matching, Flow Covering
    6. 8.6 Exercises
  17. Chapter 9: Girth, Embedding, Small Cover
    1. 9.1 Girth
    2. 9.2 Small Genus Embedding
    3. 9.3 Small Circuit Double Covers
    4. 9.4 Exercises
  18. Chapter 10: Compatible Circuit Decompositions
    1. 10.1 Introduction
    2. 10.2 Relation with Faithful Circuit Cover
    3. 10.3 Counterexamples and Graph Minor Related Results
    4. 10.4 Planar Graphs
    5. 10.5 Dominating Circuit and Sabidussi Conjecture
    6. 10.6 Construction of Contra Pairs
    7. 10.7 Open Problems
    8. 10.8 Exercises
  19. Chapter 11: Other Circuit Decompositions
    1. 11.1 Restricted Circuit Decompositions
    2. 11.2 Open Problems
    3. 11.3 Exercises
  20. Chapter 12: Reductions of Weights, Coverages
    1. 12.1 Weight Reduction for Contra Pairs
    2. 12.2 Coverage Reduction with Fixed Parity
    3. 12.3 Exercises
  21. Chapter 13: Orientable Cover
    1. 13.1 Orientable Double Cover
    2. 13.2 Circular Double Covers and Modulo Orientations
    3. 13.3 Open Problems
    4. 13.4 Exercises
  22. Chapter 14: Shortest Cycle Covers
    1. 14.1 Shortest Cover and Double Cover
    2. 14.2 Minimum Eulerian Weight
    3. 14.3 3-Even Subgraph Covers
      1. 14.3.1 Basis of Cycle Space
      2. 14.3.2 3-Even Subgraph Covers
      3. 14.3.3 (≥ 4)-Even Subgraph Covers
      4. 14.3.4 Upper Bounds of SCC3
      5. 14.3.5 Relations with Other Major Conjectures
      6. 14.3.6 Fano Plane and Fano Flows
      7. 14.3.7 Incomplete Fano Flows, Fμ-Flows
      8. 14.3.8 Some Proofs
    4. 14.4 Open Problems
    5. 14.5 Exercises
  23. Chapter 15: Beyond Integer (1, 2)-Weight
    1. 15.1 Rational Weights
    2. 15.2 Group Weights
    3. 15.3 Integer Weights
      1. 15.3.1 Non-Negative Weights and Petersen Minor
      2. 15.3.2 Integer Semi-Group Weights
      3. 15.3.3 Small Range
    4. 15.4 Open Problems
    5. 15.5 Exercises
  24. Chapter 16: Petersen Chain and Hamilton Weights
    1. 16.1 Local Structures
    2. 16.2 Hamilton Weight
    3. 16.3 (K4)-Graphs
    4. 16.4 P10-Free Hamilton Weighted Graphs
    5. 16.5 Circuit Chain and Petersen Chain
    6. 16.6 Minimal Contra Pair
    7. 16.7 Open Problems
    8. 16.8 Exercises
  25. Appendix A Preliminary
    1. A.1 Fundamental Theorems
    2. A.2 Even Subgraphs and Parity Subgraphs
    3. A.3 Exercises
  26. Appendix B Snarks, Petersen Graph
    1. B.1 3-Edge-Coloring of Cubic Graphs, Snarks
      1. B.1.1 Parity Lemma
      2. B.1.2 Snarks
      3. B.1.3 Construction of Snarks
      4. B.1.4 Girths and Bonds of Snarks
      5. B.1.5 Small Snarks
    2. B.2 A Mini Encyclopedia of The Petersen Graph
    3. B.3 Exercises
    4. B.4 Various Drawings of The Petersen Graph
  27. Appendix C Integer Flow Theory
    1. C.1 Tutte’s Integer Flows
    2. C.2 Fundamental Lemmas
    3. C.3 Exercises
  28. Appendix D Hints for Exercises
  29. Glossary of Terms and Symbols
  30. References
  31. Author Index
  32. Subject Index