A263293 -id:A263293 - cp's OEIS frontend

A294217 Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).

1, 1, 1, 2, 1, 1, 4, 4, 2, 1, 11, 12, 8, 2, 1, 34, 60, 43, 15, 3, 1, 156, 378, 360, 121, 25, 3, 1, 1044, 3843, 4869, 2166, 378, 41, 4, 1, 12346, 64455, 113622, 68774, 14306, 1095, 65, 4, 1, 274668, 1921532, 4605833, 3953162, 1141597, 104829, 3441, 100, 5, 1

Offset: 1

Eric W. Weisstein, Oct 25 2017

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A327366. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 10 2020

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    4,   4,   2,   1;
   11,  12,   8,   2,  1;
   34,  60,  43,  15,  3, 1;
  156, 378, 360, 121, 25, 3, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)
Eric Weisstein's World of Mathematics, Minimum Vertex Degree

Row sums are A000088 (simple graphs on n nodes).
Columns k=0..2 are A000088(n-1), A324693, A324670.
Cf. A263293 (triangle of n-node maximum vertex degree counts).
The labeled version is A327366.
Cf. A002494, A004110, A261919, A327227, A327230, A327335, A327372.

T(n, 0) = A000088(n-1).
T(n, n-2) = A004526(n) for n > 1.
T(n, n-1) = 1.
T(n, k) = A263293(n, n-1-k). - Andrew Howroyd, Sep 03 2019

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 5, 3, 1, 1, 1, 5, 8, 10, 3, 1, 1, 1, 6, 14, 26, 16, 4, 1, 1, 1, 7, 20, 61, 60, 29, 4, 1, 1, 1, 8, 30, 128, 243, 184, 45, 5, 1, 1, 1, 9, 40, 254, 800, 1228, 488, 75, 5, 1, 1, 1, 10, 55, 467, 2518, 7252, 6684, 1509, 115, 6, 1

Offset: 0

Andrew Howroyd, Apr 08 2020

T(n,k) is the number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to k and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333737.

Terms may be computed without generating each graph by enumerating the graphs by degree sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A192517 can be used to extend this method to the unlabeled case.

			Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  0 | 1 1  1   1    1     1      1       1 ...
  1 | 1 1  1   1    1     1      1       1 ...
  2 | 1 2  3   4    5     6      7       8 ...
  3 | 1 2  5   8   14    20     30      40 ...
  4 | 1 3 10  26   61   128    254     467 ...
  5 | 1 3 16  60  243   800   2518    6999 ...
  6 | 1 4 29 184 1228  7252  38194  175369 ...
  7 | 1 4 45 488 6684 78063 772243 6254652 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..377 (antidiagonals 0..26)

Rows n=0..4 are A000012, A000012, A000027(n+1), A006918(n+1), A333897.
Columns k=0..5 are A000012, A008619, A000990, A333894, A333895, A333896.
Cf. A188403, A192517, A263293, A333161, A333330, A333737, A334546.

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Original entry on oeis.org

0, 1, 1, 4, 12, 60, 378, 3843, 64455, 1921532, 104098702, 10348794144, 1893781768084, 639954768875644, 400905675004630820, 467554784370658979194, 1019317687720204607541914, 4170177760438554428852944352, 32130458453030025927403299167172

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Minimum Vertex Degree
Gus Wiseman, The a(2) = 1 through a(5) = 12 unlabeled graphs with minimum degree 1.

Column k = 1 of A294217.
A diagonal of A263293.
The labeled version is A327227.
The generalization to set-systems is A327335, with covering case A327230.
Unlabeled covering graphs are A002494.
Cf. A000088, A004110, A100743, A141580, A245797, A261919, A327105, A327362, A327364, A327366, A327372.

a(n) = A002494(n) - A261919(n).

First differences of A141580. - Andrew Howroyd, Jan 11 2021

A339788 Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 7, 6, 2, 1, 1, 3, 11, 13, 6, 2, 1, 1, 4, 17, 30, 15, 6, 2, 1, 1, 4, 25, 60, 39, 15, 6, 2, 1, 1, 5, 36, 128, 94, 41, 15, 6, 2, 1, 1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1, 1, 6, 70, 523, 561, 270, 105, 41, 15, 6, 2, 1

Offset: 1

Andrew Howroyd, Dec 18 2020

A forest is an acyclic graph.

(The component trees here are not rooted. - N. J. A. Sloane, Dec 19 2020)

			Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   1;
  1, 2,  4,   2,   1;
  1, 3,  7,   6,   2,   1;
  1, 3, 11,  13,   6,   2,  1;
  1, 4, 17,  30,  15,   6,  2,  1;
  1, 4, 25,  60,  39,  15,  6,  2, 1;
  1, 5, 36, 128,  94,  41, 15,  6, 2, 1;
  1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A005195.

Cf. A144215 (max degree <= k), A144528, A238414 (trees), A263293 (graphs).

\\ Here V(n, k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, EulerT(V(n,k-1)[2..1+n])~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }

T(n,k) = A144215(n,k) - A144215(n,k-1) for k > 0.

A324670 Number of simple graphs on n unlabeled nodes with minimum degree exactly 2.

Original entry on oeis.org

0, 0, 1, 2, 8, 43, 360, 4869, 113622, 4605833, 325817259, 40350371693, 8825083057727, 3447229161054412, 2432897732375453872, 3135299553791882831175, 7445569254636418368355175, 32831169277561326131677454356, 270499962116368309216399255404116

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Eric Weisstein's World of Mathematics, Minimum Vertex Degree

Column k=2 of A294217.
A diagonal of A263293.
Cf. A005637, A007111, A261919.

a(n) = A261919(n) - A007111(n).

A324740 Number of simple graphs on n unlabeled nodes with maximum degree exactly 2.

Original entry on oeis.org

0, 0, 2, 4, 8, 15, 25, 41, 65, 100, 150, 225, 327, 474, 678, 962, 1348, 1884, 2602, 3581, 4889, 6644, 8968, 12064, 16124, 21476, 28462, 37585, 49407, 64747, 84495, 109936, 142522, 184226, 237350, 304977, 390669, 499169, 636039, 808468, 1024996, 1296573, 1636151

Offset: 1

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Column k=2 of A263293.
A diagonal of A294217.
Cf. A003292, A008619.

seq(n) = Vec( (1-x)*(1-x^2)/prod(k=1, n, 1 - x^k + O(x*x^n))^2 - 1/((1-x)*(1-x^2)), -n) \\ Andrew Howroyd, Sep 03 2019

a(n) = A003292(n) - A008619(n).

A332760 Triangle of number of connected graphs with n>=2 nodes and maximum degree 1<=k

Original entry on oeis.org

1, 0, 2, 0, 2, 4, 0, 2, 8, 11, 0, 2, 27, 49, 34, 0, 2, 62, 289, 344, 156, 0, 2, 192, 1735, 4457, 3687, 1044, 0, 2, 529, 11676, 63493, 109623, 63411, 12346, 0, 2, 1731, 87669, 1067440, 3835541, 4540334, 1909186, 274668, 0, 2

Offset: 2

Henry Bottomley, Feb 22 2020

			Triangle starts
1;
0,  2;
0,  2,  4;
0,  2,  8,    11;
0,  2,  27,   49,   34;
0,  2,  62,  289,  344,  156;
0,  2, 192, 1735, 4457, 3687, 1044;
0,  2,...

Mathoverflow, What is the number of connected graphs with n vertices of max. degree up to D?

Cf. A263293, A001349 (row sums), A000088.

T(n,n-1) = A000088(n-1).

T(n,2) = 2 for n>2 as the only possibilities are a cycle graph or a path graph.

a(32)-a(48) from Chai Wah Wu, Sep 08 2020

cp's OEIS Frontend

A294217 Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Views

Author

Keywords

Links

Crossrefs

Formula

A339788 Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A324670 Number of simple graphs on n unlabeled nodes with minimum degree exactly 2.

Views

Author

Keywords

Links

Crossrefs

Formula

A324740 Number of simple graphs on n unlabeled nodes with maximum degree exactly 2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A332760 Triangle of number of connected graphs with n>=2 nodes and maximum degree 1<=k

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions