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
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
KEYWORD
nonn,hard,more
AUTHOR
Pierre-Louis Giscard, Oct 15 2021
STATUS
approved