14
$\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$
3

3 Answers 3

15
$\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$
6
  • $\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$ Jun 22, 2016 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$ Jun 22, 2016 at 22:49
  • $\begingroup$ OK. For $k=4$, your construction can give a graph on just 14 vertices. Very good. $\endgroup$ Jun 22, 2016 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$ Jun 22, 2016 at 23:01
  • $\begingroup$ Do you expect that $22$ is the smallest order for a $2$-connected $k$-regular non-traceable graph? $\endgroup$ Jun 23, 2016 at 11:08
8
$\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$
6
$\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 and acknowledge you have read our privacy policy.

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