hamiltonian


Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

\begin{conjecture} \begin{enumerate} \item If $G$ is a countable connected graph then its third \Def[power]{Glossary_of_graph_theory#Distance} is hamiltonian. \item If $G$ is a 2-connected countable graph then its square is hamiltonian. \end{enumerate} \end{conjecture}

Keywords: hamiltonian; infinite graph

Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

\begin{conjecture} \begin{enumerate} \item If $G$ is a 4-edge-connected locally finite graph, then its \Def{line graph} is hamiltonian. \item If the line graph $L(G)$ of a locally finite graph $G$ is 4-connected, then $L(G)$ is hamiltonian. \end{enumerate} \end{conjecture}

Keywords: hamiltonian; infinite graph; line graphs

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

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

\begin{problem} Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $r > 2$? \end{problem}

Keywords: hamiltonian; infinite graph; uniquely 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

Barnette's Conjecture ★★★

Author(s): Barnette

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

Keywords: bipartite; cubic; hamiltonian

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

Syndicate content