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)
> 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'.
>
>
> Jan B.M. Lucassen
> 5624 KT   EINDHOVEN
> tel.: 040 - 243 40 58
>
> e-mail: jan.lucassen at planet.nl
>
>
>

```

• Prev by Date: Re: Re: operators for relations in sets
• Next by Date: Re: Bug in Reduce?
• Previous by thread: Hamiltoncircuits on polyhedra
• Next by thread: Re: Hamiltoncircuits on polyhedra