A002887 -id:A002887 - cp's OEIS frontend

A002888 a(n) is the cutting number of the tree corresponding to A002887(n).

Original entry on oeis.org

1, 2, 9, 20, 670

Offset: 1

N. J. A. Sloane

Frank Harary and Phillip A. Ostrand, How cutting is a cut point?, pp. 147-150 of R. K. Guy et al., editors, Combinatorial Structures and Their Applications (Proceedings Calgary Conference Jun 1969), Gordon and Breach, NY, 1970.
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).

Frank Harary and Phillip A. Ostrand, The cutting center theorem for trees, Discrete Mathematics, 1 (1971), 7-18.

Cf. A002887, A331237.

Title improved by Sean A. Irvine, Jan 16 2020

A331237 Total cutting number of all trees of order n.

Original entry on oeis.org

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

A331238 Triangle T(n, k) of the number of trees of order n with cutting number k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 7, 2, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 8, 4, 7, 7, 2, 3, 3, 1, 1, 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 (including trees as considered here), is the maximum cutting number of any node in the graph.

			Triangle begins:
  1;
  1;
  0, 1;
  0, 0, 1, 1;
  0, 0, 0, 0, 1, 1, 1;
  0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 2, 3, 1, 1, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 7, 2, 2, 3, 1, 1, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 8, 4, 7, 7, 2, 3, 3, 1, 1, 1;
...
The smallest nonzero entry on each row occurs at n-2 and the maximum at (n-1)*(n-2)/2.

Sean A. Irvine, Rows n=1..27 flattened
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)
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. A000055 (row sums), A002887, A002888, A331237.

A331236 Total cutting number of all simple connected graphs of order n.

Original entry on oeis.org

0, 0, 1, 7, 43, 302, 2622, 31129, 564452, 17585400, 1006927107, 107458067322

Offset: 1

Sean A. Irvine, Jan 13 2020

F. Harary and P. A. Ostrand, How cutting is a cut point?, pp. 147-150 of R. K. Guy et al., editors, Combinatorial Structures and Their Applications (Proceedings Calgary Conference Jun 1969), Gordon and Breach, NY, 1970. [Annotated scan of page 147 only.]
F. Harary and P. A. Ostrand, How cutting is a cut point?, pp. 147-150 of R. K. Guy et al., editors, Combinatorial Structures and Their Applications (Proceedings Calgary Conference Jun 1969), Gordon and Breach, NY, 1970. [Annotated scan of pages 148, 149 only.]
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. A331237 (trees), A331422.

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

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

cp's OEIS Frontend

A002888 a(n) is the cutting number of the tree corresponding to A002887(n).

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A331237 Total cutting number of all trees of order n.

Views

Author

Keywords

Links

Crossrefs

Formula

A331238 Triangle T(n, k) of the number of trees of order n with cutting number k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A331236 Total cutting number of all simple connected graphs of order n.

Views

Author

Keywords

Links

Crossrefs

Formula