In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
It is an unsolved problem, posed by George Szekeres and Paul Seymour and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embeddings, and in that context is also known as the circular embedding conjecture.
Read more about Cycle Double Cover: Formulation, Reduction To Snarks, Reducible Configurations, Circular Embedding Conjecture, Stronger Conjectures and Related Problems
Famous quotes containing the words cycle, double and/or cover:
“Oh, life is a glorious cycle of song,
A medley of extemporanea;
And love is a thing that can never go wrong;
And I am Marie of Roumania.”
—Dorothy Parker (1893–1967)
“Well, I had gone and spoiled it again, made another mistake. A double one in fact. There were plenty of ways to get rid of that officer by some simple and plausible device, but no, I must pick out a picturesque one; it is the crying defect of my character.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“I wouldn’t pray just for a old man that’s dead because he’s all right. If I was to pray, I’d pray for the folks that’s alive and don’t know which way to turn. Grampa here, he ain’t got no more trouble like that. He’s got his job all cut out for him. So cover him up and let him get to it.”
—Nunnally Johnson (1897–1977)