A385334 Cat number of complete graphs on n vertices.

0, 1, 2, 5, 8, 11, 17, 21, 28, 33, 41, 47, 59, 66, 77, 85, 100, 109, 123, 133, 151, 162, 179, 191, 215, 228, 248, 262, 287, 302, 325, 341, 372, 389, 415, 433, 465, 484, 513, 533, 571, 592, 624, 646, 685, 708, 743, 767, 815, 840, 878, 904, 950, 977, 1018, 1046

Offset

1,3

Comments

The name comes from the pursuit-evasion game of Cat Herding, where an evader with arbitrarily large (nonzero) speed (the cat) takes turns with an omnipresent pursuer (the herder) who deletes one edge on their turn. The number of edges deleted in order to isolate the cat to one vertex is the score of the game, which the herder tries to minimize, while the cat tries to maximize. Under optimal play, the score is the cat number of the underlying graph.

Links

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

Rylo Ashmore, Danny Dyer, Trent Marbach, and Rebecca Milley, Cuts, cats, and complete graphs, Theoretical Computer Science, Volume 1050, 2025, 115393.

Formula

a(1)=0, a(2)=1, a(3)=2, a(n) = floor(n/2)*ceiling(n/2) + a(ceiling(n/2)) for n>=4.

Example

For n=2, cutting a single edge isolates the cat, for n=3, cutting the diametrically opposing edge forces the cat to move to a leaf, isolating the cat in 2 cuts. Further analysis can be found in the reference paper.

Mathematica

a[1]=0; a[2]=1; a[3]=2; a[n_]:=Floor[n/2]*Ceiling[n/2]+a[Ceiling[n/2]]; Array[a, 56] (* James C. McMahon, Jul 15 2025 *)

Prog

(SageMath)
def a(n):
    temp = 0;
    while (n>3):
        temp = temp + floor(n*n/4)
        n = ceil(n/2)
    return temp + n - 1;

Crossrefs

Cf. A002620.

Sequence in context: A300272 A352143 A365808 * A344719 A192147 A226817

Adjacent sequences: A385331 A385332 A385333 * A385335 A385336 A385337

Keyword

easy,nonn

Author

Rylo Ashmore, Jun 25 2025

Status

approved