cp's OEIS Frontend

A337178 Number of biconnected geodetic graphs with n unlabeled vertices.

%I A337178 #71 Nov 18 2023 08:36:54
%S A337178 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 A337178 Number of biconnected geodetic graphs with n unlabeled vertices.
%C A337178 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 A337178 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 A337178 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 A337178 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 A337178 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 A337178 Wikipedia, <a href="https://en.wikipedia.org/wiki/Geodetic_graph">Geodetic graph</a>
%e A337178 For n=5 there are exactly a(5)=2 biconnected geodetic graphs: a 5-cycle and the complete graph on 5 vertices.
%o A337178 (Python using Sagemath environment)
%o A337178 from sage.all import *
%o A337178 from sage.graphs.graph import Graph
%o A337178 import itertools
%o A337178 def geodetic_check(G):
%o A337178     # G = Graph(graph6)  # converts from graph6 to sage's Graph
%o A337178     all_dist = G.distance_all_pairs()  # distance between every pair of vertices
%o A337178     # check for geodeticity
%o A337178     # for each pair of vertices in G
%o A337178     for pair in itertools.combinations(G.vertices(), 2):
%o A337178         (u, v) = pair
%o A337178         # find any neighbor i of v that has dist(u, i) = dist(u, v) - 1 excluding u
%o A337178         predecessor = [i for i in G.neighbors(v) if all_dist[u][i] == all_dist[u][v] - 1 and i != u]
%o A337178         # if there are more than 1 such neighbor
%o A337178         if len(predecessor) > 1:
%o A337178             return
%Y A337178 Cf. A002218, A337179.
%K A337178 nonn,more
%O A337178 1,5
%A A337178 John Cu and _Murray Elder_, Jan 28 2021
%E A337178 a(12)-a(25) from Florian Stober and Armin Weiß added by _Murray Elder_, Nov 14 2023