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,8

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.

Links

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

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.

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.

Example

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

Crossrefs

Row sums: A001349.

Cf. A343649.

Sequence in context: A363044 A086329 A294118 * A359363 A318996 A294490

Adjacent sequences: A343645 A343646 A343647 * A343649 A343650 A343651

Keyword

nonn,tabl

Author

Pontus von Brömssen, Apr 24 2021

Status

approved