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) V ( Γ ) and an initial set S S S 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 S S S is called a zero forcing set , and the minimum cardinality of such a set is the zero forcing number Z ( Γ ) Z(\Gamma) Z ( Γ ) . 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 S S S of V ( Γ ) V(\Gamma) V ( Γ ) is a connected zero forcing set if S S S is a zero forcing set and the induced subgraph Γ ∣ S \Gamma|_{S} Γ ∣ S is connected. The minimum cardinality of such a set is the connected zero forcing number Z C ( Γ ) Z_C(\Gamma) Z C ( Γ ) . 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 Z C ( Γ ) Z_C(\Gamma) Z C ( Γ ) 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 k k k -th exponent in the polynomial enumerates the number of zero forcing sets with k k k 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 Z C Γ ( x ) = ∑ k a k x k Z_C^\Gamma(x)=\sum_k a_kx^k Z C Γ ( x ) = ∑ k a k x k , where a k a_k a k counts the number of connected zero forcing sets of Γ \Gamma Γ of size k k k . 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 S S S 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 Z C T ( x ) Z_C^T(x) Z C T ( x ) for a tree T T T . Building on this, we turn to the question of how the coefficients of Z C T ( x ) Z_C^T(x) Z C T ( x ) behave when the number of vertices n n n and the number of many pendant vertices p p p of T T T are held fixed. We first establish sharp lower bounds for each coefficient of the connected zero forcing polynomial, over all trees on n n n vertices with p p p 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 n n n and p p p are both fixed, then for p < 5 p < 5 p < 5 there is a unique maximal tree but for p ≥ 5 p \ge5 p ≥ 5 in general no single tree whose connected zero forcing polynomial dominates coefficient by coefficient the polynomials of every other tree with n n n vertices and p p p 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 n n n vertices and p p p many pendant vertices, there exists a uniform tree on n n n vertices and p p p 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 v v v of a graph Γ \Gamma Γ is called a pendant vertex if d ( v ) = 1 d(v)=1 d ( 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 v v v is called a branch vertex , if d ( v ) ≥ 3 d(v)\ge3 d ( v ) ≥ 3 . For a subgraph S S S of Γ \Gamma Γ and a vertex u ∈ V ( Γ ) u\in V(\Gamma) u ∈ V ( Γ ) , the external neighborhood of u u u in Γ \Gamma Γ , denoted N S Γ ( u ) N_{S}^{\Gamma}(u) N S Γ ( u ) , is defined to be the collection of all vertices in V ( Γ ) ∖ V ( S ) V(\Gamma)\setminus V(S) V ( Γ ) ∖ V ( S ) which are adjacent to u u u in Γ \Gamma Γ . We define N S Γ [ u ] : = N S Γ ( u ) ∪ { u } N_{S}^{\Gamma}[u]:=N_{S}^{\Gamma}(u)\cup\{u\} N S Γ [ u ] := N S Γ ( u ) ∪ { u } . The external degree of u u u , denoted by d S ( u ) d_{S}(u) d S ( u ) is defined as d S ( u ) = ∣ N S Γ ( u ) ∣ d_{S}(u)=\lvert N_{S}^{\Gamma}(u)\rvert d S ( u ) = ∣ N S Γ ( u )∣ .
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 u u u and pendant vertices v 1 , v 2 , … , v k v_{1},v_{2},\ldots,v_{k} v 1 , v 2 , … , v k , let h i = dist ( u , v i ) h_{i}=\operatorname{dist}(u,v_{i}) h i = dist ( u , v i ) for i ∈ [ k ] i\in[k] i ∈ [ k ] . Then the starlike graph Γ \Gamma Γ is denoted by S h 1 , h 2 , … , h k S_{h_{1},h_{2},\ldots,h_{k}} S h 1 , h 2 , … , h k .
Figure 1. The starlike graph S h 1 , h 2 , … , h k S_{h_{1},h_{2},\ldots,h_{k}} S h 1 , h 2 , … , h k .
Let p ≥ 4 p\ge4 p ≥ 4 and n ≥ p + 2 n\ge p+2 n ≥ p + 2 . Choose a partition p = k + ( p − k ) p=k+(p-k) p = k + ( p − k ) , where 2 ≤ k ≤ p − 2 2\le k\le p-2 2 ≤ k ≤ p − 2 . Then the graph H k , p − k n H^{n}_{k,p-k} H k , p − k n is the tree with n n n vertices and p p p many pendant vertices, such that H k , p − k n H^{n}_{k,p-k} H k , p − k n has exactly two vertices u 1 , u 2 u_{1},u_{2} u 1 , u 2 with degree ≥ 3 \ge3 ≥ 3 , d ( u 1 ) = k + 1 d(u_{1})=k+1 d ( u 1 ) = k + 1 , d ( u 2 ) = p − k + 1 d(u_{2})=p-k+1 d ( u 2 ) = p − k + 1 , and every pendant vertex is adjacent to either u 1 u_{1} u 1 or u 2 u_{2} u 2 .
Definition 2.1. For a finite tree T T T , we define the stem of T T T to be the minimal subtree of T T T containing all the branch vertices of T T T . We denote the stem of T T T by st ( T ) \operatorname{st}(T) 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 T T T , st ( T ) \operatorname{st}(T) st ( T ) is unique.
For a connected graph Γ \Gamma Γ and a subset S ⊆ V ( Γ ) S\subseteq V(\Gamma) S ⊆ V ( Γ ) , let C S ( Γ ; i ) {}^{S}_{C}(\Gamma;i) C S ( Γ ; i ) denote the collection of all connected zero forcing sets of Γ \Gamma Γ of size i i i containing S S S . When S = ∅ S=\varnothing S = ∅ , i.e. the collection of all connected zero forcing sets of Γ \Gamma Γ of size i i i is denoted by Z C ( Γ ; i ) \mathcal{Z}_{C}(\Gamma;i) Z C ( Γ ; i ) . Further, we denote ∣ Z C ( Γ ; i ) ∣ = Z C S ( Γ ; i ) |\mathcal{Z}_{C}(\Gamma;i)| = Z^{S}_{C}(\Gamma;i) ∣ Z C ( Γ ; i ) ∣ = Z C S ( Γ ; i ) and ∣ Z C ( Γ ; i ) ∣ = Z C ( Γ ; i ) |\mathcal{Z}_{C}(\Gamma;i)| = Z_{C}(\Gamma;i) ∣ Z C ( Γ ; i ) ∣ = Z C ( Γ ; i ) . We define Z C S ( x ) : = ∑ i = 0 ∣ V ( Γ ) ∣ Z C S ( Γ ; i ) x i Z^{S}_{C}(x) := \sum_{i=0}^{|V(\Gamma)|} Z^{S}_{C}(\Gamma;i)x^{i} Z C S ( x ) := ∑ i = 0 ∣ V ( Γ ) ∣ Z C S ( Γ ; 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 S S S . Also, when S S S contain a single vertex v v v , we write S S S as v v v in place of { v } \{v\} { v } .
Figure 2. The graph H k , p − k n \mathcal{H}^{n}_{k,p-k} H k , p − k n .
Let P ( Γ ) P(\Gamma) P ( Γ ) denote the set of pendant vertices of Γ \Gamma Γ and p ( Γ ) : = ∣ P ( Γ ) ∣ p(\Gamma) := |P(\Gamma)| p ( Γ ) := ∣ P ( Γ ) ∣ . We denote by T n , p \mathcal{T}_{n,p} T n , p the collection of all trees with n n n vertices and p p p many pendant vertices. A pendant vertex l l l of a tree T T T is said to be a seed of a vertex v ∈ V ( st ( T ) ) v \in V(\operatorname{st}(T)) v ∈ V ( st ( T )) , if the pendant path between v v v and l l l contains only the vertex v v v from v ∈ V ( st ( T ) ) v \in V(\operatorname{st}(T)) v ∈ V ( st ( T )) . We denote by the set L v L_v L v , the set of all seeds of v v v in T T T . If ∣ L v ∣ = 1 |L_v| = 1 ∣ L v ∣ = 1 for some vertex v ∈ st ( T ) v \in\operatorname{st}(T) v ∈ st ( T ) , we denote that only vertex by l v l_v l v . Note that a pendant vertex in T T T has a unique seeding vertex in st ( T ) \operatorname{st}(T) st ( T ) . By d ( l ) d(l) d ( l ) , we denote the distance of the pendant vertex l l l from its seeding vertex. For a tree T T T , we define the following.
S 1 T : = { v ∈ V ( st ( T ) ) ∣ d st ( T ) ( v ) = 1 } . S^{T}_{1}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)=1\}. S 1 T := { v ∈ V ( st ( T )) ∣ d st ( T ) ( v ) = 1 } .
S 2 T : = { v ∈ V ( st ( T ) ) ∣ d st ( T ) ( v ) = 2 } . S^{T}_{2}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)=2\}. S 2 T := { v ∈ V ( st ( T )) ∣ d st ( T ) ( v ) = 2 } .
S 3 T : = { v ∈ V ( st ( T ) ) ∣ d st ( T ) ( v ) ≥ 3 } . S^{T}_{3}:=\{v\in V(\operatorname{st}(T))\mid d_{\operatorname{st}(T)}(v)\geq3\}. S 3 T := { v ∈ V ( st ( T )) ∣ d st ( T ) ( v ) ≥ 3 } .
Define S T : = S 1 T ∪ S 2 T ∪ S 3 T S^{T}:=S^{T}_{1}\cup S^{T}_{2}\cup S^{T}_{3} S T := S 1 T ∪ S 2 T ∪ S 3 T . For a vertex u ∈ S T u\in S^{T} u ∈ S T , let T u T_u T u denote the minimal subtree of T T T containing u u u and all the seeds of u u u . It is worth noticing that for any vertex v ∈ S 1 T ∪ S 2 T v\in S^{T}_{1}\cup S^{T}_{2} v ∈ S 1 T ∪ S 2 T , T v T_v T v is a path, and for any vertex w ∈ S 3 T w\in S^{T}_{3} w ∈ S 3 T , T w T_w T 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 ∣ V ( st ( T )) ∣ + ∑ l ∈ P ( T ) d ( l ) = n .
Observation 2.3. Every pendant vertex of T T T has a unique seeding vertex. Also, for every vertex v v v of st ( T ) \operatorname{st}(T) st ( T ) , we have ∣ L v ∣ = d st ( T ) ( v ) |L_v|=d_{\operatorname{st}(T)}(v) ∣ L v ∣ = d st ( T ) ( v ) .
As a corollary of the above, we get the following.
Corollary 2.4. Let T ∈ T n , p T\in\mathcal{T}_{n,p} T ∈ T n , p . Then ∑ v ∈ V ( st ( T ) ) d st ( T ) ( v ) = p \sum_{v\in V(\operatorname{st}(T))}d_{\operatorname{st}(T)}(v)=p ∑ v ∈ V ( st ( T )) d 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 T T T induces a subtree of T T T , and forcing all of T T T 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 T T T contains V ( st ( T ) ) V(\operatorname{st}(T)) V ( 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.
Lemma 3.2. Let P P P be a path of length n n n , with two endpoints v 1 v_1 v 1 and v 2 v_2 v 2 , and an intermediate point w w w at a distance of l l l from v 1 v_1 v 1 , with 0 < l < n 0 < l < n 0 < l < n . Then Z C P , v 1 ( x ) = Z C P , v 2 ( x ) = x ( 1 + x x n − 1 x − 1 ) Z_C^{P,v_1}(x) = Z_C^{P,v_2}(x) = x(1+x\frac{x^{n-1}}{x-1}) Z C P , v 1 ( x ) = Z C P , v 2 ( x ) = x ( 1 + x x − 1 x n − 1 ) , and Z C P , w ( x ) = x 2 ( x k − 1 ) ( x n − k − 1 ) ( x − 1 ) 2 ( x + ( x − 1 ) ( 1 x l − 1 + 1 x n − l − 1 ) ) Z_C^{P,w}(x) = x^2\frac{(x^{k-1})(x^{n-k-1})}{(x-1)^2}(x+(x-1)(\frac{1}{x^{l-1}}+\frac{1}{x^{n-l-1}})) Z C P , w ( x ) = x 2 ( x − 1 ) 2 ( x k − 1 ) ( x n − k − 1 ) ( x + ( x − 1 ) ( x l − 1 1 + x n − l − 1 1 )) .
Proof. Since, v 1 v_1 v 1 (equivalently v 2 v_2 v 2 ) is a terminal point of P P P , for any k ∈ [ n ] k \in[n] k ∈ [ n ] the only connected zero forcing set of P P P containing v 1 v_1 v 1 (equivalently v 2 v_2 v 2 ) is the subpath of P P P starting at v 1 v_1 v 1 (equivalently v 2 v_2 v 2 ), with length k k k . So, we have Z C P , v 1 ( x ) = Z C P , v 2 ( x ) = x + x 2 + ⋯ + x n + 1 = x ( 1 + x x n − 1 x − 1 ) Z_C^{P,v_1}(x)=Z_C^{P,v_2}(x)=x+x^2+\cdots+x^{n+1}=x(1+x\frac{x^{n-1}}{x-1}) Z C P , v 1 ( x ) = Z C P , v 2 ( x ) = x + x 2 + ⋯ + x n + 1 = x ( 1 + x x − 1 x n − 1 ) .
Now, consider the set of all connected zero forcing sets of P P P , containing w w w . It is easy to see that a connected zero forcing set of P P P , containing w w w can miss at most one neighbor of w w w . Now, the generating function for the number of connected zero forcing sets of P P P containing both the neighbors of w w w is x ( x + x 2 + ⋯ + x l ) ( x + x 2 + ⋯ + x n − l ) x(x+x^2+\cdots+x^l)(x+x^2+\cdots+x^{n-l}) x ( x + x 2 + ⋯ + x l ) ( x + x 2 + ⋯ + x n − l ) , and generating function for the number of connected zero forcing sets of P P P containing exactly one of the neighbors of w w w is x ( x + x 2 + ⋯ + x l ) + x ( x + x 2 + ⋯ + x n − l ) x(x+x^2+\cdots+x^l)+x(x+x^2+\cdots+x^{n-l}) x ( x + x 2 + ⋯ + x l ) + x ( x + x 2 + ⋯ + x n − l ) . Thus, we have Z C P , w ( x ) = x ( x + x 2 + ⋯ + x l ) ( x + x 2 + ⋯ + x n − l ) + x ( x + x 2 + ⋯ + x l ) + x ( x + x 2 + ⋯ + x n − l ) = x 2 ( x k − 1 ) ( x n − k − 1 ) ( x − 1 ) 2 ( x + ( x − 1 ) ( 1 x l − 1 + 1 x n − l − 1 ) ) Z_C^{P,w}(x)=x(x+x^2+\cdots+x^l)(x+x^2+\cdots+x^{n-l})+x(x+x^2+\cdots+x^l)+x(x+x^2+\cdots+x^{n-l})=x^2\frac{(x^{k-1})(x^{n-k-1})}{(x-1)^2}(x+(x-1)(\frac{1}{x^{l-1}}+\frac{1}{x^{n-l-1}})) Z C P , w ( x ) = x ( x + x 2 + ⋯ + x l ) ( x + x 2 + ⋯ + x n − l ) + x ( x + x 2 + ⋯ + x l ) + x ( x + x 2 + ⋯ + x n − l ) = x 2 ( x − 1 ) 2 ( x k − 1 ) ( x n − k − 1 ) ( x + ( x − 1 ) ( x l − 1 1 + x n − l − 1 1 )) .
:::
Lemma 3.3. Let T T T be the starlike graph S h 1 , h 2 , … , h k S_{h_1,h_2,\ldots,h_k} S h 1 , h 2 , … , h k , for k ≥ 3 k \ge3 k ≥ 3 . Then Z C T ( x ) = x k ( ∏ i = 1 k x h i − 1 x − 1 ) ( x + ∑ i = 1 k x − 1 x h i − 1 ) Z_C^T(x)=x^k(\prod_{i=1}^k\frac{x^{h_i-1}}{x-1})(x+\sum_{i=1}^k\frac{x-1}{x^{h_i-1}}) Z C T ( x ) = x k ( ∏ i = 1 k x − 1 x h i − 1 ) ( x + ∑ i = 1 k x h i − 1 x − 1 ) .
Proof. Let v v v be the central vertex of the starlike graph S h 1 , h 2 , … , h k S_{h_1,h_2,\ldots,h_k} S h 1 , h 2 , … , h k . Again, it can be seen that a connected zero forcing set of S h 1 , h 2 , … , h k S_{h_1,h_2,\ldots,h_k} S h 1 , h 2 , … , h k contains v v v , and can miss at most one neighbor of v v v . Now, the generating function for the number of connected zero forcing sets of S h 1 , h 2 , … , h k S_{h_1,h_2,\ldots,h_k} S h 1 , h 2 , … , h k containing all the neighbors of w w w is x ( ∏ i = 1 k ( x + x 2 + ⋯ + x i ) ) x(\prod_{i=1}^k(x+x^2+\cdots+x^i)) x ( ∏ i = 1 k ( x + x 2 + ⋯ + x i )) , and the generating function for the number of connected zero forcing sets of S h 1 , h 2 , … , h k S_{h_1,h_2,\ldots,h_k} S h 1 , h 2 , … , h k containing all but one neighbors of w w w is x ( ∑ i = 1 k ∏ j ≠ i k ( x + x 2 + ⋯ + x i ) ) x(\sum_{i=1}^k\prod_{j\ne i}^k(x+x^2+\cdots+x^i)) x ( ∑ i = 1 k ∏ j = i k ( x + x 2 + ⋯ + x i )) .
Thus, the connected zero forcing polynomial is x ( ∏ i = 1 k ( x + x 2 + ⋯ + x i ) ) + x ( ∑ i = 1 k ∏ j ≠ i k ( x + x 2 + ⋯ + x i ) ) x(\prod_{i=1}^k(x+x^2+\cdots+x^i))+x(\sum_{i=1}^k\prod_{j\ne i}^k(x+x^2+\cdots+x^i)) x ( ∏ i = 1 k ( x + x 2 + ⋯ + x i )) + x ( ∑ i = 1 k ∏ j = i k ( x + x 2 + ⋯ + x i )) , and a few steps of simple calculations yield that Z C S h 1 , h 2 , … , h k ( x ) = x k ( ∏ i = 1 k x h i − 1 x − 1 ) ( x + ∑ i = 1 k x − 1 x h i − 1 ) Z_C^{S_{h_1,h_2,\ldots,h_k}}(x)=x^k(\prod_{i=1}^k\frac{x^{h_i-1}}{x-1})(x+\sum_{i=1}^k\frac{x-1}{x^{h_i-1}}) Z C S h 1 , h 2 , … , h k ( x ) = x k ( ∏ i = 1 k x − 1 x h i − 1 ) ( x + ∑ i = 1 k x h i − 1 x − 1 ) .
:::
Now, we have the following.
Proposition 3.4. Let T T T be a finite tree. Then
Z C T ( x ) = x ∣ V ( st ( T ) ) ∣ − ∣ S T ∣ ( ∏ v ∈ S 1 T ∪ S 2 T Z C T v , v ( x ) ) ( ∏ w ∈ S 3 T Z C T w ( x ) ) . Z_C^T(x)=x^{|V(\operatorname{st}(T))|-|S^T|}\left(\prod_{v\in S_1^T\cup S_2^T}Z_C^{T_v,v}(x)\right)\left(\prod_{w\in S_3^T}Z_C^{T_w}(x)\right). Z C T ( x ) = x ∣ V ( st ( T )) ∣ − ∣ S T ∣ v ∈ S 1 T ∪ S 2 T ∏ Z C T v , v ( x ) w ∈ S 3 T ∏ Z C T w ( x ) .
Proof. Let T T T be a finite tree. Then Lemma 3.1 implies that any connected zero forcing set of T T T contains V ( st ( T ) ) V(\operatorname{st}(T)) V ( st ( T )) . Let v ∈ S T v\in S^T v ∈ S T . Then Figure 3 shows that if v ∈ S 1 T ∪ S 2 T v\in S_1^T\cup S_2^T v ∈ S 1 T ∪ S 2 T , then the restriction of any connected zero forcing set of T T T over T v T_v T v is a connected zero forcing set of T v T_v T v , containing v v v , and if v ∈ S 3 T v\in S_3^T v ∈ S 3 T , then the restriction of any connected zero forcing set of T T T over T v T_v T v is a connected zero forcing set of T v T_v T v . In addition, it can be seen that taking a collection of a zero forcing set of T v T_v T v containing v v v , for all v ∈ S 1 T ∪ S 2 T v\in S_1^T\cup S_2^T v ∈ S 1 T ∪ S 2 T , and a collection of a zero forcing set of T w T_w T w for all w ∈ S 3 T w\in S_3^T w ∈ S 3 T , along with all the remaining vertices of st ( T ) \operatorname{st}(T) st ( T ) , forms a connected zero forcing set of T T T . Thus, the connected zero forcing polynomial of T T T is a product of Z C T v , v ( x ) Z_C^{T_v,v}(x) Z C T v , v ( x ) for all v ∈ S 1 T ∪ S 2 T v\in S_1^T\cup S_2^T v ∈ S 1 T ∪ S 2 T , with Z C T w ( x ) Z_C^{T_w}(x) Z C T w ( x ) for all w ∈ S 3 T w\in S_3^T w ∈ S 3 T , multiplied by x ∣ V ( st ( T ) ) ∣ − ∣ S T ∣ x^{|V(\operatorname{st}(T))|-|S^T|} x ∣ V ( st ( T )) ∣ − ∣ S T ∣ . This concludes the proof.
Figure 3. The subtrees T v T_v T v .
Using the above results, we now compute the expression for the connected zero forcing polynomial of a tree.
Theorem 3.5. Let T T T be a tree with n n n vertices and p p p many pendant vertices. Then
Z C T ( x ) = x ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) ( x − 1 ) p × ∏ v ∈ S T ( x + ∑ l ∈ L v x − 1 x d ( l ) − 1 ) . Z_C^T(x)=x^{|V(\operatorname{st}(T))|+p-|S^T|}\frac{\prod_{l\in P(T)}(x^{d(l)}-1)}{(x-1)^p}\times\prod_{v\in S^T}\left(x+\sum_{l\in L_v}\frac{x-1}{x^{d(l)}-1}\right). Z C T ( x ) = x ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ ( x − 1 ) p ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) × v ∈ S T ∏ ( x + l ∈ L v ∑ x d ( l ) − 1 x − 1 ) . Proof. Let T T T be a tree with n n n vertices and p p p many pendant vertices, with Z C ( T ) = k Z_C(T)=k Z C ( T ) = k . Then Proposition 3.4 says that Z C T ( x ) = x ∣ V ( st ( T ) ) ∣ − ∣ S T ∣ ( ∏ u ∈ S 1 T ∪ S 2 T Z C T u , v ( x ) ) ( ∏ w ∈ S 3 T Z C T w ( x ) ) Z_C^T(x)=x^{|V(\operatorname{st}(T))|-|S^T|}\left(\prod_{u\in S^T_1\cup S^T_2}Z_C^{T_u,v}(x)\right)\left(\prod_{w\in S^T_3}Z_C^{T_w}(x)\right) Z C T ( x ) = x ∣ V ( st ( T )) ∣ − ∣ S T ∣ ( ∏ u ∈ S 1 T ∪ S 2 T Z C T u , v ( x ) ) ( ∏ w ∈ S 3 T Z C T w ( x ) ) . So, Lemma 3.2 and 3.3 implies
Z C T ( x ) = x ∣ V ( st ( T ) ) ∣ − ∣ S T ∣ ∏ u ∈ S 1 T x ( 1 + x d ( l ) − 1 x − 1 ) × ∏ v ∈ S 2 T ∪ S 3 T ( x d st ( T ) ( v ) ∏ l ∈ L v ( x d ( l ) − 1 x − 1 ) ( x + ∑ l ∈ L v ( x − 1 x d ( l ) − 1 ) ) ) Z_C^T(x)=x^{|V(\operatorname{st}(T))|-|S^T|}\prod_{u\in S^T_1}x\left(1+\frac{x^{d(l)}-1}{x-1}\right)\times\prod_{v\in S^T_2\cup S^T_3}\left(x^{d_{\operatorname{st}(T)}(v)}\prod_{l\in L_v}\left(\frac{x^{d(l)}-1}{x-1}\right)\left(x+\sum_{l\in L_v}\left(\frac{x-1}{x^{d(l)}-1}\right)\right)\right) Z C T ( x ) = x ∣ V ( st ( T )) ∣ − ∣ S T ∣ u ∈ S 1 T ∏ x ( 1 + x − 1 x d ( l ) − 1 ) × v ∈ S 2 T ∪ S 3 T ∏ ( x d st ( T ) ( v ) l ∈ L v ∏ ( x − 1 x d ( l ) − 1 ) ( x + l ∈ L v ∑ ( x d ( l ) − 1 x − 1 ) ) ) = x ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ ∏ l ∈ P ( T ) ( x d ( l ) − 1 x − 1 ) × ∏ u ∈ S 1 T ( x + x − 1 x d ( l ) − 1 ) × ∏ v ∈ S 2 T ∪ S 3 T ( x + ∑ l ∈ L v ( x − 1 x d ( l ) − 1 ) ) =x^{|V(\operatorname{st}(T))|+p-|S^T|}\prod_{l\in P(T)}\left(\frac{x^{d(l)}-1}{x-1}\right)\times\prod_{u\in S^T_1}\left(x+\frac{x-1}{x^{d(l)}-1}\right)\times\prod_{v\in S^T_2\cup S^T_3}\left(x+\sum_{l\in L_v}\left(\frac{x-1}{x^{d(l)}-1}\right)\right) = x ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ l ∈ P ( T ) ∏ ( x − 1 x d ( l ) − 1 ) × u ∈ S 1 T ∏ ( x + x d ( l ) − 1 x − 1 ) × v ∈ S 2 T ∪ S 3 T ∏ ( x + l ∈ L v ∑ ( x d ( l ) − 1 x − 1 ) ) = x ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) ( x − 1 ) p × ∏ v ∈ S T ( x + ∑ l ∈ L v x − 1 x d ( l ) − 1 ) . =x^{|V(\operatorname{st}(T))|+p-|S^T|}\frac{\prod_{l\in P(T)}(x^{d(l)}-1)}{(x-1)^p}\times\prod_{v\in S^T}\left(x+\sum_{l\in L_v}\frac{x-1}{x^{d(l)}-1}\right). = x ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ ( x − 1 ) p ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) × v ∈ S T ∏ ( x + l ∈ L v ∑ x d ( l ) − 1 x − 1 ) .
Corollary 3.6. Let T T T be a tree with n n n vertices and p p p many pendant vertices. Then Z C ( T ) = ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ Z_C(T)=|V(\operatorname{st}(T))|+p-|S^T| Z C ( T ) = ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ . In addition, we have Z C ( T ; Z C ( T ) ) = ∏ v ∈ S T d st ( T ) ( v ) Z_C(T;Z_C(T))=\prod_{v\in S^T}d_{\operatorname{st}(T)}(v) Z C ( T ; Z C ( T )) = ∏ v ∈ S T d st ( T ) ( v ) .
Proof. From Theorem 3.5 it can be seen that Z C T ( x ) x ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ \frac{Z_C^T(x)}{x^{|V(\operatorname{st}(T))|+p-|S^T|}} x ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ Z C T ( x ) is a polynomial in x x x . Also, it is easy to see that Z C T ( x ) x ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ ∣ x = 0 = ∏ v ∈ S T ∣ L v ∣ = ∏ v ∈ S T d st ( T ) ( v ) \left.\frac{Z_C^T(x)}{x^{|V(\operatorname{st}(T))|+p-|S^T|}}\right|_{x=0}=\prod_{v\in S^T}|L_v|=\prod_{v\in S^T}d_{\operatorname{st}(T)}(v) x ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ Z C T ( x ) x = 0 = ∏ v ∈ S T ∣ L v ∣ = ∏ v ∈ S T d st ( T ) ( v ) , which is nonzero. Hence, the smallest exponent of x x x in Z C T ( x ) Z_C^T(x) Z C T ( x ) with nonzero coefficient is ∣ V ( st ( T ) ) ∣ + p − ∣ S T ∣ |V(\operatorname{st}(T))|+p-|S^T| ∣ V ( st ( T )) ∣ + p − ∣ S T ∣ , and the corresponding coefficient is ∏ v ∈ S T d st ( T ) ( v ) \prod_{v\in S^T}d_{\operatorname{st}(T)}(v) ∏ v ∈ S T d st ( T ) ( v ) . Thus, the result follows.
As a simple consequence of the above result, we have the following.
Corollary 3.7. Let T 1 T_1 T 1 and T 2 T_2 T 2 be two trees with n n n vertices and p p p many pendant vertices. Suppose both T 1 T_1 T 1 and T 2 T_2 T 2 have exactly two vertices v 1 v_1 v 1 , v 1 ′ v_1' v 1 ′ and v 2 v_2 v 2 , v 2 ′ v_2' v 2 ′ respectively, with degree more than 2. Then dist ( v 1 , v 1 ′ ) ≥ dist ( v 2 , v 2 ′ ) \operatorname{dist}(v_1,v_1') \ge\operatorname{dist}(v_2,v_2') dist ( v 1 , v 1 ′ ) ≥ dist ( v 2 , v 2 ′ ) implies Z C ( T 1 ) ≥ Z C ( T 2 ) Z_C(T_1) \ge Z_C(T_2) Z C ( T 1 ) ≥ Z C ( T 2 ) .
The following results are simple applications of results obtained in this section.
Corollary 3.8. Let S 1 , … , 1 , n − p S_{1,\ldots,1,n-p} S 1 , … , 1 , n − p be a starlike graph on n n n vertices and p p p many pendant vertices. Then
Z C S 1 , … , 1 , n − p ( x ) = p x p + p x p + 1 + ⋯ + p x n − 1 + x n . Z_C^{S_{1,\ldots,1,n-p}}(x) = px^p + px^{p+1} + \cdots+ px^{n-1} + x^n. Z C S 1 , … , 1 , n − p ( x ) = p x p + p x p + 1 + ⋯ + p x n − 1 + x n . Proof. Consider the starlike graph S 1 , … , 1 , n − p S_{1,\ldots,1,n-p} S 1 , … , 1 , n − p . Then from Lemma 3.3 , we have
Z C S 1 , … , 1 , n − p ( x ) = x k ( x n − p − 1 ) x − 1 ( x + p − 1 + x − 1 x n − p − 1 ) Z_C^{S_{1,\ldots,1,n-p}}(x) = \frac{x^k(x^{n-p}-1)}{x-1}\left(x+p-1+\frac{x-1}{x^{n-p}-1}\right) Z C S 1 , … , 1 , n − p ( x ) = x − 1 x k ( x n − p − 1 ) ( x + p − 1 + x n − p − 1 x − 1 ) = x k ( p x n − p − 1 x − 1 + x n − p ) = x k ( p + p x + ⋯ + p x n − p − 1 + x n − p ) . = x^k\left(p\frac{x^{n-p}-1}{x-1}+x^{n-p}\right)=x^k\left(p+px+\cdots+px^{n-p-1}+x^{n-p}\right). = x k ( p x − 1 x n − p − 1 + x n − p ) = x k ( p + p x + ⋯ + p x n − p − 1 + x n − p ) . Since degree of Z C S 1 , … , 1 , n − p ( x ) Z_C^{S_{1,\ldots,1,n-p}}(x) Z C S 1 , … , 1 , n − p ( x ) is n n n , we have k = p k=p k = p . Thus, the result holds.
Corollary 3.9. Let 2 ≤ k ≤ p − 2 2 \le k \le p-2 2 ≤ k ≤ p − 2 be a positive integer. Then H k , p − k n ∈ T n , p \mathcal{H}_{k,p-k}^n \in\mathcal{T}_{n,p} H k , p − k n ∈ T n , p and
Z C H k , p − k n ( x ) = k ( p − k ) x n − 2 + p x n − 1 + x n . Z_C^{\mathcal{H}_{k,p-k}^n}(x)=k(p-k)x^{n-2}+px^{n-1}+x^n. Z C H k , p − k n ( x ) = k ( p − k ) x n − 2 + p x n − 1 + x n . Proof. For 2 ≤ k ≤ p − 2 2 \le k \le p-2 2 ≤ k ≤ p − 2 , consider the graph H k , p − k n \mathcal{H}_{k,p-k}^n H k , p − k n . Then from Theorem 3.5 we have
Z C H k , p − k n = x k ( x + k ) ( x + p − k ) = x k + 2 + p x k + 1 + k ( p − k ) x k . Z_C^{\mathcal{H}_{k,p-k}^n}=x^k(x+k)(x+p-k)=x^{k+2}+px^{k+1}+k(p-k)x^k. Z C H k , p − k n = x k ( x + k ) ( x + p − k ) = x k + 2 + p x k + 1 + k ( p − k ) x k . Since degree of Z C H k , p − k n Z_C^{\mathcal{H}_{k,p-k}^n} Z C H k , p − k n is n n n , we have k = n − 2 k=n-2 k = n − 2 . This concludes the proof.
Bounds for the connected zero forcing polynomial of trees
In [5 ] , the authors conjectured that, if we consider the path p n p_n p n with n n n vertices, then for any graph G G G with n n n vertices, Z ( p n ; i ) ≥ Z ( G , i ) Z(p_n;i) \ge Z(G,i) Z ( p n ; i ) ≥ Z ( G , i ) for all i ≥ 1 i \ge1 i ≥ 1 . In [16 ] and [22 ] , the authors included some classes of graphs in support of this conjecture in [5 ] . But for connected zero forcing sets the scenario is totally different. For example, consider the following two graphs S 1 , 1 , 1 S_{1,1,1} S 1 , 1 , 1 and P 4 P_4 P 4 . Then
Z C S 1 , 1 , 1 ( x ) = x 4 + 3 x 3 + 0. x 2 + 0. x Z_C^{S_{1,1,1}}(x)=x^4+3x^3+0.x^2+0.x Z C S 1 , 1 , 1 ( x ) = x 4 + 3 x 3 + 0. x 2 + 0. x
and
Z C P 4 ( x ) = x 4 + 2 x 3 + 3. x 2 + 2 x . Z_C^{P_4}(x)=x^4+2x^3+3.x^2+2x. Z C P 4 ( x ) = x 4 + 2 x 3 + 3. x 2 + 2 x .
Clearly, Z C ( P 4 , 3 ) ≱ Z C ( S 1 , 1 , 1 , 3 ) Z_C(P_4,3)\not\geq Z_C(S_{1,1,1},3) Z C ( P 4 , 3 ) ≥ Z C ( S 1 , 1 , 1 , 3 ) . In fact, the polynomials Z C S 1 , 1 , 1 ( x ) Z_C^{S_{1,1,1}}(x) Z C S 1 , 1 , 1 ( x ) and Z C P 4 ( x ) Z_C^{P_4}(x) Z C P 4 ( x ) are not comparable to each other. Though the polynomial Z ( S 1 , 1 , … , 1 , i ) ≤ Z ( G , i ) Z(S_{1,1,\ldots,1},i)\leq Z(G,i) Z ( S 1 , 1 , … , 1 , i ) ≤ Z ( G , i ) for 1 ≤ i ≤ n 1\leq i\leq n 1 ≤ i ≤ n and for any graph G G G with n n n vertices. But Z C S 1 , 1 , … , 1 ( x ) Z_C^{S_{1,1,\ldots,1}}(x) Z C S 1 , 1 , … , 1 ( x ) and Z C P n ( x ) Z_C^{P_n}(x) Z C P n ( x ) are even not comparable. In fact, if we add a new vertex v v v by an edge with some vertex u u u of some tree T T T , then we have the following Lemma 4.1.
Lemma 4.1. Let T T T be a tree which is not a path, and u ∈ V ( T ) u\in V(T) u ∈ V ( T ) . Let T u ∪ { v } T^u\cup\{v\} T u ∪ { v } denote the new tree formed after attaching a new pendant vertex v v v with u u u by an edge. Then we have the following:
If u ∈ P ( T ) u\in P(T) u ∈ P ( T ) , then Z C ( T u ∪ { v } ; i ) = Z C ( T ; i ) + Z C u ( T ; i − 1 ) Z_C(T^u\cup\{v\};i)=Z_C(T;i)+Z_C^u(T;i-1) Z C ( T u ∪ { v } ; i ) = Z C ( T ; i ) + Z C u ( T ; i − 1 ) , for i > 2 i>2 i > 2 ,
If u ∉ P ( T ) u\notin P(T) u ∈ / P ( T ) , then Z C ( T u ∪ { v } ; i ) = Z C N T [ u ] ( T ; i ) + Z C u ( T ; i − 1 ) Z_C(T^u\cup\{v\};i)=Z_C^{N_T[u]}(T;i)+Z_C^u(T;i-1) Z C ( T u ∪ { v } ; i ) = Z C N T [ u ] ( T ; i ) + Z C u ( T ; i − 1 ) .
Proof. T T T is a tree with n − 1 n-1 n − 1 vertices and p − 1 p-1 p − 1 many pendant vertices, and u ∈ V ( T ) u\in V(T) u ∈ V ( T ) . T u ∪ { v } T^u\cup\{v\} T u ∪ { v } is the new tree formed after attaching a new pendant vertex v v v with u u u by an edge. It is easy to see that any connected zero forcing set of T u ∪ { v } T^u\cup\{v\} T u ∪ { v } containing v v v also contains u u u , since T T T is not a path. In addition, any connected zero forcing set of T u ∪ { v } T^u\cup\{v\} T u ∪ { v } which does not contain v v v is a connected zero forcing set of T T T . Case 1: If u ∈ P ( T ) u \in P(T) u ∈ P ( T ) , then any connected zero forcing set of T T T will also be a connected zero forcing set of T u ∪ { v } T^{u} \cup\{v\} T u ∪ { v } . Thus, we have Z C ( T u ∪ { v } ; i ) = Z C ( T ; i ) + Z C u ( T ; i − 1 ) Z_C(T^{u} \cup\{v\};i) = Z_C(T;i) + Z_C^{u}(T;i-1) Z C ( T u ∪ { v } ; i ) = Z C ( T ; i ) + Z C u ( T ; i − 1 ) , for i > 2 i > 2 i > 2 .
Case 2: If u ∉ P ( T ) u \notin P(T) u ∈ / P ( T ) , for any connected zero forcing set of T u ∪ { v } T^{u} \cup\{v\} T u ∪ { v } which does not contain v v v , the only way v v v can be colored is when v v v gets colored by u u u , and u u u can color v v v only when all the vertices in N T [ u ] N_T[u] N T [ u ] are colored. Since T u ∪ { v } T^{u} \cup\{v\} T u ∪ { v } is a tree, a connected zero forcing set of T u ∪ { v } T^{u} \cup\{v\} T u ∪ { v } can induce coloring on all the vertices in N T [ u ] N_T[u] N T [ u ] only when the connected zero forcing set itself contains the set N T [ u ] N_T[u] N T [ u ] . On the other hand, it is easy to see that all the connected zero forcing set of T T T which contains N T [ u ] N_T[u] N T [ u ] are also connected zero forcing sets of T u ∪ { v } T^{u} \cup\{v\} T u ∪ { v } . Thus, we have Z C ( T u ∪ { v } ; i ) = Z C N T [ u ] ( T ; i ) + Z C u ( T ; i − 1 ) Z_C(T^{u} \cup\{v\};i) = Z_C^{N_T[u]}(T;i) + Z_C^{u}(T;i-1) Z C ( T u ∪ { v } ; i ) = Z C N T [ u ] ( T ; i ) + Z C u ( T ; i − 1 ) .
From the above discussion, it seems that there is no relation between the coefficients of the connected zero forcing polynomials of the trees. But that is not the scenario if we fix the number of pendant vertices of the trees. In fact, when the number of pendant vertices p p p is fix, then for trees in T n , p \mathcal{T}_{n,p} T n , p , we prove interesting results in Sections 4.1 and 4.2. Before proceeding further, let us clarify some terminology. When we say that a tree T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p is minimal or maximal , we mean that its connected zero forcing polynomial is coefficientwise minimal or maximal, respectively.
Lower bounds for the connected zero forcing polynomial of trees
In this section, we establish several important and interesting results concerning the connected zero forcing polynomials of trees, namely, Proposition 4.6 and Proposition 4.7. In particular, we determine lower bounds for the connected zero forcing polynomials of trees belonging to T n , p \mathcal{T}_{n,p} T n , p . In these two propositions, we show that although the connected zero forcing polynomials of the trees S 1 , 1 , … , 1 , n − p S_{1,1,\ldots,1,n-p} S 1 , 1 , … , 1 , n − p and H 2 , p − 2 n \mathcal{H}^{n}_{2,p-2} H 2 , p − 2 n in T n , p \mathcal{T}_{n,p} T n , p are incomparable, every other tree T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p satisfies
Z C T ( x ) ≥ Z C S 1 , 1 , … , 1 , n − p ( x ) Z_C^T(x) \ge Z_C^{S_{1,1,\ldots,1,n-p}}(x) Z C T ( x ) ≥ Z C S 1 , 1 , … , 1 , n − p ( x )
and
Z C T ( x ) ≥ Z C H 2 , p − 2 n ( x ) . Z_C^T(x) \ge Z_C^{\mathcal{H}^{n}_{2,p-2}}(x). Z C T ( x ) ≥ Z C H 2 , p − 2 n ( x ) .
Thus, the two trees S 1 , 1 , … , 1 , n − p S_{1,1,\ldots,1,n-p} S 1 , 1 , … , 1 , n − p and H 2 , p − 2 n \mathcal{H}^{n}_{2,p-2} H 2 , p − 2 n are precisely the two minimal elements of T n , p \mathcal{T}_{n,p} T n , p with respect to the ordering induced by their connected zero forcing polynomials.
Lemma 4.2. Let T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p . Then we have the following:
Z C ( T ; n − 1 ) = p Z_C(T;n-1) = p Z C ( T ; n − 1 ) = p ,
If ∣ S T ∣ ≥ 2 |S^T| \ge2 ∣ S T ∣ ≥ 2 , then there exists an integer m m m with 2 ≤ m ≤ p − 2 2 \le m \le p-2 2 ≤ m ≤ p − 2 , such that Z C ( T ; n − 2 ) ≥ m ( p − m ) Z_C(T;n-2) \ge m(p-m) Z C ( T ; n − 2 ) ≥ m ( p − m ) .
Proof. Consider the reciprocal of the polynomial Z C T ( x ) Z_C^T(x) Z C T ( x ) to be Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) . Then theorem 3.5 and some simple calculations yield
Z C T ∗ ( x ) = ∏ l ∈ P ( T ) ( x d ( l ) − 1 x − 1 ) × ∏ v ∈ S T ( 1 + ∑ l ∈ L v ( x d ( l ) x − 1 x d ( l ) − 1 ) ) . Z_C^{T^*}(x) = \prod_{l \in P(T)} \left(\frac{x^{d(l)}-1}{x-1}\right) \times\prod_{v \in S^T} \left(1+\sum_{l \in L_v} \left(x^{d(l)}\frac{x-1}{x^{d(l)}-1}\right)\right). Z C T ∗ ( x ) = l ∈ P ( T ) ∏ ( x − 1 x d ( l ) − 1 ) × v ∈ S T ∏ ( 1 + l ∈ L v ∑ ( x d ( l ) x d ( l ) − 1 x − 1 ) ) .
So, Z C ( T ; n − 1 ) Z_C(T;n-1) Z C ( T ; n − 1 ) is the coefficient of x x x in Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) , and Z C ( T ; n − 2 ) Z_C(T;n-2) Z C ( T ; n − 2 ) is the coefficient of x 2 x^2 x 2 in Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) .
It can be calculated that d d x Z C T ∗ ( x ) ∣ x = 0 = ∑ l ∈ P ( T ) , d ( l ) = 1 1 + ∑ l ∈ P ( T ) , d ( l ) ≥ 2 1 = p \left.\frac{d}{dx}Z_C^{T^*}(x)\right|_{x=0} = \sum_{\substack{l\in P(T),\\d(l)=1}} 1 + \sum_{\substack{l\in P(T),\\d(l)\ge2}} 1 = p d x d Z C T ∗ ( x ) x = 0 = ∑ l ∈ P ( T ) , d ( l ) = 1 1 + ∑ l ∈ P ( T ) , d ( l ) ≥ 2 1 = p . So, the coefficient of x x x in Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) , i.e. Z C ( T ; n − 1 ) = p Z_C(T;n-1)=p Z C ( T ; n − 1 ) = p .
If ∣ S 2 T ∣ ≥ 2 |S_2^T| \ge2 ∣ S 2 T ∣ ≥ 2 , it is easy to see that ∣ S 2 T ∣ ≥ 2 |S_2^T| \ge2 ∣ S 2 T ∣ ≥ 2 . Choose u ∈ S 2 T u \in S_2^T u ∈ S 2 T . Clearly 2 ≤ ∣ L u ∣ ≤ p − 2 2 \le|L_u| \le p-2 2 ≤ ∣ L u ∣ ≤ p − 2 . Now,
Z C T ∗ ( x ) = ( ∏ l ∈ L u x d ( l ) − 1 x − 1 × ( 1 + ∑ l ∈ L u ( x d ( l ) x − 1 x d ( l ) − 1 ) ) ) × Z_C^{T^*}(x)=\left(\prod_{l\in L_u}\frac{x^{d(l)}-1}{x-1}\times\left(1+\sum_{l\in L_u}\left(x^{d(l)}\frac{x-1}{x^{d(l)}-1}\right)\right)\right)\times Z C T ∗ ( x ) = ( l ∈ L u ∏ x − 1 x d ( l ) − 1 × ( 1 + l ∈ L u ∑ ( x d ( l ) x d ( l ) − 1 x − 1 ) ) ) ×
( ∏ l ∈ P ( T ) ∖ L u x d ( l ) − 1 x − 1 × ∏ v ∈ S 2 T ∖ { u } ( 1 + ∑ l ∈ L v ( x d ( l ) x − 1 x d ( l ) − 1 ) ) ) . \left(\prod_{l\in P(T)\setminus L_u}\frac{x^{d(l)}-1}{x-1}\times\prod_{v\in S_2^T\setminus\{u\}}\left(1+\sum_{l\in L_v}\left(x^{d(l)}\frac{x-1}{x^{d(l)}-1}\right)\right)\right). l ∈ P ( T ) ∖ L u ∏ x − 1 x d ( l ) − 1 × v ∈ S 2 T ∖ { u } ∏ ( 1 + l ∈ L v ∑ ( x d ( l ) x d ( l ) − 1 x − 1 ) ) .
Then the previous case yields that the coefficient of x x x in ∏ l ∈ L u ( x d ( l ) − 1 x − 1 ) × ( 1 + ∑ l ∈ L u ( x d ( l ) x − 1 x d ( l ) − 1 ) ) \prod_{l\in L_u}\left(\frac{x^{d(l)}-1}{x-1}\right)\times\left(1+\sum_{l\in L_u}\left(x^{d(l)}\frac{x-1}{x^{d(l)}-1}\right)\right) ∏ l ∈ L u ( x − 1 x d ( l ) − 1 ) × ( 1 + ∑ l ∈ L u ( x d ( l ) x d ( l ) − 1 x − 1 ) ) is ∣ L u ∣ |L_u| ∣ L u ∣ and the coefficient of x x x in ∏ l ∈ P ( T ) ∖ L u ( x d ( l ) − 1 x − 1 ) × ∏ v ∈ S 2 T ∖ { u } ( 1 + ∑ l ∈ L v ( x d ( l ) x − 1 x d ( l ) − 1 ) ) \prod_{l\in P(T)\setminus L_u}\left(\frac{x^{d(l)}-1}{x-1}\right)\times\prod_{v\in S_2^T\setminus\{u\}}\left(1+\sum_{l\in L_v}\left(x^{d(l)}\frac{x-1}{x^{d(l)}-1}\right)\right) ∏ l ∈ P ( T ) ∖ L u ( x − 1 x d ( l ) − 1 ) × ∏ v ∈ S 2 T ∖ { u } ( 1 + ∑ l ∈ L v ( x d ( l ) x d ( l ) − 1 x − 1 ) ) is p − ∣ L u ∣ p-|L_u| p − ∣ L u ∣ .
Hence, we have the coefficient of x 2 x^2 x 2 in Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) is greater than or equal to ∣ L u ∣ ( p − ∣ L u ∣ ) |L_u|(p-|L_u|) ∣ L u ∣ ( p − ∣ L u ∣ ) , where 2 ≤ ∣ L u ∣ ≤ p − 2 2 \le|L_u| \le p-2 2 ≤ ∣ L u ∣ ≤ p − 2 . This concludes the proof.
The following observation is useful.
Observation 4.3. Let H = { h 1 , h 2 , … , h k } H=\{h_1,h_2,\ldots,h_k\} H = { h 1 , h 2 , … , h k } be a multiset of k k k positive integers. Consider the polynomial g H ( x ) = ∏ i = 1 k ∑ j = 0 h i x j g_H(x)=\prod_{i=1}^{k}\sum_{j=0}^{h_i}x^j g H ( x ) = ∏ i = 1 k ∑ j = 0 h i x j . Then the coefficient of x l x^l x l in g ( x ) g(x) g ( x ) is bounded below by k k k , for 1 ≤ l ≤ ∑ i = 1 k h i − 1 1\le l\le\sum_{i=1}^{k}h_i-1 1 ≤ l ≤ ∑ i = 1 k h i − 1 .
Proof. The proof proceeds by induction on k k k . Clearly, the result is true for k = 1 k=1 k = 1 . Let the result be true for k = m − 1 k=m-1 k = m − 1 for a positive integer m ≥ 2 m\ge2 m ≥ 2 . Consider the multiset H = { h 1 , h 2 , … , h m } H=\{h_1,h_2,\ldots,h_m\} H = { h 1 , h 2 , … , h m } of m m m positive integers. Define h = h 1 + h 2 + ⋯ + h m − 1 h=h_1+h_2+\cdots+h_{m-1} h = h 1 + h 2 + ⋯ + h m − 1 . Then
g H ( x ) = ( ∏ i = 1 m − 1 ∑ j = 0 h i x j ) ( ∑ j = 0 h m x j ) . g_H(x)=\left(\prod_{i=1}^{m-1}\sum_{j=0}^{h_i}x^j\right)\left(\sum_{j=0}^{h_m}x^j\right). g H ( x ) = ( i = 1 ∏ m − 1 j = 0 ∑ h i x j ) ( j = 0 ∑ h m x j ) .
Let ∏ i = 1 m − 1 ∑ j = 0 h i x j = ∑ i = 0 h c i x i \prod_{i=1}^{m-1}\sum_{j=0}^{h_i}x^j=\sum_{i=0}^{h}c_i x^i ∏ i = 1 m − 1 ∑ j = 0 h i x j = ∑ i = 0 h c i x i , where c 0 = 1 = c h 1 + h 2 + ⋯ + h m − 1 c_0=1=c_{h_1+h_2+\cdots+h_{m-1}} c 0 = 1 = c h 1 + h 2 + ⋯ + h m − 1 and c i ≥ m − 1 c_i\ge m-1 c i ≥ m − 1 for 1 ≤ i ≤ h − 1 1\le i\le h-1 1 ≤ i ≤ h − 1 . Then coefficient of x l x^l x l in g H ( x ) g_H(x) g H ( x ) is ∑ i + j = l , 0 ≤ i ≤ h , 0 ≤ j ≤ h k c i \sum_{\substack{i+j=l,\\0\le i\le h,\\0\le j\le h_k}}c_i ∑ i + j = l , 0 ≤ i ≤ h , 0 ≤ j ≤ h k c i . Now, for 1 ≤ l ≤ h + h k − 1 1\le l\le h+h_k-1 1 ≤ l ≤ h + h k − 1 we can choose integers i 1 , j 1 i_1,j_1 i 1 , j 1 such that 0 ≤ i 1 < i 1 + 1 ≤ h 0\le i_1<i_1+1\le h 0 ≤ i 1 < i 1 + 1 ≤ h , 0 ≤ j 1 − 1 < j 1 ≤ h k 0\le j_1-1<j_1\le h_k 0 ≤ j 1 − 1 < j 1 ≤ h k and i 1 + j 1 = l i_1+j_1=l i 1 + j 1 = l . So, ∑ i + j = l , 0 ≤ i ≤ h , 0 ≤ j ≤ h k c i ≥ c i 1 + c i 1 + 1 ≥ m \sum_{\substack{i+j=l,\\0\le i\le h,\\0\le j\le h_k}}c_i\ge c_{i_1}+c_{i_1+1}\ge m ∑ i + j = l , 0 ≤ i ≤ h , 0 ≤ j ≤ h k c i ≥ c i 1 + c i 1 + 1 ≥ m .
Hence the statement holds for k = m k=m k = m . This concludes the proof.
We will now find a lower bound for the coefficients of the connected zero forcing polynomial of any T ∈ T n , p T\in\mathcal{T}_{n,p} T ∈ T n , p . Before going into the main result, we will first explore such lower bounds for Z C T v , v ( x ) Z_C^{T_v,v}(x) Z C T v , v ( x ) , when v ∈ S 1 T ∪ S 2 T v\in S_1^T\cup S_2^T v ∈ S 1 T ∪ S 2 T , and for Z C T v ( x ) Z_C^{T_v}(x) Z C T v ( x ) , when v ∈ S 3 T v\in S_3^T v ∈ S 3 T . Note that for v ∈ S 1 T v\in S_1^T v ∈ S 1 T , Z C T v , v ( x ) Z_C^{T_v,v}(x) Z C T v , v ( x ) is of the form x + x 2 + ⋯ + x k + 1 x+x^2+\cdots+x^{k+1} x + x 2 + ⋯ + x k + 1 , where k k k is the length of the path T v T_v T v . Hence, each nonzero coefficient is bounded below by the number of pendant vertices of T T T , which T v T_v T v contains. The next result shows that such phenomena also holds for v ∈ S 2 T v\in S_2^T v ∈ S 2 T or and v ∈ S 3 T v\in S_3^T v ∈ S 3 T .
Lemma 4.4. Let T T T be a tree on n n n vertices, such that either T T T is a path of length more than 1 1 1 with an internal vertex v v v , or a starlike graph. Then we have the following,
If T T T is a path, then each nonzero coefficient of Z C T , v ( x ) Z_C^{T,v}(x) Z C T , v ( x ) other than the first and the last one, is bounded below by $2.
Proof. Let T T T be either a path with an internal vertex v v v or a starlike graph. Further, if T T T is a starlike graph, we denote the central vertex of T T T by v v v . In either cases, ∂ ( l ) \partial(l) ∂ ( l ) will denote the distance between l l l and v v v , for an l ∈ P ( T ) l \in P(T) l ∈ P ( T ) . Then, Lemma 3.2 implies that
Z C T , v ( x ) = x 2 ∏ l ∈ P ( T ) ( x ∂ ( l ) − 1 ) ( x − 1 ) 2 ( x + ∑ l ∈ P ( T ) x − 1 x ∂ ( l ) − 1 ) , Z_C^{T,v}(x) = x^2 \frac{\prod_{l \in P(T)} \left(x^{\partial(l)-1}\right)}{(x-1)^2}\left(x+\sum_{l \in P(T)}\frac{x-1}{x^{\partial(l)-1}}\right), Z C T , v ( x ) = x 2 ( x − 1 ) 2 ∏ l ∈ P ( T ) ( x ∂ ( l ) − 1 ) x + l ∈ P ( T ) ∑ x ∂ ( l ) − 1 x − 1 ,
when T T T is a path, and Lemma 3.3 implies that
Z C T ( x ) = x p ( T ) ( ∏ l ∈ P ( T ) x ∂ ( l ) − 1 x − 1 ) ( x + ∑ l ∈ P ( T ) x − 1 x ∂ ( l ) − 1 ) , Z_C^T(x) = x^{p(T)}\left(\prod_{l \in P(T)}\frac{x^{\partial(l)-1}}{x-1}\right)\left(x+\sum_{l \in P(T)}\frac{x-1}{x^{\partial(l)-1}}\right), Z C T ( x ) = x p ( T ) l ∈ P ( T ) ∏ x − 1 x ∂ ( l ) − 1 x + l ∈ P ( T ) ∑ x ∂ ( l ) − 1 x − 1 ,
when T T T is starlike. Now, a few steps of simple calculations yield that in both the cases, the polynomial is of the form
x p ( T ) ( x ∏ l ∈ P ( T ) ∑ i = 0 ∂ ( l ) − 1 x i + ∑ l ∈ P ( T ) ( ∏ l ′ ∈ P ( T ) , l ′ ≠ l ∑ i = 0 ∂ ( l ′ ) − 1 x i ) ) . x^{p(T)}\left(x\prod_{l \in P(T)}\sum_{i=0}^{\partial(l)-1}x^i+\sum_{l \in P(T)}\left(\prod_{\substack{l' \in P(T),\\ l'\ne l}}\sum_{i=0}^{\partial(l')-1}x^i\right)\right). x p ( T ) x l ∈ P ( T ) ∏ i = 0 ∑ ∂ ( l ) − 1 x i + l ∈ P ( T ) ∑ l ′ ∈ P ( T ) , l ′ = l ∏ i = 0 ∑ ∂ ( l ′ ) − 1 x i .
Consider the polynomial
f ( x ) : = x ∏ l ∈ P ( T ) ∑ i = 0 ∂ ( l ) − 1 x i + ∑ l ∈ P ( T ) ( ∏ l ′ ∈ P ( T ) , l ′ ≠ l ∑ i = 0 ∂ ( l ′ ) − 1 x i ) . f(x):=x\prod_{l \in P(T)}\sum_{i=0}^{\partial(l)-1}x^i+\sum_{l \in P(T)}\left(\prod_{\substack{l' \in P(T),\\ l'\ne l}}\sum_{i=0}^{\partial(l')-1}x^i\right). f ( x ) := x l ∈ P ( T ) ∏ i = 0 ∑ ∂ ( l ) − 1 x i + l ∈ P ( T ) ∑ l ′ ∈ P ( T ) , l ′ = l ∏ i = 0 ∑ ∂ ( l ′ ) − 1 x i .
We will show that each nonzero coefficient of f ( x ) f(x) f ( x ) is bounded below by p ( T ) p(T) p ( T ) .
Define P 1 ( T ) : = { l ∈ P ( T ) ∣ ∂ ( l ) = 1 } P_1(T):=\{l\in P(T)\mid\partial(l)=1\} P 1 ( T ) := { l ∈ P ( T ) ∣ ∂ ( l ) = 1 } , and P 2 ( T ) : = { l ∈ P ( T ) ∣ ∂ ( l ) ≥ 2 } P_2(T):=\{l\in P(T)\mid\partial(l)\ge2\} P 2 ( T ) := { l ∈ P ( T ) ∣ ∂ ( l ) ≥ 2 } . So, P ( T ) = P 1 ( T ) ⊔ P 2 ( T ) P(T)=P_1(T)\sqcup P_2(T) P ( T ) = P 1 ( T ) ⊔ P 2 ( T ) . Then
f ( x ) = ( x + ∣ P 1 ( T ) ∣ ) ( ∏ l ∈ P 2 ( T ) ∑ i = 0 ∂ ( l ) − 1 x i ) + ∑ l ∈ P 2 ( T ) ( ∏ l ′ ∈ P 2 ( T ) , l ′ ≠ l ∑ i = 0 ∂ ( l ′ ) − 1 x i ) . f(x)=(x+|P_1(T)|)\left(\prod_{l\in P_2(T)}\sum_{i=0}^{\partial(l)-1}x^i\right)+\sum_{l\in P_2(T)}\left(\prod_{\substack{l'\in P_2(T),\\l'\ne l}}\sum_{i=0}^{\partial(l')-1}x^i\right). f ( x ) = ( x + ∣ P 1 ( T ) ∣ ) l ∈ P 2 ( T ) ∏ i = 0 ∑ ∂ ( l ) − 1 x i + l ∈ P 2 ( T ) ∑ l ′ ∈ P 2 ( T ) , l ′ = l ∏ i = 0 ∑ ∂ ( l ′ ) − 1 x i .
Let the polynomial ∏ l ∈ P 2 ( T ) ∑ i = 0 ∂ ( l ) − 1 x i \prod_{l\in P_2(T)}\sum_{i=0}^{\partial(l)-1}x^i ∏ l ∈ P 2 ( T ) ∑ i = 0 ∂ ( l ) − 1 x i be of the form ∑ j = 0 k c j x j \sum_{j=0}^{k}c_jx^j ∑ j = 0 k c j x j , where k = ∑ l ∈ P 2 ( T ) ( ∂ ( l ) − 1 ) k=\sum_{l\in P_2(T)}(\partial(l)-1) k = ∑ l ∈ P 2 ( T ) ( ∂ ( l ) − 1 ) . Then
( x + ∣ P 1 ( T ) ∣ ) ( ∏ l ∈ P 2 ( T ) ∑ i = 0 ∂ ( l ) − 1 x i ) = ∣ P 1 ( T ) ∣ + ∑ i = 1 k ( ∣ P 1 ( T ) ∣ c i + c i − 1 ) x i + x k + 1 . (x+|P_1(T)|)\left(\prod_{l\in P_2(T)}\sum_{i=0}^{\partial(l)-1}x^i\right)=|P_1(T)|+\sum_{i=1}^{k}(|P_1(T)|c_i+c_{i-1})x^i+x^{k+1}. ( x + ∣ P 1 ( T ) ∣ ) l ∈ P 2 ( T ) ∏ i = 0 ∑ ∂ ( l ) − 1 x i = ∣ P 1 ( T ) ∣ + i = 1 ∑ k ( ∣ P 1 ( T ) ∣ c i + c i − 1 ) x i + x k + 1 .
Clearly ∂ ( l ) − 1 \partial(l)-1 ∂ ( l ) − 1 are all positive integers for all l ∈ P 2 ( T ) l\in P_2(T) l ∈ P 2 ( T ) . So we have c 0 = 1 = c k c_0=1=c_k c 0 = 1 = c k , and by Observation 4.3 we have c i ≥ ∣ P 2 ( T ) ∣ c_i\ge|P_2(T)| c i ≥ ∣ P 2 ( T ) ∣ , for 1 ≤ i ≤ k − 1 1\le i\le k-1 1 ≤ i ≤ k − 1 . Hence, ∣ P 1 ( T ) ∣ c i + c i − 1 ≥ ∣ P 1 ( T ) ∣ + ∣ P 2 ( T ) ∣ = ∣ P ( T ) ∣ |P_1(T)|c_i+c_{i-1}\ge|P_1(T)|+|P_2(T)|=|P(T)| ∣ P 1 ( T ) ∣ c i + c i − 1 ≥ ∣ P 1 ( T ) ∣ + ∣ P 2 ( T ) ∣ = ∣ P ( T ) ∣ , for 2 ≤ i ≤ k 2\le i\le k 2 ≤ i ≤ k . If ∣ P 1 ( T ) ∣ ≥ 1 |P_1(T)|\ge1 ∣ P 1 ( T ) ∣ ≥ 1 , then ∣ P 1 ( T ) ∣ c 1 + c 0 ≥ ∣ P 1 ( T ) ∣ + ∣ P 2 ( T ) ∣ = ∣ P ( T ) ∣ |P_1(T)|c_1+c_0\ge|P_1(T)|+|P_2(T)|=|P(T)| ∣ P 1 ( T ) ∣ c 1 + c 0 ≥ ∣ P 1 ( T ) ∣ + ∣ P 2 ( T ) ∣ = ∣ P ( T ) ∣ , since c 0 = 1 c_0=1 c 0 = 1 and c 1 ≥ ∣ P 2 ( T ) ∣ c_1\ge|P_2(T)| c 1 ≥ ∣ P 2 ( T ) ∣ . If ∣ P 1 ( T ) ∣ = 0 |P_1(T)|=0 ∣ P 1 ( T ) ∣ = 0 , then P 2 ( T ) = P ( T ) P_2(T)=P(T) P 2 ( T ) = P ( T ) . Hence, the coefficient of x x x in ∑ l ∈ P ( T ) ( ∏ l ′ ∈ P ( T ) , l ′ ≠ l ∑ i = 0 ∂ ( l ′ ) − 1 x i ) \sum_{l\in P(T)}\left(\prod_{\substack{l'\in P(T),\\l'\ne l}}\sum_{i=0}^{\partial(l')-1}x^i\right) ∑ l ∈ P ( T ) ( ∏ l ′ ∈ P ( T ) , l ′ = l ∑ i = 0 ∂ ( l ′ ) − 1 x i ) is ∣ P ( T ) ∣ ( ∣ P ( T ) ∣ − 1 ) ≥ ∣ P ( T ) ∣ |P(T)|(|P(T)|-1)\ge|P(T)| ∣ P ( T ) ∣ ( ∣ P ( T ) ∣ − 1 ) ≥ ∣ P ( T ) ∣ . Hence, the coefficient of x j x^j x j in f ( x ) f(x) f ( x ) is greater than or equal to p ( T ) p(T) p ( T ) , for 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k .
Also, the following holds.
Lemma 4.5. Let f 1 ( x ) = ∑ i = 0 m c i x i f_1(x)=\sum_{i=0}^{m}c_ix^i f 1 ( x ) = ∑ i = 0 m c i x i and f 2 ( x ) = ∑ j = 0 n d j x j f_2(x)=\sum_{j=0}^{n}d_jx^j f 2 ( x ) = ∑ j = 0 n d j x j , m , n ≥ 2 m,n\ge2 m , n ≥ 2 be two polynomials with positive integral coefficients, such that c i ≥ a c_i\ge a c i ≥ a and d j ≥ b d_j\ge b d j ≥ b , for 1 ≤ i ≤ m − 1 1\le i\le m-1 1 ≤ i ≤ m − 1 , 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 . If f 1 ( x ) f 2 ( x ) = ∑ i = 0 m + n l i x i f_1(x)f_2(x)=\sum_{i=0}^{m+n}l_ix^i f 1 ( x ) f 2 ( x ) = ∑ i = 0 m + n l i x i , then l i ≥ a + b l_i\ge a+b l i ≥ a + b for 1 ≤ i ≤ m + n − 1 1\le i\le m+n-1 1 ≤ i ≤ m + n − 1 .
Proof. f 1 ( x ) = ∑ i = 0 m c i x i f_1(x)=\sum_{i=0}^{m}c_ix^i f 1 ( x ) = ∑ i = 0 m c i x i and f 2 ( x ) = ∑ j = 0 n d j x j f_2(x)=\sum_{j=0}^{n}d_jx^j f 2 ( x ) = ∑ j = 0 n d j x j are two polynomials with positive integral coefficients, such that c i ≥ a c_i\ge a c i ≥ a and d j ≥ b d_j\ge b d j ≥ b , for 1 ≤ i ≤ m − 1 1\le i\le m-1 1 ≤ i ≤ m − 1 , 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 . Since f 1 ( x ) f 2 ( x ) = ∑ i = 0 m + n l i x i f_1(x)f_2(x)=\sum_{i=0}^{m+n}l_ix^i f 1 ( x ) f 2 ( x ) = ∑ i = 0 m + n l i x i , we have
l i = ∑ h + k = i 0 ≤ h ≤ m 0 ≤ k ≤ n c h d k , l_i=\sum_{\substack{h+k=i\\0\le h\le m\\0\le k\le n}}c_hd_k, l i = h + k = i 0 ≤ h ≤ m 0 ≤ k ≤ n ∑ c h d k ,
for 0 ≤ i ≤ m + n 0\le i\le m+n 0 ≤ i ≤ m + n . Now, for 1 ≤ l ≤ m + n − 1 1\le l\le m+n-1 1 ≤ l ≤ m + n − 1 we can choose integers h ′ , k ′ h',k' h ′ , k ′ such that 0 ≤ h ′ < h ′ + 1 ≤ m 0\le h'<h'+1\le m 0 ≤ h ′ < h ′ + 1 ≤ m , 0 ≤ k ′ − 1 < k ′ ≤ n 0\le k'-1<k'\le n 0 ≤ k ′ − 1 < k ′ ≤ n and h ′ + k ′ = l h'+k'=l h ′ + k ′ = l . So, we have
l i = ∑ h + k = i 0 ≤ h ≤ m 0 ≤ k ≤ n c h d k ≥ c h ′ d k ′ + c h ′ + 1 d k ′ − 1 ≥ a + b . l_i=\sum_{\substack{h+k=i\\0\le h\le m\\0\le k\le n}}c_hd_k\ge c_{h'}d_{k'}+c_{h'+1}d_{k'-1}\ge a+b. l i = h + k = i 0 ≤ h ≤ m 0 ≤ k ≤ n ∑ c h d k ≥ c h ′ d k ′ + c h ′ + 1 d k ′ − 1 ≥ a + b .
Thus, the result holds.
Note that the above result still holds if one or both of the polynomials are of the form 1 + x 1+x 1 + x . So, as a consequence of the above two results, we now arrive at the following lower bound for the coefficients of the connected zero forcing polynomial of trees.
Proposition 4.6. Let T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p with Z C ( T ) = k Z_C(T)=k Z C ( T ) = k . Then Z C ( T ; i ) ≥ Z C ( S 1 , 1 , … , n − p ; i ) = p Z_C(T;i) \ge Z_C(S_{1,1,\ldots,n-p};i)=p Z C ( T ; i ) ≥ Z C ( S 1 , 1 , … , n − p ; i ) = p for k < i < n k<i<n k < i < n .
Proposition 4.7. Let n , p ∈ N n,p \in\mathbb{N} n , p ∈ N with p ≥ 4 p \ge4 p ≥ 4 , n ≥ p + 2 n \ge p+2 n ≥ p + 2 , and T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p such that T ≠ S 1 , … , 1 , n − p T \ne S_{1,\ldots,1,n-p} T = S 1 , … , 1 , n − p . Then Z C ( T ; i ) ≥ Z C ( H 2 , p − 2 n ; i ) Z_C(T;i) \ge Z_C(H^n_{2,p-2};i) Z C ( T ; i ) ≥ Z C ( H 2 , p − 2 n ; i ) for all i ∈ [ n ] i \in[n] i ∈ [ n ] .
Proof. Let n , p ∈ N n,p \in\mathbb{N} n , p ∈ N with p ≥ 4 p \ge4 p ≥ 4 and n ≥ p + 2 n \ge p+2 n ≥ p + 2 . Let T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p such that T ≠ S 1 , … , 1 , n − p T \ne S_{1,\ldots,1,n-p} T = S 1 , … , 1 , n − p . When S T = { u } S^T=\{u\} S T = { u } we have
Z C T ∗ ( x ) = ∏ l ∈ P ( T ) ( x d ( l ) − 1 x − 1 ) + ∑ l ∈ L v x d ( l ) ∏ l ′ ∈ P ( T ) ∖ { l } ( x d ( l ′ ) − 1 x − 1 ) . Z_C^{T^*}(x)=\prod_{l\in P(T)}\left(\frac{x^{d(l)}-1}{x-1}\right)+\sum_{l\in L_v}x^{d(l)}\prod_{l'\in P(T)\setminus\{l\}}\left(\frac{x^{d(l')}-1}{x-1}\right). Z C T ∗ ( x ) = l ∈ P ( T ) ∏ ( x − 1 x d ( l ) − 1 ) + l ∈ L v ∑ x d ( l ) l ′ ∈ P ( T ) ∖ { l } ∏ ( x − 1 x d ( l ′ ) − 1 ) .
Let P ( T ) 1 : = { l ∈ P ( T ) ∣ d ( l ) = 1 } P(T)_1:=\{l\in P(T)\mid d(l)=1\} P ( T ) 1 := { l ∈ P ( T ) ∣ d ( l ) = 1 } , P ( T ) 2 : = { l ∈ P ( T ) ∣ d ( l ) = 2 } P(T)_2:=\{l\in P(T)\mid d(l)=2\} P ( T ) 2 := { l ∈ P ( T ) ∣ d ( l ) = 2 } , P ( T ) 3 : = { l ∈ P ( T ) ∣ d ( l ) ≥ 3 } P(T)_3:=\{l\in P(T)\mid d(l)\ge3\} P ( T ) 3 := { l ∈ P ( T ) ∣ d ( l ) ≥ 3 } , and ∣ P ( T ) 2 ∣ + ∣ P ( T ) 3 ∣ = t |P(T)_2|+|P(T)_3|=t ∣ P ( T ) 2 ∣ + ∣ P ( T ) 3 ∣ = t . Clearly, ∣ P ( T ) 1 ∣ + t = p |P(T)_1|+t=p ∣ P ( T ) 1 ∣ + t = p and t ≥ 2 t\ge2 t ≥ 2 as T ≠ S 1 , … , 1 , n − p T\ne S_{1,\ldots,1,n-p} T = S 1 , … , 1 , n − p . Then
Z C T ∗ ( x ) = ( 1 + ∣ P ( T ) 1 ∣ x ) ∏ l ∈ P ( T ) 2 ∪ P ( T ) 3 ( x d ( l ) − 1 x − 1 ) + x 2 ∑ l ∈ P ( T ) 2 ∏ l ′ ∈ P ( T ) 2 ∪ P ( T ) 3 , l ′ ≠ l ( x d ( l ′ ) − 1 x − 1 ) + ∑ l ∈ P ( T ) 3 x d ( l ) ∏ l ′ ∈ P ( T ) 2 ∪ P ( T ) 3 , l ′ ≠ l ( x d ( l ′ ) − 1 x − 1 ) . \begin{aligned}
Z_C^{T^*}(x)={}&(1+|P(T)_1|x)\prod_{l\in P(T)_2\cup P(T)_3}\left(\frac{x^{d(l)}-1}{x-1}\right)\\
&+x^2\sum_{l\in P(T)_2}\prod_{\substack{l'\in P(T)_2\cup P(T)_3,\\l'\ne l}}\left(\frac{x^{d(l')}-1}{x-1}\right)\\
&+\sum_{l\in P(T)_3}x^{d(l)}\prod_{\substack{l'\in P(T)_2\cup P(T)_3,\\l'\ne l}}\left(\frac{x^{d(l')}-1}{x-1}\right).
\end{aligned} Z C T ∗ ( x ) = ( 1 + ∣ P ( T ) 1 ∣ x ) l ∈ P ( T ) 2 ∪ P ( T ) 3 ∏ ( x − 1 x d ( l ) − 1 ) + x 2 l ∈ P ( T ) 2 ∑ l ′ ∈ P ( T ) 2 ∪ P ( T ) 3 , l ′ = l ∏ ( x − 1 x d ( l ′ ) − 1 ) + l ∈ P ( T ) 3 ∑ x d ( l ) l ′ ∈ P ( T ) 2 ∪ P ( T ) 3 , l ′ = l ∏ ( x − 1 x d ( l ′ ) − 1 ) .
It is easy to calculate that the coefficient of x 2 x^2 x 2 in Z C T ∗ ( x ) Z_C^{T^*}(x) Z C T ∗ ( x ) is t ( ∣ P ( T ) 1 ∣ + 1 ) + ( t 2 ) t(|P(T)_1|+1)+\binom{t}{2} t ( ∣ P ( T ) 1 ∣ + 1 ) + ( 2 t ) . If t = p t=p t = p , then
t ( ∣ P ( T ) 1 ∣ + 1 ) + ( t 2 ) = p + ( p 2 ) ≥ 2 ( p − 2 ) , t(|P(T)_1|+1)+\binom{t}{2}=p+\binom{p}{2}\ge2(p-2), t ( ∣ P ( T ) 1 ∣ + 1 ) + ( 2 t ) = p + ( 2 p ) ≥ 2 ( p − 2 ) ,
and if t = p − 1 t=p-1 t = p − 1 , then
t ( ∣ P ( T ) 1 ∣ + 1 ) + ( t 2 ) = p − 1 + ( p − 1 2 ) ≥ 2 ( p − 2 ) , since p ≥ 4. t(|P(T)_1|+1)+\binom{t}{2}=p-1+\binom{p-1}{2}\ge2(p-2),\text{ since }p\ge4. t ( ∣ P ( T ) 1 ∣ + 1 ) + ( 2 t ) = p − 1 + ( 2 p − 1 ) ≥ 2 ( p − 2 ) , since p ≥ 4.
If 2 ≤ t ≤ p − 2 2\le t\le p-2 2 ≤ t ≤ p − 2 , then
t ( ∣ P ( T ) 1 ∣ + 1 ) + ( t 2 ) = t ( p − t − 1 2 ) ≥ t ( p − t ) . t(|P(T)_1|+1)+\binom{t}{2}=t\left(p-\frac{t-1}{2}\right)\ge t(p-t). t ( ∣ P ( T ) 1 ∣ + 1 ) + ( 2 t ) = t ( p − 2 t − 1 ) ≥ t ( p − t ) .
Now, a few simple calculations yield that t ( p − t ) ≥ 2 ( p − 2 ) t(p-t)\ge2(p-2) t ( p − t ) ≥ 2 ( p − 2 ) , for 2 ≤ t ≤ p − 2 2\le t\le p-2 2 ≤ t ≤ p − 2 . Thus, from corollary 4.2 and 3.9, it can be seen that if T ∈ T n , p T\in\mathcal{T}_{n,p} T ∈ T n , p such that T ≠ S 1 , … , 1 , n − p T\ne S_{1,\ldots,1,n-p} T = S 1 , … , 1 , n − p , then Z C ( T ; i ) ≥ Z C ( H 2 , p − 2 n ; i ) Z_C(T;i)\ge Z_C(H^n_{2,p-2};i) Z C ( T ; i ) ≥ Z C ( H 2 , p − 2 n ; i ) , for all i ∈ [ n ] i\in[n] i ∈ [ n ] . This concludes the proof.
Upper bounds for the connected zero forcing polynomial of trees
We begin this section with a definition and one of the most important results of this paper, namely, Theorem 4.9. We then prove that, for p = 2 p=2 p = 2 and 3 3 3 , there always exists a maximum tree in T n , p \mathcal{T}_{n,p} T n , p . However, for p ≥ 5 p\ge5 p ≥ 5 , we present several interesting examples demonstrating that, as the number of pendant vertices increases, there exists a certain threshold value of n n n beyond which no tree T ∈ T n , p T\in\mathcal{T}_{n,p} T ∈ T n , p satisfies Z C ( T ′ , i ) ≤ Z C ( T , i ) Z_C(T',i)\le Z_C(T,i) Z C ( T ′ , i ) ≤ Z C ( T , i ) for every 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n and every T ′ ∈ T n , p T'\in\mathcal{T}_{n,p} T ′ ∈ T n , p . In other words, for such values of n n n and p p p , there is no tree in T n , p \mathcal{T}_{n,p} T n , p whose connected zero forcing polynomial coefficients simultaneously dominate those of every other tree in the family.
Definition 4.8. Let T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p and p 1 p_1 p 1 , p 2 p_2 p 2 be any two pendant vertices of T T T , such that the distance of p 1 p_1 p 1 and p 2 p_2 p 2 from their seeding vertices are d 1 d_1 d 1 and d 2 d_2 d 2 respectively (here the seeding vertices of p 1 p_1 p 1 and p 2 p_2 p 2 can be same). Then T T T is said to be an uniform tree if ∣ d 1 − d 2 ∣ \lvert d_1-d_2\rvert ∣ d 1 − d 2 ∣ is either 0 or 1 for any two pendant vertices p 1 p_1 p 1 and p 2 p_2 p 2 in T T T .
Theorem 4.9. Let T ′ T' T ′ be any tree in T n , p \mathcal{T}_{n,p} T n , p . Also let T ′ T' T ′ has the seeding vertices { s 1 , … , s k } \{s_1,\ldots,s_k\} { s 1 , … , s k } and for 1 ≤ j ≤ k 1 \le j \le k 1 ≤ j ≤ k , each of the seeding vertex s j s_j s j has a j a_j a j many seeds. Then there always exists a uniform tree T T T such that Z C ( T ′ , i ) ≤ Z C ( T , i ) Z_C(T',i) \le Z_C(T,i) Z C ( T ′ , i ) ≤ Z C ( T , i ) for 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n .
Proof. Let us consider the polynomials ( 1 + x + x 2 + ⋯ x m ) (1+x+x^2+\cdots x^m) ( 1 + x + x 2 + ⋯ x m ) and ( 1 + x + x 2 + ⋯ + x r ) (1+x+x^2+\cdots+x^r) ( 1 + x + x 2 + ⋯ + x r ) , where m ≤ r m \le r m ≤ r . Let
∑ i = 0 m x i ∑ j = 0 r x j = ∑ k = 0 m + r c t x t . \sum_{i=0}^{m}x^i\sum_{j=0}^{r}x^j=\sum_{k=0}^{m+r}c_tx^t. i = 0 ∑ m x i j = 0 ∑ r x j = k = 0 ∑ m + r c t x t .
Then we know that the coefficient of x t x^t x t in the product of these two polynomials is given by
c t = { t + 1 , if 0 ≤ t ≤ m , m + 1 , if m ≤ t ≤ r , m + r − t + 1 , if r ≤ t ≤ m + r , 0 , otherwise. (1) c_t=
\begin{cases}
t+1, & \text{if } 0\le t\le m,\\
m+1, & \text{if } m\le t\le r,\\
m+r-t+1, & \text{if } r\le t\le m+r,\\
0, & \text{otherwise.}
\end{cases} \tag*{(1)} c t = ⎩ ⎨ ⎧ t + 1 , m + 1 , m + r − t + 1 , 0 , if 0 ≤ t ≤ m , if m ≤ t ≤ r , if r ≤ t ≤ m + r , otherwise. (1)
From Theorem 3.5 , we know that if T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p and Z C ( T ) = k Z_C(T)=k Z C ( T ) = k . Then
Z C T ( x ) = x k ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) ( x − 1 ) p × ∏ v ∈ S T ( x + ∑ l ∈ L v x − 1 x d ( l ) − 1 ) . (2) Z_C^T(x)=\frac{x^k\prod_{l\in P(T)}(x^{d(l)}-1)}{(x-1)^p}\times\prod_{v\in S^T}\left(x+\sum_{l\in L_v}\frac{x-1}{x^{d(l)}-1}\right). \tag*{(2)} Z C T ( x ) = ( x − 1 ) p x k ∏ l ∈ P ( T ) ( x d ( l ) − 1 ) × v ∈ S T ∏ ( x + l ∈ L v ∑ x d ( l ) − 1 x − 1 ) . (2)
Case I: Let T ′ T' T ′ be a uniform tree in T n , p \mathcal{T}_{n,p} T n , p . Then consider T = T ′ T=T' T = T ′ .
Case II: Let T ′ T' T ′ be a non-uniform tree. Let T T T be a uniform tree in T n , p \mathcal{T}_{n,p} T n , p with seeding vertices { s 1 , … , s k } \{s_1,\ldots,s_k\} { s 1 , … , s k } , where each seeding vertex s j s_j s j has a j a_j a j seeds, for 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k . Let l ′ l' l ′ and l ′ ′ l'' l ′′ be two seeds of a seeding vertex v v v of T T T .
Subcase I: Suppose that both l ′ l' l ′ and l ′ ′ l'' l ′′ are at distance d d d from v v v . Assume that l ′ l' l ′ is adjacent to a vertex u u u in T T T . Delete the edge u l ′ ul' u l ′ and add the edge l ′ l ′ ′ l'l'' l ′ l ′′ . Let T 1 T_1 T 1 denote the resulting tree. Clearly, u u u becomes a pendant vertex of T 1 T_1 T 1 , and its distance from v v v decreases to d − 1 d-1 d − 1 . Moreover, l ′ ′ l'' l ′′ is no longer a pendant vertex of T 1 T_1 T 1 , whereas l ′ l' l ′ becomes a pendant vertex. Consequently, the distance of l ′ l' l ′ from v v v in T 1 T_1 T 1 is d + 1 d+1 d + 1 . Thus, the connected zero forcing polynomial of T 1 T_1 T 1 is given by
Z C T 1 ( x ) = ∏ l ∈ P ( T ) l ≠ l ′ , l ′ ′ ( x d ( l ) − 1 ) x − k ( x − 1 ) p ∏ v ′ ∈ S T v ′ ≠ v ( x + ∑ l ∈ L v ′ x − 1 x d ( l ) − 1 ) ( x d − 1 − 1 ) ( x d + 1 − 1 ) ( x + x − 1 x d − 1 − 1 + x − 1 x d + 1 − 1 + ∑ l ∈ L v l ≠ l ′ , l ′ ′ x − 1 x d ( l ) − 1 ) . (3) Z_C^{T_1}(x)=\frac{\prod_{\substack{l\in P(T)\\l\ne l',l''}}(x^{d(l)}-1)}{x^{-k}(x-1)^p}\prod_{\substack{v'\in S^T\\v'\ne v}}\left(x+\sum_{l\in L_{v'}}\frac{x-1}{x^{d(l)}-1}\right)(x^{d-1}-1)(x^{d+1}-1)\left(x+\frac{x-1}{x^{d-1}-1}+\frac{x-1}{x^{d+1}-1}+\sum_{\substack{l\in L_v\\l\ne l',l''}}\frac{x-1}{x^{d(l)}-1}\right). \tag*{(3)} Z C T 1 ( x ) = x − k ( x − 1 ) p ∏ l ∈ P ( T ) l = l ′ , l ′′ ( x d ( l ) − 1 ) v ′ ∈ S T v ′ = v ∏ x + l ∈ L v ′ ∑ x d ( l ) − 1 x − 1 ( x d − 1 − 1 ) ( x d + 1 − 1 ) x + x d − 1 − 1 x − 1 + x d + 1 − 1 x − 1 + l ∈ L v l = l ′ , l ′′ ∑ x d ( l ) − 1 x − 1 . (3)
Let
A = x k ∏ l ∈ P ( T ) l ≠ l ′ , l ′ ′ ( x d ( l ) − 1 ) ( x − 1 ) p × ∏ v ′ ∈ S T v ′ ≠ v ( x + ∑ l ∈ L v ′ x − 1 x d ( l ) − 1 ) . A=\frac{x^k\prod_{\substack{l\in P(T)\\l\ne l',l''}}(x^{d(l)}-1)}{(x-1)^p}\times\prod_{\substack{v'\in S^T\\v'\ne v}}\left(x+\sum_{l\in L_{v'}}\frac{x-1}{x^{d(l)}-1}\right). A = ( x − 1 ) p x k ∏ l ∈ P ( T ) l = l ′ , l ′′ ( x d ( l ) − 1 ) × v ′ ∈ S T v ′ = v ∏ x + l ∈ L v ′ ∑ x d ( l ) − 1 x − 1 .
and
B = ∑ l ∈ L v l ≠ l ′ , l ′ ′ x − 1 x d ( l ) − 1 . B=\sum_{\substack{l\in L_v\\l\ne l',l''}}\frac{x-1}{x^{d(l)}-1}. B = l ∈ L v l = l ′ , l ′′ ∑ x d ( l ) − 1 x − 1 .
So Equation (3) can be written as
Z C T 1 ( x ) = A × ( x d − 1 − 1 ) ( x d + 1 − 1 ) ( x + x − 1 x d − 1 − 1 + x − 1 x d + 1 − 1 + B ) . (4) Z_{C}^{T_1}(x)=A\times(x^{d-1}-1)(x^{d+1}-1)\left(x+\frac{x-1}{x^{d-1}-1}+\frac{x-1}{x^{d+1}-1}+B\right). \tag*{(4)} Z C T 1 ( x ) = A × ( x d − 1 − 1 ) ( x d + 1 − 1 ) ( x + x d − 1 − 1 x − 1 + x d + 1 − 1 x − 1 + B ) . (4)
Similarly, Equation (2) can be written as
Z C T ( x ) = A × ( x d − 1 ) 2 ( x + 2 x − 1 x d − 1 + B ) . (5) Z_C^T(x)=A\times(x^d-1)^2\left(x+2\frac{x-1}{x^d-1}+B\right). \tag*{(5)} Z C T ( x ) = A × ( x d − 1 ) 2 ( x + 2 x d − 1 x − 1 + B ) . (5)
Using (1)
[ ( ∑ i = 0 d − 1 x i ) 2 x + 2 ( ∑ i = 0 d − 1 x i ) + B ( ∑ i = 0 d − 1 x i ) 2 ] = [ x ( 1 + 2 x + 3 x 2 + ⋯ + ( d − 1 ) x d − 2 + d x d − 1 + ( d − 1 ) x d + ( d − 2 ) x d + 1 + ⋯ + 2 x 2 d − 3 + x 2 d − 2 ) × + 2 ∑ i = 0 d − 1 x i + B ( ∑ i = 0 d − 1 x i ) 2 ] = 2 + 3 x + 4 x 2 + 5 x 3 + 6 x 4 ⋯ + ( d + 1 ) x d − 1 + d x d + ( d − 1 ) x d + 1 + ⋯ + 2 x 2 d − 2 + x 2 d − 1 + B ( ∑ i = 0 d − 1 x i ) 2 . (6) \begin{aligned}
\left[\left(\sum_{i=0}^{d-1}x^i\right)^2x+2\left(\sum_{i=0}^{d-1}x^i\right)+B\left(\sum_{i=0}^{d-1}x^i\right)^2\right] \\
&=\left[x(1+2x+3x^2+\cdots+(d-1)x^{d-2}+dx^{d-1}+(d-1)x^d+(d-2)x^{d+1}+\cdots+2x^{2d-3}+x^{2d-2})\times+2\sum_{i=0}^{d-1}x^i+B\left(\sum_{i=0}^{d-1}x^i\right)^2\right] \\
&=2+3x+4x^2+5x^3+6x^4\cdots+(d+1)x^{d-1}+dx^d+(d-1)x^{d+1}+\cdots+2x^{2d-2}+x^{2d-1}+B\left(\sum_{i=0}^{d-1}x^i\right)^2. \tag*{(6)}
\end{aligned} ( i = 0 ∑ d − 1 x i ) 2 x + 2 ( i = 0 ∑ d − 1 x i ) + B ( i = 0 ∑ d − 1 x i ) 2 = x ( 1 + 2 x + 3 x 2 + ⋯ + ( d − 1 ) x d − 2 + d x d − 1 + ( d − 1 ) x d + ( d − 2 ) x d + 1 + ⋯ + 2 x 2 d − 3 + x 2 d − 2 ) × + 2 i = 0 ∑ d − 1 x i + B ( i = 0 ∑ d − 1 x i ) 2 = 2 + 3 x + 4 x 2 + 5 x 3 + 6 x 4 ⋯ + ( d + 1 ) x d − 1 + d x d + ( d − 1 ) x d + 1 + ⋯ + 2 x 2 d − 2 + x 2 d − 1 + B ( i = 0 ∑ d − 1 x i ) 2 . (6)
Again, using (1) , we have
[ ( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) x + ∑ i = 0 d − 2 x i + ∑ i = 0 d x i + B ( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) ] = [ x ( 1 + 2 x + ⋯ + ( d − 1 ) x d − 2 + ( d − 1 ) x d − 1 + ( d − 1 ) x d + ⋯ + 2 x 2 d − 3 + x 2 d − 2 ) + ∑ i = 0 d − 2 x i + ∑ i = 0 d x i + B ( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) ] = 2 + 3 x + 4 x 2 + 5 x 3 + 6 x 4 ⋯ + ( d + 0 ) x d − 1 + d x d + ( d − 1 ) x d + 1 + ⋯ + 2 x 2 d − 2 + x 2 d − 1 + B ( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) . (7) \begin{aligned}
\left[\left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right)x+\sum_{i=0}^{d-2}x^i+\sum_{i=0}^{d}x^i+B\left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right)\right] \\
&=\left[x(1+2x+\cdots+(d-1)x^{d-2}+(d-1)x^{d-1}+(d-1)x^d+\cdots+2x^{2d-3}+x^{2d-2})+\sum_{i=0}^{d-2}x^i+\sum_{i=0}^{d}x^i+B\left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right)\right] \\
&=2+3x+4x^2+5x^3+6x^4\cdots+(d+0)x^{d-1}+dx^d+(d-1)x^{d+1}+\cdots+2x^{2d-2}+x^{2d-1}+B\left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right). \tag*{(7)}
\end{aligned} [ ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) x + i = 0 ∑ d − 2 x i + i = 0 ∑ d x i + B ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) ] = [ x ( 1 + 2 x + ⋯ + ( d − 1 ) x d − 2 + ( d − 1 ) x d − 1 + ( d − 1 ) x d + ⋯ + 2 x 2 d − 3 + x 2 d − 2 ) + i = 0 ∑ d − 2 x i + i = 0 ∑ d x i + B ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) ] = 2 + 3 x + 4 x 2 + 5 x 3 + 6 x 4 ⋯ + ( d + 0 ) x d − 1 + d x d + ( d − 1 ) x d + 1 + ⋯ + 2 x 2 d − 2 + x 2 d − 1 + B ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) . (7)
If we notice the Equations (6) and (7), then it is clear,
( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) ≤ ( ∑ i = 0 d − 1 x i ) 2 . \left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right)\leq\left(\sum_{i=0}^{d-1}x^i\right)^2. ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) ≤ ( i = 0 ∑ d − 1 x i ) 2 .
So,
B ( ∑ i = 0 d − 2 x i ) ( ∑ i = 0 d x i ) ≤ B ( ∑ i = 0 d − 1 x i ) 2 . (8) B\left(\sum_{i=0}^{d-2}x^i\right)\left(\sum_{i=0}^{d}x^i\right)\leq B\left(\sum_{i=0}^{d-1}x^i\right)^2. \tag*{(8)} B ( i = 0 ∑ d − 2 x i ) ( i = 0 ∑ d x i ) ≤ B ( i = 0 ∑ d − 1 x i ) 2 . (8)
Hence, using Equations (6), (7), and (8) from the Equations (4) and (5), we can say
Z C T ( x ) ≥ Z C T 1 ( x ) . Z_C^T(x)\geq Z_C^{T_1}(x). Z C T ( x ) ≥ Z C T 1 ( x ) .
Subcase II: Suppose that the distances of the vertices l ′ l' l ′ and l ′ ′ l'' l ′′ from v v v are d d d and d + 1 d+1 d + 1 , respectively. Now, following the same construction as in Subcase I, we obtain a tree T 1 T_1 T 1 in which u u u becomes a pendant vertex at distance d − 1 d-1 d − 1 from v v v , while l ′ l' l ′ becomes a pendant vertex at distance d + 2 d+2 d + 2 from v v v . Thus, the connected zero forcing polynomial of T 1 T_1 T 1 is given by
Z C T 1 ( x ) = A × ( x d − 1 − 1 ) ( x d + 2 − 1 ) ( x + x − 1 x d − 1 − 1 + x − 1 x d + 2 − 1 + B ) . (9) Z_C^{T_1}(x)=A\times(x^{d-1}-1)(x^{d+2}-1)\left(x+\frac{x-1}{x^{d-1}-1}+\frac{x-1}{x^{d+2}-1}+B\right). \tag*{(9)} Z C T 1 ( x ) = A × ( x d − 1 − 1 ) ( x d + 2 − 1 ) ( x + x d − 1 − 1 x − 1 + x d + 2 − 1 x − 1 + B ) . (9)
where the values of A A A and B B B are exactly the same as those in Subcase I. Again, following a similar argument and using Equation (1) , we obtain, from Equations (4) and (9) , that
Z C T ( x ) ≥ Z C T 1 ( x ) . Z_C^T(x) \ge Z_C^{T_1}(x). Z C T ( x ) ≥ Z C T 1 ( x ) .
Subcase III: Suppose that v ′ , v ′ ′ ∈ st ( T ) v',v'' \in\operatorname{st}(T) v ′ , v ′′ ∈ st ( T ) , where v ′ v' v ′ and v ′ ′ v'' v ′′ are the seeding vertices of l ′ l' l ′ and l ′ ′ l'' l ′′ , respectively. Assume that the distance of l ′ l' l ′ from v ′ v' v ′ is d d d , while the distance of l ′ ′ l'' l ′′ from v ′ ′ v'' v ′′ is d + 1 d+1 d + 1 . Suppose that l ′ l' l ′ is adjacent to a vertex u u u in T T T . Delete the edge u l ′ ul' u l ′ and add the edge l ′ ′ l ′ l''l' l ′′ l ′ . Let T 1 T_1 T 1 denote the resulting tree. Then
Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 2 − 1 ) ( x + x − 1 x d − 1 − 1 + ∑ l ∈ L v ′ l ≠ l ′ x − 1 x d ( l ) − 1 ) ( x + x − 1 x d + 1 − 1 + ∑ l ∈ L v ′ ′ l ≠ l ′ ′ x − 1 x d ( l ) − 1 ) (10) Z_C^{T_1}(x)=C\times(x^{d-1}-1)(x^{d+2}-1)\left(x+\frac{x-1}{x^{d-1}-1}+\sum_{\substack{l\in L_{v'}\\l\ne l'}}\frac{x-1}{x^{d(l)}-1}\right)\left(x+\frac{x-1}{x^{d+1}-1}+\sum_{\substack{l\in L_{v''}\\l\ne l''}}\frac{x-1}{x^{d(l)}-1}\right) \tag*{(10)} Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 2 − 1 ) x + x d − 1 − 1 x − 1 + l ∈ L v ′ l = l ′ ∑ x d ( l ) − 1 x − 1 x + x d + 1 − 1 x − 1 + l ∈ L v ′′ l = l ′′ ∑ x d ( l ) − 1 x − 1 (10)
where
C = x k ∏ l ∈ P ( T ) l ≠ l ′ , l ′ ′ ( x d ( l ) − 1 ) ( x − 1 ) p × ∏ v ∈ S T v ≠ v ′ , v ′ ′ ( x + ∑ l ∈ L v x − 1 x d ( l ) − 1 ) . (11) C=\frac{x^k\prod_{\substack{l\in P(T)\\l\ne l',l''}}(x^{d(l)}-1)}{(x-1)^p}\times\prod_{\substack{v\in S^T\\v\ne v',v''}}\left(x+\sum_{l\in L_v}\frac{x-1}{x^{d(l)}-1}\right). \tag*{(11)} C = ( x − 1 ) p x k ∏ l ∈ P ( T ) l = l ′ , l ′′ ( x d ( l ) − 1 ) × v ∈ S T v = v ′ , v ′′ ∏ ( x + l ∈ L v ∑ x d ( l ) − 1 x − 1 ) . (11)
Let
D 1 = ∑ l ∈ L v ′ l ≠ l ′ x − 1 x d ( l ) − 1 , D 2 = ∑ l ∈ L v ′ l ≠ l ′ ′ x − 1 x d ( l ) − 1 . (12) D_1=\sum_{\substack{l\in L_{v'}\\l\ne l'}}\frac{x-1}{x^{d(l)}-1},\qquad D_2=\sum_{\substack{l\in L_{v'}\\l\ne l''}}\frac{x-1}{x^{d(l)}-1}. \tag*{(12)} D 1 = l ∈ L v ′ l = l ′ ∑ x d ( l ) − 1 x − 1 , D 2 = l ∈ L v ′ l = l ′′ ∑ x d ( l ) − 1 x − 1 . (12)
So, Equation (10) can be written as
Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 2 − 1 ) ( x + x − 1 x d − 1 − 1 + D 1 ) ( x + x − 1 x d + 2 − 1 + D 2 ) (13) Z_C^{T_1}(x)=C\times(x^{d-1}-1)(x^{d+2}-1)\left(x+\frac{x-1}{x^{d-1}-1}+D_1\right)\left(x+\frac{x-1}{x^{d+2}-1}+D_2\right) \tag*{(13)} Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 2 − 1 ) ( x + x d − 1 − 1 x − 1 + D 1 ) ( x + x d + 2 − 1 x − 1 + D 2 ) (13)
Similarly, Equation (2) can be written as
Z C T ( x ) = C × ( x d − 1 ) ( x d + 1 − 1 ) ( x + x − 1 x d − 1 + D 1 ) ( x + x − 1 x d + 1 − 1 + D 2 ) (14) Z_C^T(x)=C\times(x^d-1)(x^{d+1}-1)\left(x+\frac{x-1}{x^d-1}+D_1\right)\left(x+\frac{x-1}{x^{d+1}-1}+D_2\right) \tag*{(14)} Z C T ( x ) = C × ( x d − 1 ) ( x d + 1 − 1 ) ( x + x d − 1 x − 1 + D 1 ) ( x + x d + 1 − 1 x − 1 + D 2 ) (14)
Now,
[ x ∑ i = 0 d − 2 x i + D 1 ∑ i = 0 d − 2 x i ] [ x ∑ i = 0 d + 1 x i + D 2 ∑ i = 0 d + 1 x i ] = x 2 ∑ i = 0 d − 2 x i ∑ i = 0 d + 1 x i + x ( D 1 + D 2 ) ∑ i = 0 d − 2 x i ∑ i = 0 d + 1 x i + D 1 D 2 ∑ i = 0 d − 2 x i ∑ i = 0 d + 1 x i . (15) \begin{aligned}
\left[x\sum_{i=0}^{d-2}x^i+D_1\sum_{i=0}^{d-2}x^i\right]\left[x\sum_{i=0}^{d+1}x^i+D_2\sum_{i=0}^{d+1}x^i\right] \\
&=x^2\sum_{i=0}^{d-2}x^i\sum_{i=0}^{d+1}x^i+x(D_1+D_2)\sum_{i=0}^{d-2}x^i\sum_{i=0}^{d+1}x^i+D_1D_2\sum_{i=0}^{d-2}x^i\sum_{i=0}^{d+1}x^i. \tag*{(15)}
\end{aligned} [ x i = 0 ∑ d − 2 x i + D 1 i = 0 ∑ d − 2 x i ] [ x i = 0 ∑ d + 1 x i + D 2 i = 0 ∑ d + 1 x i ] = x 2 i = 0 ∑ d − 2 x i i = 0 ∑ d + 1 x i + x ( D 1 + D 2 ) i = 0 ∑ d − 2 x i i = 0 ∑ d + 1 x i + D 1 D 2 i = 0 ∑ d − 2 x i i = 0 ∑ d + 1 x i . (15)
Again,
[ x ∑ i = 0 d − 1 x i + D 1 ∑ i = 0 d − 1 x i ] [ x ∑ i = 0 d x i + D 2 ∑ i = 0 d x i ] = x 2 ∑ i = 0 d − 1 x i ∑ i = 0 d x i + x ( D 1 + D 2 ) ∑ i = 0 d − 1 x i ∑ i = 0 d x i + D 1 D 2 ∑ i = 0 d − 1 x i ∑ i = 0 d x i . (16) \begin{aligned}
\left[x\sum_{i=0}^{d-1}x^i+D_1\sum_{i=0}^{d-1}x^i\right]\left[x\sum_{i=0}^{d}x^i+D_2\sum_{i=0}^{d}x^i\right] \\
&=x^2\sum_{i=0}^{d-1}x^i\sum_{i=0}^{d}x^i+x(D_1+D_2)\sum_{i=0}^{d-1}x^i\sum_{i=0}^{d}x^i+D_1D_2\sum_{i=0}^{d-1}x^i\sum_{i=0}^{d}x^i. \tag*{(16)}
\end{aligned} [ x i = 0 ∑ d − 1 x i + D 1 i = 0 ∑ d − 1 x i ] [ x i = 0 ∑ d x i + D 2 i = 0 ∑ d x i ] = x 2 i = 0 ∑ d − 1 x i i = 0 ∑ d x i + x ( D 1 + D 2 ) i = 0 ∑ d − 1 x i i = 0 ∑ d x i + D 1 D 2 i = 0 ∑ d − 1 x i i = 0 ∑ d x i . (16)
By above calculations and observing Equation (1) it is clear that, if r 1 − m 1 ≥ r 2 − m 2 r_1-m_1\ge r_2-m_2 r 1 − m 1 ≥ r 2 − m 2 then
∑ i = 0 m 1 x i ∑ j = 0 r 1 x j ≤ ∑ i = 0 m 2 x i ∑ j = 0 r 2 x j . (17) \sum_{i=0}^{m_1}x^i\sum_{j=0}^{r_1}x^j\le\sum_{i=0}^{m_2}x^i\sum_{j=0}^{r_2}x^j. \tag*{(17)} i = 0 ∑ m 1 x i j = 0 ∑ r 1 x j ≤ i = 0 ∑ m 2 x i j = 0 ∑ r 2 x j . (17)
So,
∑ i = 0 d − 1 x i ∑ i = 0 d x i ≥ ∑ i = 0 d − 2 x i ∑ i = 0 d + 1 x i . (18) \sum_{i=0}^{d-1} x^i \sum_{i=0}^{d} x^i \ge\sum_{i=0}^{d-2} x^i \sum_{i=0}^{d+1} x^i. \tag*{(18)} i = 0 ∑ d − 1 x i i = 0 ∑ d x i ≥ i = 0 ∑ d − 2 x i i = 0 ∑ d + 1 x i . (18)
Hence, using Equations (15), (16), and (18), from Equations (13) and (14), we can clearly say
Z C T ( x ) ≥ Z C T 1 ( x ) . Z_C^T(x) \ge Z_C^{T_1}(x). Z C T ( x ) ≥ Z C T 1 ( x ) .
Subcase IV: Suppose that v ′ , v ′ ′ ∈ st ( T ) v',v'' \in\operatorname{st}(T) v ′ , v ′′ ∈ st ( T ) , where v ′ v' v ′ and v ′ ′ v'' v ′′ are the seeding vertices of l ′ l' l ′ and l ′ ′ l'' l ′′ , respectively. Assume that the distance of l ′ l' l ′ from v ′ v' v ′ and that of l ′ ′ l'' l ′′ from v ′ ′ v'' v ′′ are both equal to d d d . Suppose that l ′ l' l ′ is adjacent to a vertex u u u in T T T . Delete the edge u l ′ ul' u l ′ and add the edge l ′ l ′ ′ l'l'' l ′ l ′′ . Let T 1 T_1 T 1 denote the resulting tree. Then, following an argument similar to that in Subcase III, we obtain
Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 1 − 1 ) ( x + x − 1 x d − 1 − 1 + D 1 ) ( x + x − 1 x d + 1 − 1 + D 2 ) . (19) Z_C^{T_1}(x) = C \times(x^{d-1}-1)(x^{d+1}-1)\left(x+\frac{x-1}{x^{d-1}-1}+D_1\right)\left(x+\frac{x-1}{x^{d+1}-1}+D_2\right). \tag*{(19)} Z C T 1 ( x ) = C × ( x d − 1 − 1 ) ( x d + 1 − 1 ) ( x + x d − 1 − 1 x − 1 + D 1 ) ( x + x d + 1 − 1 x − 1 + D 2 ) . (19)
Z C T 1 ( x ) = C × ( x d − 1 ) ( x d − 1 ) ( x + x − 1 x d − 1 + D 1 ) ( x + x − 1 x d − 1 + D 2 ) . (20) Z_C^{T_1}(x) = C \times(x^d-1)(x^d-1)\left(x+\frac{x-1}{x^d-1}+D_1\right)\left(x+\frac{x-1}{x^d-1}+D_2\right). \tag*{(20)} Z C T 1 ( x ) = C × ( x d − 1 ) ( x d − 1 ) ( x + x d − 1 x − 1 + D 1 ) ( x + x d − 1 x − 1 + D 2 ) . (20)
where the values of C C C , D 1 D_1 D 1 , and D 2 D_2 D 2 are given in Equations (11) and (12). By a similar way just like Subcase III, someone can prove
Z C T ( x ) ≥ Z C T 1 ( x ) . Z_C^T(x) \ge Z_C^{T_1}(x). Z C T ( x ) ≥ Z C T 1 ( x ) .
Now, if T 1 = T ′ T_1=T' T 1 = T ′ , then the proof is complete. Otherwise, we construct a tree T 2 T_2 T 2 from T 1 T_1 T 1 by following the same procedure used to construct T 1 T_1 T 1 from T T T . Clearly, we have T 2 ≤ T 1 T_2 \le T_1 T 2 ≤ T 1 . Thus, by the preceding arguments and observing (17) , we can inductively construct a sequence of trees terminating at T ′ T' T ′ such that
T ′ = T s ≤ T s − 1 ≤ ⋯ ≤ T 2 ≤ T 1 ≤ T . T'=T_s \le T_{s-1} \le\cdots\le T_2 \le T_1 \le T. T ′ = T s ≤ T s − 1 ≤ ⋯ ≤ T 2 ≤ T 1 ≤ T .
Hence, the proof is complete.
Corollary 4.10. Let T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p , and p 1 p_1 p 1 , p 2 p_2 p 2 be two pendant vertices of T T T . Let p 1 p_1 p 1 be adjacent to some vertex v v v of T T T . Suppose distance of p 1 p_1 p 1 and p 2 p_2 p 2 from their respective seeding vertices (or vertex) be d 1 d_1 d 1 and d 2 d_2 d 2 respectively. Delete the edge between v v v and p 1 p_1 p 1 and connect p 1 p_1 p 1 with p 2 p_2 p 2 by an edge. Let T ′ T' T ′ be this new tree. Then Z C T ( x ) ≥ Z C T ′ ( x ) Z_C^T(x) \ge Z_C^{T'}(x) Z C T ( x ) ≥ Z C T ′ ( x ) if and only if ∣ d 1 − d 2 ∣ ≤ ∣ ( d 1 − 1 ) − ( d 2 + 1 ) ∣ \lvert d_1-d_2\rvert\le\lvert(d_1-1)-(d_2+1)\rvert ∣ d 1 − d 2 ∣ ≤ ∣( d 1 − 1 ) − ( d 2 + 1 )∣ .
Corollary 4.11. Let T T T and T ′ ∈ T n , p T' \in\mathcal{T}_{n,p} T ′ ∈ T n , p be two non-isomorphic graphs with the vertices { v 1 , ⋯ , v n } \{v_1,\cdots,v_n\} { v 1 , ⋯ , v n } which satisfy the following conditions.
T T T and T ′ T' T ′ are both starlike graphs.
T T T is a uniform tree.
Then Z C ( T , i ) ≥ Z C ( T ′ , i ) Z_C(T,i) \ge Z_C(T',i) Z C ( T , i ) ≥ Z C ( T ′ , i ) for all 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n and for any star graph T ′ ∈ T n , p T' \in\mathcal{T}_{n,p} T ′ ∈ T n , p .
Proof. It is clear that, if we consider the set of all starlike graphs in T n , p \mathcal{T}_{n,p} T n , p , then the set has a unique uniform tree. Hence, by Theorem 4.9, above T T T is the unique maximal element for the set of all starlike graphs in T n , p \mathcal{T}_{n,p} T n , p .
Corollary 4.12. Let T ∈ T n , 3 T \in\mathcal{T}_{n,3} T ∈ T n , 3 be the uniform tree. Then Z C ( T , i ) ≥ Z C ( T ′ , i ) Z_C(T,i) \ge Z_C(T',i) Z C ( T , i ) ≥ Z C ( T ′ , i ) for all 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n and for any tree T ′ ∈ T n , 3 T' \in\mathcal{T}_{n,3} T ′ ∈ T n , 3 .
Lemma 4.13. Let T ∈ T n , 4 T \in\mathcal{T}_{n,4} T ∈ T n , 4 . Then there exists a starlike graph T ′ ∈ T n , 4 T' \in\mathcal{T}_{n,4} T ′ ∈ T n , 4 such that Z C ( T , i ) ≤ Z C ( T ′ , i ) Z_C(T,i) \le Z_C(T',i) Z C ( T , i ) ≤ Z C ( T ′ , i ) for $1 \le i \le n.
Proof. Let T ∈ T n , 4 T \in\mathcal{T}_{n,4} T ∈ T n , 4 . If T T T is a starlike graph, then we can choose T ′ = T T'=T T ′ = T . Otherwise, s t ( T ) st(T) s t ( T ) is a path with the two terminal vertices having external degree 2, and all other vertices of s t ( T ) st(T) s t ( T ) have external degree zero. Suppose, T T T is not a graph of type H \mathcal{H} H . We now perform the following operation on T T T . Let u 1 , u 2 , … , u l u_1,u_2,\ldots,u_l u 1 , u 2 , … , u l be the vertices of s t ( T ) st(T) s t ( T ) with u i u_i u i being adjacent to u i + 1 u_{i+1} u i + 1 . We do contraction on the edge between u 1 , u 2 u_1,u_2 u 1 , u 2 and add a new pendant vertex on a pendant vertex having minimum distance from its seed u 1 u_1 u 1 . We denote the obtained graph by T 1 T_1 T 1 . Clearly T 1 ∈ T n , 4 T_1 \in\mathcal{T}_{n,4} T 1 ∈ T n , 4 . We will now show that Z C ( T 1 , i ) ≥ Z C ( T , i ) Z_C(T_1,i) \ge Z_C(T,i) Z C ( T 1 , i ) ≥ Z C ( T , i ) for 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n . Let the distance of the two pendant vertices from their seeding vertex u 1 u_1 u 1 be s 1 , s 2 s_1,s_2 s 1 , s 2 respectively in T T T , with s 1 ≤ s 2 s_1 \le s_2 s 1 ≤ s 2 . Then the connected zero forcing polynomial Z C T ( x ) Z_C^T(x) Z C T ( x ) is of the form
Z C T ( x ) = x l + 2 ( x ( x s 1 − 1 x − 1 ) ( x s 2 − 1 x − 1 ) + x s 1 − 1 x − 1 + x s 2 − 1 x − 1 ) g ( x ) , Z_C^T(x)=x^{l+2}\left(x\left(\frac{x^{s_1}-1}{x-1}\right)\left(\frac{x^{s_2}-1}{x-1}\right)+\frac{x^{s_1}-1}{x-1}+\frac{x^{s_2}-1}{x-1}\right)g(x), Z C T ( x ) = x l + 2 ( x ( x − 1 x s 1 − 1 ) ( x − 1 x s 2 − 1 ) + x − 1 x s 1 − 1 + x − 1 x s 2 − 1 ) g ( x ) ,
and the connected zero forcing polynomial Z C T 1 ( x ) Z_C^{T_1}(x) Z C T 1 ( x ) is of the form
Z C T 1 ( x ) = x l + 1 ( x ( x s 1 + 1 − 1 x − 1 ) ( x s 2 − 1 x − 1 ) + x s 1 + 1 − 1 x − 1 + x s 2 − 1 x − 1 ) g ( x ) , Z_C^{T_1}(x)=x^{l+1}\left(x\left(\frac{x^{s_1+1}-1}{x-1}\right)\left(\frac{x^{s_2}-1}{x-1}\right)+\frac{x^{s_1+1}-1}{x-1}+\frac{x^{s_2}-1}{x-1}\right)g(x), Z C T 1 ( x ) = x l + 1 ( x ( x − 1 x s 1 + 1 − 1 ) ( x − 1 x s 2 − 1 ) + x − 1 x s 1 + 1 − 1 + x − 1 x s 2 − 1 ) g ( x ) ,
where g ( x ) g(x) g ( x ) is a polynomial with all coefficients non-negative. Now,
x ( x s 1 + 1 − 1 x − 1 ) ( x s 2 − 1 x − 1 ) + x s 1 + 1 − 1 x − 1 + x s 2 − 1 x − 1 = x ( 1 + x ( x s 1 − 1 x − 1 ) ) ( x s 2 − 1 x − 1 ) + 1 + x ( x s 1 − 1 x − 1 ) + x s 2 − 1 x − 1 . x\left(\frac{x^{s_1+1}-1}{x-1}\right)\left(\frac{x^{s_2}-1}{x-1}\right)+\frac{x^{s_1+1}-1}{x-1}+\frac{x^{s_2}-1}{x-1}
=x\left(1+x\left(\frac{x^{s_1}-1}{x-1}\right)\right)\left(\frac{x^{s_2}-1}{x-1}\right)+1+x\left(\frac{x^{s_1}-1}{x-1}\right)+\frac{x^{s_2}-1}{x-1}. x ( x − 1 x s 1 + 1 − 1 ) ( x − 1 x s 2 − 1 ) + x − 1 x s 1 + 1 − 1 + x − 1 x s 2 − 1 = x ( 1 + x ( x − 1 x s 1 − 1 ) ) ( x − 1 x s 2 − 1 ) + 1 + x ( x − 1 x s 1 − 1 ) + x − 1 x s 2 − 1 .
So,
Z C T 1 ( x ) − Z C T ( x ) = x l + 1 g ( x ) ( 1 + ∑ i = 0 s 2 − 1 x i ) = x l + 1 g ( x ) ( 1 + x s 2 − 1 x − 1 ) . Z_C^{T_1}(x)-Z_C^T(x)=x^{l+1}g(x)\left(1+\sum_{i=0}^{s_2-1}x^i\right)=x^{l+1}g(x)\left(1+\frac{x^{s_2}-1}{x-1}\right). Z C T 1 ( x ) − Z C T ( x ) = x l + 1 g ( x ) ( 1 + i = 0 ∑ s 2 − 1 x i ) = x l + 1 g ( x ) ( 1 + x − 1 x s 2 − 1 ) .
Thus, we have that Z C T 1 ( x ) − Z C T ( x ) Z_C^{T_1}(x)-Z_C^T(x) Z C T 1 ( x ) − Z C T ( x ) is a polynomial with all coefficients non-negative. Hence, Z C ( T 1 , i ) ≥ Z C ( T , i ) Z_C(T_1,i) \ge Z_C(T,i) Z C ( T 1 , i ) ≥ Z C ( T , i ) for 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n . Continuing the above process, we can construct a tree T h ∈ T n , 4 T_h \in\mathcal{T}_{n,4} T h ∈ T n , 4 of type H \mathcal{H} H , such that Z C ( H , i ) ≥ Z C ( T , i ) Z_C(\mathcal{H},i) \ge Z_C(T,i) Z C ( H , i ) ≥ Z C ( T , i ) for 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n . We now show that for any tree T h T_h T h of type H \mathcal{H} H , there exists a starlike graph T h ′ T'_h T h ′ such that
Z C ( T h ′ , i ) ≥ Z C ( T h , i ) for 1 ≤ i ≤ n . Z_C(T'_h,i) \ge Z_C(T_h,i) \quad\text{for } 1 \le i \le n. Z C ( T h ′ , i ) ≥ Z C ( T h , i ) for 1 ≤ i ≤ n .
Let the distance of the four pendant vertices from their seeding vertices in the graph T h T_h T h be t 1 , t 2 t_1,t_2 t 1 , t 2 and t 3 , t 4 t_3,t_4 t 3 , t 4 , respectively, where the distances t 1 t_1 t 1 and t 2 t_2 t 2 correspond to the pendant vertices with the same seeding vertex, and the distances t 3 t_3 t 3 and t 4 t_4 t 4 correspond to the pendant vertices with the other seeding vertex. Also, assume that t 1 ≤ t 2 ≤ t 3 ≤ t 4 t_1 \le t_2 \le t_3 \le t_4 t 1 ≤ t 2 ≤ t 3 ≤ t 4 . Construct the graph T h ′ T'_h T h ′ by contracting the only edge in s t ( T h ) st(T_h) s t ( T h ) and adding a new pendant vertex with the vertex having distance t 1 t_1 t 1 . Then we have
Z C T h ( x ) = x 4 ( x ( x t 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) + x t 1 − 1 x − 1 + x t 2 − 1 x − 1 ) ( x ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + x t 3 − 1 x − 1 + x t 4 − 1 x − 1 ) , Z_C^{T_h}(x)=x^4\left(x\left(\frac{x^{t_1}-1}{x-1}\right)\left(\frac{x^{t_2}-1}{x-1}\right)+\frac{x^{t_1}-1}{x-1}+\frac{x^{t_2}-1}{x-1}\right)\left(x\left(\frac{x^{t_3}-1}{x-1}\right)\left(\frac{x^{t_4}-1}{x-1}\right)+\frac{x^{t_3}-1}{x-1}+\frac{x^{t_4}-1}{x-1}\right), Z C T h ( x ) = x 4 ( x ( x − 1 x t 1 − 1 ) ( x − 1 x t 2 − 1 ) + x − 1 x t 1 − 1 + x − 1 x t 2 − 1 ) ( x ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) + x − 1 x t 3 − 1 + x − 1 x t 4 − 1 ) ,
Z C T h ′ ( x ) = x 4 ( x ( x t 1 + 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( x t 1 + 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) + ( x t 1 + 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( x t 1 + 1 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) ) = x 4 ( ( x ( 1 + x ( x t 1 − 1 x − 1 ) ) ( x t 2 − 1 x − 1 ) + ( 1 + x ( x t 1 − 1 x − 1 ) ) + ( x t 2 − 1 x − 1 ) ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( 1 + x ( x t 1 − 1 x − 1 ) ) ( x t 2 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( 1 + x ( x t 1 − 1 x − 1 ) ) ( x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ) = x 4 ( x ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) ( x ( x t 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) + x t 1 − 1 x − 1 + x t 2 − 1 x − 1 ) + x ( x t 1 − 1 x − 1 ) ( x t 2 − 1 x − 1 ) \begin{aligned}
Z_C^{T'_h}(x)={}&x^4(x(\frac{x^{t_1+1}-1}{x-1})(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_3}-1}{x-1})(\frac{x^{t_4}-1}{x-1})+(\frac{x^{t_1+1}-1}{x-1})(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_3}-1}{x-1})\\
&+(\frac{x^{t_1+1}-1}{x-1})(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_4}-1}{x-1})+(\frac{x^{t_1+1}-1}{x-1})(\frac{x^{t_3}-1}{x-1})(\frac{x^{t_4}-1}{x-1})\\
&+(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_3}-1}{x-1})(\frac{x^{t_4}-1}{x-1}))\\
={}&x^4((x(1+x(\frac{x^{t_1}-1}{x-1}))(\frac{x^{t_2}-1}{x-1})+(1+x(\frac{x^{t_1}-1}{x-1}))+(\frac{x^{t_2}-1}{x-1}))(\frac{x^{t_3}-1}{x-1})(\frac{x^{t_4}-1}{x-1})\\
&+(1+x(\frac{x^{t_1}-1}{x-1}))(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_4}-1}{x-1})+(1+x(\frac{x^{t_1}-1}{x-1}))(\frac{x^{t_2}-1}{x-1})(\frac{x^{t_3}-1}{x-1}))\\
={}&x^4(x(\frac{x^{t_3}-1}{x-1})(\frac{x^{t_4}-1}{x-1})(x(\frac{x^{t_1}-1}{x-1})(\frac{x^{t_2}-1}{x-1})+\frac{x^{t_1}-1}{x-1}+\frac{x^{t_2}-1}{x-1})+x(\frac{x^{t_1}-1}{x-1})(\frac{x^{t_2}-1}{x-1})
\end{aligned} Z C T h ′ ( x ) = = = x 4 ( x ( x − 1 x t 1 + 1 − 1 ) ( x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) + ( x − 1 x t 1 + 1 − 1 ) ( x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 ) + ( x − 1 x t 1 + 1 − 1 ) ( x − 1 x t 2 − 1 ) ( x − 1 x t 4 − 1 ) + ( x − 1 x t 1 + 1 − 1 ) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) + ( x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 )) x 4 (( x ( 1 + x ( x − 1 x t 1 − 1 )) ( x − 1 x t 2 − 1 ) + ( 1 + x ( x − 1 x t 1 − 1 )) + ( x − 1 x t 2 − 1 )) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) + ( 1 + x ( x − 1 x t 1 − 1 )) ( x − 1 x t 2 − 1 ) ( x − 1 x t 4 − 1 ) + ( 1 + x ( x − 1 x t 1 − 1 )) ( x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 )) x 4 ( x ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) ( x ( x − 1 x t 1 − 1 ) ( x − 1 x t 2 − 1 ) + x − 1 x t 1 − 1 + x − 1 x t 2 − 1 ) + x ( x − 1 x t 1 − 1 ) ( x − 1 x t 2 − 1 )
× ( x t 3 − 1 x − 1 + x t 4 − 1 x − 1 ) + ( 1 + x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) + ( x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 + x t 4 − 1 x − 1 ) . \times\left(\frac{x^{t_{3}}-1}{x-1}+\frac{x^{t_{4}}-1}{x-1}\right)+\left(1+\frac{x^{t_{2}}-1}{x-1}\right)\left(\frac{x^{t_{3}}-1}{x-1}\right)\left(\frac{x^{t_{4}}-1}{x-1}\right)+\left(\frac{x^{t_{2}}-1}{x-1}\right)\left(\frac{x^{t_{3}}-1}{x-1}+\frac{x^{t_{4}}-1}{x-1}\right). × ( x − 1 x t 3 − 1 + x − 1 x t 4 − 1 ) + ( 1 + x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) + ( x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 + x − 1 x t 4 − 1 ) .
So,
Z C T h ′ ( x ) − Z C T h ( x ) = x 4 ( ( 1 + x t 2 − 1 x − 1 ) ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) − ( x t 1 − 1 x − 1 ) ( x t 3 − 1 x − 1 + x t 4 − 1 x − 1 ) ) = x 4 ( ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 − x t 1 − 1 x − 1 ) + ( x t 4 − 1 x − 1 ) ( x t 2 − 1 x − 1 x t 3 − 1 x − 1 − x t 1 − 1 x − 1 ) ) = x 4 ( ( x t 3 − 1 x − 1 ) ( x t 4 − x t 1 x − 1 ) + ( x t 4 − 1 x − 1 ) ( x t 3 − x t 1 x − 1 ) + ( x t 3 − 1 x − 1 ) ( x t 4 − 1 x − 1 ) ( ∑ i = 1 t 2 − 1 x i ) ) . \begin{aligned}
Z_{C}^{T_{h}^{\prime}}(x)-Z_{C}^{T_{h}}(x)
&=x^{4}\left(\left(1+\frac{x^{t_{2}}-1}{x-1}\right)\left(\frac{x^{t_{3}}-1}{x-1}\right)\left(\frac{x^{t_{4}}-1}{x-1}\right)-\left(\frac{x^{t_{1}}-1}{x-1}\right)\left(\frac{x^{t_{3}}-1}{x-1}+\frac{x^{t_{4}}-1}{x-1}\right)\right)\\
&=x^{4}\left(\left(\frac{x^{t_{3}}-1}{x-1}\right)\left(\frac{x^{t_{4}}-1}{x-1}-\frac{x^{t_{1}}-1}{x-1}\right)+\left(\frac{x^{t_{4}}-1}{x-1}\right)\left(\frac{x^{t_{2}}-1}{x-1}\frac{x^{t_{3}}-1}{x-1}-\frac{x^{t_{1}}-1}{x-1}\right)\right)\\
&=x^{4}\left(\left(\frac{x^{t_{3}}-1}{x-1}\right)\left(\frac{x^{t_{4}}-x^{t_{1}}}{x-1}\right)+\left(\frac{x^{t_{4}}-1}{x-1}\right)\left(\frac{x^{t_{3}}-x^{t_{1}}}{x-1}\right)+\left(\frac{x^{t_{3}}-1}{x-1}\right)\left(\frac{x^{t_{4}}-1}{x-1}\right)\left(\sum_{i=1}^{t_{2}-1}x^{i}\right)\right).
\end{aligned} Z C T h ′ ( x ) − Z C T h ( x ) = x 4 ( ( 1 + x − 1 x t 2 − 1 ) ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) − ( x − 1 x t 1 − 1 ) ( x − 1 x t 3 − 1 + x − 1 x t 4 − 1 ) ) = x 4 ( ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 − x − 1 x t 1 − 1 ) + ( x − 1 x t 4 − 1 ) ( x − 1 x t 2 − 1 x − 1 x t 3 − 1 − x − 1 x t 1 − 1 ) ) = x 4 ( ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − x t 1 ) + ( x − 1 x t 4 − 1 ) ( x − 1 x t 3 − x t 1 ) + ( x − 1 x t 3 − 1 ) ( x − 1 x t 4 − 1 ) ( i = 1 ∑ t 2 − 1 x i ) ) .
Since t 1 ≤ t 3 ≤ t 4 t_{1}\leq t_{3}\leq t_{4} t 1 ≤ t 3 ≤ t 4 , we find that the above polynomial has all coefficients non-negative. Hence, Z C ( T h ′ , i ) ≥ Z C ( T h , i ) Z_{C}(T_{h}^{\prime},i)\geq Z_{C}(T_{h},i) Z C ( T h ′ , i ) ≥ Z C ( T h , i ) for 1 ≤ i ≤ n 1\leq i\leq n 1 ≤ i ≤ n . This concludes the proof.
Theorem 4.14. Let T ∈ T n , 4 T\in\mathcal{T}_{n,4} T ∈ T n , 4 be the uniform starlike tree. Then Z C ( T , i ) ≥ Z C ( T ′ , i ) Z_{C}(T,i)\geq Z_{C}(T^{\prime},i) Z C ( T , i ) ≥ Z C ( T ′ , i ) for all 1 ≤ i ≤ n 1\leq i\leq n 1 ≤ i ≤ n and for any graph T ′ ∈ T n , 4 T^{\prime}\in\mathcal{T}_{n,4} T ′ ∈ T n , 4 .
Proof. By Corollary 4.11 and Lemma 4.13, the proof is trivial.
Now, let us consider P = 5 P=5 P = 5 . Then for n = 6 n=6 n = 6 , S 1 , 1 , 1 , 1 , 1 S_{1,1,1,1,1} S 1 , 1 , 1 , 1 , 1 is the unique tree in T 6 , 5 \mathcal{T}_{6,5} T 6 , 5 . Again for 7 ≤ n ≤ 8 7\leq n\leq8 7 ≤ n ≤ 8 , one can easily check that T ∈ H 2 , 3 n T\in\mathcal{H}_{2,3}^{n} T ∈ H 2 , 3 n is the maximum element, where T T T is the tree in Figure 4 .
Figure 4. Caption
Now for n ≥ 9 n\geq9 n ≥ 9 , by the following python program, one can check that T n , 5 \mathcal{T}_{n,5} T n , 5 does not have a unique maximal element. In general someone can check the following results.
Result 4.15. Let T , T ′ ∈ T n , 5 T,T^{\prime}\in\mathcal{T}_{n,5} T , T ′ ∈ T n , 5 , where T ′ T^{\prime} T ′ be the uniform starlike tree and T ∈ H 2 , 3 n T\in\mathcal{H}_{2,3}^{n} T ∈ H 2 , 3 n be a uniform tree. Also let st ( T ) = { v 1 , v 2 } \operatorname{st}(T)=\{v_{1},v_{2}\} st ( T ) = { v 1 , v 2 } and degree of v 1 , v 2 v_{1},v_{2} v 1 , v 2 be 2 and 3 respectively. Let n = i t + j ( t + 1 ) + 2 n=it+j(t+1)+2 n = i t + j ( t + 1 ) + 2 , where 0 ≤ i , j ≤ 5 0\leq i,j\leq5 0 ≤ i , j ≤ 5 , i + j = 5 i+j=5 i + j = 5 , and n ≥ 9 n\geq9 n ≥ 9 . Then T T T and T ′ T^{\prime} T ′ does not dominate by any other tree and they are never comparable when T T T satisfies the following conditions.
If 0 ≤ j ≤ 3 0\leq j\leq3 0 ≤ j ≤ 3 , then distance of both the seeds of v 1 v_{1} v 1 from v 1 v_{1} v 1 is t t t .
If 4 ≤ j ≤ 5 4\leq j\leq5 4 ≤ j ≤ 5 , then distance of every the seeds of v 2 v_{2} v 2 from v 2 v_{2} v 2 is t + 1 t+1 t + 1 .
In Figure 5, for 1 ≤ i ≤ 5 1\leq i\leq5 1 ≤ i ≤ 5 , h i h_i h i is either t t t or t + 1 t+1 t + 1 and n = ( h 1 + ⋯ + h 5 ) + 1 n=(h_1+\cdots+h_5)+1 n = ( h 1 + ⋯ + h 5 ) + 1 .
In Figure 6, for 0 ≤ j ≤ 3 0\leq j\leq3 0 ≤ j ≤ 3 , h j h_j h j is either t t t or t + 1 t+1 t + 1 , and n = h 1 + h 2 + h 3 + 2 t + 2 n=h_1+h_2+h_3+2t+2 n = h 1 + h 2 + h 3 + 2 t + 2 . Again, for 4 ≤ j ≤ 5 4\leq j\leq5 4 ≤ j ≤ 5 , h j h_j h j is either t t t or t + 1 t+1 t + 1 , and n = h 4 + h 5 + 3 ( t + 1 ) + 2 n=h_4+h_5+3(t+1)+2 n = h 4 + h 5 + 3 ( t + 1 ) + 2 .
Result 4.16. Let T , T 1 , T ′ ∈ T n , 5 T,T_1,T^{\prime}\in\mathcal{T}_{n,5} T , T 1 , T ′ ∈ T n , 5 , where T T T and T ′ T^{\prime} T ′ are defined in Result 4.15. Let st ( T 1 ) = { v 1 ′ , v 2 ′ } \operatorname{st}(T_1)=\{v_1^{\prime},v_2^{\prime}\} st ( T 1 ) = { v 1 ′ , v 2 ′ } and degree of v 1 ′ v_1^{\prime} v 1 ′ and v 2 ′ v_2^{\prime} v 2 ′ be 2 and 3 respectively. Also let n = i t + j ( t + 1 ) + 2 n=it+j(t+1)+2 n = i t + j ( t + 1 ) + 2 , where i = 2 i=2 i = 2 , j = 3 j=3 j = 3 , and n ≥ 9 n\geq9 n ≥ 9 . Then T , T 1 , T ′ ∈ T n , 5 T,T_1,T^{\prime}\in\mathcal{T}_{n,5} T , T 1 , T ′ ∈ T n , 5 are not comparable to each other and none of them is dominated by any T ′ ′ ∈ T n , 5 T^{\prime\prime}\in\mathcal{T}_{n,5} T ′′ ∈ T n , 5 if T ′ T^{\prime} T ′ satisfies the following conditions.
Figure 5. The uniform starlike tree T ′ ∈ T n , 5 T^{\prime} \in\mathcal{T}_{n,5} T ′ ∈ T n , 5 .
Figure 6.
The distance of the seeds of v 1 v_1 v 1 from v 1 v_1 v 1 is t t t and t + 1 t+1 t + 1 respectively.
The distance of the seeds of v 2 v_2 v 2 from v 2 v_2 v 2 is t t t , t + 1 t+1 t + 1 , t + 1 t+1 t + 1 respectively.
But it can be checked any tree in T n , 5 \mathcal{T}_{n,5} T n , 5 is dominated by atleast one of T T T , T 1 T_1 T 1 or T ′ T^{\prime} T ′ .
Let us consider some examples in the support of the above results.
Example 4.17. Let T T T , T 1 T_1 T 1 , T ′ ∈ T n , 5 T^{\prime} \in\mathcal{T}_{n,5} T ′ ∈ T n , 5 be same as Results 4.15 and 4.16.
Case I: Let n = 9 n=9 n = 9 . Then
Z C T ( x ) = 6 x 5 + 13 x 6 + 11 x 7 + 5 x 8 + x 9 , Z C T 1 ( x ) = 6 x 5 + 12 x 6 + 11 x 7 + 5 x 8 + x 9 , Z_C^T(x)=6x^5+13x^6+11x^7+5x^8+x^9,\quad Z_C^{T_1}(x)=6x^5+12x^6+11x^7+5x^8+x^9, Z C T ( x ) = 6 x 5 + 13 x 6 + 11 x 7 + 5 x 8 + x 9 , Z C T 1 ( x ) = 6 x 5 + 12 x 6 + 11 x 7 + 5 x 8 + x 9 ,
Z C T ′ ( x ) = 5 x 5 + 13 x 6 + 12 x 7 + 5 x 8 + x 9 . Z_C^{T^{\prime}}(x)=5x^5+13x^6+12x^7+5x^8+x^9. Z C T ′ ( x ) = 5 x 5 + 13 x 6 + 12 x 7 + 5 x 8 + x 9 .
Case II: Let n = 10 n=10 n = 10 . Then
Z C T ( x ) = 6 x 5 + 17 x 6 + 19 x 7 + 12 x 8 + 5 x 9 + x 10 , Z C T 1 ( x ) = 6 x 5 + 16 x 6 + 19 x 7 + 13 x 8 + 5 x 9 + x 10 , Z_C^T(x)=6x^5+17x^6+19x^7+12x^8+5x^9+x^{10},\quad Z_C^{T_1}(x)=6x^5+16x^6+19x^7+13x^8+5x^9+x^{10}, Z C T ( x ) = 6 x 5 + 17 x 6 + 19 x 7 + 12 x 8 + 5 x 9 + x 10 , Z C T 1 ( x ) = 6 x 5 + 16 x 6 + 19 x 7 + 13 x 8 + 5 x 9 + x 10 ,
Z C T ′ ( x ) = 5 x 5 + 17 x 6 + 22 x 7 + 14 x 8 + 5 x 9 + x 10 . Z_C^{T^{\prime}}(x)=5x^5+17x^6+22x^7+14x^8+5x^9+x^{10}. Z C T ′ ( x ) = 5 x 5 + 17 x 6 + 22 x 7 + 14 x 8 + 5 x 9 + x 10 .
Case III: Let n = 11 n=11 n = 11 . Then
Z C T ( x ) = 6 x 5 + 20 x 6 + 29 x 7 + 25 x 8 + 14 x 9 + 5 x 10 + x 11 , Z C T 1 ( x ) = 6 x 5 + 19 x 6 + 27 x 7 + 24 x 8 + 14 x 9 + 5 x 10 + x 11 , Z_C^T(x)=6x^5+20x^6+29x^7+25x^8+14x^9+5x^{10}+x^{11},\quad Z_C^{T_1}(x)=6x^5+19x^6+27x^7+24x^8+14x^9+5x^{10}+x^{11}, Z C T ( x ) = 6 x 5 + 20 x 6 + 29 x 7 + 25 x 8 + 14 x 9 + 5 x 10 + x 11 , Z C T 1 ( x ) = 6 x 5 + 19 x 6 + 27 x 7 + 24 x 8 + 14 x 9 + 5 x 10 + x 11 ,
Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 35 x 7 + 30 x 8 + 15 x 9 + 5 x 10 + x 11 . Z_C^{T^{\prime}}(x)=5x^5+21x^6+35x^7+30x^8+15x^9+5x^{10}+x^{11}. Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 35 x 7 + 30 x 8 + 15 x 9 + 5 x 10 + x 11 .
Case IV: Let n = 12 n=12 n = 12 . Then
Z C T ( x ) = Z C T 1 ( x ) = 6 x 5 + 23 x 6 + 39 x 7 + 41 x 8 + 30 x 9 + 15 x 10 + 5 x 11 + x 12 , Z_C^T(x)=Z_C^{T_1}(x)=6x^5+23x^6+39x^7+41x^8+30x^9+15x^{10}+5x^{11}+x^{12}, Z C T ( x ) = Z C T 1 ( x ) = 6 x 5 + 23 x 6 + 39 x 7 + 41 x 8 + 30 x 9 + 15 x 10 + 5 x 11 + x 12 ,
Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 39 x 7 + 43 x 8 + 31 x 9 + 15 x 10 + 5 x 11 + x 12 . Z_C^{T^{\prime}}(x)=5x^5+21x^6+39x^7+43x^8+31x^9+15x^{10}+5x^{11}+x^{12}. Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 39 x 7 + 43 x 8 + 31 x 9 + 15 x 10 + 5 x 11 + x 12 .
Case V: Let n = 13 n=13 n = 13 . Then
Z C T ( x ) = 6 x 5 + 23 x 6 + 43 x 7 + 53 x 8 + 47 x 9 + 31 x 10 + 15 x 11 + 5 x 12 + x 13 , Z_C^T(x)=6x^5+23x^6+43x^7+53x^8+47x^9+31x^{10}+15x^{11}+5x^{12}+x^{13}, Z C T ( x ) = 6 x 5 + 23 x 6 + 43 x 7 + 53 x 8 + 47 x 9 + 31 x 10 + 15 x 11 + 5 x 12 + x 13 ,
Z C T 1 ( x ) = 6 x 5 + 23 x 6 + 42 x 7 + 51 x 8 + 46 x 9 + 31 x 10 + 15 x 11 + 5 x 12 + x 13 , Z_C^{T_1}(x)=6x^5+23x^6+42x^7+51x^8+46x^9+31x^{10}+15x^{11}+5x^{12}+x^{13}, Z C T 1 ( x ) = 6 x 5 + 23 x 6 + 42 x 7 + 51 x 8 + 46 x 9 + 31 x 10 + 15 x 11 + 5 x 12 + x 13 ,
Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 43 x 7 + 56 x 8 + 50 x 9 + 32 x 10 + 15 x 11 + 5 x 12 + x 13 . Z_C^{T^{\prime}}(x)=5x^5+21x^6+43x^7+56x^8+50x^9+32x^{10}+15x^{11}+5x^{12}+x^{13}. Z C T ′ ( x ) = 5 x 5 + 21 x 6 + 43 x 7 + 56 x 8 + 50 x 9 + 32 x 10 + 15 x 11 + 5 x 12 + x 13 .
It is readily verified that, in every case, T T T and T ′ T^{\prime} T ′ are incomparable. Furthermore, except in Case II, we have T 1 ≤ T T_1 \leq T T 1 ≤ T ; in Case II, T 1 T_1 T 1 and T T T are also incomparable. On the other hand, T 1 T_1 T 1 and T ′ T^{\prime} T ′ are incomparable in every cases. Consequently, in Case II, the three trees T T T , T 1 T_1 T 1 , and T ′ T^{\prime} T ′ are pairwise incomparable.
Moreover, a direct computational verification using the python program, someone can check that all other trees in T n , 5 \mathcal{T}_{n,5} T n , 5 are dominated by at least one of T T T or T 1 T_1 T 1 or T ′ T' T ′ , but there does not have any T ′ ′ ∈ T n , 5 T'' \in\mathcal{T}_{n,5} T ′′ ∈ T n , 5 which dominates both of T T T and T ′ T' T ′ .
Observation 4.18. Since the patterns of T T T , T 1 T_1 T 1 , and T ′ T' T ′ are fixed, increasing the value of n n n does not affect the comparability relations among T T T , T 1 T_1 T 1 , and T ′ T' T ′ . Only the coefficients get increased in the exponents of x x x in their connected zero forcing polynomials and whenever n n n is increased by 5, the connected zero forcing polynomial acquires five more additional power of x x x relative to the corresponding polynomial for the preceding value of n n n .
Example 4.19. Let us consider p = 8 p = 8 p = 8 . Now, for n = 9 n = 9 n = 9 , the unique starlike tree S 1 , 1 , … , 1 S_{1,1,\ldots,1} S 1 , 1 , … , 1 is the only element in T n , 8 \mathcal{T}_{n,8} T n , 8 . For n = 10 , 11 , 12 n = 10, 11, 12 n = 10 , 11 , 12 using the python program, someone can check that the following T 1 T_1 T 1 , T 2 T_2 T 2 and T 3 T_3 T 3 in Figure 7 are the unique maximal tree in T 10 , 8 \mathcal{T}_{10,8} T 10 , 8 , T 11 , 8 \mathcal{T}_{11,8} T 11 , 8 and T 12 , 8 \mathcal{T}_{12,8} T 12 , 8 respectively. But for n ≥ 13 n \ge13 n ≥ 13 , there does not exist a unique maximal tree in T n , 8 \mathcal{T}_{n,8} T n , 8 . For n = 13 n = 13 n = 13 , the following two maximal trees T 1 ′ T'_1 T 1 ′ and T 2 ′ T'_2 T 2 ′ in Figure 8 are not comparable to each, as
Z C T 1 ′ ( x ) = 15 x 8 + 44 x 9 + 49 x 10 + 27 x 11 + 8 x 12 + x 13 , Z_C^{T'_1}(x) = 15x^8 + 44x^9 + 49x^{10} + 27x^{11} + 8x^{12} + x^{13}, Z C T 1 ′ ( x ) = 15 x 8 + 44 x 9 + 49 x 10 + 27 x 11 + 8 x 12 + x 13 , Z C T 2 ′ ( x ) = 18 x 8 + 45 x 9 + 48 x 10 + 27 x 11 + 8 x 12 + x 13 . Z_C^{T'_2}(x) = 18x^8 + 45x^9 + 48x^{10} + 27x^{11} + 8x^{12} + x^{13}. Z C T 2 ′ ( x ) = 18 x 8 + 45 x 9 + 48 x 10 + 27 x 11 + 8 x 12 + x 13 . In fact for n = 17 n = 17 n = 17 , the following tress T 4 T_4 T 4 , T 5 T_5 T 5 , T 6 T_6 T 6 , T 7 ∈ T 17 , 8 T_7 \in\mathcal{T}_{17,8} T 7 ∈ T 17 , 8 in Figure 9 are maximal and they are not comparable to each other.
Figure 7. Unique maximal trees
Figure 8. Non comparable maximal trees in T 13 , 8 \mathcal{T}_{13,8} T 13 , 8
Figure 9. Non comparable maximal trees in T 17 , 8 \mathcal{T}_{17,8} T 17 , 8
By the python program, someone can check
Z C T 4 ( x ) = 16 x 8 + 92 x 9 + 230 x 10 + 333 x 11 + 316 x 12 + 211 x 13 + 102 x 14 + 35 x 15 + 8 x 16 + x 17 , Z_C^{T_4}(x) = 16x^8 + 92x^9 + 230x^{10} + 333x^{11} + 316x^{12} + 211x^{13} + 102x^{14} + 35x^{15} + 8x^{16} + x^{17}, Z C T 4 ( x ) = 16 x 8 + 92 x 9 + 230 x 10 + 333 x 11 + 316 x 12 + 211 x 13 + 102 x 14 + 35 x 15 + 8 x 16 + x 17 ,
Z C T 5 ( x ) = 15 x 8 + 88 x 9 + 225 x 10 + 333 x 11 + 321 x 12 + 215 x 13 + 103 x 14 + 35 x 15 + 8 x 16 + x 17 , Z_C^{T_5}(x) = 15x^8 + 88x^9 + 225x^{10} + 333x^{11} + 321x^{12} + 215x^{13} + 103x^{14} + 35x^{15} + 8x^{16} + x^{17}, Z C T 5 ( x ) = 15 x 8 + 88 x 9 + 225 x 10 + 333 x 11 + 321 x 12 + 215 x 13 + 103 x 14 + 35 x 15 + 8 x 16 + x 17 ,
Z C T 6 ( x ) = 18 x 8 + 93 x 9 + 212 x 10 + 289 x 11 + 270 x 12 + 184 x 13 + 92 x 14 + 33 x 15 + 8 x 16 + x 17 , Z_C^{T_6}(x) = 18x^8 + 93x^9 + 212x^{10} + 289x^{11} + 270x^{12} + 184x^{13} + 92x^{14} + 33x^{15} + 8x^{16} + x^{17}, Z C T 6 ( x ) = 18 x 8 + 93 x 9 + 212 x 10 + 289 x 11 + 270 x 12 + 184 x 13 + 92 x 14 + 33 x 15 + 8 x 16 + x 17 ,
Z C T 7 ( x ) = 8 x 8 + 57 x 9 + 176 x 10 + 308 x 11 + 336 x 12 + 238 x 13 + 112 x 14 + 36 x 15 + 8 x 16 + x 17 . Z_C^{T_7}(x) = 8x^8 + 57x^9 + 176x^{10} + 308x^{11} + 336x^{12} + 238x^{13} + 112x^{14} + 36x^{15} + 8x^{16} + x^{17}. Z C T 7 ( x ) = 8 x 8 + 57 x 9 + 176 x 10 + 308 x 11 + 336 x 12 + 238 x 13 + 112 x 14 + 36 x 15 + 8 x 16 + x 17 .
It is clear that none of T 4 T_4 T 4 , T 5 T_5 T 5 , T 6 T_6 T 6 and T 7 T_7 T 7 are comparable to each other. Also, by the python program, someone can check none of them is dominated by any T ∈ T 17 , 8 T \in\mathcal{T}_{17,8} T ∈ T 17 , 8 .
Observation 4.20. From Example 4.17, we know, for p = 5 p = 5 p = 5 , till n = 8 n = 8 n = 8 we have a unique maximal tree in T n , 5 \mathcal{T}_{n,5} T n , 5 . But for n ≥ 8 n \ge8 n ≥ 8 , we do not have a unique maximal tree. In fact we found 3 maximal tree which are not comparable to each other and all other trees in T n , 5 \mathcal{T}_{n,5} T n , 5 are dominated by atleast one of them.
Again, from Example 4.19 we know, for p = 8 p = 8 p = 8 , till n = 12 n = 12 n = 12 , there exists a unique maximal tree. But for n ≥ 13 n \ge13 n ≥ 13 , we do not have a unique maximal tree. In fact we found 4 maximal trees in T 17 , 8 \mathcal{T}_{17,8} T 17 , 8 which are not comparable to each other.
Concluding Remarks and Open Problems
Zero forcing sets and connected zero forcing sets have applications in various areas of mathematics and related disciplines. Although zero forcing sets have been extensively studied, the theory of connected zero forcing sets remains relatively unexplored. In this paper, we investigate several properties of connected zero forcing sets of trees by introducing the connected zero forcing polynomial Z C T ( x ) Z_C^T(x) Z C T ( x ) of a tree T T T . For fixed values of n n n and p p p , we determine the minimal elements in T n , p \mathcal{T}_{n,p} T n , p . Through several illustrative examples, we also demonstrate that there need not exist a unique maximal element in T n , p \mathcal{T}_{n,p} T n , p . This observation motivates the following conjecture.
Conjecture 5.1. For p ≥ 5 p \ge5 p ≥ 5 , there exists a sufficiently large integer N N N (depending on p p p ) such that, for every n ≥ N n \ge N n ≥ N , there is no unique tree T ∈ T n , p T \in\mathcal{T}_{n,p} T ∈ T n , p satisfying
T ≥ T ′ , for every T ′ ∈ T n , p . T \ge T',
\qquad\text{for every } T' \in\mathcal{T}_{n,p}. T ≥ T ′ , for every T ′ ∈ T n , p .
More generally, as the number of pendant vertices increases, the number of pairwise incomparable maximal elements in T n , p \mathcal{T}_{n,p} T n , p tends to increase for sufficiently large values of n n n , where the threshold may depend on p p p .
In this paper, we investigate several properties of connected zero forcing polynomials of finite trees. Our results reveal that these polynomials exhibit properties that can differ significantly from those of the usual zero forcing polynomials of trees. Since unicyclic graphs are among the graph classes most closely related to trees, it would be interesting to investigate the connected zero forcing polynomials of unicyclic graphs. In particular, we propose the following problem.
Problem 5.2. Determine the connected zero forcing polynomial of a unicyclic graph. Furthermore, for fixed positive integers n n n and p p p , do there exist unicyclic graphs U min U_{\min} U m i n and U max U_{\max} U m a x , each having n n n vertices and p p p pendant vertices, such that
U min ≤ U ≤ U max U_{\min} \le U \le U_{\max} U m i n ≤ U ≤ U m a x for every unicyclic graph U U U with n n n vertices and p p p pendant vertices?
Throughout our investigation of the minimal and maximal elements of trees, we have fixed the number of pendant vertices. It is natural to ask what happens when this restriction is removed. More precisely, consider two trees T 1 ∈ T n , p 1 T_1 \in\mathcal{T}_{n,p_1} T 1 ∈ T n , p 1 and T 2 ∈ T n , p 2 T_2 \in\mathcal{T}_{n,p_2} T 2 ∈ T n , p 2 , where p 1 p_1 p 1 and p 2 p_2 p 2 need not be equal. Let Z C T 1 ( x ) Z_C^{T_1}(x) Z C T 1 ( x ) and Z C T 2 ( x ) Z_C^{T_2}(x) Z C T 2 ( x ) denote their respective connected zero forcing polynomials. This leads to the following problem.
Problem 5.3. Given two trees T 1 ∈ T n , p 1 T_1 \in\mathcal{T}_{n,p_1} T 1 ∈ T n , p 1 and T 2 ∈ T n , p 2 T_2 \in\mathcal{T}_{n,p_2} T 2 ∈ T n , p 2 , can we always find an integer l l l , with 1 ≤ l ≤ n 1 \le l \le n 1 ≤ l ≤ n , such that
Z C ( T 1 , i ) ≤ Z C ( T 2 , i ) for 1 ≤ i ≤ l Z_C(T_1,i) \le Z_C(T_2,i) \qquad\text{for } 1 \le i \le l Z C ( T 1 , i ) ≤ Z C ( T 2 , i ) for 1 ≤ i ≤ l and
Z C ( T 1 , i ) ≥ Z C ( T 2 , i ) for l + 1 ≤ i ≤ n ? Z_C(T_1,i) \ge Z_C(T_2,i) \qquad\text{for } l+1 \le i \le n? Z C ( T 1 , i ) ≥ Z C ( T 2 , i ) for l + 1 ≤ i ≤ n ?
Finally, although this paper focuses on trees, it is natural to extend the investigation to arbitrary finite graphs. Such an extension could provide a broader understanding of the structural and algebraic properties of connected zero forcing sets. In this direction, we propose the following problem.
Problem 5.4. Let G G G be an arbitrary finite graph. Determine its connected zero forcing polynomial Z C G ( x ) Z_C^G(x) Z C G ( x ) . Furthermore, given two finite graphs G 1 G_1 G 1 and G 2 G_2 G 2 , each having n n n vertices and p p p pendant vertices, what relationships, if any, exist between their connected zero forcing sets and their corresponding connected zero forcing polynomials? More generally, what can be said about these relationships when the two graphs have different numbers of pendant vertices?
The problems concerning zero forcing sets and the zero forcing number have been extensively studied. Various authors have explored connections between zero forcing and other graph-theoretic properties. For instance, a close relationship between restricted power domination and zero forcing sets and the zero forcing number was established in [6 ] . In [12 ] , Burgarth et al. investigated the impact of zero forcing sets, a graph-theoretic concept, on the controllability of networks. In [14 , 15 ] , the authors studied zero forcing in random graphs. Furthermore, Goldberg and Berman [17 ] established a bound on the maximum nullity of a matrix with a given sign pattern in terms of the zero forcing number.
It would be interesting to investigate whether analogous connections can be established by considering connected zero forcing sets and the connected zero forcing number in place of their standard counterparts.
Acknowledgments
We thank Dr. Anurag Singh for several conversations on this work. The first-named author thanks Harish-Chandra Research Institute, India, for providing funding (in the form of post-doctoral fellowship) during this work. The second-named author expresses gratitude to the Department of Mathematical Sciences IISER Mohali, India for providing funding (in the form of post-doctoral fellowship) during this work.
Conflict of interest
The authors declare that there are no conflicts of interest.