A348365 Number of connected realizable graphs on n vertices.

1, 1, 2, 5, 15, 58, 265

Offset

1,3

Comments

a(n) is the number of realizable connected unlabelled graphs on n vertices. A realizable graph H is a graph for which there exists a (multi di)graph G such that the vertices of H are exactly the simple cycles of G and two vertices of H share an edge if the corresponding simple cycles in G share at least one vertex. Thus H encodes the "cycle skeleton" of G. Formally, H is the dependency graph of the trace monoid formed by the simple cycles on G equipped with the independency relation that two cycles commute if they are vertex-disjoint.

Links

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

Jean Fromentin, Pierre-Louis Giscard and Théo Karaboghossian, Why walks lead us astray in the study of graphs, arXiv:2110.15618 [math.CO], 2021.

Théo Karaboghossian, Pierre-Louis Giscard and Jean Fromentin, Trace monoids, hike monoids and number theory, slides, WACA (Calais, France 2021).

Formula

a(n) is strictly increasing, a(n+1)>a(n) and a(n) grows at least exponentially with n as n->infinity.

Example

For n = 4, a(4) = 5 because out of the 6 unlabelled connected graphs on 4 vertices only 1 is not realizable: the square.

Crossrefs

Compare with A001349 (all graphs), sequence close to A048192.

Sequence in context: A351158 A187981 A334155 * A048192 A078792 A208808

Adjacent sequences: A348362 A348363 A348364 * A348366 A348367 A348368

Keyword

nonn,hard,more

Author

Pierre-Louis Giscard, Oct 15 2021

Status

approved