Timeline for Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 1, 2013 at 12:58 | vote | accept | Mohammad Al-Turkistany | ||
| Dec 1, 2013 at 12:55 | history | edited | nvcleemp | CC BY-SA 3.0 |
added 310 characters in body
|
| Dec 1, 2013 at 12:51 | comment | added | nvcleemp | No problem, I have added a drawing. | |
| Dec 1, 2013 at 12:41 | history | edited | nvcleemp | CC BY-SA 3.0 |
added an illustration
|
| Dec 1, 2013 at 12:16 | comment | added | Mohammad Al-Turkistany | I guess I am missing something obvious. Can you illustrate you answer using a drawing? | |
| Dec 1, 2013 at 7:40 | comment | added | nvcleemp | Well, that minimum is 2. Take a $K_4$ and repeat the operation described to the same edge and the minimum hamming distance remains equal to 2. | |
| Dec 1, 2013 at 4:12 | comment | added | Mohammad Al-Turkistany | Yes. I am looking for asymptotic tight minimum. | |
| Nov 30, 2013 at 18:46 | comment | added | nvcleemp | 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. | |
| Nov 30, 2013 at 15:58 | comment | added | Mohammad Al-Turkistany | 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$. | |
| Nov 30, 2013 at 12:20 | comment | added | nvcleemp | 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. | |
| Nov 30, 2013 at 11:32 | comment | added | Mohammad Al-Turkistany | 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$). | |
| Nov 30, 2013 at 8:56 | history | answered | nvcleemp | CC BY-SA 3.0 |