Possible bug in HamiltonianCycle

• To: mathgroup at smc.vnet.net
• Subject: [mg83597] Possible bug in HamiltonianCycle
• From: "Steve Luttrell" <steve at _removemefirst_luttrell.org.uk>
• Date: Sat, 24 Nov 2007 04:10:54 -0500 (EST)

```I have applied HamiltonianCycle to various graphs, but seem to have been
obtaining inconsistent results. Here is an example of what I mean:

In[1]:= Needs["Combinatorica`"]

In[2]:=

Define the corresponding directed graph.
Out[3]= \[SkeletonIndicator]Graph:<36,12,Directed>\[SkeletonIndicator]

Verify that the original adjacency matrix can be recovered.
Out[4]= True

Compute a Hamiltonian cycle in this graph.
In[5]:= h=HamiltonianCycle[g]
Out[5]= {1,7,2,3,9,12,4,11,10,6,5,8,1}

Break the cycle into its individual edges.
In[6]:= p=Partition[h,2,1]
Out[6]=
{{1,7},{7,2},{2,3},{3,9},{9,12},{12,4},{4,11},{11,10},{10,6},{6,5},{5,8},{8,1}}

Display the adjacency matrix entry corresponding to each of these edges.
Out[7]= {1,1,1,1,1,1,1,1,1,1,1,0}

This is where the problem lies, because all these matrix elements should be
1 in a Hamiltonian cycle.

Have I missed something obvious, or is this a bug?

Steve Luttrell
West Malvern, UK

```

• Prev by Date: Re: Dynamic Timeout
• Next by Date: Re: Contour Lines
• Previous by thread: Re: Contour Lines
• Next by thread: Re: Possible bug in HamiltonianCycle