The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #71 Nov 18 2023 08:36:54
%S 0,1,1,1,2,1,3,1,3,4,3,1,9,2,4,8,6,5,13,3,13,19,11,3,32
%N Number of biconnected geodetic graphs with n unlabeled vertices.
%C A graph is geodetic if each pair of vertices is joined by a unique shortest path. A vertex v of a connected graph G is a cut vertex if G-v is disconnected. A connected graph G is biconnected if it has no cut vertices. To obtain this sequence, non-isomorphic (biconnected) graphs were generated using _Brendan McKay_'s nauty program, then the geodetic property was checked on this output.
%H John Cu, <a href="https://vrs.amsi.org.au/student-profile/john-cu/">Length of Embedded Circuits in Geodetic Graphs</a>, AMSI Vacation Research Scholar project, 2021.
%H Brendan McKay and Adolfo Piperno, <a href="http://users.cecs.anu.edu.au/~bdm/nauty/">nauty and Traces</a>. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
%H K. R. Parthasarathy and N. Srinivasan, <a href="https://doi.org/10.1016/0095-8956(82)90063-6">Some general constructions of geodetic blocks</a>, Journal of Combinatorial Theory, Series B (33) Issue 2, October 1982, Pages 121-136.
%H Florian Stober and Armin Weiß, <a href="https://arxiv.org/abs/2308.08970">Geodetic Graphs: Experiments and New Constructions</a>, arXiv:2308.08970 [math.CO], 2023.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Geodetic_graph">Geodetic graph</a>
%e For n=5 there are exactly a(5)=2 biconnected geodetic graphs: a 5-cycle and the complete graph on 5 vertices.
%o (Python using Sagemath environment)
%o from sage.all import *
%o from sage.graphs.graph import Graph
%o import itertools
%o def geodetic_check(G):
%o # G = Graph(graph6) # converts from graph6 to sage's Graph
%o all_dist = G.distance_all_pairs() # distance between every pair of vertices
%o # check for geodeticity
%o # for each pair of vertices in G
%o for pair in itertools.combinations(G.vertices(), 2):
%o (u, v) = pair
%o # find any neighbor i of v that has dist(u, i) = dist(u, v) - 1 excluding u
%o predecessor = [i for i in G.neighbors(v) if all_dist[u][i] == all_dist[u][v] - 1 and i != u]
%o # if there are more than 1 such neighbor
%o if len(predecessor) > 1:
%o return
%Y Cf. A002218, A337179.
%K nonn,more
%O 1,5
%A John Cu and _Murray Elder_, Jan 28 2021
%E a(12)-a(25) from Florian Stober and Armin Weiß added by _Murray Elder_, Nov 14 2023