pith. sign in

arxiv: 2605.07298 · v1 · submitted 2026-05-08 · 🧮 math.CO

On the Number of Zero Forcing Minimal Forts on Trees

Nguyen Hoang Dat , Franklin H. J. Kenter This is my paper

Pith reviewed 2026-05-11 01:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords zero forcingminimal fortstreespathsrecursionstrong inductiongraph enumerationforests
0
0 comments X

The pith

The maximum number of minimal forts on any tree with n vertices is at most binom(n,2) times the number on the path with n vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the largest possible number of minimal forts over all trees on n vertices cannot exceed the binomial coefficient n choose 2 multiplied by the exact count for the single path graph on the same number of vertices. This settles a conjecture in zero-forcing theory by showing that tree shape cannot produce arbitrarily more of these sets than a straight line does. The argument rests on exhaustive computer enumeration of small trees to anchor the base cases of a strong induction, together with a recursion that tallies minimal forts across any forest rather than only paths. A reader cares because the bound supplies a concrete, simple limit on how many such sets can exist in tree-structured graphs.

Core claim

We prove that F_{T_n} is at most binom(n,2) times F_{P_n}, where F_{T_n} is the maximum number of minimal forts over every tree on n vertices and F_{P_n} is the number for the path on n vertices. The proof uses strong induction on n. The base cases are settled by running an efficient enumeration algorithm on every tree of small order. In the inductive step, an adaptation of the path recursion that works for arbitrary forests reduces the count on a larger tree to counts on strictly smaller forests.

What carries the argument

The recursion relation for counting minimal forts, extended from paths to all forests, which breaks any tree into smaller sub-forests and thereby supports the inductive step.

If this is right

  • The inequality holds for every n once the base cases and the forest recursion are accepted.
  • The count of minimal forts on any tree is controlled by a quadratic factor times the path count.
  • The same recursion applies directly to every forest, not only to trees.
  • Exhaustive enumeration suffices to verify the bound up to any fixed moderate n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The quadratic relative bound may simplify complexity estimates for algorithms that search for minimal forts on trees.
  • The forest recursion could be tested on other sparse graph families to obtain similar comparison bounds.
  • The introduced enumeration procedure may be reusable for counting other zero-forcing objects on small graphs.

Load-bearing premise

The adapted recursion counts minimal forts correctly on every forest and the computer enumeration of all small trees is both accurate and complete.

What would settle it

Any single tree on n vertices whose number of minimal forts exceeds binom(n,2) times the number on the path P_n would disprove the claimed bound.

Figures

Figures reproduced from arXiv: 2605.07298 by Franklin H. J. Kenter, Nguyen Hoang Dat.

Figure 1
Figure 1. Figure 1: Continuous log-plot of the functions describing the number of minimal forts of different families of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The tree T(19, 4, 4, 2). It is the unique tree on 19 vertices with the maximum number of minimal forts (162) among all trees on 19 vertices [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of a tree with the minimum number of minimal forts (8) among all trees on [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Log-plot of the execution time (ns) for individual trees based on the number of vertices. [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Plot of 5 3 (FPn − 1) − n−6 2  as referenced in Lemma 16. Lemma 17. For d ≥ 6, the ratio 1 d [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Examples of unicyclic graphs with forts (as uncolored vertices) that do not obey results for trees. [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
read the original abstract

We solve a conjecture by Becker et al. (arXiv:2404.05963) on the topic of zero forcing regarding the number of minimal forts of a tree. They conjectured and we prove $\mathcal{F}_{T_n} \le \binom{n}{2} \mathcal{F}_{P_n}$ where $\mathcal{F}_{T_n}$ is the maximum number of minimal forts on a tree on $n$ vertices and $\mathcal{F}_{P_n}$ is the number of minimal forts of the path graph on $n$ vertices. Our solution relies on both a computational and theoretical approach. Computationally, we introduce and implement an efficient algorithm to compute the exact number of minimal forts for small trees; this is used to establish the large base case required for our strong induction. Theoretically, we provide an adaptation of the recursion relation that defines $\mathcal{F}_{P_n}$ that applies for all forests; this is used in the induction step to establish the result.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves the conjecture of Becker et al. that the maximum number of minimal forts on any n-vertex tree satisfies F_{T_n} ≤ binom(n,2) F_{P_n}, where F_{P_n} counts minimal forts on the path P_n. The argument proceeds by strong induction on n: a custom enumeration algorithm computes exact counts for all trees on at most N vertices to establish the base, after which an adaptation of the path recursion is applied to forests to bound the quantity in the inductive step.

Significance. If the base-case counts and the forest recursion are both correct, the result supplies a concrete polynomial upper bound on the extremal number of minimal forts over all trees, resolving the stated conjecture in zero-forcing theory. The hybrid computational-inductive strategy is a standard and efficient route for such problems once the base and recursion are verified.

major comments (2)
  1. [§3] §3 (Computational Enumeration): the algorithm is asserted to produce the exact base-case values up to N, yet the manuscript supplies neither pseudocode, complexity analysis, nor an independent verification (e.g., explicit counts for n≤6 or a link to reproducible code). Any under- or over-count in this base propagates directly into the induction and therefore constitutes a load-bearing gap.
  2. [§4] §4 (Induction Step and Adapted Recursion): the adaptation of the path recursion to arbitrary forests is invoked to close the inductive step, but no formal argument is given that the relation continues to count every minimal fort configuration exactly once when branches or disconnected components are present. Without this justification the inequality F_{T_n} ≤ binom(n,2) F_{P_n} is not yet established for all trees.
minor comments (2)
  1. [Notation] The abstract uses mathcal{F} while the body uses F; standardize the notation throughout.
  2. [Appendix] Add a short table or appendix listing the computed base-case values for small n so readers can spot-check the induction hypothesis.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and for highlighting points that will strengthen the clarity and rigor of the manuscript. We address each major comment below and will incorporate the suggested improvements in the revised version.

read point-by-point responses

  1. Referee: [§3] §3 (Computational Enumeration): the algorithm is asserted to produce the exact base-case values up to N, yet the manuscript supplies neither pseudocode, complexity analysis, nor an independent verification (e.g., explicit counts for n≤6 or a link to reproducible code). Any under- or over-count in this base propagates directly into the induction and therefore constitutes a load-bearing gap.

    Authors: We agree that additional details on the enumeration procedure are necessary for independent verification and to ensure the base cases are robust. In the revised manuscript we will add pseudocode for the algorithm, a complexity analysis, and explicit counts of minimal forts for all trees on n ≤ 6 vertices. We will also include a link to the publicly available source code used to generate the base-case data. revision: yes

  2. Referee: [§4] §4 (Induction Step and Adapted Recursion): the adaptation of the path recursion to arbitrary forests is invoked to close the inductive step, but no formal argument is given that the relation continues to count every minimal fort configuration exactly once when branches or disconnected components are present. Without this justification the inequality F_{T_n} ≤ binom(n,2) F_{P_n} is not yet established for all trees.

    Authors: We acknowledge that a more explicit justification of the adapted recursion is required. In the revised manuscript we will expand the inductive step to include a detailed formal argument showing that the recursion partitions the set of minimal forts exactly once for any forest, accounting for both branched structures and disconnected components. This will be achieved by classifying minimal forts according to their intersection with the distinguished vertices and verifying that the counting relation holds without overlap or omission. revision: yes

Circularity Check

0 steps flagged

No significant circularity; induction relies on external computation and explicit adaptation

full rationale

The derivation proceeds by strong induction on n. The base case up to a fixed N is supplied by an independent computational enumeration algorithm whose correctness is external to the target inequality. The induction step invokes an explicitly adapted recursion that extends the path case to forests; this adaptation is stated and applied as a separate theoretical step rather than being defined in terms of the final bound. No equation reduces the claimed inequality F_{T_n} ≤ binom(n,2) F_{P_n} to a fitted parameter, a self-referential definition, or a load-bearing self-citation. The result therefore remains non-circular under the stated criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the standard principle of strong induction and the domain-specific claim that the path recursion extends to forests; no free parameters or new entities are introduced.

axioms (2)
  • standard math Strong induction on the number of vertices
    Invoked to lift the bound from small trees (computed) to all trees.
  • domain assumption The recursion counting minimal forts on paths extends to arbitrary forests
    Adapted and used in the induction step as stated in the abstract.

pith-pipeline@v0.9.0 · 5467 in / 1265 out tokens · 54339 ms · 2026-05-11T01:02:55.627650+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Hardness results and approximation algorithms for some problems on graphs

    Aazami, A. Hardness results and approximation algorithms for some problems on graphs . PhD thesis, University of Waterloo Waterloo, Ontario, Canada, 2008

    work page 2008

  2. [2]

    Leader selection for strong structural controllability in networks using zero forcing sets

    Abbas, W., Shabbir, M., Yaz c o g lu, Y., and Koutsoukos, X. Leader selection for strong structural controllability in networks using zero forcing sets. In 2022 American Control Conference (ACC)\/ (2022), IEEE, pp. 1444--1449

    work page 2022

  3. [3]

    Zero forcing sets and the minimum rank of graphs

    AIM Minimum Rank--Special Graphs Work Group . Zero forcing sets and the minimum rank of graphs. Linear algebra and its applications 428 , 7 (2008), 1628--1648

    work page 2008

  4. [4]

    R., Hanely, D., Ong, B., and Previte, J

    Becker, P., Cameron, T. R., Hanely, D., Ong, B., and Previte, J. P. On the number of minimal forts of a graph. Graphs and Combinatorics 41 , 1 (2025), 25

    work page 2025

  5. [5]

    Brimkov, B., Mikesell, D., and Hicks, I. V. Improved computational approaches and heuristics for zero forcing. INFORMS Journal on Computing 33 , 4 (2021), 1384--1399

    work page 2021

  6. [6]

    J., and Heath, L

    Brueni, D. J., and Heath, L. S. The P M U placement problem. SIAM Journal on Discrete Mathematics 19 , 3 (2005), 744--761

    work page 2005

  7. [7]

    Zero forcing, linear and quantum controllability for systems evolving on networks

    Burgarth, D., D'Alessandro, D., Hogben, L., Severini, S., and Young, M. Zero forcing, linear and quantum controllability for systems evolving on networks. IEEE Transactions on Automatic Control 58 , 9 (2013), 2349--2354

    work page 2013

  8. [8]

    R., Hogben, L., Kenter, F

    Cameron, T. R., Hogben, L., Kenter, F. H., Mojallal, S. A., and Schuerger, H. Forts,(fractional) zero forcing, and cartesian products of graphs. arXiv preprint arXiv:2310.17904\/ (2023)

    work page arXiv 2023

  9. [9]

    R., and Li, K

    Cameron, T. R., and Li, K. On the minimal forts of trees. arXiv preprint arXiv:2512.12874\/ (2025)

    work page arXiv 2025

  10. [10]

    C., and Hicks, I

    Fast, C. C., and Hicks, I. V. Effects of vertex degrees on the zero-forcing number and propagation time of a graph. Discrete Applied Mathematics 250\/ (2018), 215--226

    work page 2018

  11. [11]

    V., and Brimkov, B

    Hicks, I. V., and Brimkov, B. The many face(t)s of zero forcing. Notices of the American Mathematical Society 71 , 2 (2024), 167--173

    work page 2024

  12. [12]

    Hybrid search for the optimal P M U placement problem on a power grid

    Liao, C.-S., Hsieh, T.-J., Guo, X.-C., Liu, J.-H., and Chu, C.-C. Hybrid search for the optimal P M U placement problem on a power grid. European Journal of Operational Research 243 , 3 (2015), 985--994

    work page 2015

  13. [13]

    Combinatorial Data: Trees

    McKay, B. Combinatorial Data: Trees . https://users.cecs.anu.edu.au/ bdm/data/, 2025. Accessed: 14 November 2025

    work page 2025

  14. [14]

    Monshizadeh, N., Zhang, S., and Camlibel, M. K. Zero forcing sets and controllability of dynamical systems defined on graphs. IEEE Transactions on Automatic Control 59 , 9 (2014), 2562--2567

    work page 2014

  15. [15]

    N. H. ạt . Github: Minimal F orts. https://github.com/datkony/MinimalForts, 2026

    work page 2026

  16. [16]

    Zero forcing number, constrained matchings and strong structural controllability

    Trefois, M., and Delvenne, J.-C. Zero forcing number, constrained matchings and strong structural controllability. Linear Algebra and its Applications 484\/ (2015), 199--218

    work page 2015