Return to Answer

updated broken links

Source Link

edited Jul 13, 2017 at 14:36

13.4k
5
45
102

If a full set of $n$ edges is inserted between the cycles, what you have is a "cycle permutation graph". According to this paper 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 This paper also seems relevant.

Source Link

created Jul 6, 2016 at 2:28

Brendan McKay

37.7k
3
80
147

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.