cp's OEIS Frontend

A140637 Number of unlabeled graphs of positive excess with n nodes.

%I A140637 #20 Jun 22 2025 13:43:25
%S A140637 0,0,0,2,15,110,936,12073,273972,12003332,1018992968,165091159269,
%T A140637 50502031331411,29054155657134165,31426485969804026075,
%U A140637 64001015704527557101231,245935864153532932681481794,1787577725145611700547871854870,24637809253125004524383007473440146
%N A140637 Number of unlabeled graphs of positive excess with n nodes.
%C A140637 We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices."
%C A140637 If G has just one complex component with 4 nodes, the "non-complex part" of G can be,
%C A140637 a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.
%C A140637 b) One triangle and one isolated vertex, or 2*1=2 graphs.
%C A140637 c) One unicyclic graph of order 4, so 2*2=4 graphs.
%C A140637 Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - _Gus Wiseman_, Feb 13 2024
%H A140637 Svante Janson, Donald E. Knuth, Tomasz Łuczak and Boris Pittel, <a href="http://www.math.uu.se/~svante/papers/index.html">The Birth of the Giant Component</a>.
%F A140637 a(n) = A000088(n) - A134964(n).
%e A140637 Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.
%e A140637 Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below:
%e A140637   O---O...O---O
%e A140637   |\..|...|\./|
%e A140637   |.\.|...|.X.|
%e A140637   |..\|...|/.\|
%e A140637   O---O...O---O
%e A140637 If G has one complex component with 5 nodes, the non-complex part of G can be,
%e A140637 a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.
%e A140637 b) One triangle, so A140636(5) = 13 graphs.
%e A140637 If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs.
%e A140637 If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs.
%e A140637 Finally if G is connected, we have A140636(8), or 11005 graphs.
%e A140637 The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.
%t A140637 brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
%t A140637 Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}] (* _Gus Wiseman_, Feb 14 2024 *)
%Y A140637 Cf. A000088, A005195, A001429.
%Y A140637 The labeled complement is A133686, covering A367869, connected A129271.
%Y A140637 The complement is A134964, connected A005703.
%Y A140637 The connected covering case is A140636.
%Y A140637 The labeled version is A367867, covering A367868, connected A140638.
%Y A140637 Set-systems not of this type are A367902, ranks A367906.
%Y A140637 Set-systems of this type are A367903, ranks A367907.
%Y A140637 For set-systems we have A368094, complement A368095.
%Y A140637 For multiset partitions we have A368097, complement A368098.
%Y A140637 Factorizations of this type are A368413, complement A368414.
%Y A140637 Cf. A001349, A002494, A006125, A055621, A367769, A367770, A367901.
%K A140637 nonn
%O A140637 1,4
%A A140637 _Washington Bomfim_, May 21 2008