4
$\begingroup$

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.

By Smith's theorem, cubic Hamiltonian graph contains at least two Hamiltonian cycles. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard. Given cubic graph on $N$ nodes:

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles (each Hamiltonian cycle contains $N$ nodes) in cubic Hamiltonian graph?

Here Hamming distance between two Hamiltonian cycles is the is $N-$ the number of shared edges. $N$ is the number of nodes in the graph. The upper bound is $N/2$.

EDIT: I conjecture that it is at least $\Omega(\log N)$ and I even conjecture a tighter lower bound of $\Omega( \epsilon N)$ for some constant $\epsilon \gt 0$.

$\endgroup$
2
  • 1
    $\begingroup$ I would say that the lower bound is 2, but maybe you want it expressed in terms of some invariants? $\endgroup$
    – nvcleemp
    Nov 29, 2013 at 13:58
  • $\begingroup$ @hbm: this just proves the upper bound which was given by the OP, since the hamming distance is $N - |E(H_1)\cap E(H_2)|$. It is easy to construct an arbitrarily large cubic graph in which the smallest hamming distance between two hamiltonian cycles is 2. $\endgroup$
    – nvcleemp
    Nov 30, 2013 at 8:00

1 Answer 1

4
$\begingroup$

Let me maybe just formulate the comment as an answer.

It is easy to see that the lower bound can't be 1. Assume that $H_1$ contains the edge $e$, and $H_2$ does not contain $e$. If the edge $e$ is not contained in a triangle, then it has 4 adjacent edges. Then $H_2$ has to contain all 4 of these edges, while $H_1$ can only contain 2 of them, so the hamming distance is at least 2. If the edge $e$ is contained in a triangle, then $H_1$ and $H_2$ can share at most one edge of the triangle and at most one of the incoming edges of the triangle, or no edge of the triangle and two of the incoming edges. In either case the hamming distance is at least 2.

In case of the $K_4$ the minimum Hamming distance is 2. To construct a cubic graph in which the minimum hamming distance is 2, just take any hamiltonian cubic graph. Remove an edge that is contained in a hamiltonian cycle. Take a $K_4$ and remove an edge. Connect the vertices of degree two in both graphs to get a new cubic graph. The new graph is hamiltonian and contains two hamiltonian cycles that only differ in the edges in the $K_4$, so the hamming distance is 2.

Of course the graphs above have girth 3, so it might be possible to give a better lower bound as a function of the girth of the graph.

Edit: Maybe this illustration will make things more clear. Take any hamiltonian cubic graph and take an edge that is contained in a hamiltonian cycle (shown in red at the top). Insert a $K_4$ minus an edge into that edge. The new graph has two hamiltonian cycles (shown in red at the bottom left and right) which have hamming distance 2. You can do this for any cubic graph which has a hamiltonian cycle so you can get any number of vertices and still have minimum hamming distance 2.

Inserting a $K_4$ minus an edge

Edit 2: Since both $K_4$ and $K_{3,3}$ contain hamiltonian cycles with hamming distance 2, and the construction above adds 4 vertices, we have that for all $n\geq4$, there exists a cubic hamiltonian graph $G$ on $n$ vertices such that $G$ contains at least two hamiltonian cycles at hamming distance 2.

$\endgroup$
8
  • $\begingroup$ Thanks for the answer. However, I am not interested in trivial lower bound. I am looking for a tight lower bound in cubic Hamiltonian graphs (as a function of the number of nodes $N$). $\endgroup$ Nov 30, 2013 at 11:32
  • 1
    $\begingroup$ There is no such function except maybe the constant function 2, as is proven by the construction above. You can have $N$ arbitrarily large and still have the minimum hamming distance 2. $\endgroup$
    – nvcleemp
    Nov 30, 2013 at 12:20
  • $\begingroup$ I conjecture that it is at least $\Omega(\log N)$ and I even conjecture a tighter lower bound of $\Omega( \epsilon N)$ for some constant $\epsilon \gt 0$. $\endgroup$ Nov 30, 2013 at 15:58
  • $\begingroup$ Have you read the construction? Give me any even number greater than 2 and I can construct a cubic graph with that number of vertices and minimum hamming distance 2. $\endgroup$
    – nvcleemp
    Nov 30, 2013 at 18:46
  • $\begingroup$ Yes. I am looking for asymptotic tight minimum. $\endgroup$ Dec 1, 2013 at 4:12

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.