Thanks for sharing this, Vince. This is great!
To relate it to what I’ve been saying (e.g. in
this message), we know that if p is a Hamiltonian path in G_n then
w(p) ≥ n! + (n-1)! - 3 + c2
where c2 is the number of 2-cycles visited by p. We also know that
cc + (n-2)c2 ≥ (n-1)!
where cc is the number of connected components of the 2-cycle graph of p. (That’s the graph whose nodes are the 2-cycles visited by p, and where there is an edge between two 2-cycles if they share at least one 1-cycle.)
The case considered here is where the 2-cycle graph is connected, i.e. cc = 1, hence (n-2)c2 + 1 ≥ (n-1)!. Thus c2 ≥ (n-2)! + (n-3)! - 1/(n-2). Since c2 is a whole number, for n > 3 this implies c2 ≥ (n-2)! + (n-3)!. So
w(p) ≥ n! + (n-1)! + (n-2)! + (n-3)! - 3
whenever n > 3, if the 2-cycle graph is connected.
Cheers,
Robin