[seqfan] A064513, A058201, and the graph degree/diameter problem.

Allan Wechsler acwacw at gmail.com
Mon Nov 16 19:53:28 CET 2015


The degree/diameter problem is a classic in extremal graph theory. For a
given degree d and diameter k, we are asked, what is the largest number of
nodes that a graph can have?

In particular, even when the required diameter k=2, we don't know the
answer to this question beyond d=7 or so.

OEIS has two sequences that purport to give the data we have; these are
A058201 and A064513. They give values for d between 1 and 5, inclusive, and
they agree that a(1)=2, a(2)=4, a(3)=10, and a(4) = 15. But they disagree
on a(5): the older sequence says it's 24; the newer one says it's 25.

The first question this raises for me is, why do they say a(2) = 4? Doesn't
a cyclic graph of order 5 have degree 2 and diameter 2?

Wikipedia has articles on the degree/diameter problem. The first column of
their table (
https://en.wikipedia.org/wiki/Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree)
gives values 2, 5, 10, 15, 25, 32, 50. So their a(5) agrees with the later
sequence on OEIS, but their a(2) (and *my* a(2), for that matter!)
disagrees with *both* versions on OEIS.

I propose that we mark A058201 as wrong, but leave it as it stands,
otherwise, and fix A064513 to set a(2)=5 and fill in a(6) and a(7) from the
sources referenced in the Wikipedia articles.



More information about the SeqFan mailing list