cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A348365 Number of connected realizable graphs on n vertices.

This page as a plain text file.
%I A348365 #24 Nov 14 2021 01:36:36
%S A348365 1,1,2,5,15,58,265
%N A348365 Number of connected realizable graphs on n vertices.
%C A348365 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.
%H A348365 Jean Fromentin, Pierre-Louis Giscard and Théo Karaboghossian, <a href="https://arxiv.org/abs/2110.15618">Why walks lead us astray in the study of graphs</a>, arXiv:2110.15618 [math.CO], 2021.
%H A348365 Théo Karaboghossian, Pierre-Louis Giscard and Jean Fromentin, <a href="http://cecile.mammez.free.fr/Organisation_evenements/WACA/slides/Talk_Theo_Karaboghossian.pdf">Trace monoids, hike monoids and number theory</a>, slides, WACA (Calais, France 2021).
%F A348365 a(n) is strictly increasing, a(n+1)>a(n) and a(n) grows at least exponentially with n as n->infinity.
%e A348365 For n = 4, a(4) = 5 because out of the 6 unlabelled connected graphs on 4 vertices only 1 is not realizable: the square.
%Y A348365 Compare with A001349 (all graphs), sequence close to A048192.
%K A348365 nonn,hard,more
%O A348365 1,3
%A A348365 _Pierre-Louis Giscard_, Oct 15 2021