New URL: http://www.iki.fi/~kartturi/matikka/permgraf/troctahe.htm

Listing of all 18 Hamiltonian Paths of truncated octahedron, with the criteria that path must start 1234, 2134, 2314, 3214, 3124, 1324, 1342

Solution numbers 1-18 refer to lexicographic ordering (as generated by transham.c C-program) sequences of 23 transpositions, the first six being always (1 2), (2 3), (1 2), (2 3), (1 2), (3 4) (*) thus these are also the eighteen (lexicographically) first Hamiltonian paths of the total 344 possible such paths through the truncated octahedron. Note that the antipodal vertex of 1234 in the truncated octahedron is 4321, and for any vertex x, the antipodal vertex is x(14)(23) i.e., its four-element permutation list reversed.

Symbols for the generators (transpositions) used:

a
(1 2)
b
(2 3)
c
(3 4)

The solutions 1 and 9 are the only Hamiltonian cycles obeying the condition (*), and furthermore, the latter is palindromic:

Note also, how, because of that property and because transpositions are their own inverses, it can be specified naturally as a conjugate of the transposition b or any other "centered subword" of ababacabcbababcbacababa, i.e. any other "centered subword" is also a 2-cycle. Furthermore, if we take any two permutations equally distant from the both ends of that path, then the other can be produced from the other by multiplying it (from the left) by transposition (3 4). Here's how to check it in Maple: 

> with(group);

# Maple's mulperms function follows the convention that ``permutations act on the right'',
# but we want just the opposite, permutations acting on left, à la Rotman (An Introduction to the Theory of Groups),
# so we define this, to avoid any further confusion:

> permul := (a,b) -> mulperms(b,a);

> a := [[1,2]]; b := [[2,3]]; c := [[3,4]];

> g := permul(permul(permul(permul(permul(permul(permul(permul(permul(permul(a,b),a),b),a),c),a),b),c),b),a); convert(g,'permlist',4);

                         g := [[1, 2, 3, 4]]


                             [2, 3, 4, 1]

> conj_b := permul(permul(g,b),invperm(g)); convert(conj_b,'permlist',4);

                          conj_b := [[3, 4]]


                             [1, 2, 4, 3]

> convert(permul([[3,4]],convert([1,3,4,2],'disjcyc')),'permlist',4);

                             [1, 4, 3, 2]
Solution 1: (ababac)2(abcba)(b)(abcba) Solution 9: (ababac)(abcba)(b)(abcba)(cababa)


Solution 4 contains 1's (a's) on every odd position, thus it has 3's (c's) only on even positions:

Solution 3: (ababac)(a)(babc)(bcba)(babc)2 Solution 4: (ababac)(abacab)2(abaca)
Solution 11: (ababac)(a)(bcbababc)2 Solution 12: (ababac)(a)(bcba)2(babc)(bcba)


From next four, all graphs except top right (solution 16) contain 3's (c's) only on even positions:

Solution 15: (ababac)(babc)(bcba)(babc)2(b) Solution 16: (ababac)(bacaba)2(bacab)
Solution 17: (ababac)(b)(cbababcb)2 Solution 18: (ababac)(bcba)2(babc)(bcba)(b)


Solution 2 contains 3's (c's) only on even positions:

Solution 2: (ababac)(a)(babacb)(abc)(bababc)(b) Solution 5: (ababac)(abacab)2(abcac)
Solution 10: (ababac)(abcbababcbacbabab) Solution 13: (ababac)(abcb)2(abcab)(cb)2


Both have 3's only on even positions:

Solution 6: (ababac)(abacababacbcacbab) Solution 8: (ababac)(aba)(cb)2(c)(cbab)2
Solution 7: (ababac)(abacababcbabcacbc) Solution 14: (ababac)(abcb)2(abca)(cb)2(c)
(EIS A057112)
All palindromic solutions: 9, 43, 56, 62, 114, 171, 174, 231, 283, 289, 302, 336
Note that except the solutions 114, 171, 174 and 231, which end in 4231, all others are Hamiltonian cycles ending in a vertex adjacent to 1234
Solution 9: (ababac)(abcba)(b)(abcba)(cababa)
(EIS A060135)
Solution 43: abcacbacabc(a)cbacabcacba = (abcacbac)3c-1
STJ (sol 302) inverted or rotated 4, 12 or 20 steps left
Solution 56: (abcba)(cababa)(c)(ababac)(abcba)
sol 9 rotated 12 transpositions left, inverse of sol 289
Solution 62: abcbcbababc(b)cbababcbcba = (ab(cb)2ab)3b-1
Double Court, inverse or rotation of sol 283
Solution 283: cbababcbcba(b)abcbcbababc = (cb(ab)2cb)3b-1
CSW-ordering for S4
Double Court (sol 62) inverted or rotated 4, 12 or 20 steps left.
Solution 289: (cbabc)(acbcbc)(a)(cbcbca)(cbabc)
sol 9 rotated 12 left and inverted, or solution 56 inverted, or solution 336 rotated 12 left.
Solution 302: cbacabcacba(c)abcacbacabc = (cbacabca)3a-1
Steinhaus-Trotter-Johnson ordering for S4
Solution 336: (cbcbca)(cbabc)(b)(cbabc)(acbcbc)
Inverse of the solution 9
Solution 114: bababcabcba(b)abcbacbabab
Inverse of 231
Solution 171: bacabcbacba(c)abcabcbacab = (bacab)(cba)2(c)(abc)2(bacab)
Inverse of 174
Solution 174: bcacbabcabc(a)cbacbabcacb = (bcacb)(abc)2(a)(cba)2(bcacb)
Inverse of 171
Solution 231: bcbcbacbabc(b)cbabcabcbcb
Inverse of 114


Back to Antti Karttunen's main page.