Source-linked AI summary
Propagation time for zero forcing on a graph
Leslie Hogben, My Huynh, Nicole Kingsley, Sarah Meyer, Shanise Walker, Michael Young
TL;DR
The paper studies propagation time, the number of simultaneous-force steps needed to color a graph, and properties of minimum zero forcing sets. It proves that every connected graph of order greater than one has at least two efficient sets, characterizes a tree family with minimum propagation time |G| − 2, and gives a diameter bound for trees; a general question about propagation time one remains open.
Problem
Propagation time is a significant part of controlling an entire network through sequential operations on a subset of particles, and the paper undertakes a systematic study of it.
Source: §1 · p. 2Method
The paper studies efficient zero forcing sets, extreme propagation times, and the relationship between propagation time and diameter.
Source: §1 · p. 2Results
Every connected graph of order greater than one has at least two efficient zero forcing sets, and for trees PT(G) = |G| − 2 exactly when G = S(1, 1, n − 3).
Source: §2 · p. 6, §3.1 · p. 8Takeaways & Limitations
Diameter is an upper bound for propagation time in trees, but no direct ordering relationship holds for arbitrary graphs.
Source: §4 · p. 15The general question of which graphs have propagation time one remains open despite several constructions.
Source: §3.2 · p. 13
Abstract
from arXiv · showhide
Zero forcing (also called graph infection) on a simple, undirected graph $G$ is based on the color-change rule: If each vertex of $G$ is colored either white or black, and vertex $v$ is a black vertex with only one white neighbor $w$, then change the color of $w$ to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set $B$ of graph $G$ is the minimum number of steps that it takes to force all the vertices of $G$ black, starting with the vertices in $B$ black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs $G$ having extreme minimum propagation times $|G| - 1$, $|G| - 2$, and $0$ are characterized, and results regarding graphs having minimum propagation time $1$ are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable.
1 Propagation time
Zero forcing colors a graph through successive forces from black vertices, and propagation time counts the steps when independent forces occur simultaneously. The section defines minimum and maximum propagation time and shows that minimum propagation time can vary across minimum zero forcing sets and need not behave monotonically under edge deletion.
1 Propagation time
- The paper frames propagation time as the steps needed for simultaneous network control and systematically studies its properties.Earlier work introduced zero forcing for minimum-rank problems and quantum-system control; propagation time was implicit in one study and explicit in another.Source: §1 · p. 2
- Two non-isomorphic minimum zero forcing sets can have different propagation times, although the dart’s three minimum sets each have propagation time 3.Isomorphic minimum sets have the same propagation time.Source: §1 · p. 2
- A graph’s minimum propagation time is the least time over its minimum zero forcing sets, while its maximum propagation time is the greatest.A minimum zero forcing set has the smallest cardinality among sets that force the whole graph black.Source: §1 · pp. 2–3
- Deleting one edge changes C4 from Z(C4) = 2 and pt(C4) = 1 to P3 with Z(P3) = 1 and pt(P3) = 2, so minimum propagation time is not subgraph monotone.The example changes both the zero forcing number and the minimum propagation time.Source: §1 · p. 2
- An efficient zero forcing set is a minimum zero forcing set that achieves the graph’s minimum propagation time; pd(G) = 0 exactly when every minimum set is efficient.The section denotes the collection of efficient sets by Eff(G).Source: §1 · pp. 3–4
- For S(2, 5, 11), the propagation time interval is [12, 16], but no minimum zero forcing set has propagation time 14; its discrepancy is 4.The interval therefore need not contain every propagation time realized by a minimum zero forcing set.Source: §1 · p. 3
2 Efficient zero forcing sets
The section develops efficient zero forcing sets and sets of forces to study minimum propagation time. It shows that every connected graph of order greater than one has at least two efficient zero forcing sets.
2 Efficient zero forcing sets
- Unordered sets of forces are used because propagation-time analysis schedules forces as soon as possible, unlike chronological lists that record a particular order.A set of forces is the unordered set of forces from a chronological list [6].Source: §2 · pp. 4–5
- An efficient zero forcing set is a minimum zero forcing set whose propagation time equals the graph's minimum; an efficient set of forces achieves that time.The section defines the corresponding families Eff(G) and Feff(G).Source: §2 · p. 5
- An efficient set of forces need not reproduce the propagation process, even when its starting set is efficient.In Example 2.7, b turns black at step 2 under the chosen force set but can be forced at step 1 in the propagation process.Source: §2 · pp. 5–6
- Every connected graph of order greater than one has at least two efficient zero forcing sets.Reversing an efficient set of forces yields another efficient set, distinct from the original one.Source: §2 · p. 6
- For W5, the four listed efficient zero forcing sets all contain a, while another type of minimum zero forcing set has propagation time 2 rather than 1.The efficient sets are {a, b, c}, {a, c, d}, {a, d, e}, and {a, b, e}.Source: §2 · p. 7
- A vertex can belong to an efficient zero forcing set without forcing any vertex exactly when deleting it lowers the zero forcing number by one and preserves minimum propagation time.Source: §2 · p. 7
3 Graphs with extreme minimum propagation time
This section characterizes graphs with extreme minimum propagation times and develops structural results for propagation times 0 and 1. It also presents constructions and reductions for time one, including conditions involving matching graphs, components, and degrees of vertices in every minimum zero forcing set.
3.1 High propagation time
- For a graph G, Proposition 3.1 lists equivalent conditions including Z(G) = 1 and G is a path; therefore, Z(G) = 1 exactly when G is a path.pt(G) = |G| − 2 implies PT(G) = |G| − 2, but not conversely.Source: §3.1 · p. 7
- For trees, PT(G) = |G| −2 exactly for S(1, 1, n −3), whereas pt(G) = |G| −2 only for K1,3.For disconnected graphs, the proof identifies Pn−1 ∪ P1 as the graph with PT(G) = |G| −2.Source: §3.1 · p. 8
- pt(G) = |G| −2 is characterized by disconnected Pn−1 ∪ P1, K1,3, or qualifying zigzag graphs on two parallel paths.The theorem excludes Figure 6 graphs and gives endpoint-degree conditions; its proof constructs the zigzag structure from a minimum zero forcing set.Source: §3.1 · pp. 9–10
3.2 Low propagation time
- pt(G) = 0, PT(G) = 0, Z(G) = |G|, and having no edges are equivalent.Source: §3.2 · p. 10
- Any two of |G| = 2Z(G), pt(G) = 1, and G being a matching graph imply the third; matching choice can affect propagation time.For example, C5□P2 has Z = 4 and pt > 1, while the Petersen graph has Z = 5 and pt = 1.Source: §3.2 · p. 11
- If pt((H1, H2, µ)) = 1, then H1, H2, and the matching graph have the same number of components; moreover, pt((H, Kn, µ)) = 1 exactly when H is connected.Source: §3.2 · p. 12
- M(K_n □ P_2^s) = Z(K_n □ P_2^s) = n2^(s−1), and pt(K_n □ P_2^s) = 1.This holds for s ≥ 1.Source: §3.2 · p. 13
- pt(P_2 □ P_2^s) = 1, pt(K_n □ P_2^s) = 1, and pt((K_n, H, µ)) = 1 when H is connected; characterizing matching graphs with pt = 1 remains open.The open question asks which matching graphs (H_1, H_2, µ) have propagation time one.Source: §3.2 · p. 13
- If pt(G) = 1, deleting a vertex from an efficient zero forcing set that performs no force leaves propagation time equal to 1.The deleted vertex must be in an efficient zero forcing set and perform no force in the chosen efficient force set.Source: §3.2 · p. 13
- Removing all non-forcing vertices of an efficient zero forcing set yields a prime subgraph that is a matching graph with complementary efficient zero forcing sets and propagation time 1.The prime subgraph is formed from the vertices remaining after removing the starting-set vertices that perform no force.Source: §3.2 · p. 14
- If G has no isolated vertices and pt(G) = 1, adjoining a new vertex adjacent to every vertex of G preserves propagation time 1.Source: §3.2 · p. 14
- When pt(G) = 1, every vertex in an efficient zero forcing set has degree at least 4.Source: §3.2 · p. 14
- If deg(v) > Z(G) and pt(G) = 1, then v belongs to every efficient zero forcing set, but the converse fails.An example has Z(G) = 5, deg(v) = 4, and v in every efficient zero forcing set.Source: §3.2 · pp. 14–15
4 Relationship of propagation time and diameter
For arbitrary graphs, diameter and propagation time are not comparable; for trees, the diameter bounds even the maximum propagation time over minimum zero forcing sets.
4 Relationship of propagation time and diameter
- For the dart, diam(G) = 2 < pt(G) = 3, while diam(C4) = 2 > 1 = pt(C4), showing neither quantity bounds the other generally.The k-comb example also shows that diameter can be arbitrarily larger than minimum propagation time.Source: §4 · p. 15
- A minimum zero forcing set yields a trail of length at least pt(G, B), constructed backward through the forces that produced each vertex.At each earlier forcing time, the trail extends by one or two edges.Source: §4 · p. 15
- Figure 11's graph has pt(G) = 4 but no path of length 4; the proof's trail abcdecf has length 6.The example distinguishes the trail-length bound from a claim that a path of propagation-time length must exist.Source: §4 · p. 16, Figure 11 · p. 16
- For every tree T and minimum zero forcing set B, pt(T, B) ≤ diam(T), so pt(T) ≤ PT(T) ≤ diam(T).The argument uses a trail at least as long as propagation time; in a tree, every trail is a path.Source: §4 · pp. 15–16
- For k ≡ 0 mod 4, the k-comb example exhibits diameter arbitrarily larger than minimum propagation time; its described zero forcing set has size k/2.The k-comb is formed by appending a leaf to every vertex of a k-vertex path.Source: §4 · p. 16, Figure 12 · p. 16
- A graph with ℓ leaves has Z(G) ≥ ⌈ℓ/2⌉, since at most two leaves can lie on a maximal forcing chain.Source: §4 · p. 16