Prufer Code/ LabeledTreeToCode Bug?

*To*: mathgroup at smc.vnet.net*Subject*: [mg104530] Prufer Code/ LabeledTreeToCode Bug?*From*: Thomas Dowling <thomasgdowling at gmail.com>*Date*: Tue, 3 Nov 2009 02:54:22 -0500 (EST)

Hello, 1. I am interested in generating the Prufer code for the following simple graph which I generate as follows: Needs["Combinatorica`"] Needs["GraphUtilities`"] In[137]= gr1 = MakeSimple[ ToCombinatoricaGraph[{2 -> 4, 4 -> 3, 3 -> 1}, Method -> "CircularEmbedding"]]; 2. I can visualize the graph as follows, and all is well (it is as I expect, with no edge between vertices 1 and 2): In[140]= ShowGraph[gr1, EdgeColor -> Orange, VertexColor -> LightYellow, VertexLabelPosition -> Center, VertexStyle -> Disk[Large]] 3. However, if I now generate the Prufer code for gr1, I get a strange result. In[141]= LabeledTreeToCode@gr1 Out[141]= {2, 3} 4. Firstly, the above Prufer code is clearly wrong: it surely should be {3,4}? Secondly, if I use EdgeList, I also get an apparently wrong answer: In[143]= EdgeList[gr1] {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}} Why the edge between vertices 1 and 2? 5. If I 'work backwards' I do not get back the original graph: In[144]= pcgr1 = CodeToLabeledTree[{2, 3}]; ShowGraph[pcgr1, VertexLabel -> True, EdgeColor -> Orange, VertexColor -> LightYellow, VertexLabelPosition -> Center, VertexStyle -> Disk[Large]] In[145]= EdgeList[pcgr1] Out[145]= {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}} The EdgeList is correct for pcgr1, but pcgr1 is not identical with gr1! 6. Finally, if I work with the expected Prufer code, I get a graph and EdgeList consistent with what I expected for gr1 but did not get: In[148]= gr3 = CodeToLabeledTree[{3, 4}]; In[149]= ShowGraph[gr3, EdgeColor -> Orange, VertexLabel -> True, VertexColor -> LightYellow, VertexLabelPosition -> Center, VertexStyle -> Disk[Large]] In[150]= EdgeList[gr3] Out[150]= {{1, 3}, {2, 4}, {3, 1}, {3, 4}, {4, 2}, {4, 3}} 7. I am working with Mathematica 7.0.0 on a Mac Powerbook G4 (non-Intel) with OS X v 10.5.8. Have I missed something or is this a bug? I am also wondering if others can reproduce this behaviour on other systems, in particular with Mathematica 7.0.1. Any help / workaround will be greatly appreciated. Thanks, Tom Dowling

**Follow-Ups**:**Re: Prufer Code/ LabeledTreeToCode Bug?***From:*Thomas Dowling <thomasgdowling@gmail.com>