10
$\begingroup$

In this paper (Construction 2.6 p860) the authors have built examples of connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected).

Question: Is there a $2$-connected $k$-regular graph without Hamiltonian path?

Remark: every $2$-connected $k$-regular graph with at most $3k+3$ vertices admits a Hamiltonian cycle or is one of the two exceptions, which admit a Hamiltonian path.

$\endgroup$
12
$\begingroup$

Take $k>3$ long paths between two vertices $a,b$. This graph is already 2-connected. Now add some edges to make it $k$-regular so that every edge joins only interior vertices of the same path (it is not hard). Then $G\setminus\{a,b\}$ has more connected components than any graph having Hamiltonian path with two vertices removed.

$\endgroup$
  • $\begingroup$ 1) The question is about paths, not cycles. 2) Start at $a$, take one of the paths to $b$, take the other path back to $a$ – isn't that a Hamiltonian cycle? $\endgroup$ – Gerry Myerson Jun 22 '16 at 22:42
  • $\begingroup$ 2) I think, no, because we have $k>3$ paths between $a,b$. Well, for $k=3$ this does not work, but there exist another constructions. $\endgroup$ – Fedor Petrov Jun 22 '16 at 22:49
  • $\begingroup$ OK. For $k=4$, your construction can give a graph on just 14 vertices. Very good. $\endgroup$ – Gerry Myerson Jun 22 '16 at 22:57
  • $\begingroup$ I doubt, we need more vertices in paths for making graph $k$-regular. 22 vertices are enough for $k=4$. $\endgroup$ – Fedor Petrov Jun 22 '16 at 23:01
  • $\begingroup$ Do you expect that $22$ is the smallest order for a $2$-connected $k$-regular non-traceable graph? $\endgroup$ – Sebastien Palcoux Jun 23 '16 at 11:08
7
$\begingroup$

According to this excerpt from the book Covering Walks in Graphs by Fujie & Zhang (2014), the Zamfirescu graph of order 36[1] is non-traceable (i.e.: does not contain a Hamiltonian path). Moreover, this graph is a snark and hence 3-regular and 2-connected.

The Thomassen graph of order 34[2] is also 3-regular, 2-connected, and non-traceable.

  1. Zamfirescu, Tudor. "On longest paths and circuits in graphs." Mathematica Scandinavica 38.2 (1976): 211-239.

  2. Thomassen, Carsten. "Hypohamiltonian and hypotraceable graphs." Discrete Mathematics 9.1 (1974): 91-96.

$\endgroup$
3
$\begingroup$

The smallest graph coming from the construction of Fedor Petrov's answer can be realized as follows:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.