Message Boards Message Boards

GROUPS:

Embeddings for Degree Diameter graphs

Posted 3 years ago
4798 Views
|
15 Replies
|
17 Total Likes
|

UPDATED: More graphs added and some corrections.

A famous open problem is the Degree diameter problem. What is the largest regular graph with a given degree and diameter? Of the known solutions, we have two good pictures.

Grid[Transpose[{GraphData[#], #} & /@ {"PetersenGraph", "HoffmanSingletonGraph"}]]  

Petersen and Hoffman-Singleton

I found the Hoffman-Singleton embedding myself, and it's widely used now. But it's a challenge to find nice embeddings for highly-connected non-planar graphs. With Hoffman-Singleton I could confidently start with the assumption that some sort of symmetrical representation had to exist. Here are some edge lists for graphs we don't have good pictures for.

degreediameter33 = {{1, 2}, {1, 14}, {1, 20}, {2, 3}, {2, 8}, {3, 4}, {3, 18}, {4, 5}, {4, 11}, {5, 6}, {5, 15}, {6, 7}, {6, 19}, {7, 8}, {7, 12}, {8, 9}, {9, 10}, {9, 16}, {10, 11}, {10, 20}, {11, 12}, {12, 13}, {13, 14}, {13, 17}, {14, 15}, {15, 16}, {16, 17}, {17, 18}, {18, 19}, {19, 20}};
degreediameter34 = {{1,2},{1,36},{1,37},{2,3},{2,14},{3,4},{3,29},{4,5},{4,34},{5,6},{5,21},{6,7},{6,26},{7,8},{7,38},{8,9},{8,15},{9,10},{9,35},{10,11},{10,28},{11,12},{11,20},{12,13},{12,32},{13,14},{13,25},{14,15},{15,16},{16,17},{16,22},{17,18},{17,33},{18,19},{18,27},{19,20},{19,37},{20,21},{21,22},{22,23},{23,24},{23,30},{24,25},{24,36},{25,26},{26,27},{27,28},{28,29},{29,30},{30,31},{31,32},{31,38},{32,33},{33,34},{34,35},{35,36},{37,38}};
degreediameter35 = {{1,26},{1,41},{1,43},{2,30},{2,39},{2,44},{3,31},{3,34},{3,45},{4,23},{4,29},{4,46},{5,33},{5,42},{5,47},{6,34},{6,37},{6,48},{7,26},{7,32},{7,49},{8,24},{8,36},{8,50},{9,37},{9,40},{9,51},{10,29},{10,35},{10,52},{11,27},{11,39},{11,53},{12,22},{12,40},{12,54},{13,32},{13,38},{13,55},{14,30},{14,42},{14,56},{15,22},{15,25},{15,57},{16,35},{16,41},{16,58},{17,24},{17,33},{17,59},{18,25},{18,28},{18,60},{19,23},{19,38},{19,61},{20,27},{20,36},{20,62},{21,28},{21,31},{21,63},{22,43},{23,44},{24,45},{25,46},{26,47},{27,48},{28,49},{29,50},{30,51},{31,52},{32,53},{33,54},{34,55},{35,56},{36,57},{37,58},{38,59},{39,60},{40,61},{41,62},{42,63},{43,64},{44,64},{45,64},{46,65},{47,65},{48,65},{49,66},{50,66},{51,66},{52,67},{53,67},{54,67},{55,68},{56,68},{57,68},{58,69},{59,69},{60,69},{61,70},{62,70},{63,70}};
degreediameter42 = {{1,2},{1,4},{1,12},{1,13},{2,3},{2,8},{2,11},{3,4},{3,6},{3,15},{4,5},{4,10},{5,6},{5,8},{5,14},{6,7},{6,12},{7,8},{7,10},{7,13},{8,9},{9,10},{9,12},{9,15},{10,11},{11,12},{11,14},{13,14},{13,15},{14,15}};
degreediameter43 = {{1,2},{1,6},{1,26},{1,38},{2,3},{2,4},{2,5},{3,20},{3,24},{3,31},{4,13},{4,19},{4,25},{5,14},{5,18},{5,36},{6,7},{6,11},{6,35},{7,8},{7,9},{7,10},{8,25},{8,29},{8,39},{9,18},{9,24},{9,30},{10,19},{10,23},{10,31},{11,12},{11,16},{11,32},{12,13},{12,14},{12,15},{13,30},{13,34},{14,23},{14,29},{15,24},{15,28},{15,39},{16,17},{16,21},{16,38},{17,18},{17,19},{17,20},{18,33},{19,28},{20,29},{20,34},{21,22},{21,26},{21,35},{22,23},{22,24},{22,25},{23,37},{25,33},{26,27},{26,32},{27,28},{27,29},{27,30},{28,36},{30,37},{31,32},{31,41},{32,33},{33,40},{34,35},{34,41},{35,36},{36,40},{37,38},{37,41},{38,39},{39,40},{40,41}};
degreediameter44 = {{1,32},{1,50},{1,66},{1,92},{2,31},{2,49},{2,65},{2,91},{3,34},{3,52},{3,68},{3,94},{4,33},{4,51},{4,67},{4,93},{5,36},{5,54},{5,70},{5,96},{6,35},{6,53},{6,69},{6,95},{7,38},{7,56},{7,58},{7,98},{8,37},{8,55},{8,57},{8,97},{9,40},{9,44},{9,60},{9,86},{10,39},{10,43},{10,59},{10,85},{11,42},{11,46},{11,62},{11,88},{12,41},{12,45},{12,61},{12,87},{13,30},{13,48},{13,64},{13,90},{14,29},{14,47},{14,63},{14,89},{15,36},{15,64},{15,74},{15,95},{16,35},{16,63},{16,73},{16,96},{17,38},{17,66},{17,76},{17,97},{18,37},{18,65},{18,75},{18,98},{19,40},{19,68},{19,78},{19,85},{20,39},{20,67},{20,77},{20,86},{21,42},{21,70},{21,80},{21,87},{22,41},{22,69},{22,79},{22,88},{23,30},{23,58},{23,82},{23,89},{24,29},{24,57},{24,81},{24,90},{25,32},{25,60},{25,84},{25,91},{26,31},{26,59},{26,83},{26,92},{27,34},{27,62},{27,72},{27,93},{28,33},{28,61},{28,71},{28,94},{29,50},{29,79},{30,49},{30,80},{31,52},{31,81},{32,51},{32,82},{33,54},{33,83},{34,53},{34,84},{35,56},{35,71},{36,55},{36,72},{37,44},{37,73},{38,43},{38,74},{39,46},{39,75},{40,45},{40,76},{41,48},{41,77},{42,47},{42,78},{43,62},{43,90},{44,61},{44,89},{45,64},{45,92},{46,63},{46,91},{47,66},{47,94},{48,65},{48,93},{49,68},{49,96},{50,67},{50,95},{51,70},{51,98},{52,69},{52,97},{53,58},{53,86},{54,57},{54,85},{55,60},{55,88},{56,59},{56,87},{57,84},{58,83},{59,72},{60,71},{61,74},{62,73},{63,76},{64,75},{65,78},{66,77},{67,80},{68,79},{69,82},{70,81},{71,90},{72,89},{73,92},{74,91},{75,94},{76,93},{77,96},{78,95},{79,98},{80,97},{81,86},{82,85},{83,88},{84,87}};
degreediameter52 = {{1,4},{1,6},{1,7},{1,8},{1,9},{2,3},{2,5},{2,7},{2,8},{2,9},{3,6},{3,10},{3,11},{3,12},{4,5},{4,10},{4,11},{4,12},{5,13},{5,14},{5,15},{6,13},{6,14},{6,15},{7,16},{7,20},{7,23},{8,17},{8,21},{8,24},{9,18},{9,19},{9,22},{10,17},{10,19},{10,23},{11,18},{11,20},{11,24},{12,16},{12,21},{12,22},{13,17},{13,20},{13,22},{14,18},{14,21},{14,23},{15,16},{15,19},{15,24},{16,17},{16,18},{17,18},{19,20},{19,21},{20,21},{22,23},{22,24},{23,24}};
degreediameter62 = {{1,2},{1,3},{1,4},{1,19},{1,21},{1,30},{2,5},{2,6},{2,18},{2,24},{2,28},{3,7},{3,8},{3,20},{3,22},{3,29},{4,9},{4,10},{4,17},{4,23},{4,27},{5,10},{5,11},{5,14},{5,22},{5,26},{6,7},{6,12},{6,15},{6,25},{6,27},{7,13},{7,16},{7,23},{7,26},{8,9},{8,11},{8,14},{8,25},{8,28},{9,12},{9,15},{9,24},{9,26},{10,13},{10,16},{10,25},{10,29},{11,12},{11,20},{11,23},{11,30},{12,17},{12,21},{12,29},{13,14},{13,17},{13,24},{13,30},{14,18},{14,21},{14,27},{15,16},{15,18},{15,22},{15,30},{16,20},{16,21},{16,28},{17,19},{17,22},{17,28},{18,19},{18,23},{18,29},{19,20},{19,25},{19,26},{20,24},{20,27},{21,26},{21,31},{22,27},{22,31},{23,28},{23,31},{24,29},{24,31},{25,30},{25,31},{26,32},{27,32},{28,32},{29,32},{30,32},{31,32}}; 
degreediameter63 = {{1,39},{1,47},{1,53},{1,91},{1,106},{1,108},{2,40},{2,48},{2,54},{2,92},{2,107},{2,109},{3,41},{3,49},{3,55},{3,93},{3,108},{3,110},{4,42},{4,50},{4,56},{4,94},{4,109},{4,111},{5,43},{5,51},{5,57},{5,75},{5,95},{5,110},{6,44},{6,52},{6,58},{6,76},{6,96},{6,111},{7,45},{7,53},{7,59},{7,75},{7,77},{7,97},{8,46},{8,54},{8,60},{8,76},{8,78},{8,98},{9,47},{9,55},{9,61},{9,77},{9,79},{9,99},{10,48},{10,56},{10,62},{10,78},{10,80},{10,100},{11,49},{11,57},{11,63},{11,79},{11,81},{11,101},{12,50},{12,58},{12,64},{12,80},{12,82},{12,102},{13,51},{13,59},{13,65},{13,81},{13,83},{13,103},{14,52},{14,60},{14,66},{14,82},{14,84},{14,104},{15,53},{15,61},{15,67},{15,83},{15,85},{15,105},{16,54},{16,62},{16,68},{16,84},{16,86},{16,106},{17,55},{17,63},{17,69},{17,85},{17,87},{17,107},{18,56},{18,64},{18,70},{18,86},{18,88},{18,108},{19,57},{19,65},{19,71},{19,87},{19,89},{19,109},{20,58},{20,66},{20,72},{20,88},{20,90},{20,110},{21,59},{21,67},{21,73},{21,89},{21,91},{21,111},{22,60},{22,68},{22,74},{22,75},{22,90},{22,92},{23,38},{23,61},{23,69},{23,76},{23,91},{23,93},{24,39},{24,62},{24,70},{24,77},{24,92},{24,94},{25,40},{25,63},{25,71},{25,78},{25,93},{25,95},{26,41},{26,64},{26,72},{26,79},{26,94},{26,96},{27,42},{27,65},{27,73},{27,80},{27,95},{27,97},{28,43},{28,66},{28,74},{28,81},{28,96},{28,98},{29,38},{29,44},{29,67},{29,82},{29,97},{29,99},{30,39},{30,45},{30,68},{30,83},{30,98},{30,100},{31,40},{31,46},{31,69},{31,84},{31,99},{31,101},{32,41},{32,47},{32,70},{32,85},{32,100},{32,102},{33,42},{33,48},{33,71},{33,86},{33,101},{33,103},{34,43},{34,49},{34,72},{34,87},{34,102},{34,104},{35,44},{35,50},{35,73},{35,88},{35,103},{35,105},{36,45},{36,51},{36,74},{36,89},{36,104},{36,106},{37,38},{37,46},{37,52},{37,90},{37,105},{37,107},{38,79},{38,98},{38,103},{39,80},{39,99},{39,104},{40,81},{40,100},{40,105},{41,82},{41,101},{41,106},{42,83},{42,102},{42,107},{43,84},{43,103},{43,108},{44,85},{44,104},{44,109},{45,86},{45,105},{45,110},{46,87},{46,106},{46,111},{47,75},{47,88},{47,107},{48,76},{48,89},{48,108},{49,77},{49,90},{49,109},{50,78},{50,91},{50,110},{51,79},{51,92},{51,111},{52,75},{52,80},{52,93},{53,76},{53,81},{53,94},{54,77},{54,82},{54,95},{55,78},{55,83},{55,96},{56,79},{56,84},{56,97},{57,80},{57,85},{57,98},{58,81},{58,86},{58,99},{59,82},{59,87},{59,100},{60,83},{60,88},{60,101},{61,84},{61,89},{61,102},{62,85},{62,90},{62,103},{63,86},{63,91},{63,104},{64,87},{64,92},{64,105},{65,88},{65,93},{65,106},{66,89},{66,94},{66,107},{67,90},{67,95},{67,108},{68,91},{68,96},{68,109},{69,92},{69,97},{69,110},{70,93},{70,98},{70,111},{71,75},{71,94},{71,99},{72,76},{72,95},{72,100},{73,77},{73,96},{73,101},{74,78},{74,97},{74,102}};
degreediameter82 = {{1,9},{1,11},{1,17},{1,30},{1,36},{1,42},{1,48},{1,54},{2,3},{2,10},{2,17},{2,24},{2,31},{2,38},{2,45},{2,52},{3,10},{3,11},{3,12},{3,13},{3,14},{3,15},{3,16},{4,9},{4,10},{4,23},{4,29},{4,35},{4,41},{4,47},{4,53},{5,6},{5,10},{5,20},{5,30},{5,33},{5,43},{5,46},{5,56},{6,10},{6,19},{6,28},{6,37},{6,39},{6,48},{6,57},{7,8},{7,10},{7,22},{7,27},{7,32},{7,44},{7,49},{7,54},{8,10},{8,21},{8,25},{8,36},{8,40},{8,51},{8,55},{9,10},{9,18},{9,26},{9,34},{9,42},{9,50},{11,16},{11,23},{11,30},{11,37},{11,44},{11,51},{12,13},{12,20},{12,27},{12,34},{12,41},{12,48},{12,55},{13,19},{13,26},{13,33},{13,40},{13,47},{13,54},{14,15},{14,22},{14,29},{14,36},{14,43},{14,50},{14,57},{15,21},{15,28},{15,35},{15,42},{15,49},{15,56},{16,18},{16,25},{16,32},{16,39},{16,46},{16,53},{17,52},{17,53},{17,54},{17,55},{17,56},{17,57},{18,22},{18,28},{18,34},{18,40},{18,46},{18,52},{19,23},{19,26},{19,36},{19,39},{19,49},{19,52},{20,21},{20,30},{20,32},{20,41},{20,50},{20,52},{21,25},{21,37},{21,42},{21,47},{21,52},{22,29},{22,33},{22,44},{22,48},{22,52},{23,27},{23,35},{23,43},{23,51},{23,52},{24,31},{24,32},{24,33},{24,34},{24,35},{24,36},{24,37},{25,26},{25,31},{25,43},{25,48},{25,53},{26,31},{26,44},{26,50},{26,56},{27,31},{27,42},{27,46},{27,57},{28,31},{28,41},{28,51},{28,54},{29,30},{29,31},{29,39},{29,47},{29,55},{30,31},{30,40},{30,49},{32,35},{32,39},{32,50},{32,54},{33,42},{33,51},{33,53},{34,37},{34,43},{34,49},{34,55},{35,40},{35,48},{35,56},{36,41},{36,46},{37,44},{37,47},{37,57},{38,45},{38,46},{38,47},{38,48},{38,49},{38,50},{38,51},{39,42},{39,45},{39,55},{40,45},{40,57},{41,44},{41,45},{41,53},{42,45},{43,45},{43,54},{44,45},{44,56},{46,47},{46,56},{47,54},{49,53},{50,51},{50,57},{51,55},{53,57},{55,56}}; 

Here is what those graphs look like in an untamed state.

degree diameter graphs

Can anyone find improved pictures for these graphs? The attached notebook has larger untamed degree-diameter graphs.

Attachments:
15 Replies

Looks like 34 is kin to symmetries:

Graph[UndirectedEdge @@@ degreediameter34, GraphLayout -> #] & /@ {"RadialDrawing", "BalloonEmbedding"}

enter image description here

Is this sort of thing you are looking for?

Here's a good embedding of the largest known degree-4 diameter-2 graph

GraphPlot[Rule @@@ {{1, 2}, {1, 8}, {1, 12}, {1, 15}, {2, 3}, {2, 6}, {2, 9}, {3, 4}, {3, 11}, {3, 14}, {4, 5}, 
 {4, 8}, {4, 12}, {5, 6}, {5,10}, {5, 15}, {6, 7}, {6, 13}, {7, 8}, {7, 11}, {7, 14}, {8, 9}, {9, 10}, {9, 13}, 
 {10, 11}, {10, 15}, {11, 12}, {12, 13}, {13,14}, {14, 15}}, VertexCoordinateRules -> 
 Thread[Range[15] -> Table[{Sin[2 Pi n/15], Cos[2 Pi n/15]}, {n, 1, 15}] ]]

degree diameter graph 4 - 2

Here's a decent embedding of the largest known degree-3 diameter-3 graph:

GraphPlot[Rule@@@{{1,2},{1,14},{1,20},{2,3},{2,7},{3,4},{3,17},{4,5},{4,11},{5,6},{5,15},{6,7},{6,19},
 {7,8},{8,9},{8,12},{9,10},{9,16},{10,11},{10,20},{11,12},{12,13},{13,14},{13,18},{14,15},{15,16},{16,17},
 {17,18},{18,19},{19,20}},VertexCoordinateRules -> 
Thread[Range[20]-> Table[{Sin[2 Pi n/20],Cos[2 Pi n/20]},{n,1,20}] ]]

degree diameter graph 3 - 3

UPDATE: This one is faulty! I must have gotten the edge set wrong. A corrected version is several posts below.

Here's something for Degree 3 Diameter 4

GraphPlot[Rule@@@{{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,14},
{14,15},{15,16},{16,17},{17,18},{18,19},{19,20},{20,21},{21,22},{22,23},{23,24},{24,25},{25,26},{26,27},
{27,28},{28,29},{29,30},{30,31},{31,32},{32,33},{33,34},{34,35},{35,36},{36,37},{1,37},{1,23},{2,31},{3,18},
{4,13},{5,26},{6,35},{7,30},{8,22},{9,17},{10,38},{11,32},{12,21},{14,36},{15,29},{16,25},{19,34},{20,28},
{24,33},{27,38},{37,38}}, VertexCoordinateRules -> Thread[Append[Range[37],38]-> 
Append[Table[{Sin[2 Pi n/37],Cos[2 Pi n/37]},{n,1,37,1}] ,{0,0}]]]

degree 3 diameter 4

Something for Degree 5 Diameter 2

GraphPlot[Rule@@@{{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},{10,11},{11,12},{12,13},
{13,14},{14,15},{15,16},{16,17},{17,18},{18,19},{19,20},{20,21},{21,22},{22,23},{23,24},{1,24},
{1,4},{1,11},{1,19},{2,7},{2,15},{2,21},{3,9},{3,17},{3,24},{4,13},{4,22},{5,7},{5,10},{5,20},{6,12},
{6,16},{6,24},{7,18},{8,11},{8,14},{8,22},{9,12},{9,19},{10,15},{10,23},{11,17},{12,21},{13,15},
{13,18},{14,20},{14,24},{16,19},{16,22},{17,20},{18,23},{21,23}},
VertexCoordinateRules -> Thread[Range[24]-> Table[{Sin[(2 Pi n -Pi)/24],Cos[(2 Pi n-Pi)/24]},{n,1,24}] ]] 

degree 5 diameter 2

Your first graph, degreediameter33, can be shown like this:

enter image description here

enter image description here

Is this the kind of thing you are looking for? If not, can you explain in more detail?

For completeness, the coordinates:

{1 -> {Sqrt[5/8 + Sqrt[5]/8], 1/4 (-1 + Sqrt[5])}, 
 2 -> {3/4 (1 - Sqrt[5]), -3 Sqrt[5/8 + Sqrt[5]/8]}, 
 3 -> {3/4 (-1 + Sqrt[5]), -3 Sqrt[5/8 + Sqrt[5]/8]}, 
 4 -> {3/4 (1 + Sqrt[5]), -3 Sqrt[5/8 - Sqrt[5]/8]}, 5 -> {0, 1}, 
 6 -> {3/4 (-1 - Sqrt[5]), 3 Sqrt[5/8 - Sqrt[5]/8]}, 7 -> {-3, 0}, 
 8 -> {3/4 (-1 - Sqrt[5]), -3 Sqrt[5/8 - Sqrt[5]/8]}, 
 9 -> {-Sqrt[5/8 + Sqrt[5]/8], 1/4 (-1 + Sqrt[5])}, 
 10 -> {3/4 (1 + Sqrt[5]), 3 Sqrt[5/8 - Sqrt[5]/8]}, 11 -> {3, 0}, 
 12 -> {Sqrt[5/8 - Sqrt[5]/8], 1/4 (-1 - Sqrt[5])}, 
 13 -> {2 Sqrt[5/8 - Sqrt[5]/8], 1/2 (-1 - Sqrt[5])}, 
 14 -> {2 Sqrt[5/8 + Sqrt[5]/8], 1/2 (-1 + Sqrt[5])}, 15 -> {0, 2}, 
 16 -> {-2 Sqrt[5/8 + Sqrt[5]/8], 1/2 (-1 + Sqrt[5])}, 
 17 -> {-2 Sqrt[5/8 - Sqrt[5]/8], 1/2 (-1 - Sqrt[5])}, 
 18 -> {-Sqrt[5/8 - Sqrt[5]/8], 1/4 (-1 - Sqrt[5])}, 
 19 -> {3/4 (1 - Sqrt[5]), 3 Sqrt[5/8 + Sqrt[5]/8]}, 
 20 -> {3/4 (-1 + Sqrt[5]), 3 Sqrt[5/8 + Sqrt[5]/8]}}

I don't have the patience to do complete degreediameter34 (which you have also found a drawing for), but here's a clear set of steps to get a nice drawing.

First, notice that it contains these two subgraphs:

Mathematica graphics

(These do not contain all vertices.)

Then notice that it contains these three binary trees emanating from vertex 3:

Mathematica graphics

(This second drawing does contain all vertices, but it contains none of the edges from the previous two subgraphs I showed.)

Notice that the "centres" of the two subgraphs, 1 and 24, are the leaves of the "middle" tree emanating from vertex 3, shown at the top of the drawing.

Now all we need to do is to keep flipping around the branches of the tree to make it consistent with the symmetries exposed in the first two subgraphs, then re-insert the edges from those two subgraphs.

degreediameter42 can be drawn like this:

Mathematica graphics

We have two hexagons inside with a 6-fold symmetry and a triangle outside with a 3-fold symmetry.

What I am more interested in is a general approach for producing symmetric drawings like these. I asked a related question on Math.SE a while ago. There were no answers, but there are a few interesting comments.

https://math.stackexchange.com/questions/2641700/graph-layout-that-reflects-graph-symmetries

I also linked a few possibly relevant papers in the comments.


For the 33 and 42 case above my approach was to try to construct geometric symmetries that reflect symmetries present in graph itself (i.e. its automorphism group). In particular, looking at the orbits of vertices under the action of the automorphism group can be useful. For the first graph (33), we get the following partition of vertices:

In[1314]:= GroupOrbits@GraphAutomorphismGroup[g]
Out[1314]= {{1, 5, 9, 12, 18}, {2, 3, 4, 6, 7, 8, 10, 11, 19, 20}, {13, 14, 15, 16, 17}}

Vertices within these subsets can be transformed into each other by automorphism, but an automorphism can't take a vertex in one subset into a vertex in another one. Thus a good starting point may be drawing each subset on its own circular shell. The ordering within a shell is still important though. The most difficult one to order here is the largest subset, {2, 3, 4, 6, 7, 8, 10, 11, 19, 20}. But notice that the subgraph it induces is a cycle, which immediately gives us an ordering. Matching the other two to it was not difficult.

Similar thinking worked with the 42 graph.

The automorphism group of the 34 was too complicated, so instead I looked for the shortest cycles, and their union. This immediately revealed a nice pattern. Deleting the edges in this pattern left only a tree, whose symmetry was visually obvious.


I'm quite curious about how @Ed Pegg found his drawings.

Posted 5 months ago

Here's a start at a nice embedding for the valence=5, diameter=3 case. The largest known graph has 72 vertices.

edgy53={{1,4},{1,8},{1,22},{1,55},{1,70},{2,3},{2,5},{2,24},{2,54},{2,72},{3,6},{3,23},{3,53},{3,71},{4,7},{4,21},{4,56},{4,69},{5,9},{5,10},{5,27},{5,69},{6,11},{6,12},{6,26},{6,70},{7,9},{7,11},{7,25},{7,71},{8,10},{8,12},{8,28},{8,72},{9,13},{9,37},{9,65},{10,15},{10,39},{10,68},{11,16},{11,40},{11,66},{12,14},{12,38},{12,67},{13,14},{13,18},{13,44},{13,57},{14,20},{14,42},{14,60},{15,16},{15,17},{15,43},{15,58},{16,19},{16,41},{16,59},{17,22},{17,24},{17,33},{17,64},{18,21},{18,24},{18,35},{18,62},{19,21},{19,23},{19,36},{19,63},{20,22},{20,23},{20,34},{20,61},{21,28},{21,29},{22,25},{22,30},{23,27},{23,31},{24,26},{24,32},{25,28},{25,32},{25,46},{26,27},{26,29},{26,48},{27,30},{27,47},{28,31},{28,45},{29,33},{29,34},{29,51},{30,35},{30,36},{30,50},{31,33},{31,35},{31,49},{32,34},{32,36},{32,52},{33,37},{33,61},{34,39},{34,63},{35,40},{35,64},{36,38},{36,62},{37,38},{37,42},{37,68},{38,44},{38,66},{39,40},{39,41},{39,67},{40,43},{40,65},{41,46},{41,48},{41,57},{42,45},{42,48},{42,59},{43,45},{43,47},{43,60},{44,46},{44,47},{44,58},{45,52},{45,53},{46,49},{46,54},{47,51},{47,55},{48,50},{48,56},{49,52},{49,56},{49,70},{50,51},{50,53},{50,72},{51,54},{51,71},{52,55},{52,69},{53,57},{53,58},{54,59},{54,60},{55,57},{55,59},{56,58},{56,60},{57,61},{58,63},{59,64},{60,62},{61,62},{61,66},{62,68},{63,64},{63,65},{64,67},{65,70},{65,72},{66,69},{66,72},{67,69},{67,71},{68,70},{68,71}};

We can check the diameter easily with the code below.

GraphDiameter[Graph[#[[1]] \[UndirectedEdge] #[[2]] & /@ edgy53]]

Graphing this in various ways shows a messy graph. This particular embedding has a lot of structure to it, though. Take a look at grouping the 72 vertices into 18 blocks of 4 vertices.

sub18=RotateLeft[SortBy[Union[Ceiling[edgy53/4]], #[[2]]-#[[1]]&],6];
GraphPlot[Rule@@@sub18, VertexLabeling->True, Method-> "CircularEmbedding"]  

subgraph 18

A highly symmetric graph is the result. The next stage would be to shuffle each set of 4 vertices in some nice way so that the full 72 vertex graph has lots of symmetry. Maybe someone else can do that.

Graph[#[[1]] \[UndirectedEdge] #[[2]] & /@ edgy53, VertexCoordinates -> Thread[Range[72] -> CirclePoints[72]]]   
Posted 4 months ago

I'm quite curious about how @Ed Pegg found his drawings.

The circular embeddings look to come from (generalized) LCF notations:

  • degreediameter33: {{-10, 7, -6, 5, -7, -10, 7, -5, 6, -7, -10, 7, 5, -4, -7, -10, 7, 4, -5, -7}, 1}
  • degreediameter42: {{{-5, 5}, {4, 8}, {-4, 8}, {4, 7}, {-4, 7}}, 3}
  • degreediameter52: {{{-11, 2, 5}, {-6, -3, 10}, {-10, -3, 6}, {-5, 5,11}, {-6, 3, 10}, {-9, 3, 6}, {-5, -2, 9}, {-10, -6, 6}}, 3}

Similarly, one can get this one:

  • degreediameter34: {{-19, -16, 13, 7, -9, -16, 15, 9, -10, -16, -7, 15, 8, -17, 15, -13, -9, 8, 14, -19, -8, -15, 8, 16, 11, -8, -15, 16, 9, -15, -8, 16, -14, 9, 17, -11, 10, -9}, 1}

degreediameter34 order-1 LCF embedding

Posted 4 months ago

My 34 graph was faulty. Here's a corrected version.

edges34={{1,2},{1,36},{1,37},{2,3},{2,14},{3,4},{3,29},{4,5},{4,34},{5,6},{5,21},{6,7},{6,26},{7,8},{7,38},{8,9},{8,15},{9,10},{9,35},{10,11},{10,28},{11,12},{11,20},{12,13},{12,32},{13,14},{13,25},{14,15},{15,16},{16,17},{16,22},{17,18},{17,33},{18,19},{18,27},{19,20},{19,37},{20,21},{21,22},{22,23},{23,24},{23,30},{24,25},{24,36},{25,26},{26,27},{27,28},{28,29},{29,30},{30,31},{31,32},{31,38},{32,33},{33,34},{34,35},{35,36},{37,38}};  
coords = Thread[Join[Range[36],{37,38}]->Join[RotateRight[Table[{Sin[2 Pi n/36],Cos[2 Pi n/36]},{n,1,36}],1],{{0,1/3},{-1/6,1/2}}]];
GraphPlot[Rule @@@ edges34, VertexCoordinateRules -> coords]

graph deg=3 diam=4

Posted 4 months ago

Here's a symmetrical embedding for the 72 vertex graph of degree=5, diameter=3.

e53={{1,2},{1,13},{1,24},{1,62},{1,72},{2,3},{2,21},{2,37},{2,66},{3,4},{3,8},{3,28},{3,59},{4,5},{4,16},{4,41},{4,51},{5,6},{5,24},{5,45},{5,64},{6,7},{6,11},{6,31},{6,38},{7,8},{7,19},{7,54},{7,68},{8,9},{8,43},{8,72},{9,10},{9,14},{9,34},{9,65},{10,11},{10,22},{10,47},{10,57},{11,12},{11,27},{11,70},{12,13},{12,17},{12,37},{12,44},{13,14},{13,50},{13,60},{14,15},{14,25},{14,54},{15,16},{15,20},{15,40},{15,71},{16,17},{16,29},{16,63},{17,18},{17,33},{17,52},{18,19},{18,23},{18,26},{18,43},{19,20},{19,56},{19,66},{20,21},{20,31},{20,60},{21,22},{21,46},{21,53},{22,23},{22,35},{22,69},{23,24},{23,39},{23,58},{24,25},{24,32},{25,26},{25,37},{25,48},{26,27},{26,45},{26,61},{27,28},{27,32},{27,52},{28,29},{28,40},{28,65},{29,30},{29,48},{29,69},{30,31},{30,35},{30,55},{30,62},{31,32},{31,43},{32,33},{32,67},{33,34},{33,38},{33,58},{34,35},{34,46},{34,71},{35,36},{35,51},{36,37},{36,41},{36,61},{36,68},{37,38},{38,39},{38,49},{39,40},{39,44},{39,64},{40,41},{40,53},{41,42},{41,57},{42,43},{42,47},{42,50},{42,67},{43,44},{44,45},{44,55},{45,46},{45,70},{46,47},{46,59},{47,48},{47,63},{48,49},{48,56},{49,50},{49,61},{49,72},{50,51},{50,69},{51,52},{51,56},{52,53},{52,64},{53,54},{53,72},{54,55},{54,59},{55,56},{55,67},{56,57},{57,58},{57,62},{58,59},{58,70},{59,60},{60,61},{60,65},{61,62},{62,63},{63,64},{63,68},{64,65},{65,66},{66,67},{66,71},{67,68},{68,69},{69,70},{70,71},{71,72}};

Graph[#[[1]] \[UndirectedEdge] #[[2]] & /@ e53, VertexCoordinates -> Thread[Range[72] -> CirclePoints[72]]]  

degree 5 diameter 3

The circular embeddings look to come from (generalized) LCF notations:

Hello @Eric,

Thanks for the response. It's nice to see you post here. MathWorld is a resource used and appreciated by so many—thank you for developing and maintaining it!

What I meant with my question is that I would have been interested in the general approach or methodology that others used to construct such embeddings. I tried to describe my approach above (starting with automorphism groups and vertex orbits).

Posted 4 months ago

The degree 3, diameter 5 graph is something I saw on a site that no longer seems stable. But I had a screen capture. deg 3 diam 5

I implemented that but didn't check it. As stated, a diameter 6 graph results. The error is "j \pm 1", which should be "j+1". With the correction, the correct graph comes out. I've updated degreediameter35 up in the first post.

raw35 = Flatten[{
Flatten[Table[{{"A",i,j}, {"B",Mod[i+(-1)^n 2^j ,7],Mod[j+1,3] }},{i,0,6},{j,0,2},{n,1,2}],2], 
Flatten[Table[{{"A",i,j}, {"C",i,j }},{i,0,6},{j,0,2}],1],
Flatten[Table[{{"B",i,j}, {"C",i,j }},{i,0,6},{j,0,2}],1],
Flatten[Table[{ {"C",i,j },{"D",i,4}},{i,0,6},{j,0,2}],1]},1];
edges35=Sort[raw35/.Thread[Union[Flatten[raw35,1]]-> Range[70]]]  

It's not hard to look at all of the Hamiltonian cycles for a small cubic graph. None of them seem to be all that symmetrical.

e35=Join[Partition[Range[70],2,1,1],{{1,25},{2,62},{3,30},{4,14},{5,37},{6,50},{7,65},{8,58},{9,33},{10,70},{11,19},{12,45},{13,55},{15,68},{16,60},{17,48},{18,38},{20,52},{21,29},{22,66},{23,56},{24,49},{26,36},{27,44},{28,59},{31,41},{32,47},{34,54},{35,67},{39,63},{40,57},{42,69},{43,51},{46,64},{53,61}}];
g35 =Graph[UndirectedEdge@@@e35,VertexCoordinates->Thread[Range[70]->CirclePoints[70]]]

deg 3 diameter 5

However, there does seem to be some vertical symmetry, so perhaps a trick like what I did with the 3-4 graph would work.

Posted 4 months ago

For regular Hamiltonian graphs, finding LCF embeddings is the simplest approach I know. In cases where all Hamiltonian cycles can be enumerated, simply find them all and compute the corresponding (canonicalized) LCF notations. Any with large exponents have nice symmetric circular embeddings.

In cases where all cannot be found (because there are too many to enumerate completely, the Hoffman-Singleton graph being a good example), randomly permute the graph many times to see if you can find a Hamiltonian cycle giving a nice LCF notation.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract