A369192 -id:A369192 - cp's OEIS frontend

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

1, 0, 1, 2, 5, 10, 28, 68, 193, 534, 1568, 4635, 14146, 43610, 137015, 435227, 1400058, 4547768, 14917504, 49348612, 164596939, 553177992, 1872805144, 6385039022, 21917878860, 75739158828, 263438869515, 922219844982, 3249042441125, 11519128834499, 41097058489426

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

			The a(0) = 1 through a(5) = 10 simple graphs:
  {}  .  {12}  {12-13}     {12-34}        {12-13-45}
               {12-13-23}  {12-13-14}     {12-13-14-15}
                           {12-13-24}     {12-13-14-25}
                           {12-13-14-23}  {12-13-23-45}
                           {12-13-24-34}  {12-13-24-35}
                                          {12-13-14-15-23}
                                          {12-13-14-23-25}
                                          {12-13-14-23-45}
                                          {12-13-14-25-35}
                                          {12-13-24-35-45}

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

The connected case is A005703, labeled A129271.
The case of exactly n edges is A006649, covering case of A001434.
The labeled version is A369191.
Partial row sums of A370167, covering case of A008406.
The non-covering version with loops is A370168, labeled A066383.
The version with loops is A370169, labeled A369194.
The non-covering version is A370315, labeled A369192.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A054548, A062734, A116508, A367862, A367863, A368599, A369193.

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

\\ G defined in A008406.
a(n)=my(A=O(x*x^n)); if(n==0, 1, polcoef((G(n,A)-G(n-1,A))/(1-x), n)) \\ Andrew Howroyd, Feb 19 2024

a(8) onwards from Andrew Howroyd, Feb 19 2024

A370315 Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 54, 146, 436, 1372, 4577, 15971, 58376, 221876, 876012, 3583099, 15159817, 66248609, 298678064, 1387677971, 6637246978, 32648574416, 165002122350, 855937433641, 4553114299140, 24813471826280, 138417885372373, 789683693019999, 4603838061688077

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

			The a(1) = 1 through a(4) = 9 graph edge sets:
  {}  {}    {}          {}
      {12}  {12}        {12}
            {12-13}     {12-13}
            {12-13-23}  {12-34}
                        {12-13-14}
                        {12-13-23}
                        {12-13-24}
                        {12-13-14-23}
                        {12-13-24-34}

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

The case of exactly n edges is A001434, covering A006649.
The connected covering case is A005703, labeled A129271.
Partial row sums of A008406, covering A370167.
The labeled version is A369192.
The version with loops is A370168, labeled A066383.
The covering case is A370316, labeled A369191.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000666, A322661, A322700, A369194, A369196, A369197, A369199, A370169.

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}]], Length[#]<=n&]]],{n,0,5}]

a(n) = if(n<=1, n>=0, polcoef(G(n, O(x*x^n))/(1-x),n)) \\ G(n) defined in A008406. - Andrew Howroyd, Feb 20 2024

Sum of first n+1 terms of row n of A008406.

A369198 Number of labeled loop-graphs with n vertices and the same number of edges as covered vertices.

Original entry on oeis.org

1, 2, 6, 30, 241, 2759, 40824, 736342, 15622835, 380668095, 10467815086, 320529284621, 10813165015074, 398413594789777, 15917197015926392, 685312404706694574, 31631317971844128229, 1558017329350990780607, 81567807853701988869120, 4522975947689168088308305

Offset: 0

Gus Wiseman, Jan 18 2024

nonn

			The a(0) = 1 through a(3) = 30 loop-graphs (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{2}}        {{2}}
             {{1},{2}}    {{3}}
             {{1},{1,2}}  {{1},{2}}
             {{2},{1,2}}  {{1},{3}}
                          {{2},{3}}
                          {{1},{1,2}}
                          {{1},{1,3}}
                          {{2},{1,2}}
                          {{2},{2,3}}
                          {{3},{1,3}}
                          {{3},{2,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{2},{2,3}}
                          {{1},{3},{1,2}}
                          {{1},{3},{2,3}}
                          {{2},{3},{1,2}}
                          {{2},{3},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1},{1,3},{2,3}}
                          {{2},{1,2},{1,3}}
                          {{2},{1,2},{2,3}}
                          {{2},{1,3},{2,3}}
                          {{3},{1,2},{1,3}}
                          {{3},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1,2},{1,3},{2,3}}

The version counting all vertices is A014068.
The loopless case is A367862, counting all vertices A116508.
The covering case is A368597, connected A368951.
With inequality we have A369196, covering A369194, connected A369197.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs, also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000272, A000666, A006649, A062740, A066383, A367863, A369192, A369193.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[#]==Length[Union@@#]&]],{n,0,5}]

Binomial transform of A368597.

cp's OEIS Frontend

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A370315 Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A369198 Number of labeled loop-graphs with n vertices and the same number of edges as covered vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula