A343648 Triangle read by rows, 1 <= k <= n: T(n,k) is the number of (unlabeled) connected graphs with n nodes and zero forcing number k.

1, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 10, 9, 1, 0, 1, 33, 58, 19, 1, 0, 1, 94, 457, 266, 34, 1, 0, 1, 319, 3977, 5574, 1184, 61, 1, 0, 1, 1053, 39547, 142039, 72944, 5393, 102, 1, 0, 1, 3683, 414891, 4170606, 5919941, 1180610, 26668, 170, 1, 0

Offset: 1

Author

Pontus von Brömssen, Apr 24 2021

Keywords

• nonn
• tabl

Comments

The zero forcing 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 zero forcing number is the minimum number of blue nodes in an initial coloring that leads to all nodes being blue after a finite number of steps.

Examples

			Triangle begins:
   n\k 1     2       3        4        5        6      7    8  9  10
  ------------------------------------------------------------------
   1:  1
   2:  1     0
   3:  1     1       0
   4:  1     4       1        0
   5:  1    10       9        1        0
   6:  1    33      58       19        1        0
   7:  1    94     457      266       34        1      0
   8:  1   319    3977     5574     1184       61      1    0
   9:  1  1053   39547   142039    72944     5393    102    1  0
  10:  1  3683  414891  4170606  5919941  1180610  26668  170  1   0
		

Links

• Shaun M. Fallat, Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader, The inverse eigenvalue problem of a graph, zero forcing, and related parameters, Notices of the American Mathematical Society 67 (2020), 257-261.

Crossrefs

Row sums: A001349.

Cf. A343649.

Formula

T(n,1) = 1. (The path graph is the only n-node graph with zero forcing number 1.)

T(n,n-1) = 1 for n >= 2. (The complete graph is the only connected n-node graph with zero forcing number n-1.)

T(n,n) = 0 for n >= 2.