A348365 Number of connected realizable graphs on n vertices.

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

Offset: 1

Author

Pierre-Louis Giscard, Oct 15 2021

Keywords

• nonn
• hard
• more

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.

Examples

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

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).

Crossrefs

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

Formula

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