A008406 -id:A008406 - cp's OEIS frontend

A027416 Number of unlabeled (and unrooted) trees on n nodes having a centroid.

1, 1, 0, 1, 1, 3, 3, 11, 13, 47, 61, 235, 341, 1301, 1983, 7741, 12650, 48629, 82826, 317955, 564225, 2144505, 3926353, 14828074, 27940136, 104636890, 201837109, 751065460, 1479817181, 5469566585, 10975442036, 40330829030, 82270184950

Offset: 0

N. J. A. Sloane

nonn

Also, number of rooted unlabeled trees on n nodes not having a primary branch.
A tree has either a center or a bicenter and either a centroid or a bicentroid. (These terms were introduced by Jordan.)
If the number of edges in a longest path in the tree is 2m, then the middle node in the path is the unique center, otherwise the two middle nodes in the path are the unique bicenters.
On the other hand, define the weight of a node P to be the greatest number of nodes in any subtree connected to P. Then either there is a unique node of minimal weight, the centroid of the tree, or there is a unique pair of minimal weight nodes, the bicentroids.
Let T be a tree with root node R. If R and the edges incident with it are deleted, the resulting rooted trees are called branches. A primary branch (there can be at most one) has i nodes where n/2 <= i <= n-1.

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 35, 36.

N. J. A. Sloane, Table of n, a(n) for n = 0..200
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
C. Jordan, Sur les assemblages des lignes, J. Reine angew. Math., 70 (1869), 185-190.
A. Meir and J. W. Moon, On the branch-sizes of rooted unlabeled trees, in "Graph Theory and Its Applications", Annals New York Acad. Sci., Vol. 576, 1989, pp. 399-407.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1. [This articles states incorrectly that A000676 and A000677 give the numbers of trees with respectively a centroid and bicentroid.]
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.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Cf. A102911 (trees with a bicentroid), A027415 (trees with a primary branch), A000676 (trees with a center), A000677 (trees with a bicenter), A000055 (trees), A000081 (rooted trees).

N := 50: Y := [ 1,1 ]: for n from 3 to N do x*mul( (1-x^i)^(-Y[ i ]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); Y := [ op(Y),b ]; od: P:=n->sum(Y[n-i]*Y[i],i=1..floor(n/2)): seq(Y[n]-P(n),n=1..35); # Emeric Deutsch, Nov 21 2004

a(n) = A000055(n) - A102911(n/2) if n is even, else a(n) = A000055(n).
a(n) = A000081(n) - A027415(n). - Emeric Deutsch, Nov 21 2004
a(n) = [x^n] 1 + x/Product_{i=1..ceiling(n/2)-1} (1-x^i)^A000081(i).  See Cayley link above. - Geoffrey Critzer, Jul 30 2022

More terms from Emeric Deutsch, Nov 21 2004

Entry revised (with new definition) by N. J. A. Sloane, Feb 26 2007

A052283 Triangle read by rows: T(n,k) is the number of unlabeled directed graphs on n nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 4, 4, 4, 1, 1, 1, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1, 1, 1, 5, 16, 61, 154, 379, 707, 1155, 1490, 1670, 1490, 1155, 707, 379, 154, 61, 16, 5, 1, 1, 1, 1, 5, 17, 76, 288, 1043, 3242, 8951, 21209, 43863, 78814, 124115, 171024, 207362, 220922, 207362, 171024, 124115, 78814, 43863, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 0

Vladeta Jovovic, Feb 07 2000

Triangular array read by rows T(n,k) is the number of unlabeled directed graphs (no self loops allowed) on n nodes with exactly k edges where n >= 1, 0 <= k <= n(n-1). - Geoffrey Critzer, Nov 01 2011

			[1],
[1],
[1,1,1],
[1,1,4,4,4,1,1],
[1,1,5,13,27,38,48,38,27,13,5,1,1];
(the last batch giving the numbers of directed graphs with 4 nodes and from 0 to 12 arcs).

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 247.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.

Andrew Howroyd, Table of n, a(n) for n = 0..2680 (rows 0..20)
R. Absil and H Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Philippe Ramirez and Stéphane Legendre, Revisiting asymmetric marriage rules, in Social Networks 52 (2017), pp. 261-269.
Stackexchange, Number of distinct connected digraphs..., (2017)
Eric Weisstein's World of Mathematics, Simple Directed Graph

Cf. A000273 (row sums), A070166, A008406, A003085, A283753 (weakly connected).

Table[CoefficientList[GraphPolynomial[n, x, Directed], x], {n, 1, 10}] (* Geoffrey Critzer, Nov 01 2011 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_, t_] := Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^(2 g), {i, 2, Length[v]}, {j, 1, i-1}] * Product[ t[v[[i]]]^(v[[i]] - 1), {i, 1, Length[v]}];
gp[n_] := (s = 0; Do[s += permcount[p]*edges[p, 1 + x^# &], {p, IntegerPartitions[n]}]; s/n!);
A052283 = Reap[For[n = 1, n <= 6, n++, p = gp[n]; For[k = 0, k <= Exponent[p, x], k++, Sow[Coefficient[p, x, k]]]]][[2, 1]] (* Jean-François Alcover, Jul 09 2018, after Andrew Howroyd *)

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)^(2*g))) * prod(i=1, #v, t(v[i])^(v[i]-1))}
gp(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p,i->1+x^i)); s/n!}
for(n=1, 6, my(p=gp(n)); for(k=0, poldegree(p), print1(polcoeff(p,k), ", ")); print); \\ Andrew Howroyd, Nov 05 2017

T(n,0) = T(n,1) = T(n,n(n-1)-1) = T(n,n) = 1. - Geoffrey Critzer, Nov 01 2011

T(2k,k) = T(2k+1,k) = T(2k+2,k) =... and is the maximum value of column k. - Geoffrey Critzer, Nov 01 2011

a(0)=1 prepended and terms a(62) and beyond from Andrew Howroyd, Apr 20 2020

A241706 Number of simple connected graphs on n nodes with diameter 2.

Original entry on oeis.org

0, 0, 1, 4, 14, 59, 373, 4154, 91518, 4116896

Offset: 1

Travis Hoppe and Anna Petrone, Apr 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 [But beware errors] (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Graph Diameter

Column k=2 of A294522.

Simple connected graphs of diameter k: A241706, A241707, A241708, A241709, A241710.

A000717 Number of graphs with n nodes and floor(n(n-1)/4) edges.

Original entry on oeis.org

1, 1, 1, 3, 6, 24, 148, 1646, 34040, 1358852, 106321628, 16006173014, 4525920859198, 2404130854745735, 2426376196165902704, 4648429222263945620900, 16788801124652327714275292, 114722035311851620271616102401

Offset: 1

N. J. A. Sloane

This is the largest number of graphs with n vertices that all have the same number of edges. a(n) <= A371161(n). - Allan Bickle, Apr 18 2024

			There are three graphs with 4 vertices and 3 edges, K_3 U K_1, K_{1,3}, and P_4, so a(4) = 3. - _Allan Bickle_, Apr 18 2024

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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).

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

Cf. A008406, A371161.

More terms from Sean A. Irvine, Mar 10 2011

A201922 Triangle read by rows: T(n,m) = number of unlabeled graphs on n nodes with m connected components, m = 1,2,...,n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 21, 8, 3, 1, 1, 112, 30, 9, 3, 1, 1, 853, 145, 32, 9, 3, 1, 1, 11117, 1028, 154, 33, 9, 3, 1, 1, 261080, 12320, 1065, 156, 33, 9, 3, 1, 1, 11716571, 274806, 12513, 1074, 157, 33, 9, 3, 1, 1, 1006700565, 12007355, 276114, 12550, 1076, 157, 33, 9, 3, 1, 1

Offset: 1

Max Alekseyev, Dec 06 2011

			Triangle starts:
    1
    1   1
    2   1   1
    6   3   1   1
   21   8   3   1   1
  112  30   9   3   1   1
  853 145  32   9   3   1   1 ...

Alois P. Heinz, Rows n = 1..75, flattened
P. Flajolet, R. Sedgewick, Analytic combinatorics, Theorem I.1 (Multiset)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 82
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A001349 (first column), A000088 (row sum), A201968 (limits in the diagonals), A106240, A274934 (2nd column).

nn=10; c=(A000088=Table[NumberOfGraphs[n], {n,0,nn}]; f[x_] = 1-Product[1/(1-x^k)^a[k], {k,1,nn}]; a[0]=a[1]=a[2]=1; coes=CoefficientList[Series[f[x], {x,0,nn}], x]; sol=First[Solve[Thread[Rest[coes+A000088]==0]]]; Table[a[n], {n,0,nn}]/.sol); f[list_]:=Select[list,#>0&]; g=Product[1/(1-y x^n)^c[[n+1]], {n,1,nn}]; Map[f, Drop[CoefficientList[Series[g, {x,0,nn}], {x,y}],1]] //Flatten (* Geoffrey Critzer, Apr 19 2012  (c in above Mma code is given by Jean Francois Alcover in A001349) *)

T(n,m) = sum over the partitions of n with m parts: 1*K1 + 2*K2 + ... + n*Kn = n, K1 + K2 + ... + Kn = m, of Product_{i=1..n} binomial(A001349(i) + Ki - 1, Ki).

O.g.f.: Product_{n>=1} 1/(1 - y*x^n)^A001349(n). - Geoffrey Critzer, Apr 19 2012

A241707 Number of simple connected graphs on n nodes with diameter 3.

Original entry on oeis.org

0, 0, 0, 1, 5, 43, 387, 5797, 148229, 6959721

Offset: 1

Travis Hoppe and Anna Petrone, Apr 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 [But beware errors] (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Graph Diameter

Column k=3 of A294522.

Simple connected graphs of diameter k: A241706, A241707, A241708, A241709, A241710.

A263859 Triangle read by rows: T(n,k) (n>=1, k>=0) is the number of posets with n elements and rank k (or depth k+1).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 6, 1, 1, 20, 31, 10, 1, 1, 55, 162, 84, 15, 1, 1, 163, 940, 734, 185, 21, 1, 1, 556, 6372, 7305, 2380, 356, 28, 1, 1, 2222, 52336, 86683, 35070, 6259, 623, 36, 1, 1, 10765, 534741, 1261371, 619489, 125597, 14258, 1016, 45, 1

Offset: 1

Christian Stump, Oct 28 2015

Row sums give A000112, n >= 1.

The rank of a poset is the number of cover relations in a maximal chain.

			Triangle begins:
1,
1,1,
1,3,1,
1,8,6,1,
1,20,31,10,1,
1,55,162,84,15,1,
1,163,940,734,185,21,1,
1,556,6372,7305,2380,356,28,1,
1,2222,52336,86683,35070,6259,623,36,1,
1,10765,534741,1261371,619489,125597,14258,1016,45,1,
...

R. J. Mathar, Table of n, a(n) for n = 1..136
G. Brinkmann and B. D. McKay, Posets on up to 16 Points [On Brendan McKay's home page]
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
FindStat - Combinatorial Statistic Finder, The rank of the poset.
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A000112 (row sums), A342500 (connected).

More terms from Brinkmann-McKay (2002) added by N. J. A. Sloane, Mar 18 2017

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

Original entry on oeis.org

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

A039735 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled planar graphs with n >= 1 nodes and 0 <= k <= 3n-6 edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 20, 13, 5, 2, 1, 1, 2, 5, 10, 21, 41, 65, 97, 130, 144, 135, 98, 51, 16, 5, 1, 1, 2, 5, 11, 24, 56, 115, 221, 401, 658, 956, 1217, 1264, 1042, 631, 275, 72, 14, 1, 1, 2, 5

Offset: 1

Brendan McKay

Planar graphs with n >= 3 nodes have at most 3n-6 edges. - Charles R Greathouse IV, Feb 18 2013

			Triangle starts
n\k 0  1  2  3  4  5  6  7  8  9 10 11 12
--:-- -- -- -- -- -- -- -- -- -- -- -- --
1:  1
2:  1  1
3:  1  1  1  1
4:  1  1  2  3  2  1  1
5:  1  1  2  4  6  6  6  4  2  1
6:  1  1  2  5  9 15 21 24 24 20 13  5  2

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. J. Wilson, Introduction to Graph Theory. Academic Press, NY, 1972, p. 162.

F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463. (MR0068198) See page 457, equation (2.9).

Cf. A005470 (row sums), A008406, A049334.

From Michael Somos, Aug 23 2015: (Start)
Sum_{k} T(n, k) = A005470(n) if n >= 1.
log(1 + A(x, y)) = Sum_{n>0} B(x^n, y^n) / n where A(x, y) = Sum_{n>0, k>=0} T(n,k) * x^n * y^k and similarly B(x, y) with A049334. (End)

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

cp's OEIS Frontend

A027416 Number of unlabeled (and unrooted) trees on n nodes having a centroid.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A052283 Triangle read by rows: T(n,k) is the number of unlabeled directed graphs on n nodes with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A241706 Number of simple connected graphs on n nodes with diameter 2.

Views

Author

Keywords

Links

Crossrefs

A000717 Number of graphs with n nodes and floor(n(n-1)/4) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A201922 Triangle read by rows: T(n,m) = number of unlabeled graphs on n nodes with m connected components, m = 1,2,...,n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A241707 Number of simple connected graphs on n nodes with diameter 3.

Views

Author

Keywords

Links

Crossrefs

A263859 Triangle read by rows: T(n,k) (n>=1, k>=0) is the number of posets with n elements and rank k (or depth k+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A039735 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled planar graphs with n >= 1 nodes and 0 <= k <= 3n-6 edges.