Abstract: We consider a discrete-time dynamical process on graphs, firstly introduced in connection with a protocol for controlling large networks of spin 1/2 quantum mechanical particles [Phys. Rev. Lett. 99, 100501 (2007)]. A description is as follows: each vertex of an initially selected set has a packet of information (the same for every element of the set), which will be distributed among vertices of the graph; a vertex v can pass its packet to an adjacent vertex w only if w is its only neighbour without the information. By mean of examples, we describe some general properties, mainly concerning homeomorphism, and redundant edges. We prove that the cardinality of the smallest sets propagating the information in all vertices of a balanced m-ary tree of depth k is exactly (m^{k+1}+(-1)^{k})/(m+1). For binary trees, this number is related to alternating sign matrices.
Recommendations
Cited in
(35)- Positive zero forcing and edge clique coverings
- Positive semidefinite zero forcing numbers of two classes of graphs
- On the zero forcing number of a graph involving some classical parameters
- scientific article; zbMATH DE number 1553119 (Why is no real title available?)
- On the error of \textit{a priori} sampling: zero forcing sets and propagation time
- Some Cayley graphs with propagation time of at most two
- On leaky forcing and resilience
- Solving systems of linear equations through zero forcing set
- Logic circuits from zero forcing
- Skew throttling
- A short proof for a lower bound on the zero forcing number
- Failed skew zero forcing on a graph
- Minimum rank and zero forcing number for butterfly networks
- A technique for computing the zero forcing number of a graph with a cut-vertex
- On zero forcing number of graphs and their complements
- Propagation time for zero forcing on a graph
- Approximating the minimum rank of a graph via alternating projection
- A Differential Approach for Staged Trees
- Throttling positive semidefinite zero forcing propagation time on graphs
- Failed zero forcing and critical sets on directed graphs
- Throttling processes equivalent to full throttling on trees
- Positive semidefinite propagation time
- On the nullity of a connected graph in terms of order and maximum degree
- On the complexity of the positive semidefinite zero forcing number
- Some Cayley graphs with propagation time 1
- The zero forcing number of claw-free cubic graphs
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Some bounds on the zero forcing number of a graph
- Throttling for zero forcing and variants
- On the relationships between zero forcing numbers and certain graph coverings
- Zero forcing number for Cartesian product of some graphs
- Infection in hypergraphs
- Hopping forcing number in random d-regular graphs
- Bounds on expected propagation time of probabilistic zero forcing
- On the adjacency-Jacobsthal numbers
This page was built for publication: Nondiscriminatory propagation on trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548664)
