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

DOI10.2140/INVOLVE.2023.16.493MaRDI QIDQ6132811zbMATH OpenOpenAlexFDO

Authors Nicolas Swanson, Eric Ufferman

Publication date 17 August 2023

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.03821

zbMATH Keywords

failed zero forcing

Mathematics Subject Classification ID

Graph theory (05C99)

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 $ell$ such that all graphs with at least $ell$ vertices must satisfy $F(G)geqk$. We answer this question affirmatively by proving that for a graph $G$ with $n$ vertices, $F(G)geqlfloorfracn-12floor$.

Recommendations

• The failed zero forcing number of a graph
• On the complexity of failed zero forcing
• Failed zero forcing and critical sets on directed graphs
• A lower bound on the zero forcing number
• Computing the zero forcing number for generalized Petersen graphs

Cites work

• The failed zero forcing number of a graph
• Zero forcing sets and the minimum rank of graphs

Cited in

(5)

• Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
• Failed skew zero forcing on a graph
• Failed zero forcing and critical sets on directed graphs
• The failed zero forcing number of a graph
• Failed zero forcing numbers of trees and circulant graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132811)