cp's OEIS Frontend

The throttling number of a graph can be defined as follows. Start with a blue/white coloring of the nodes. At each step, all white nodes, which are currently the unique white neighbor of a blue node, are colored blue. The throttling number is the minimum, over all possible initial colorings, of the sum of the number of blue nodes in the initial coloring and the number of steps required to color all nodes blue.

A connected graph with n nodes has throttling number n if and only if it does not contain any 4-path, 4-cycle, or bowtie graph as an induced subgraph (Carlson and Kritschgau 2021, Theorem 4.2). Apparently, all these graphs can be constructed in the following way (for n >= 2). Let the nodes be 1, ..., n and choose a subset of special nodes. We require that n is a special node and that 1 is not, so there are 2^(n-2) possible choices for the set of special nodes. For i < j, let there be an edge between i and j if and only if j is a special node. These graphs do not contain any of the forbidden induced subgraphs, and different sets of special nodes lead to nonisomorphic graphs. Consequently, T(n,n) >= 2^(n-2). Apparently, equality holds, so that there are no other such graphs.

Given a graph G where each vertex is initially considered filled or unfilled, we apply the skew color change rule, which states that a vertex v becomes filled if and only if it is the unique empty neighbor of some other vertex in the graph. The failed skew zero forcing number of G, is the maximum cardinality of any subset S of vertices on which repeated application of the color change rule will not result in all vertices being filled. Note that C^2_n = Ci_n(1,2) is the square of C_n.