A331238 -id:A331238 - cp's OEIS frontend

A331237 Total cutting number of all trees of order n.

0, 0, 1, 5, 15, 47, 127, 363, 978, 2778, 7624, 21566, 60584, 172221, 488978, 1398457, 4001323, 11490717, 33037548, 95195793, 274609124, 793298293, 2294114542, 6641070332, 19241453969, 55795142707, 161910611244

Offset: 1

Sean A. Irvine, Jan 13 2020

Frank Harary and Peter J. Slater, A linear algorithm for the cutting center of a tree, Information Processing Letters, 23 (1986), 317-319.
Sean A. Irvine, Java program (github)

Cf. A002887, A002888, A331236, A331238.

a(n) = Sum_{T} c(T) where the sum is over all trees with n vertices and c(T) is the cutting number of T.

a(n) = Sum_{k=0..(n-1)*(n-2)/2} A331238(n, k).

A331422 Triangle T(n, k) of the number of connected graphs of order n with cutting number k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 3, 0, 2, 1, 10, 0, 0, 5, 3, 2, 1, 56, 0, 0, 0, 29, 0, 13, 8, 3, 2, 1, 468, 0, 0, 0, 0, 219, 0, 0, 63, 69, 0, 16, 12, 3, 2, 1, 7123, 0, 0, 0, 0, 0, 2706, 0, 0, 0, 502, 263, 300, 0, 85, 80, 24, 16, 12, 3, 2, 1, 194066, 0, 0, 0, 0, 0, 0, 52879, 0, 0, 0, 0, 6191, 3197, 0, 2148, 861, 632, 319, 352, 132, 160, 80, 24, 21, 12, 3, 2, 1

Offset: 1

Sean A. Irvine, Jan 16 2020

The cutting number of a node v in a graph G is the number of pairs of nodes {u,w} of G such that u!=v, w!=v, and every path from u to w contains v. The cutting number of a connected graph, is the maximum cutting number of any node in the graph.

			The triangle begins:
    1;
    1;
    1, 1;
    3, 0, 2, 1;
   10, 0, 0, 5,  3,   2,  1;
   56, 0, 0, 0, 29,   0, 13, 8,  3,  2, 1;
  468, 0, 0, 0,  0, 219,  0, 0, 63, 69, 0, 16, 12, 3,  2, 1;
  ...
The length of row n is 1 + (n-1)*(n-2)/2.

Sean A. Irvine, Rows n = 1..12 flattened
Sean A. Irvine, Java program (github)
Simon Mukwembi and Senelani Dorothy Hove-Musekwa, On bounds for the cutting number of a graph, Indian J. Pure Appl. Math., 43 (2012), 637-649.

Cf. A331238 (trees), A001349 (row sums), A002218 (first column).

cp's OEIS Frontend

A331237 Total cutting number of all trees of order n.

Views

Author

Keywords

Links

Crossrefs

Formula