O'Reilly logo

Circuit Double Cover of Graphs by Cun-Quan Zhang

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

1Circuit double cover

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required