Return to Question

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.

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles 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$.

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$.

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.

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles 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$.

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.

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles 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$.

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.

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles 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.

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.

What is the best lower bound on the minimum Hamming distance between two Hamiltonian cycles 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$.