OFFSET
1,4
COMMENTS
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."
If G has just one complex component with 4 nodes, the "non-complex part" of G can be,
a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.
b) One triangle and one isolated vertex, or 2*1=2 graphs.
c) One unicyclic graph of order 4, so 2*2=4 graphs.
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
LINKS
Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel, The Birth of the Giant Component.
EXAMPLE
Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.
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:
O---O...O---O
|\..|...|\./|
|.\.|...|.X.|
|..\|...|/.\|
O---O...O---O
If G has one complex component with 5 nodes, the non-complex part of G can be,
a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.
b) One triangle, so A140636(5) = 13 graphs.
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.
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.
Finally if G is connected, we have A140636(8), or 11005 graphs.
The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.
MATHEMATICA
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 5}] (* Gus Wiseman, Feb 14 2024 *)
CROSSREFS
The connected covering case is A140636.
KEYWORD
nonn
AUTHOR
Washington Bomfim, May 21 2008
STATUS
approved