A054923 -id:A054923

A001436

Number of connected graphs with n nodes, n+2 edges.
(Formerly M3583 N1453)

+0
3

0, 0, 0, 1, 4, 22, 107, 486, 2075, 8548, 33851, 130365, 489387, 1799700, 6499706, 23118465, 81134475, 281454170, 966388692, 3288208176, 11098235911, 37188198356, 123800999503, 409715126169, 1348690034859, 4417932007626, 14407260221164

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Sean A. Irvine, Table of n, a(n) for n = 1..40

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

CROSSREFS

A diagonal of A054923.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Description corrected Aug 02 1996.

More terms from Sean A. Irvine, Jul 23 2012

STATUS

approved

A002905

Number of connected graphs with n edges.
(Formerly M2486 N0985)

+0
27

1, 1, 1, 3, 5, 12, 30, 79, 227, 710, 2322, 8071, 29503, 112822, 450141, 1867871, 8037472, 35787667, 164551477, 779945969, 3804967442, 19079312775, 98211456209, 518397621443, 2802993986619, 15510781288250, 87765472487659, 507395402140211, 2994893000122118, 18035546081743772, 110741792670074054, 692894304050453139

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Max Alekseyev, Table of n, a(n) for n = 0..60

G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.

Nicolas Borie, The Hopf Algebra of graph invariants, arXiv preprint arXiv:1511.05843 [math.CO], 2015.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Mike Cummings and Adam Van Tuyl, The GeometricDecomposability package for Macaulay2, arXiv:2211.02471 [math.AC], 2022.

Anjan Dutta and Hichem Sahbi, Graph Kernels based on High Order Graphlet Parsing and Hashing, arXiv:1803.00425 [cs.CV], 2018.

Gordon Royle, Small graphs

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 1 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Eric Weisstein's World of Mathematics, Polynema.

FORMULA

A000664 and this sequence are an Euler transform pair. - N. J. A. Sloane, Aug 30 2016

EXAMPLE

a(3) = 3 since the three connected graphs with three edges are a path, a triangle and a "Y".

The first difference between this sequence and A046091 is for n=9 edges where we see K_{3,3}, the well-known "utility graph".

MATHEMATICA

A000664 = Cases[Import["https://oeis.org/A000664/b000664.txt", "Table"], {_, _}][[All, 2]];

(* EulerInvTransform is defined in A022562 *)

Join[{1}, EulerInvTransform[Rest @ A000664]] (* Jean-François Alcover, May 10 2019, updated Mar 17 2020 *)

CROSSREFS

Column sums of A054924 or equivalently row sums of A054923.

Cf. A000664, A046091 (for connected planar graphs), A275421 (multisets).

Apart from a(3), same as A003089.

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jan 12 2000

More terms from Gordon F. Royle, Jun 05 2003

a(25)-a(26) from Max Alekseyev, Sep 19 2009

a(27)-a(60) from Max Alekseyev, Sep 07 2016

STATUS

approved

A046742

Triangle of number of connected graphs with k >= 1 edges and n nodes (2 <= n <= k+1).

+0
5

1, 0, 1, 0, 1, 2, 0, 0, 2, 3, 0, 0, 1, 5, 6, 0, 0, 1, 5, 13, 11, 0, 0, 0, 4, 19, 33, 23, 0, 0, 0, 2, 22, 67, 89, 47, 0, 0, 0, 1, 20, 107, 236, 240, 106, 0, 0, 0, 1, 14, 132, 486, 797, 657, 235, 0, 0, 0, 0, 9, 138, 814, 2075, 2678, 1806, 551, 0, 0, 0, 0, 5, 126, 1169, 4495, 8548, 8833, 5026, 1301

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,6

LINKS

Sean A. Irvine, Table of n, a(n) for n = 1..190

G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.

Gordon Royle, Small graphs

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points, Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967. doi: 10.2172/4180737. Table 1 (complete up to 18 nodes)

EXAMPLE

1;

0 1;

0 1 2;

0 0 2 3;

0 0 1 5 6;

0 0 1 5 13 11;

0 0 0 4 19 33 23;

0 0 0 2 22 67 89 47;

0 0 0 1 20 107 236 240 106;

0 0 0 1 14 132 486 797 657 235;

0 0 0 0 9 138 814 2075 2678 1806 551;

0 0 0 0 5 126 1169 4495 8548 8833 5026 1301;

0 0 0 0 2 95 1454 8404 22950 33851 28908 13999 3159;

0 0 0 0 1 64 1579 13855 53863 109844 130365 93569 39260 7741;

0 0 0 0 1 40 1515 20303 112618 313670 499888 489387 300748 110381 19320;

0 0 0 0 0 21 1290 26631 211866 803905 1694642 2179949 1799700 959374 311465 ...

... (so with 5 edges there's 1 graph with 4 nodes, 5 with 5 nodes and 1 with 6 nodes).

CROSSREFS

Cf. A002905 (row sums), A008406, A046751, A054923, A054924 (transpose), A001349 (column sums).

KEYWORD

nonn,easy,nice,tabl

AUTHOR

N. J. A. Sloane

EXTENSIONS

Data corrected by Sean A. Irvine, Apr 23 2021

STATUS

approved

A046751

Triangle read by rows of number of connected graphs with n nodes and k edges (n >= 2, 1 <= k <= n(n-1)/2).

+0
5

1, 0, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 0, 3, 5, 5, 4, 2, 1, 1, 0, 0, 0, 0, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,7

LINKS

Table of n, a(n) for n=2..78.

G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.

Gordon Royle, Small graphs

Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

EXAMPLE

1;

0,1,1;

0,0,2,2,1, 1;

0,0,0,3,5, 5, 4, 2, 1, 1;

0,0,0,0,6,13,19,22, 20, 14, 9, 5, 2, 1, 1;

0,0,0,0,0,11,33,67,107,132,138,126,95,64,40,21,10,5,2,1,1;

[ the 4th row giving the numbers of connected graphs with 4 nodes and from 1 to 10 edges ].

CROSSREFS

See A054924, which is the main entry for this triangle.

Cf. A002905, A008406, A046742, A054923, A054924.

KEYWORD

nonn,easy,nice,tabf

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Apr 21 2000

STATUS

approved

A054924

Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled connected graphs with n nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

+0
20

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0, 3, 5, 5, 4, 2, 1, 1, 0, 0, 0, 0, 0, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,11

REFERENCES

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

LINKS

R. W. Robinson, Rows 1 to 20 of triangle, flattened (corrected by Sean A. Irvine, Apr 29 2022)

G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.

Sean A. Irvine, Java code (github)

Gordon Royle, Small graphs

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

EXAMPLE

Triangle begins:

1;

0,1;

0,0,1,1;

0,0,0,2,2,1,1;

0,0,0,0,3,5,5,4,2,1,1;

0,0,0,0,0,6,13,19,22,20,14,9,5,2,1,1;

the last batch giving the numbers of connected graphs with 6 nodes and from 0 to 15 edges.

MATHEMATICA

A076263 gives a Mathematica program which produces the nonzero entries in each row.

Needs["Combinatorica`"]; Table[Print[row = Join[Array[0&, n-1], Table[ Count[ Combinatorica`ListGraphs[n, k], g_ /; Combinatorica`ConnectedQ[g]], {k, n-1, n*(n-1)/2}]]]; row, {n, 1, 8}] // Flatten (* Jean-François Alcover, Jan 15 2015 *)

CROSSREFS

Cf. A008406, A054925.

Other versions of this triangle: A046751, A076263, A054923, A046742.

Row sums give A001349, column sums give A002905. A046751 is essentially the same triangle. A054923 and A046742 give same triangle but read by columns.

Main diagonal is A000055. Next diagonal is A001429. Largest entry in each row gives A001437.

KEYWORD

nonn,easy,nice,tabf

AUTHOR

N. J. A. Sloane

STATUS

approved

A076864

Number of connected loopless multigraphs with n edges.

+0
16

1, 1, 2, 5, 12, 33, 103, 333, 1183, 4442, 17576, 72810, 314595, 1410139, 6541959, 31322474, 154468852, 783240943, 4077445511, 21765312779, 118999764062, 665739100725, 3807640240209, 22246105114743, 132672322938379, 807126762251748

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Inverse Euler transform of A050535.

LINKS

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

Patrick T. Komiske, Eric M. Metodiev, and Jesse Thaler, Energy flow polynomials: A complete linear basis for jet substructure, arXiv:1712.07124 [hep-ph], 2017.

Tsuyoshi Miezaki, Akihiro Munemasa, Yusaku Nishimura, Tadashi Sakuma, and Shuhei Tsujie, Universal graph series, chromatic functions, and their index theory, arXiv:2403.09985 [math.CO], 2024. See p. 23.

N. J. A. Sloane, Transforms

Gus Wiseman, Non-isomorphic representatives of the unlabeled connected multigraphs counted by the first 5 terms

MATHEMATICA

A050535 = Cases[Import["https://oeis.org/A050535/b050535.txt", "Table"], {_, _}][[All, 2]];

(* EulerInvTransform is defined in A022562 *)

Join[{1}, EulerInvTransform[A050535 // Rest]] (* Jean-François Alcover, Feb 11 2020, updated Mar 17 2020 *)

CROSSREFS

Row sums of A191646.

Cf. A050535 (multisets), A076865, A076866, A076867.

Cf. A000664, A007718, A054923, A191970, A275421, A317672, A322114, A322137, A322148.

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Nov 23 2002

EXTENSIONS

More terms from Sean A. Irvine, Oct 02 2011

Name and comment swapped by Gus Wiseman, Nov 28 2018

a(0)=1 prepended by Andrew Howroyd, Oct 23 2019

STATUS

approved

A094602

Total number of edges in all connected unlabeled graphs on n nodes.

+0
1

0, 1, 5, 25, 130, 951, 9552, 160220, 4756703, 264964172, 27746801125, 5419696866001, 1964101824992259, 1319988856541150115, 1648566523004692022634, 3838409698542815296758222, 16719797018733808721401666187, 136732968429033400292302529059213

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

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

FORMULA

a(n) = Sum_{k=1..binomial(n,2)} k*A054924(n, k). - Andrew Howroyd, Feb 01 2020

PROG

(PARI) \\ See A054923 for G, InvEulerMT.

a(n)={subst(deriv(InvEulerMT(vector(n, k, G(k, y)))[n]), y, 1)} \\ Andrew Howroyd, Feb 01 2020

CROSSREFS

Cf. A046751, A054923, A054924, A086314, A095351.

KEYWORD

nonn

AUTHOR

Vladeta Jovovic, Jun 06 2004

EXTENSIONS

Terms a(17) and beyond from Andrew Howroyd, Feb 01 2020

STATUS

approved

A191646

Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.

+0
27

1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 11, 11, 6, 0, 1, 6, 22, 34, 29, 11, 0, 1, 7, 37, 85, 110, 70, 23, 0, 1, 9, 61, 193, 348, 339, 185, 47, 0, 1, 11, 95, 396, 969, 1318, 1067, 479, 106, 0, 1, 13, 141, 771, 2445, 4457, 4940, 3294, 1279, 235

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1274 (terms 0..119 from R. J. Mathar)

R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; see Section 4.

Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]

B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation 60 (2013), 94-112.

Gordon Royle, Small Multigraphs.

Gus Wiseman, Illustration of the 33 connected multigraphs counted in row 5.

FORMULA

T(n,k=3) = A253186(n) = A034253(n,k=2) for n >= 1. - Petros Hadjicostas, Oct 02 2019

EXAMPLE

Triangle T(n,k) (with rows n >= 0 and columns k >= 1) begins as follows:

1;

0, 1;

0, 1, 1;

0, 1, 2, 2;

0, 1, 3, 5, 3;

0, 1, 4, 11, 11, 6;

0, 1, 6, 22, 34, 29, 11;

...

PROG

(PARI)

EulerT(v)={my(p=exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1); Vec(p/x, -#v)}

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i), 1))}

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}

edges(v, x)={sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i], v[j])); g*x^(v[i]*v[j]/g))) + sum(i=1, #v, my(t=v[i]); ((t-1)\2)*x^t + if(t%2, 0, x^(t/2)))}

G(n, m)={my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(edges(p, x) + O(x*x^m), -m))); s/n!}

R(n)={Mat(apply(p->Col(p+O(y^n), -n), InvEulerMT(vector(n, k, 1 + y*Ser(G(k, n-1), y)))))}

{ my(A=R(10)); for(n=1, #A, for(k=1, n, print1(A[n, k], ", ")); print) } \\ Andrew Howroyd, May 14 2018

CROSSREFS

Row sums give A076864. Diagonal is A000055.

Cf. A034253, A054923, A192517, A253186 (column k=3), A290778 (column k=4).

Cf. A000664, A007718, A036250, A050535, A191646, A191970, A275421, A317672, A322114, A322133, A322152.

KEYWORD

nonn,tabl

AUTHOR

Alberto Tacchella, Jul 04 2011

STATUS

approved

A191970

Number of connected graphs with n edges with loops allowed.

+0
15

1, 2, 2, 6, 12, 33, 93, 287, 940, 3309, 12183, 47133, 190061, 796405, 3456405, 15501183, 71681170, 341209173, 1669411182, 8384579797, 43180474608, 227797465130, 1229915324579, 6790642656907, 38311482445514, 220712337683628, 1297542216770482, 7779452884747298

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Inverse Euler transform of A053419.

From R. J. Mathar, Jul 25 2017: (Start)

The Multiset Transform gives the number of graphs with n edges (loops allowed) and k components (0<=k<=n):

1

0 2

0 2 3

0 6 4 4

0 12 15 6 5

0 33 36 24 8 6

0 93 111 64 33 10 7

0 287 324 207 92 42 12 8

0 940 1036 633 308 120 51 14 9

0 3309 3408 2084 966 409 148 60 16 10

0 12183 11897 6959 3243 1305 510 176 69 18 11

0 47133 43137 24415 10970 4432 1644 611 204 78 20 12

0 190061 163608 88402 38763 15125 5628 1983 712 232 87 22 13

0 796405 644905 332979 140671 53732 19316 6824 2322 813 260 96 24 14

0 3456405 2639871 1299054 529179 195517 68878 23515 8020 2661 914 288 105 26 15 (End)

LINKS

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

Gus Wiseman, Non-isomorphic representatives of the a(1) = 1 through a(4) = 12 connected graphs with loops.

EXAMPLE

a(1)=2: Either one node with the edge equal to a loop, or two nodes connected by the edge. a(2)=2: Either three nodes on a chain connected by the two edges, or two nodes connected by an edge, one node with a loop. Apparently multi-loops are not allowed (?). - R. J. Mathar, Jul 25 2017

PROG

(PARI) \\ See A322114 for InvEulerMT, G.

seq(n)={vecsum([Vec(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])} \\ Andrew Howroyd, Oct 22 2019

CROSSREFS

Row sums of A322114.

Cf. A000664, A002905, A007718, A050535, A053419, A054923, A191646, A191970, A275421, A322133, A322151, A322152.

KEYWORD

nonn

AUTHOR

Alberto Tacchella, Jun 20 2011

EXTENSIONS

Terms a(25) and beyond from Andrew Howroyd, Oct 22 2019

STATUS

approved

A322114

Regular triangle read by rows where T(n,k) is the number of unlabeled connected graphs with loops with n edges and k vertices, 1 <= k <= n+1.

+0
17

1, 1, 1, 0, 1, 1, 0, 1, 3, 2, 0, 0, 3, 6, 3, 0, 0, 2, 11, 14, 6, 0, 0, 1, 13, 35, 33, 11, 0, 0, 0, 10, 61, 112, 81, 23, 0, 0, 0, 5, 75, 262, 347, 204, 47, 0, 0, 0, 2, 68, 463, 1059, 1085, 526, 106, 0, 0, 0, 1, 49, 625, 2458, 4091, 3348, 1376, 235

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

LINKS

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

EXAMPLE

Triangle begins:

1

1 1

0 1 1

0 1 3 2

0 0 3 6 3

0 0 2 11 14 6

0 0 1 13 35 33 11

Non-isomorphic representatives of the graphs counted in row 4:

{{2}{3}{12}{13}} {{4}{12}{23}{34}} {{13}{24}{35}{45}}

{{2}{3}{13}{23}} {{4}{13}{23}{34}} {{14}{25}{35}{45}}

{{3}{12}{13}{23}} {{4}{13}{24}{34}} {{15}{25}{35}{45}}

{{4}{14}{24}{34}}

{{12}{13}{24}{34}}

{{14}{23}{24}{34}}

PROG

(PARI)

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i), 1))}

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}

edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c+1)\2)*if(c%2, 1, t(c/2)))}

G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}

T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}

{my(A=T(10)); for(n=1, #A, print(A[n, 1..n]))} \\ Andrew Howroyd, Oct 22 2019

CROSSREFS

Row sums are A191970. Last column is A000055.

Cf. A000664, A007716, A007718, A007719, A054923, A191646, A275421, A317533, A321254.

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Nov 26 2018

EXTENSIONS

Terms a(28) and beyond from Andrew Howroyd, Oct 22 2019

STATUS

approved