A294522 Triangle read by rows: T(n,k) is the number of simple connected graphs on n nodes with diameter k (0<=k<n).

1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 14, 5, 1, 0, 1, 59, 43, 8, 1, 0, 1, 373, 387, 82, 9, 1, 0, 1, 4154, 5797, 1027, 125, 12, 1, 0, 1, 91518, 148229, 19320, 1818, 180, 13, 1, 0, 1, 4116896, 6959721, 598913, 37856, 2928, 239, 16, 1

Offset

1,9

Links

Table of n, a(n) for n=1..55.

Eric Weisstein's World of Mathematics, Graph Diameter

Wikipedia, Distance (graph theory)

Formula

a(n,1) = 1 for n > 1 (only K_n has diameter 1).

a(n,n-1) = 1 (only P_n has diameter n-1).

Example

Triangle begins:
  1;
  0, 1;
  0, 1,    1;
  0, 1,    4,    1;
  0, 1,   14,    5,    1;
  0, 1,   59,   43,    8,   1;
  0, 1,  373,  387,   82,   9,  1;
  0, 1, 4154, 5797, 1027, 125, 12, 1;
  ...
From Eric W. Weisstein, Jun 11 2019: (Start)
a(2,1) = 1 since only P_2 has diameter 1.
a(3,1) = 1 since only C_3 has diameter 1.
a(3,2) = 1 since only P_3 has diameter 2.
a(4,1) = 1 since only K_4 has diameter 1.
a(4,2) = 4 since K_1,3, K4-e, the paw graph, and C_4 have diameter 2.
a(4,3) = 1 since only P_4 has diameter 3.
(End)

Crossrefs

Columns k=0..6 are A000007, A057427, A241706, A241707, A241708, A241709, A241710.

Row sums give A001349.

Sequence in context: A055105 A348600 A200545 * A058710 A281891 A124539

Adjacent sequences: A294519 A294520 A294521 * A294523 A294524 A294525

Keyword

nonn,tabl

Author

Andrew Howroyd, Nov 01 2017

Status

approved