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.

Improve this question
$\endgroup$
3

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Gerry Myerson
    Commented 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$
    – Fedor Petrov
    Commented Jun 22, 2016 at 22:49
  • $\begingroup$ OK. For $k=4$, your construction can give a graph on just 14 vertices. Very good. $\endgroup$
    – Gerry Myerson
    Commented 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$
    – Fedor Petrov
    Commented 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$
    – Sebastien Palcoux
    Commented 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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .