11
$\begingroup$

Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way that the resulting graph is still non-Hamiltonian. What is the maximum number $f(n)$ of such edges (let us call them links) that can be added? Equivalently:

How many edges can a non-Hamiltonian graph on $2n$ vertices with two induced $n$-cycles and maximal degree 3 have?

Obviously such a graph cannot contain a $C_4$. Thus, if in a construction there is an edge $(v_i,w_j)$, the four edges $(v_{i\pm1},w_{j\pm1})$ are excluded.

It is clear that $f(n)$ grows linearly with $n$: a trivial lower bound is $f(n)\ge [\frac n2]$, realized by adding the links $(v_{2i},w_{2i})$ for $i=1,\dots,[\frac n2]$.

What can be said about $\lim\limits_{n\to\infty}\dfrac {f(n)}n$? Or at least about $\liminf\limits_{n\to\infty}\dfrac {f(n)}n$ and $\limsup\limits_{n\to\infty}\dfrac {f(n)}n$?

The Petersen graph shows that $f(5)=5$, and it is not hard to see that $f(6)<6$, thus $f(6)=5$ by the left displayed graph where the circles are $abcde\!f$ and $123456$. Further $f(8)\ge6$ by the right graph. To see that it is not Hamiltonian, note that the two violet edges cannot belong to a H-circle. enter image description here

I have also found $f(9)\ge 7$ and generally $f(2k-5)\ge k$ for $k\ge7$ by "splitting" two vertices of the Petersen graph, but as $k$ grows, this is no big improvement on the trivial lower bound. Yet, there should be much better lower bounds.
As for upper bounds, I suppose they are notoriously hard to find. Is it possible at least to prove that $f(n)<n$ for $n\ge 6$? Equivalently, that for each $\sigma \in S_n$ the 3-regular graph with links $(v_i,w_{\sigma(i)})$ is Hamiltonian? Note that the Generalized Petersen Graph $GP(7,2)\simeq GP(7,3)$, the most "symmetric" instance of those graphs, is already Hamiltonian, which makes me conjecture this holds.

$\endgroup$
10
$\begingroup$

If a full set of $n$ edges is inserted between the cycles, what you have is a "cycle permutation graph". According to this paper, there are nonhamiltonian cycle permutation graphs for all odd $n\ge 9$. I don't know what is known for even $n$.

This paper also seems relevant.

$\endgroup$
  • $\begingroup$ You should be able to add an extra vertex (split an edge) to each cycle without creating a Hamilton cycle. If so, then the maximum number becomes at least n-1 for n > 8. Gerhard "Or Does That Not Work?" Paseman, 2016.07.06. $\endgroup$ – Gerhard Paseman Jul 6 '16 at 7:51
  • 1
    $\begingroup$ @GerhardPaseman Yes that should work, so it guarantees $f(n)\ge n-1$ for even $n\ge10$. $\endgroup$ – Wolfgang Jul 6 '16 at 10:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.