Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 3 min ago
PreprintCC BY-NC-SA 4.0arXiv

Maximizing the discrepancy between zero forcing parameters relative to graph order

  • Andrew McKay
  • Allie Ray
  • Jonathan Valliere
Open at sourcePDFDOICite

Abstract

Zero forcing is a process described by a color change rule on the vertices of a graph. In this paper, we maximize the discrepancy between various zero forcing parameters relative to graph order. First, we find an upper bound on the difference in cardinality between minimal zero forcing sets (sets containing no proper zero forcing subset) of maximum and minimum size, and we show that this bound is sharp for an infinite family of graphs. Furthermore, we derive an upper bound for the discrepancy between the maximum and minimum propagation times of the minimum zero forcing sets of any graph, showing this bound is sharp for an infinite family of graphs.

Related

  1. The Zero Forcing Number of Graph Powers
    Aida Abiad, Mary Flagg, Sina Ghasemi Nezhad +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An overview of universal obstructions for graph parameters
    Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos
    Discrete Applied MathematicsPeer-reviewedLicence not statedFull textCombinatorics & discrete mathematicsHAL
  3. Nonexistence of a Strongly Regular Graph with Parameters (266,45,0,9): A Certificate-Free Lean Proof
    Kay Akiyama
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Mixed partition functions are exactly the graph parameters of exponentially bounded edge-connection rank
    William Whistler
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. On the non-existence of certain maximizing curves of degree 7
    Łukasz Merta, Marcin Zieliński
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{mckay2026maximizing,
  title = {{Maximizing the discrepancy between zero forcing parameters relative to graph order}},
  author = {Andrew McKay and Allie Ray and Jonathan Valliere},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35522},
  eprint = {2609.35522},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35522},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Maximizing the discrepancy between zero forcing parameters relative to graph order
AU  - Andrew McKay
AU  - Allie Ray
AU  - Jonathan Valliere
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35522
UR  - https://arxiv.org/abs/2609.35522
AB  - Zero forcing is a process described by a color change rule on the vertices of a graph. In this paper, we maximize the discrepancy between various zero forcing parameters relative to graph order. First, we find an upper bound on the difference in cardinality between minimal zero forcing sets (sets containing no proper zero forcing subset) of maximum and minimum size, and we show that this bound is sharp for an infinite family of graphs. Furthermore, we derive an upper bound for the discrepancy between the maximum and minimum propagation times of the minimum zero forcing sets of any graph, showing this bound is sharp for an infinite family of graphs.
ER  -