TOPICS
Search

Zero Forcing Number


The zero forcing number Z(G) is a graph parameter that is closely related to the maximum nullity M(G) and that bounds it from above:

 M(G)<=Z(G)

(AIM 2008, Barrett et al. 2025).

ZeroForcingNumber8VertexExceptions

Results from the American Institute of Mathematics (2008) showed that M(G)=Z(G) for any graph on 6 or fewer vertices. DeLoss et al. (2008) subsequently computed M(G) and bounds on Z(G) for all 7-vertex graphs, and the resulting table establishes that M(G)=Z(G) for all graphs on 7 vertices (Barrett et al. 2025). Barrett et al. (2025) subsequently showed that M(G)=Z(G) for all graphs on 8 vertices with the exception of a set of 7 graphs denoted E_1 to E_7 and which are illustrated above. As it turns out, E_2 is the graph complement of the 3-Plummer-Toft graph.


See also

Maximum Nullity, Minimum Rank

Explore with Wolfram|Alpha

References

AIM Minimum Rank--Special Graphs Work Group. "Zero Forcing Sets and the Minimum Rank of Graphs." Lin. Alg. Appl. 428, 1628-1648, 2008.Almodovar, E.; DeLoss, L.; Hogben, L.; Hogenson, K.; Murphy, K.; Peters, T.; and Ramírez, C. A. "Minimum Rank, Maximum Nullity and Zero Forcing Number for Selected Graph Families." Involve: A Journal of Mathematics 3, 371-392, 2010.American Institute of Mathematics. "Graph Catalog: Families of Graphs." https://aimath.org/WWN/matrixspectrum/catalog2.html.American Institute of Mathematics. "AIM Minimum Rank Graph Catalog." http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/super.American Institute of Mathematics. "AIM Minimum Rank Graph Catalog References." https://web.archive.org/web/20160207084159/http://orion.math.iastate.edu/lhogben/AIMmrgraphcatrefs.pdf.Barrett, W.; Hunnell, M.; Hutchens, J.; and Sinkovic, J. "The Classification of Graphs on 8 vertices with Coinciding Zero Forcing number and Maximum Nullity." 12 Jun 2025. https://arxiv.org/abs/2506.10726.Barrett, W.; van der Holst, H.; and Loewy, R. "Graphs Whose Minimal Rank is Two." Elec. J. Lin. Alg. 11, 258-280, 2004.DeLoss, L.; Grout, J.; Hogben, L.; McKay, T.; Smith, J.; and Tims, J. "Table of Minimum Ranks of Graphs of Order at Most 7 and Selected Optimal Matrices." 4 Dec 2008. https://arxiv.org/abs/0812.0870.Fallat, S. M. and Hogben, L. "Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs." Ch. 46 in Handbook of Linear Algebra, 2nd ed. Boca Raton, FL: CRC Press, 2014.Nylen, P. M. "Minimum-Rank Matrices With Prescribed Graph." Lin. Alg. Appl. 248, 303-316, 1996.

Cite this as:

Weisstein, Eric W. "Zero Forcing Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ZeroForcingNumber.html