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,4

Comments

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)

Eric Weisstein's World of Mathematics, Minimum Vertex Degree

Formula

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

Example

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

Crossrefs

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.

Sequence in context: A322038 A123521 A322115 * A123246 A122518 A346031

Adjacent sequences: A294214 A294215 A294216 * A294218 A294219 A294220

Keyword

nonn,tabl

Author

Eric W. Weisstein, Oct 25 2017

Status

approved