Home » Subject » Graph Theory » Basic G.T.

Cycles


Graph Theory » Basic G.T. » Cycles

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

Conjecture   For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

Keywords: cover; cycle

Posted by mdevos
updated February 7th, 2012
3 comments
Graph Theory » Basic G.T. » Cycles

The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture   Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture   Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Faithful cycle covers ★★★

Author(s): Seymour

Conjecture   If $ G = (V,E) $ is a graph, $ p : E \rightarrow {\mathbb Z} $ is admissable, and $ p(e) $ is even for every $ e \in E(G) $, then $ (G,p) $ has a faithful cover.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Decomposing eulerian graphs ★★★

Author(s):

Conjecture   If $ G $ is a 6-edge-connected Eulerian graph and $ P $ is a 2-transition system for $ G $, then $ (G,P) $ has a compaible decomposition.

Keywords: cover; cycle; Eulerian

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

Posted by Robert Samal
updated August 9th, 2011
1 comment
Graph Theory » Basic G.T. » Cycles

r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

Conjecture   If $ G $ is a finite $ r $-regular graph, where $ r > 2 $, then $ G $ is not uniquely hamiltonian.

Keywords: hamiltonian; regular; uniquely hamiltonian

Posted by Robert Samal
updated June 20th, 2022
3 comments
Graph Theory » Basic G.T. » Cycles

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; line graphs

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

Problem   If $ G $ is a $ 3 $-connected finite graph, is there an assignment of lengths $ \ell: E(G) \to \mathb R^+ $ to the edges of $ G $, such that every $ \ell $-geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

Posted by Agelos
updated August 4th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $ G $, let $ cp(G) $ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $ cc(G) $ denote the cardinality of a minimum feedback vertex set (set of vertices $ X $ so that $ G-X $ is acyclic).

Conjecture   For every planar graph $ G $, $ cc(G)\leq 2cp(G) $.

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019
3 comments
Graph Theory » Basic G.T. » Cycles

Chords of longest cycles ★★★

Author(s): Thomassen

Conjecture   If $ G $ is a 3-connected graph, every longest cycle in $ G $ has a chord.

Keywords: chord; connectivity; cycle

Posted by mdevos
updated October 14th, 2023
1 comment
Graph Theory » Basic G.T. » Cycles

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

Posted by tchow
updated December 15th, 2010
4 comments
Graph Theory » Basic G.T. » Cycles

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ C $ be a circuit in a bridgeless cubic graph $ G $. Then there is a five cycle double cover of $ G $ such that $ C $ is a subgraph of one of these five cycles.

Keywords: cycle cover

Posted by arthur
updated November 24th, 2011
8 comments
Graph Theory » Basic G.T. » Cycles

Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

Conjecture   Every simple eulerian graph on $ n $ vertices can be decomposed into at most $ \frac{1}{2}(n-1) $ cycles.

Keywords:

Posted by fhavet
updated March 4th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

Conjecture   Let $ G $ be an eulerian graph of minimum degree $ 4 $, and let $ W $ be an eulerian tour of $ G $. Then $ G $ admits a decomposition into cycles none of which contains two consecutive edges of $ W $.

Keywords:

Posted by fhavet
updated March 4th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every $ 4 $-connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a $ 3 $-connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content