Longest path through hypercube corners Is the longest Hamiltonian path through the $2^d$ unit hypercube vertices known,
where path length is measured by Euclidean distance in $\mathbb{R}^d$?
The unit hypercube spans from $(0,0,\ldots,0)$ to $(1,1,\ldots,1)$.
For example, for the cube in $\mathbb{R}^3$, I believe the longest path
has length
$3\sqrt{2}+4\sqrt{3} \approx 11.17$,
avoiding all edges of length $1$, and using all $4$ of the long diagonals
and $3$ short diagonals:

          


          

Path: $(1,7,2,8,3,5,4,6)$.


This likely has been studied, in which case pointers would be appreciated. 
If exact values are not known, bounds would be useful.
 A: Illustrating @MTyson's construction for $d=n=2$.
We start with an edge $(0,1)$ for the $1$-cube, and replace $(0,1)$ with $(0,0),(1,1)$ and $(1,1),(1,0)$. This leaves one final long diagonal $(1,0),(0,1)$:

          


And the length of the path is
$$
2^1 \sqrt{2} + (2^1 -1 ) \sqrt{1} = 2 \sqrt{2} + 1 \;.
$$

For $d=n=3$, MTyson's construction yields exactly the path I illustrated:
$(1, 7, 2, 8, 3, 5, 4, 6)$.
Here I will use the vertex indices illustrated in the main post,
rather than the coordinates.


*

*One starts with the $2$-cube path $(1,2,3)$.

*The $(1,2)$ edge is replaced by $(1,7,2)$.

*The $(2,3)$ edge is replaced by $(2,8,3)$.

*The $(3,4)$ edge is replaced by $(3,5,4)$.

*Finally, the last diagonal is added: $(4,6)$.

A: We can in fact, a corrollary from MTyson's post is that we can construct a graph $G$ isomorphic to a hypercube $H$ (where the vertices are the $d$-bit strings and two vertices are adjacent in $H$ if they differ in precisely  one bit) such that every edge in $G$ has length at least $\sqrt{d-1}$ in this metric, and $G$ admits a Hamiltonian circuit where half the edges have length $\sqrt{d}$.
Vertex $(u_1,u_2,\ldots, u_d)$ is adjacent in $G$ to $(1-u_1,1-u_2,\ldots, 1-u_{i-1}, u_i, 1-u_{i+1}, \ldots, 1-u_d)$ for all $i=1,2,\ldots, d-1$, and then vertex $(u_1,u_2, \ldots, u_d)$ is also adjacent in $G$ to its opposite $\bar{u}= (1-u_1,1-u_2, \ldots, 1-u_d)$.
Then $G$ is indeed isomorphic to a hypercube $H$ and has all edges of length at least $\sqrt{d-1}$. Furthermore, as $H$ admits a Hamiltonian circuit that has all edges of the form $\{(u_1, u_2, \ldots, u_{d-1}, u_d), (u_1, u_2, \ldots, u_{d-1}, 1-u_d)\}$ (i.e., the vertices differ in precisely their last bit), it follows that $G$ admits a Hamiltonian circuit that has all edges $\{u,\bar{u}\}$.
One can also check that no Hamiltonian cycle can have longer length than
$2^{d-1}(\sqrt{d} + \sqrt{d-1})$. Indeed, for each vertex $u$, there is only one other vertex that is $\sqrt{d}$ distance from $u$. So this implies that the edges $\{e = \{u,v\}; ||u-v||_2 = \sqrt{d} \}$ form a matching. Thus only half of the edges $e$ in a Hamiltonian cycle can have length $\sqrt{d}$, the remaining must have length no more than $\sqrt{d-1}$, giving the upper bound.  
A: Take a Hamiltonian path $P$ of minimal length on the $n-1$-cube, which has length $2^{n-1}-1$. Construct a path $Q$ in the $n$-cube as follows. For each edge $(e_1,\dots,e_i,\dots,e_{n-1})\to(e_1,\dots,1-e_i,\dots,e_{n-1})$ in P add edges $(e_1,\dots,e_i,\dots,e_{n-1},0)\to(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)$ and $(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)\to(e_1,\dots,1-e_i,\dots,e_{n-1},0)$ to $Q$. Add the final long diagonal to $Q$. In the end $Q$ is Hamiltonian and has the maximal length $2^{n-1}\sqrt{n}+(2^{n-1}-1)\sqrt{n-1}$.
A: The upper bound for the length of such a path is of course $2^d\sqrt{d}$. 


*

*A random ordering of the vertices has to give you an approximation to within $\frac{1}{\sqrt{2}}$; if $u$ and $v$ are randomly chosen, then they should differ in expected $\frac{d}{2}$ bits.

*The following recursion has to come pretty close to $2^d\sqrt{d}$: Find a long Hamiltonian path $P_{d/2}$ on a hypercube $H_{d/2}$ w $2^{d/2}$ vertices, and order the vertices by where they are on $P_{d/2}$. Let $u$ and $v$ be adjacent vertices in $P_{d/2-1}$ such that $u$ comes before $v$. Then for each edge $\{u',v'\}$ in $P_{d/2-1}$, put the edge between $u1u'$ and $v0v'$.
