betaFeedback

WorksMathematics

On the connected zero forcing polynomial of finite trees

Abstract

Given a graph ΓΓ with vertex set V(Γ)V(Γ) and a set of colored vertices S, the zero forcing rule is an iterative graph coloring process which states that a colored vertex with exactly one uncolored neighbor forces that neighbor to become colored. If repeated application of this rule eventually colors every vertex of ΓΓ, the set SS is called a zero forcing set. Now, if the induced subgraph Γ∣SΓ\vert_S is connected, then SS is called a connected zero forcing set. The minimum cardinality of such a set is the connected zero forcing number ZC(Γ)Z_C(Γ). A connected zero forcing polynomial of a finite graph ΓΓ is a monic polynomial ZCΓ(x)  =  ∑kakxkZ_C^Γ(x) \;=\; \sum_{k} a_k x^k, where aka_k counts the number of connected zero forcing sets of ΓΓ of size kk, which we denote by ZC(Γ,k)Z_C(Γ,k). In this paper, we find the connected zero forcing polynomial of any finite tree TT. We then establish sharp lower bounds for each coefficient of the connected zero forcing polynomial, over all trees on nn vertices with pp many pendant vertices. We also identify a family of trees, which we call uniform trees, and we prove that for any tree on nn vertices and pp many pendant vertices, there exists a uniform tree on nn vertices and pp many pendant vertices, whose connected zero forcing polynomial bounds as an upper bound, the connected zero forcing polynomial of the tree coefficient wise. Again for 2≤p≤42\leq p\leq 4, we establish a sharp upper bound for each coefficient of the connected zero forcing polynomial, over all trees on nn vertices with pp many pendant vertices.

Introduction

The zero forcing process on graphs, introduced [2] originally in connection with the minimum rank problem for symmetric matrices whose off-diagonal pattern is described by a graph, has grown into a vibrant topic of research in its own right. Given a graph Γ\Gamma with vertex set V(Γ)V(\Gamma) and an initial set SS of “colored” vertices, the color change rule states that a colored vertex with exactly one uncolored neighbor forces that neighbor to become colored. If repeated application of this rule eventually colors every vertex of Γ\Gamma, the set SS is called a zero forcing set, and the minimum cardinality of such a set is the zero forcing number Z(Γ)Z(\Gamma). Beyond its original role in bounding the maximum nullity of matrices associated with a graph, zero forcing has since found application in controlling networks of coupled quantum spins, in power domination models for monitoring an electrical grid with phasor measurement units, in fault diagnosis of multiprocessor networks, in modeling the diffusion of information and influence in social networks, where forcing a vertex is a proxy for a status propagating once all but one neighbor’s status is already determined.

A natural refinement of the process, motivated by settings where the monitoring or controlling agents must themselves form a connected substructure, leads to the notion of connected zero forcing. For a graph Γ\Gamma, a subset SS of V(Γ)V(\Gamma) is a connected zero forcing set if SS is a zero forcing set and the induced subgraph Γ∣S\Gamma|_{S} is connected. The minimum cardinality of such a set is the connected zero forcing number ZC(Γ)Z_C(\Gamma). This restriction reflects a genuine constraint in many of the systems zero forcing models: in PMU deployment, for instance, the dominant cost is often the communication infrastructure and maintenance overhead rather than the devices themselves, so a utility benefits from clustering its measurement units into a single connected region, a concern that has motivated a dedicated line of work on connected power domination [9]. A similar principle holds for contagion and influence models such as target set selection, which typically assume the initially active vertices originate from a single, connected source [1], making ZC(Γ)Z_C(\Gamma) the more faithful parameter in that setting.

Beyond the zero forcing number itself, the collection of all zero forcing sets of a graph has been studied from several enumerative and dynamical angles. There is a close relation between Restricted power domination and zero forcing number [6]. In [12], Burgarth et at investigated how the graph theoretic concept of a zero forcing set impacts the controllability property. In [14] and [15], the authors worked on zero forcing on random graphs. In [3] and [19], the authors used the zero forcing number to bound the minimum rank or maximum nullity of a graph. In [17], Goldberg and Berman provided a bound for the maximum nullity of a matrix with a given sign pattern. The propagation time of a zero forcing set records the number of rounds of the color change rule needed to force the entire graph, and one natural question is how large or small this quantity can be over all minimum zero forcing sets [4, 18, 23]. A related parameter, throttling, optimizes the trade-off between the size of a zero forcing set and its propagation time by minimizing their sum over all zero forcing sets of the graph [11, 13]. Both perspectives treat the full family of zero forcing sets, rather than a single minimum-cardinality representative, as the object of interest. Based on this observation, in [5] Boyer et al. introduced the notion of the zero forcing polynomial of a finite graph as a monic polynomial, where the coefficient of the kk-th exponent in the polynomial enumerates the number of zero forcing sets with kk vertices in that graph. Clearly, the exponent corresponding to the smallest non-zero coefficient in that polynomial denotes the zero forcing number of the graph.

An analogous refinement exists for the connected variant. In [7], Brimkov and Davila discussed various applications of the connected zero forcing number. Furthermore, in [8], Brimkov and Hicks proved that determining whether a given initial colored set can successfully complete the zero forcing process remains NP-hard, even when the initial colored set induces a connected subgraph. In [20] Khosravi, Rashidi, and Sheikhhosseini introduced the connected propagation time of a graph and characterized the graphs attaining its extreme values, showing that questions of propagation speed remain meaningful once the initial set is required to stay connected throughout the process. A connected counterpart to throttling, by contrast, appears comparatively unexplored. Taken together, these results indicate that a fuller accounting of connected zero forcing sets beyond just their minimum cardinality, is a natural and largely open direction, one that the connected zero forcing polynomial is designed to address. A connected zero forcing polynomial of a finite graph Γ\Gamma is a monic polynomial ZCΓ(x)=∑kakxkZ_C^\Gamma(x)=\sum_k a_kx^k, where aka_k counts the number of connected zero forcing sets of Γ\Gamma of size kk. While the ordinary zero forcing polynomial has by now been studied for several graph families, the connected variant carries genuinely different combinatorics, since connectivity of SS interacts heavily with the structure of the underlying graph, and the enumeration problem is correspondingly different even for simple graph class, such as trees.

In this article, we undertake a systematic study of the connected zero forcing polynomial of trees. We begin by giving an enumeration of ZCT(x)Z_C^T(x) for a tree TT. Building on this, we turn to the question of how the coefficients of ZCT(x)Z_C^T(x) behave when the number of vertices nn and the number of many pendant vertices pp of TT are held fixed. We first establish sharp lower bounds for each coefficient of the connected zero forcing polynomial, over all trees on nn vertices with pp many pendant vertices, together with a characterization of the extremal trees attaining these bounds. We then take up the more delicate question of an upper bound. Here the situation is fundamentally different: we show that if nn and pp are both fixed, then for p<5p < 5 there is a unique maximal tree but for p≥5p \ge5 in general no single tree whose connected zero forcing polynomial dominates coefficient by coefficient the polynomials of every other tree with nn vertices and pp many pendant vertices. Despite this obstruction, we identify a family of trees, which we call uniform trees, characterized by having their pendant vertices distributed as evenly as possible among the branches at each vertex of degree at least three. We prove that for any tree on nn vertices and pp many pendant vertices, there exists a uniform tree on nn vertices and pp many pendant vertices, whose connected zero forcing polynomial bounds the connected zero forcing polynomial of the tree coefficient wise, from above. This gives, in place of a single extremal tree, an explicit and structurally natural family that plays the extremal role for the entire class.

Preliminary

Before going into the main results, let us first define some graph theoretic preliminaries. A vertex vv of a graph Γ\Gamma is called a pendant vertex if d(v)=1d(v)=1. A path of Γ\Gamma is said to be a pendant path, if at least one of the extreme vertices of the path is a pendant vertex. A vertex vv is called a branch vertex, if d(v)≥3d(v)\ge3. For a subgraph SS of Γ\Gamma and a vertex u∈V(Γ)u\in V(\Gamma), the external neighborhood of uu in Γ\Gamma, denoted NSΓ(u)N_{S}^{\Gamma}(u), is defined to be the collection of all vertices in V(Γ)∖V(S)V(\Gamma)\setminus V(S) which are adjacent to uu in Γ\Gamma. We define NSΓ[u]:=NSΓ(u)∪{u}N_{S}^{\Gamma}[u]:=N_{S}^{\Gamma}(u)\cup\{u\}. The external degree of uu, denoted by dS(u)d_{S}(u) is defined as dS(u)=∣NSΓ(u)∣d_{S}(u)=\lvert N_{S}^{\Gamma}(u)\rvert.

A tree is called a starlike graph, if it has exactly one vertex with degree more than two. It is easy to see that a tree has exactly one pendant vertex if and only if it is a trivial graph, exactly two pendant vertices if and only if it is a path. Further, any tree with only three pendant vertices is a starlike graph. For a starlike graph Γ\Gamma with central vertex uu and pendant vertices v1,v2,…,vkv_{1},v_{2},\ldots,v_{k}, let hi=dist⁡(u,vi)h_{i}=\operatorname{dist}(u,v_{i}) for i∈[k]i\in[k]. Then the starlike graph Γ\Gamma is denoted by Sh1,h2,…,hkS_{h_{1},h_{2},\ldots,h_{k}}.

The starlike graph

Figure 1. The starlike graph Sh1,h2,…,hkS_{h_{1},h_{2},\ldots,h_{k}}.

Let p≥4p\ge4 and n≥p+2n\ge p+2. Choose a partition p=k+(p−k)p=k+(p-k), where 2≤k≤p−22\le k\le p-2. Then the graph Hk,p−knH^{n}_{k,p-k} is the tree with nn vertices and pp many pendant vertices, such that Hk,p−knH^{n}_{k,p-k} has exactly two vertices u1,u2u_{1},u_{2} with degree ≥3\ge3, d(u1)=k+1d(u_{1})=k+1, d(u2)=p−k+1d(u_{2})=p-k+1, and every pendant vertex is adjacent to either u1u_{1} or u2u_{2}.

Definition 2.1. For a finite tree TT, we define the stem of TT to be the minimal subtree of TT containing all the branch vertices of TT. We denote the stem of TT by st⁡(T)\operatorname{st}(T).

Note that the stem of a finite tree is the union of all paths between the branch vertices of that tree. Hence, for a finite tree TT, st⁡(T)\operatorname{st}(T) is unique.

For a connected graph Γ\Gamma and a subset S⊆V(Γ)S\subseteq V(\Gamma), let CS(Γ;i){}^{S}_{C}(\Gamma;i) denote the collection of all connected zero forcing sets of Γ\Gamma of size ii containing SS. When S=∅S=\varnothing, i.e. the collection of all connected zero forcing sets of Γ\Gamma of size ii is denoted by ZC(Γ;i)\mathcal{Z}_{C}(\Gamma;i). Further, we denote ∣ZC(Γ;i)∣=ZCS(Γ;i)|\mathcal{Z}_{C}(\Gamma;i)| = Z^{S}_{C}(\Gamma;i) and ∣ZC(Γ;i)∣=ZC(Γ;i)|\mathcal{Z}_{C}(\Gamma;i)| = Z_{C}(\Gamma;i). We define ZCS(x):=∑i=0∣V(Γ)∣ZCS(Γ;i)xiZ^{S}_{C}(x) := \sum_{i=0}^{|V(\Gamma)|} Z^{S}_{C}(\Gamma;i)x^{i} to be the polynomial having coefficients as the number of connected zero forcing sets of the size of the corresponding exponent, containing the set SS. Also, when SS contain a single vertex vv, we write SS as vv in place of {v}\{v\}.

The graph $\mathcal{H}^{n}_{k,p-k}$

Figure 2. The graph Hk,p−kn\mathcal{H}^{n}_{k,p-k}.

Let P(Γ)P(\Gamma) denote the set of pendant vertices of Γ\Gamma and p(Γ):=∣P(Γ)∣p(\Gamma) := |P(\Gamma)|. We denote by Tn,p\mathcal{T}_{n,p} the collection of all trees with nn vertices and pp many pendant vertices. A pendant vertex ll of a tree TT is said to be a seed of a vertex v∈V(st⁡(T))v \in V(\operatorname{st}(T)), if the pendant path between vv and ll contains only the vertex vv from v∈V(st⁡(T))v \in V(\operatorname{st}(T)). We denote by the set LvL_v, the set of all seeds of vv in TT. If ∣Lv∣=1|L_v| = 1 for some vertex v∈st⁡(T)v \in\operatorname{st}(T), we denote that only vertex by lvl_v. Note that a pendant vertex in TT has a unique seeding vertex in st⁡(T)\operatorname{st}(T). By d(l)d(l), we denote the distance of the pendant vertex ll from its seeding vertex. For a tree TT, we define the following.

S1T:={v∈V(st⁡(T))∣dst⁡(T)(v)=1}.S^{T}_{1}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)=1\}.
S2T:={v∈V(st⁡(T))∣dst⁡(T)(v)=2}.S^{T}_{2}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)=2\}.
S3T:={v∈V(st⁡(T))∣dst⁡(T)(v)≥3}.S^{T}_{3}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)\geq3\}.

Define ST:=S1T∪S2T∪S3TS^{T}:=S^{T}_{1}\cup S^{T}_{2}\cup S^{T}_{3}. For a vertex u∈STu\in S^{T}, let TuT_u denote the minimal subtree of TT containing uu and all the seeds of uu. It is worth noticing that for any vertex v∈S1T∪S2Tv\in S^{T}_{1}\cup S^{T}_{2}, TvT_v is a path, and for any vertex w∈S3Tw\in S^{T}_{3}, TwT_w is a starlike graph.

Observation 2.2. ∣V(st⁡(T))∣+∑l∈P(T)d(l)=n|V(\operatorname{st}(T))|+\sum_{l\in P(T)}d(l)=n.

Observation 2.3. Every pendant vertex of TT has a unique seeding vertex. Also, for every vertex vv of st⁡(T)\operatorname{st}(T), we have ∣Lv∣=dst⁡(T)(v)|L_v|=d_{\operatorname{st}(T)}(v).

As a corollary of the above, we get the following.

Corollary 2.4. Let T∈Tn,pT\in\mathcal{T}_{n,p}. Then ∑v∈V(st⁡(T))dst⁡(T)(v)=p\sum_{v\in V(\operatorname{st}(T))}d_{\operatorname{st}(T)}(v)=p.

The connected zero forcing polynomial of trees

Trees give the connected variant a particularly clean structure, since any connected zero forcing set of a tree TT induces a subtree of TT, and forcing all of TT reduces to identifying a small connected “root” from which the coloring spreads along every branch. This makes trees a natural setting for moving past the connected zero forcing number itself and asking a more refined question—not just how small a connected zero forcing set can be, but how many such sets of each size a tree admits—which is exactly what the connected zero forcing polynomial is built to capture.

The following result is a consequence of [21 Observation 2].

Lemma 3.1. Every connected zero forcing set of a tree TT contains V(st⁡(T))V(\operatorname{st}(T)).

Throughout the rest of this section, we compute the connected zero forcing polynomial of trees. Before getting into the main results, let us first observe the following facts.

References

  1. [1]E. Ackerman, O. Ben-Zwi and G. Wolfovitz, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci. 411 (2010), no. 44-46, 4017–4022.DOI
  2. [2]AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648.
  3. [3]A. M. R.-S. G. W. Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (7) (2008) 1628–1648.
  4. [4]A. H. Berliner et al., Zero forcing propagation time on oriented graphs, Discrete Appl. Math. 224 (2017), 45–59.DOI
  5. [5]K. Boyer et al., The zero forcing polynomial of a graph, Discrete Appl. Math. 258 (2019), 35–48.DOI
  6. [6]C. Bozeman, B. Brimkov, C. Erickson, D. Ferrero, M. Flagg, L. Hogben, Restricted power domination and zero forcing problems, J. Comb. Optim. 37 (3) (2019) 935–956.arxiv.org/abs/1711.05190
  7. [7]B. Brimkov, R. Davila, Characterizations of the Connected Forcing Number of a Graph, https://arxiv.org/pdf/1604.00740.
  8. [8]B. Brimkov, I.V. Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math. 229 (2017) 31–45.arxiv.org/abs/1607.00658
  9. [9]B. Brimkov, D. J. Mikesell and L. A. Smith, Connected power domination in graphs, J. Comb. Optim. 38 (2019), no. 1, 292–315.arxiv.org/abs/1712.02388
  10. [11]S. K. Butler and M. E. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin. 57 (2013), 65–71.
  11. [12]D. Burgarth, D. D’Alessandro, L. Hogben, S. Severini, M. Young, Zero forcing, linear and quantum controllability for systems evolving on networks, IEEE Trans. Autom. Control 58 (9) (2013) 2349–2354.DOI
  12. [13]J. Carlson et al., Throttling positive semidefinite zero forcing propagation time on graphs, Discrete Appl. Math. 254 (2019), 33–46.DOI
  13. [14]B. Curtis, L. Gan, J. Haddock, R. Lawrence, S. Spiro, Zero forcing with random sets, Discrete Math. 347 (5) (2024) 113944. Positive semidefinite zero forcing, Linear Algebra Appl. 439 (7) (2013) 1862–1874......arxiv.org/abs/2208.12899
  14. [15]S. English, C. MacRury, P. Pralat, Probabilistic zero forcing on random graphs, Eur. J. Comb. 91 (2021) 103207.arxiv.org/abs/1909.06568
  15. [16]S. German, The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction. In: Li, Y., Stephan, F., Sun, X. (eds) Computing and Combinatorics. COCOON 2026. Lecture Notes in Computer Science, vol 16835. Springer, Singapore.DOI
  16. [17]F. Goldberg, A. Berman, Zero forcing for sign patterns, Linear Algebra Appl. 447 (2014) 56–67.arxiv.org/abs/1307.2198
  17. [18]L. Hogben et al., Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (2012), no. 13-14, 1994–2005.DOI
  18. [19]L.-H. Huang, G.J. Chang, H.-G. Yeh, On minimum rank and zero forcing sets of a graph, Linear Algebra Appl. 432 (11) (2010) 2961–2973.DOI
  19. [20]M. Khosravi, S. Rashidi and A. Sheikhhosseini, Connected zero forcing sets and connected propagation time of graphs, Trans. Comb. 9 (2020), no. 2, 77–88.
  20. [21]B. Li, Y. Cao and S. Ji, The extremal results for forcing problem of trees, Graphs Combin. 41 (2025), no. 4, Paper No. 70, 10 pp.DOI
  21. [22]K. Menon a, A. Singh, Exploring the influence of graph operations on zero forcing sets, Discrete Mathematics, 348 (2025) 114516.arxiv.org/abs/2405.01423
  22. [23]N. Warnberg, Positive semidefinite propagation time, Discrete Appl. Math. 198 (2016), 274–290.

Paper details

vlnc:W_yc73c47t
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents