Message Boards

WOLFRAM COMMUNITY

12721 Views

15 Replies

17 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Embeddings for Degree Diameter graphs

Ed Pegg

Ed Pegg, Wolfram Research

Posted 10 years ago

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:

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.

POSTED BY: Ed Pegg

15 Replies

Sort By:

Eric Weisstein

Posted 7 years 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.

POSTED BY: Eric Weisstein

Ed Pegg

Ed Pegg, Wolfram Research

Posted 7 years 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. 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.

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 BY: Ed Pegg

Szabolcs Horvát

Posted 7 years 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 manythank 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 BY: Szabolcs Horvát

Ed Pegg

Ed Pegg, Wolfram Research

Posted 7 years 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]]]

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

POSTED BY: Ed Pegg

Ed Pegg

Ed Pegg, Wolfram Research

Posted 7 years 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]

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 BY: Ed Pegg

Eric Weisstein

Posted 7 years 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 BY: Eric Weisstein

Ed Pegg

Ed Pegg, Wolfram Research

Posted 7 years 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]]]

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 BY: Ed Pegg

Szabolcs Horvát

Posted 7 years 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-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 BY: Szabolcs Horvát

Szabolcs Horvát

Posted 7 years 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 BY: Szabolcs Horvát

Szabolcs Horvát

Posted 7 years 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 BY: Szabolcs Horvát

Szabolcs Horvát

Posted 7 years 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]}}

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

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]}}

POSTED BY: Szabolcs Horvát

Ed Pegg

Ed Pegg, Wolfram Research

Posted 10 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}] ]]

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

POSTED BY: Ed Pegg

Ed Pegg

Ed Pegg, Wolfram Research

Posted 10 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}]]]

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

POSTED BY: Ed Pegg

Ed Pegg

Ed Pegg, Wolfram Research

Posted 10 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}] ]]

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

POSTED BY: Ed Pegg

Vitaliy Kaurov

Vitaliy Kaurov, WOLFRAM Research

Posted 10 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 BY: Vitaliy Kaurov

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback