|
|
A337178
|
|
Number of biconnected geodetic graphs with n unlabeled vertices.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
|
|
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
|
|
|
EXTENSIONS
|
a(12)-a(25) from Florian Stober and Armin Weiß added by Murray Elder, Nov 14 2023
|
|
STATUS
|
approved
|
|
|
|