|
|
A337179
|
|
Number of geodetic graphs with n unlabeled vertices.
|
|
1
|
|
|
1, 1, 2, 4, 10, 23, 66, 185, 586, 1880, 6360, 21975, 78230, 283087, 1043329, 3895505, 14726263, 56234210, 216719056, 841857211, 3293753840, 12969219563
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A graph is geodetic if each pair of vertices is joined by a unique shortest path. To obtain this sequence, non-isomorphic graphs were generated using Brendan McKay's nauty program, then the geodetic property is checked on this output.
|
|
LINKS
|
Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
|
|
EXAMPLE
|
For n=4 there are a(4)=4 geodetic graphs: a triangle with another edge attached to one vertex, an edge path of length 3, a tripod of 3 edges joined at a common vertex, and a complete graph on 4 vertices.
o
o o /|\
/ \ | o-|-o
o-o---o, o-o-o-o, o-o-o, \|/
o
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(12)-a(22) from Florian Stober and Armin Weiß added by Murray Elder, Nov 14 2023
|
|
STATUS
|
approved
|
|
|
|