A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset

0,7

Comments

These are graphs with n vertices and n edges having at least two cycles in the same component.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Formula

a(n) = A001434(n) - A137917(n).

Example

The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}

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}], {n}], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 5}]

Crossrefs

Without the choice condition we have A001434, covering A006649.

The labeled version without choice is A116508, covering A367863, A367862.

The complement is counted by A137917, labeled A137916.

For any number of edges we have A140637, complement A134964.

For labeled set-systems we have A368600.

The case with loops is A368835, labeled A368596.

The labeled version is A369143, covering A369144.

A006129 counts covering graphs, unlabeled A002494.

A007716 counts unlabeled multiset partitions, connected A007718.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A129271 counts connected choosable simple graphs, unlabeled A005703.

Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

Sequence in context: A037709 A037611 A171472 * A220720 A024311 A210100

Adjacent sequences: A369198 A369199 A369200 * A369202 A369203 A369204

Keyword

nonn

Author

Gus Wiseman, Jan 22 2024

Extensions

a(25) onwards from Andrew Howroyd, Feb 02 2024

Status

approved