Book contents
- Frontmatter
- Contents
- Foreword
- Foreword
- Preface
- 1 Circuit double cover
- 2 Faithful circuit cover
- 3 Circuit chain and Petersen minor
- 4 Small oddness
- 5 Spanning minor, Kotzig frames
- 6 Strong circuit double cover
- 7 Spanning trees, supereulerian graphs
- 8 Flows and circuit covers
- 9 Girth, embedding, small cover
- 10 Compatible circuit decompositions
- 11 Other circuit decompositions
- 12 Reductions of weights, coverages
- 13 Orientable cover
- 14 Shortest cycle covers
- 15 Beyond integer (1, 2)-weight
- 16 Petersen chain and Hamilton weights
- Appendix A Preliminary
- Appendix B Snarks, Petersen graph
- Appendix C Integer flow theory
- Appendix D Hints for exercises
- Glossary of terms and symbols
- References
- Author index
- Subject index
1 - Circuit double cover
Published online by Cambridge University Press: 05 May 2012
- Frontmatter
- Contents
- Foreword
- Foreword
- Preface
- 1 Circuit double cover
- 2 Faithful circuit cover
- 3 Circuit chain and Petersen minor
- 4 Small oddness
- 5 Spanning minor, Kotzig frames
- 6 Strong circuit double cover
- 7 Spanning trees, supereulerian graphs
- 8 Flows and circuit covers
- 9 Girth, embedding, small cover
- 10 Compatible circuit decompositions
- 11 Other circuit decompositions
- 12 Reductions of weights, coverages
- 13 Orientable cover
- 14 Shortest cycle covers
- 15 Beyond integer (1, 2)-weight
- 16 Petersen chain and Hamilton weights
- Appendix A Preliminary
- Appendix B Snarks, Petersen graph
- Appendix C Integer flow theory
- Appendix D Hints for exercises
- Glossary of terms and symbols
- References
- Author index
- Subject index
Summary
Most terminology and notation in this book follow standard textbooks in graph theory (such as [18], [19], [41], [242], etc.). Some terminology is slightly different from those classical textbooks.
Definition 1.0.1 Let G = (V, E) be a graph with vertex set V and edge set E.
(1) A circuit is a connected 2-regular graph.
(2) A graph (subgraph) is even if the degree of each vertex is even.
(3) A bridge (or cut-edge) of a graph G is an edge whose removal increases the number of components of G (equivalently, a bridge is an edge that is not contained in any circuit of G).
Note that, in much of the literature related to circuit covers and integer flows, an even graph/subgraph is also called a cycle, which is adapted from matroid theory, and is different from what is used in many other graph theory textbooks. For the sake of less confusion, we will use even graph/subgraph instead of cycle in this book.
Definition 1.0.2 (1) A family ℱ of circuits (or even subgraphs) of a graph G is called a circuit cover (or an even subgraph cover) if every edge of G is contained in some member(s) of ℱ.
(2) A circuit cover (or an even subgraph cover) ℱ of a graph G is a double cover of G if every edge is contained in precisely two members of ℱ.
- Type
- Chapter
- Information
- Circuit Double Cover of Graphs , pp. 1 - 9Publisher: Cambridge University PressPrint publication year: 2012