A lower bound on the failed zero-forcing number of a graph

Abstract: Given a graph

G = (V, E)

and a set of vertices marked as filled, we consider a color-change rule known as zero forcing. A set

S

is a zero forcing set if filling

S

and applying all possible instances of the color change rule causes all vertices in

V

to be filled. A failed zero forcing set is a set of vertices that is not a zero forcing set. Given a graph

G

, the failed zero forcing number

F (G)

is the maximum size of a failed zero forcing set. An open question was whether given any

k

there is a an

e l l

such that all graphs with at least

e l l

vertices must satisfy

F (G) g e q k

. We answer this question affirmatively by proving that for a graph

G

with

n

vertices,

F (G) g e q l f l o o r f r a c n - 1 2 f l o o r

.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: A lower bound on the failed zero-forcing number of a graph