Embeddings for Degree Diameter graphs

Posted 3 years ago
5453 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"}]] 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. Can anyone find improved pictures for these graphs? The attached notebook has larger untamed degree-diameter graphs. Attachments:
15 Replies
Sort By:
Posted 3 years ago
 Looks like 34 is kin to symmetries: Graph[UndirectedEdge @@@ degreediameter34, GraphLayout -> #] & /@ {"RadialDrawing", "BalloonEmbedding"} Is this sort of thing you are looking for?
Posted 3 years ago
 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}] ]] 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}] ]] 
Posted 3 years ago
 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}]]] 
Posted 3 years ago
 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}] ]] 
Posted 9 months ago
 Your first graph, degreediameter33, can be shown like this: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]}} 
Posted 9 months ago
 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:(These do not contain all vertices.)Then notice that it contains these three binary trees emanating from vertex 3:(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.
Posted 9 months ago
 degreediameter42 can be drawn like this:We have two hexagons inside with a 6-fold symmetry and a triangle outside with a 3-fold symmetry.
Posted 9 months ago
 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-symmetriesI 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 9 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"] 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 9 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}
Posted 9 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] 
Posted 9 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]]] 
Posted 9 months ago
 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).
 The degree 3, diameter 5 graph is something I saw on a site that no longer seems stable. But I had a screen capture. 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]]]  However, there does seem to be some vertical symmetry, so perhaps a trick like what I did with the 3-4 graph would work.