[Math] Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

Question

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square.

$$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$

Also, about two weeks ago, a colleague taught me that one can arrange all the numbers from $1$ to $\color{red}{305}$ in a row such that the sum of every two adjacent numbers is a perfect cube.

$$256,87,129, 214, 298, 45, 171, 172, 44, 299, 213, 130, 86, 257, 255,$$
$$88, 128, 215, 297, 46, 170, 173, 43, 300, 212, 131, 85, 258, 254, 89, 127, 216, 296,$$
$$ 47, 169, 174, 42, 301, 211, 132, 84, 259, 253, 90, 126, 217, 295, 48, 168, 175, 41, 302, $$
$$210, 133, 83, 260, 252, 91, 125, 218, 294, 49, 167, 176, 40, 303, 209, 134, 82, 261, 251,$$
$$ 92, 33, 183, 160, 56, 287, 225, 118, 98, 245, 267, 76, 140, 203, 13, 14, 202, 141, 75, 268,$$
$$ 244, 99, 26, 190, 153, 63, 280, 232, 111, 105, 238, 274, 69, 147, 196, 20, 7, 1, 124, 219,$$
$$ 293, 50, 166, 177, 39, 304, 208, 135, 81, 262, 250, 93, 32, 184, 159, 57, 286, 226, 117, 8,$$
$$ 19, 197, 146, 70, 273, 239, 104, 112, 231, 281, 62, 154, 189, 27, 37, 179, 164, 52, 291, 221,$$
$$ 122, 3, 5, 22, 194, 149, 67, 276, 236, 107, 109, 234, 278, 65, 151, 192, 24, 101, 242, 270,$$
$$ 73, 143, 200, 16, 11, 205, 138, 78, 265, 247, 96, 120, 223, 289, 54, 162, 181, 35, 29, 187,$$
$$156, 60, 283, 229, 114, 102, 241, 271, 72, 144, 199, 17, 108, 235, 277, 66, 150, 193, 23,$$
$$ 4, 121, 222, 290, 53, 163, 180, 36, 28, 188, 155, 61, 282, 230, 113, 103, 240, 272, 71, 145,$$
$$ 198, 18, 9, 116, 227, 285, 58, 158, 185, 31, 94, 249, 263, 80, 136, 207, 305, 38, 178, 165,$$
$$ 51, 292, 220, 123, 2, 6, 21, 195, 148, 68, 275, 237, 106, 110, 233, 279, 64, 152, 191, 25,$$ $$100, 243, 269, 74, 142, 201, 15, 12, 204, 139, 77, 266, 246, 97, 119, 224, 288, 55, 161,$$
$$ 182, 34, 30, 186, 157, 59, 284, 228, 115, 10, 206, 137, 79, 264, 248, 95$$

Here, I have a few questions.

Question 1 : For each $N\ge 2\in\mathbb N$, does there exist at least one positive integer $n\ge 2$ satisfying the following condition ?

Condition : One can arrange all the numbers from $1$ to $n$ in a row such that the sum of every two adjacent numbers is of the form $m^N$ for some $m\in\mathbb N$.

Question 2 : Can we find at least one concrete $n$ with an arragement for a given $N$?

Question 3 : How about cyclic arrangements where the sum of the first and last numbers is also a perfect power?

I would like to know any relevant references as well.

Remark : Question 1 has been asked previously on math.SE without receiving any answers.

Additional information : On math.SE, a user Micah commented,
"For fixed $n$ and $N$, this is equivalent to asking whether some graph on $n$ vertices with $O(n^{1+1/N})$ edges has a Hamiltonian path. This is substantially above the threshold for a random graph to have a Hamiltonian path (which happens when the expected number of edges is $O(n\log n)$ or so), so the answer is probably "yes" unless there's some interesting structure in this specific graph that interferes with your chances."

Also, a user MJD showed a square-cyclic arrangement for $n=32$ :
$$\small1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15$$

Answer 1

Not an answer, but maybe a start:

It is fairly clear why trivial cases like $n=18,$ power$=2$ don't work, after all of the sum-pairs $\neq$ a power of $2$ that are $\leq2n$ are stripped away:

Complete cycles are much easier to search for: cycleP[33, 2] (for $n=33,$ power$=2$, code below) produces

whereas cyclePall[23, 2] produces

and it is clear why nothing below $300$ish will work for power $3$ by just looking at dangling nodes of $n=200,$ power$=3$:

---

cycleP[n_, pow_] := 
With[{graph = Graph[DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #]
&@nn - Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= n &]], 
{nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] #[[2]] 
== hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &], DirectedEdges -> False, 
VertexLabels -> "Name"]}, Column[{Show[#, ImageSize -> 400] &@
HighlightGraph[graph, Style[FindCycle[graph, {n}], {Darker@Red, Thick}]], 
Flatten@(#[[All, 1]] & /@ FindCycle[graph, {n}])}]]

cyclePall[n_, pow_] := 
With[{cc = DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #] &@nn - 
Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= 
n &]], {nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] 
#[[2]] == hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &]}, With[{dd = 
Split@Sort@Join[cc[[All, 1]], cc[[All, 2]]]},
With[{jj = DeleteCases[Flatten@(If[Length@# == First@Sort[Length@# & /@ dd], #, 0] 
& /@ dd), 0]}, With[{ll = Flatten@Table[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose@{ConstantArray[jj[[kk]], n], Range@n}, {kk, Length@jj}]},
With[{zz = Table[Join[{ll[[vv]]}, cc], {vv, Length@ll}]}, With[{zzz = 
DeleteCases[Table[FindCycle[Graph[zz[[ww]], DirectedEdges -> False, 
VertexLabels -> "Name"], {n}], {ww, Length@zz}], {}]}, With[{graphs = 
(HighlightGraph[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], 
Style[#, {Darker@Red, Thick}]] & /@ zzz)},Column[{If[Length@graphs == 0, 
Show[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], ImageSize -> 400], 
Show[#, ImageSize -> 400] & /@ graphs],#[[All, 1]] & /@ (Rest@# & /@
Flatten[zzz, 1])}]]]]]]]]

(Mathematica 10 only)