Re: Hamiltoncircuits on polyhedra

*To*: mathgroup at smc.vnet.net*Subject*: [mg60455] Re: [mg60399] Hamiltoncircuits on polyhedra*From*: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>*Date*: Fri, 16 Sep 2005 03:51:10 -0400 (EDT)*References*: <200509150916.FAA15840@smc.vnet.net>*Reply-to*: Andrzej Kozlowski <andrzej at akikoz.net>*Sender*: owner-wri-mathgroup at wolfram.com

You mean the standard add-on package "DiscreteMath`Combinatorica". Indeed, this package has the function HamiltonianCycle, which finds hamiltonian cycles on graphs. The package Combinatorica already contains graph representations of the regular polyhedra, so it is easy to find HamiltonianCycles on, say Dodecahedron: HamiltonianCycle[DodecahedralGraph] {1,2,3,4,5,10,12,17,16,20,19,18,13,9,14,8,15,7,11,6,1} This is very fast. You can also try to find all Hamiltonian cycles using HamiltonianCycle[DodecahedralGraph,All] but this will take much longer (remember that the problem of finding Hamiltionian cycles is NP complete). If you want to look for Hamiltonian cycles on non-regular polyhedra, e.g. uniform polyhedra, then you will need either to provide graph representation yourself (e.g. in the form of adjacency matrices and then use the Combinatorica function FromAdjacencyMatrix to construct ta graph) or you can find such representations in the package UniformPolyhedra.m by Roman Maeder that appeared originally in The Mathematica Journal, June 1993 and was reproduced in a modified form in the electronic supplement to the book The Mathematica Programmer II. Andrzej Kozlowski On 15 Sep 2005, at 18:16, Jan Lucassen wrote: > Dear Forum, > > Fred Simons (emeritus professor of Technical University Eindhoven) > has given me your email adress. > I should like to know whether Mathematica contains software to > determine Hamiltonian circuits on polyhedrs. > I am not well informed, but I heard about the existence of so > called Mathematica commands for the determination of Hamilton > circuits if it, Mathematica, has at its disposal the package > 'Combinatorics'. > > Awaiting your answer, yours cordially . > > Jan B.M. Lucassen > Madernolaan 4 > 5624 KT EINDHOVEN > tel.: 040 - 243 40 58 > > e-mail: jan.lucassen at planet.nl > > >

**References**:**Hamiltoncircuits on polyhedra***From:*Jan Lucassen <jan.lucassen@planet.nl>