OFFSET
1,5
COMMENTS
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.
LINKS
John Cu, Length of Embedded Circuits in Geodetic Graphs, AMSI Vacation Research Scholar project, 2021.
Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
K. R. Parthasarathy and N. Srinivasan, Some general constructions of geodetic blocks, Journal of Combinatorial Theory, Series B (33) Issue 2, October 1982, Pages 121-136.
Florian Stober and Armin Weiß, Geodetic Graphs: Experiments and New Constructions, arXiv:2308.08970 [math.CO], 2023.
Wikipedia, Geodetic graph
EXAMPLE
For n=5 there are exactly a(5)=2 biconnected geodetic graphs: a 5-cycle and the complete graph on 5 vertices.
PROG
(Python using Sagemath environment)
from sage.all import *
from sage.graphs.graph import Graph
import itertools
def geodetic_check(G):
# G = Graph(graph6) # converts from graph6 to sage's Graph
all_dist = G.distance_all_pairs() # distance between every pair of vertices
# check for geodeticity
# for each pair of vertices in G
for pair in itertools.combinations(G.vertices(), 2):
(u, v) = pair
# find any neighbor i of v that has dist(u, i) = dist(u, v) - 1 excluding u
predecessor = [i for i in G.neighbors(v) if all_dist[u][i] == all_dist[u][v] - 1 and i != u]
# if there are more than 1 such neighbor
if len(predecessor) > 1:
return
CROSSREFS
KEYWORD
nonn,more
AUTHOR
John Cu and Murray Elder, Jan 28 2021
EXTENSIONS
a(12)-a(25) from Florian Stober and Armin Weiß added by Murray Elder, Nov 14 2023
STATUS
approved