A002905 -id:A002905 - cp's OEIS frontend

A303832 The number of edge-rooted unlabeled connected graphs with n edges.

1, 1, 4, 10, 32, 101, 346, 1220, 4517, 17338, 69107, 285009, 1215015, 5344224, 24223641, 113001129, 541913075, 2668817544, 13484234188, 69831773559, 370361639587, 2009988998148, 11153858854425, 63242354288220, 366140089188603, 2163036956456422, 13031489297543608

Offset: 1

R. J. Mathar, May 04 2018

nonn

			a(1)=1: the connected graph with 1 edge (which is rooted).
a(2)=1: the connected graph with 2 edges (one rooted).
a(3)=4: the triangle graph with one choice of rooting, the linear tree with either the middle or a terminating edge rooted, the star graph with one edge rooted.

Cf. A126133 (not necessarily connected), A000664, A303830 (by number of nodes).

Cf. A002905, A339039, A339040, A339041, A339044.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n)); Vec((G(2*n, x+A, [1, 1]) + G(2*n, x+A, [2]))/(2*G(2*n, x+A, [])*(1+x)))} \\ Andrew Howroyd, Nov 21 2020

G.f. A(x) satisfies: A(x)*A000664(x) = A126133(x).

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 2, 5, 27, 216, 2311, 30988, 499919, 9431026, 203743252, 4960335470, 134382267082, 4009794148101, 130668970606412, 4617468180528235, 175867725701333896, 7182126650899080024, 313063334893103361130, 14507460736615554141354, 712192629608088061633746

Offset: 0

Gus Wiseman, Nov 28 2018

nonn

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

Row sums of A322147. The unlabeled version is A191970.

Cf. A000664, A002905, A007718, A013922, A054923, A057500, A191646, A291842 (planar case), A321254, A322114, A322115.

multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[multsubs[Range[n+1],2],{n}],And[Union@@#==Range[Max@@Union@@#],Length[csm[#]]==1]&]],{n,5}]

Connected(v)={my(u=vector(#v)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); u}
seq(n)={Vec(vecsum(Connected(vector(2*n, j, (1 + x + O(x*x^n))^binomial(j+1,2)))))} \\ Andrew Howroyd, Nov 28 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 28 2018

A339040 Number of unlabeled connected simple graphs with n edges rooted at two noninterchangeable vertices.

Original entry on oeis.org

1, 3, 10, 35, 125, 460, 1747, 6830, 27502, 113987, 485971, 2129956, 9591009, 44341610, 210345962, 1023182861, 5100235807, 26035673051, 136023990102, 726877123975, 3970461069738, 22156281667277, 126234185382902, 733899631974167, 4351500789211840

Offset: 1

Andrew Howroyd, Nov 20 2020

nonn

Cf. A000664, A002905, A303832, A304074, A339039, A339041, A339042, A339044, A339063.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n), g=G(2*n, x+A, [])); Vec(G(2*n, x+A, [1, 1])/g - (G(2*n, x+A, [1])/g)^2)}

G.f.: f(x)/g(x) - r(x)^2 where f(x), g(x) and r(x) are the g.f.'s of A339063, A000664 and A339039.

A339041 Number of unlabeled connected simple graphs with n edges rooted at two indistinguishable vertices.

Original entry on oeis.org

1, 2, 7, 21, 73, 255, 946, 3618, 14376, 58957, 249555, 1087828, 4878939, 22488282, 106432530, 516783762, 2572324160, 13116137104, 68461594211, 365559412868, 1995532789212, 11129600885183, 63381069498524, 368338847181336, 2183239817036378

Offset: 1

Andrew Howroyd, Nov 20 2020

nonn

Cf. A000664, A002905, A303831, A303832, A339039, A339040, A339043, A339044, A339063, A339064.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n), g=G(2*n, x+A, []), gr=G(2*n, x+A, [1])/g); Vec(G(2*n, x+A, [1, 1])/g - gr^2 + G(2*n, x+A, [2])/g - subst(gr, x, x^2))/2}

G.f.: f(x)/g(x) - (r(x)^2 + r(x^2))/2 where f(x), g(x) and r(x) are the g.f.'s of A339064, A000664 and A339039.

A010357 Number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges.

Original entry on oeis.org

1, 1, 2, 3, 6, 14, 32, 90, 279, 942, 3468, 13777, 57747, 254671, 1170565, 5580706, 27487418, 139477796, 727458338, 3893078684, 21346838204, 119787629215, 687200870250

Offset: 1

N. J. A. Sloane

Original name: Multi-edge stars with n edges.

			From _Andrew Howroyd_, Nov 23 2020: (Start)
The a(1) = 1 graph is a single edge (K_2 = P_2).
The a(2) = 1 graph is a double edge.
The a(3) = 2 graphs are a triple edge and the triangle (K_3).
The a(4) = 3 graphs are a quadruple edge, a triangle with one double edge and the square (C_4).
(End)

George A. Baker Jr. and John M. Kincaid, The continuous-spin Ising model, g0:phi4:d field theory, and the renormalization group, J. Statist. Phys. 24 (1981), no. 3, 469-528.
Brendan McKay and Adolfo Piperno, nauty and Traces, programs for computing automorphism groups of graphs and digraphs.
Gus Wiseman, Non-isomorphic representatives of the a(1) = 1 through a(6) = 14 unlabeled 2-connected multigraphs.

Row sums of A339160.
Cf. A050535, A076864, A010355, A010359.
A002218 counts unlabeled 2-connected graphs.
A013922 counts labeled 2-connected graphs.
A322140 is a labeled version.
Cf. A002905, A006444, A007718, A275307, A304887.

Name changed by Andrew Howroyd, Dec 05 2020
a(11)-a(20) added using geng/multig from nauty by Andrew Howroyd, Dec 05 2020
a(21)-a(23) from Sean A. Irvine, Apr 18 2024

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

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

			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).

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)

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

Data corrected by Sean A. Irvine, Apr 23 2021

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

Original entry on oeis.org

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

Offset: 2

N. J. A. Sloane

			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 ].

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.)

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

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

More terms from Vladeta Jovovic, Apr 21 2000

A339039 Number of unlabeled connected simple graphs with n edges rooted at one distinguished vertex.

Original entry on oeis.org

1, 1, 2, 5, 13, 37, 114, 367, 1248, 4446, 16526, 63914, 256642, 1067388, 4590201, 20376849, 93240065, 439190047, 2126970482, 10579017047, 53983000003, 282345671127, 1512273916781, 8287870474339, 46438619162441, 265840311066579

Offset: 0

Andrew Howroyd, Nov 20 2020

nonn

Cf. A000664, A002905, A053419, A126100, A303832, A339036, A339040, A339041, A339044, A339063.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1])/G(2*n, x+A, []))}

G.f.: f(x)/g(x) where f(x) is the g.f. of A053419 and g(x) is the g.f. of A000664.

A339044 Number of unlabeled connected simple graphs with n edges rooted at one oriented edge.

Original entry on oeis.org

1, 2, 6, 18, 57, 188, 651, 2336, 8719, 33741, 135185, 559908, 2394326, 10557283, 47943126, 223987316, 1075455181, 5301593544, 26807904317, 138924912857, 737220195148, 4002876571636, 22221898966507, 126042573704637, 729944250603862, 4313430995825272

Offset: 1

Andrew Howroyd, Nov 21 2020

nonn

Cf. A000664, A002905, A303832, A304072, A339037, A339039, A339040, A339041, A339063.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1, 1])/G(2*n, x+A, [])/(1+x))}

G.f.: x*f(x)/((1+x)*g(x)) where f(x) is the g.f. of A339063 and g(x) is the g.f. of A000664.

A003089 Number of connected line graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 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

Offset: 1

N. J. A. Sloane

Sequence is identical to the number of connected graphs on n edges (A002905), except for the term a(3). The three connected 3-edge graphs (P_4, K_3 and K_{1,3}) yield only two linegraphs because K_3 and K_{1,3} have isomorphic linegraphs. No other connected nonisomorphic graphs have isomorphic linegraphs.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 221.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Max Alekseyev, Table of n, a(n) for n = 1..60
Eric Weisstein's World of Mathematics, Line Graph.

Cf. A002905.

More terms from Ronald C. Read.
More terms from Gordon F. Royle, Jun 05 2003
a(25)-a(26) from Max Alekseyev, Nov 25 2013
a(27) and beyond from Max Alekseyev, Sep 07 2016

cp's OEIS Frontend

A303832 The number of edge-rooted unlabeled connected graphs with n edges.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A339040 Number of unlabeled connected simple graphs with n edges rooted at two noninterchangeable vertices.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A339041 Number of unlabeled connected simple graphs with n edges rooted at two indistinguishable vertices.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A010357 Number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A339039 Number of unlabeled connected simple graphs with n edges rooted at one distinguished vertex.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A339044 Number of unlabeled connected simple graphs with n edges rooted at one oriented edge.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A003089 Number of connected line graphs with n nodes.

Views

Author