Cycles


Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

\begin{conjecture} For every graph with no \Def[bridge]{bridge (graph theory)}, there is a list of cycles so that every edge is contained in exactly two. \end{conjecture}

Keywords: cover; cycle

The circular embedding conjecture ★★★

Author(s): Haggard

\begin{conjecture} Every 2-\Def[connected]{connectivity (graph theory)} graph may be \Def[embedded]{graph embedding} in a surface so that the boundary of each face is a cycle. \end{conjecture}

Keywords: cover; cycle

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a (5,2)-cycle-cover. \end{conjecture}

Keywords: cover; cycle

Faithful cycle covers ★★★

Author(s): Seymour

\begin{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. \end{conjecture}

Keywords: cover; cycle

Decomposing eulerian graphs ★★★

Author(s):

\begin{conjecture} If $G$ is a 6-\Def[edge-connected]{connectivity (graph theory)} \Def[Eulerian graph]{eulerian graph} and $P$ is a 2-transition system for $G$, then $(G,P)$ has a compaible decomposition. \end{conjecture}

Keywords: cover; cycle; Eulerian

Barnette's Conjecture ★★★

Author(s): Barnette

\begin{conjecture} Every 3-connected cubic planar bipartite graph is Hamiltonian. \end{conjecture}

Keywords: bipartite; cubic; hamiltonian

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

Author(s): Sheehan

\begin{conjecture} If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian. \end{conjecture}

Keywords: hamiltonian; regular; uniquely hamiltonian

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

\begin{conjecture} Every 4-connected \Def{line graph} is \Def[hamiltonian]{Hamilton cycle}. \end{conjecture}

Keywords: hamiltonian; line graphs

Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

\begin{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 \Def[peripheral]{peripheral cycle}? \end{problem}

Keywords: cycle space; geodesic cycles; peripheral 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).

\begin{conjecture} For every planar graph $G$, $cc(G)\leq 2cp(G)$. \end{conjecture}

Keywords: cycle packing; feedback vertex set; planar graph

Chords of longest cycles ★★★

Author(s): Thomassen

\begin{conjecture} If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord. \end{conjecture}

Keywords: chord; connectivity; cycle

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

\begin{question} Is every \Def{Cayley graph} Hamiltonian? \end{question}

Keywords:

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

\begin{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. \end{conjecture}

Keywords: cycle cover

Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

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

Keywords:

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

Author(s): Sabidussi

\begin{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$. \end{conjecture}

Keywords:

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

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

\begin{conjecture} If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle. \end{conjecture}

Keywords:

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

\begin{conjecture} Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle. \end{conjecture}

Keywords:

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

Author(s): Alspach; Rosenfeld

\begin{conjecture} Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles. \end{conjecture}

Keywords:


Syndicate content