[seqfan] Diameter-avoiding graphs

hv at crypt.org hv at crypt.org
Fri Jan 8 14:02:17 CET 2010


Inspired by my wrong first guess to a question about how to calculate
the diameter of a graph efficiently:

How many connected undirected graphs with n vertices have at least one vertex
v such that if you consider all the vertices that are equally at the furthest
distance from v, none of them is the endpoint of a diameter of the graph?

I find the first three examples at n=7 (use a fixed font to view):

 0-1-2-3   0-1-2-3   0-1-2-3
   |   |     | |     | | |
   6-5-4     6-5-4   6-5-4

In the first case, for example, the diameter is length 4, and the only
diameter endpoints are vertices 0 and 4. From vertex 6, the greatest distance
is 3, and the only vertex at that distance is vertex 3, which isn't an
endpoint. So this graph qualifies. (Similarly from vertex 2, which reaches
only vertex 5.)

For n in 7..11, I count 3, 87, 2705, 117250, 7799406 such graphs, and counting
each qualifying vertex I find 4, 112, 3434, 150078, 10217316 (neither sequence
in the OEIS).

I don't have much confidence in my code to count these, however - can
anyone confirm or deny, or add some theory?

Hugo




More information about the SeqFan mailing list