A337178 Number of biconnected geodetic graphs with n unlabeled vertices.

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

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

Table of n, a(n) for n=1..25.

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

Cf. A002218, A337179.

Sequence in context: A177040 A336887 A163313 * A321893 A308673 A324287

Adjacent sequences: A337175 A337176 A337177 * A337179 A337180 A337181

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