cycle


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

What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph $G_1=(V,E)$ and its first arbitrary shortest spanning tree $T_1=(V,E_1)$. We define the next graph $G_2=(V,E\setminus E_1)$ and find on $G_2$ the second arbitrary shortest spanning tree $T_2=(V,E_2)$. We continue similarly by finding $T_3=(V,E_3)$ on $G_3=(V,E\setminus \cup_{i=1}^{2}E_i)$, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let $T^{k}=(V,\cup_{i=1}^{k}E_i)$ be the graph obtained as union of all $k$ disjoint trees.

\textbf{Question 1}. What is the smallest number of disjoint spanning trees creates a graph $T^{k}$ containing a Hamiltonian path.

\textbf{Question 2}. What is the smallest number of disjoint spanning trees creates a graph $T^{k}$ containing a shortest Hamiltonian path?

\textbf{Questions 3 and 4}. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

Bigger cycles in cubic graphs ★★

Author(s):

\begin{problem} Let $G$ be a cyclically 4-edge-connected cubic graph and let $C$ be a cycle of $G$. Must there exist a cycle $C' \neq C$ so that $V(C) \subseteq V(C')$? \end{problem}

Keywords: cubic; cycle

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $G$,$H$ are graphs, a function $f : E(G) \rightarrow E(H)$ is called \emph{cycle-continuous} if the pre-image of every element of the (binary) cycle space of $H$ is a member of the cycle space of $G$.

\begin{problem} Does there exist an infinite set of graphs $\{G_1,G_2,\ldots \}$ so that there is no cycle continuous mapping between $G_i$ and $G_j$ whenever $i \neq j$ ? \end{problem}

Keywords: antichain; cycle; poset

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

\begin{problem} Does every connected \Def{vertex-transitive graph} have a \Def{Hamiltonian path}? \end{problem}

Keywords: cycle; hamiltonian; path; vertex-transitive

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

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

(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

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

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

Syndicate content