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