GraphBank

The Order-Degree Problem

The Degree-Diameter Problem

The order-degree problem is to find the smallest diameter of graphs given order and maximum degree. If there are multiple graphs which take the minimum diameter, a graph which has minimum average shortest path length (ASPL) will be the solution. Like the degree-diameter problem, there is known lower bound to this problem. The order-degree problem can be applied to practical use such as constructing low-latency computer network. An international competition for finding solutions of the order-degree problem Graph Golf has been held annually since 2015. Graph Bank incorporates solutions from Graph Golf.

Degree \ Order 16 36 64 96 256 300 384 512 1024 1560 3250 4096 10000 100000
3 3 / 2.2 4 / 3.06667 5 / 3.76984 6 / 4.27237 8 / 5.63637 11 / 6.45338 9 / 6.22562 11 / 7.07883 11 / 7.67897 13 / 8.6834 15 / 9.74785 13 / 9.78684 15 / 11.11141 20 / 14.692
4 3 / 1.75 4 / 3.06667 4 / 2.86905 6 / 3.51908 6 / 4.13376 7 / 4.54118 8 / 4.76953 8 / 5.03691 9 / 5.6601 9 / 6.0293 10 / 6.70522 9 / 6.75251 10 / 7.60118 13 / 9.82323
7 2 / 1.53333 3 / 1.96508 3 / 2.44444 4 / 2.52851 5 / 3.07714 4 / 3.01229 5 / 3.3161 5 / 3.46941 6 / 3.85733 6 / 4.09782 6 / 4.49848 7 / 4.62774 7 / 5.05994 13 / 9.82323
8 2 / 1.46667 3 / 1.8619 3 / 1.92659 4 / 2.38728 4 / 2.73597 4 / 3.01229 5 / 3.11518 4 / 3.11138 5 / 3.50538 5 / 3.8255 6 / 4.21886 6 / 4.33613 7 / 4.77929 13 / 9.82323
11 2 / 1.26667 3 / 1.69206 3 / 1.92659 3 / 2.11447 3 / 2.56863 4 / 2.63507 4 / 2.73117 4 / 2.8456 4 / 3.05869 5 / 3.3715 5 / 3.66771 5 / 3.7599 6 / 4.16512 13 / 9.82323
16 N / A 2 / 1.54286 2 / 1.74603 3 / 1.86645 3 / 1.99173 3 / 2.35349 4 / 2.45735 4 / 2.56371 4 / 2.78117 4 / 2.91717 4 / 3.2217 4 / 3.25272 5 / 3.62517 13 / 9.82323
23 N / A 2 / 1.34286 2 / 1.63492 3 / 1.75833 2 / 1.9098 3 / 2.07344 3 / 2.16865 3 / 2.29391 4 / 2.56643 4 / 2.69425 4 / 2.86832 4 / 2.88614 4 / 3.20026 13 / 9.82323
32 N / A 2 / 1.08571 2 / 1.49206 2 / 1.66316 2 / 1.9098 3 / 1.91338 3 / 1.97143 3 / 2.05671 3 / 1.99784 3 / 2.49107 4 / 2.71757 4 / 2.76978 4 / 2.94021 13 / 9.82323
40 N / A N / A 2 / 1.36508 2 / 1.57895 2 / 1.9098 3 / 1.86861 3 / 1.90479 3 / 1.95535 3 / 1.99784 3 / 2.03823 3 / 2.59545 3 / 2.66423 4 / 2.84947 13 / 9.82323
57 N / A N / A 2 / 1.09524 2 / 1.4 2 / 1.77647 2 / 1.80936 3 / 1.85123 3 / 1.88926 3 / 1.97918 3 / 2.03823 3 / 2.07002 3 / 2.43344 3 / 2.71552 13 / 9.82323
60 N / A N / A 2 / 1.04762 2 / 1.36842 2 / 1.76471 2 / 1.79933 3 / 1.84338 3 / 1.88291 3 / 1.96486 3 / 2.03823 3 / 2.07002 3 / 2.29522 3 / 2.65016 13 / 9.82323
64 N / A N / A N / A 2 / 1.32632 2 / 1.74902 2 / 1.78595 2 / 1.8329 3 / 1.87485 3 / 1.95115 3 / 2.02338 3 / 2.07002 3 / 1.9995 3 / 2.60993 13 / 9.82323