This problem is a special case of the traceability conjecture for oriented graphs.

For more information on this conjecture see the paper: "Progress on the Traceability Conjecture for Oriented Graphs" at http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/965 or "Traceability of k-traceable oriented graphs" at http://www.sciencedirect.com/science/article/pii/S0012365X09006438.

A graph is oriented if each edge has only one direction. A graph is traceable if it contains a Hamiltonian path. A graph is $k$-traceable if each of its subgraphs of order $k$ is traceable. An oriented graph is d-regular if each vertex has $d$ out-neighbours and $d$ in-neighbours.

Note that for a graph of order $2k$ to be $k$-traceable, we must have $2d \geq k+1 $, otherwise we can select $k$ non-traceable vertices by selecting any vertex $v$ and $k-1$ of its non-neighbours.

It is for example, easy to show that a $k$-traceable $d$-regular graph $G$ of order $2k-1$ is traceable: Select any vertex $v$. Partition the remaining vertices in two sets $I$ and $O$ with $k-1$ vertices each such that $I$ contains only in-neighbours and non-neighbours of $v$, and $O$ contains only out-neighbours and non-neighbours of $v$. Then the subgraph with vertices $I \cup v$ has a Hamilton path ending in $v$, and the subgraph with vertices $O \cup v$ has a Hamilton path starting with $v$, making $G$ traceable.

I am sure there must be a clever trick somewhere to show the special case for order $2k$ is also true.

  • $\begingroup$ One way to try and solve this problem is to list all the properties a counter-example would have, and try to see if there are some contradiction. So, suppose $G$ is a non-traceable $k$-traceable $d$-regular oriented graph of order $2k$, then $G$ has the following properties: P1: $G$ is non-traceable. P2: $G$ is $k$-traceable. P3 $2d \geq k+1 $. **P4:** $G$ is $(2k-1)$-traceable. P5: $G$ is $(2k-2)$-traceable. P6: For every arc $ab$, there exist a vertex $w$, such that $aw$ and $wb$ are arcs. $\endgroup$ – Alewyn Burger Oct 3 '12 at 10:13
  • $\begingroup$ It is amazing to think there are 2k choose k ways to split the graph, and for EACH of those splits, both halves have a Hamilton path. How can the whole graph NOT have a Hamilton path? $\endgroup$ – Alewyn Burger Oct 5 '12 at 7:30

Your Answer

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

Browse other questions tagged or ask your own question.