Nondiscriminatory propagation on trees
From MaRDI portal
Publication:3548664
DOI10.1088/1751-8113/41/48/482002zbMATH Open1156.81357arXiv0805.0181OpenAlexW3123397167MaRDI QIDQ3548664FDOQ3548664
Publication date: 16 December 2008
Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0805.0181
Recommendations
Cited In (33)
- Positive semidefinite zero forcing numbers of two classes of graphs
- On the zero forcing number of a graph involving some classical parameters
- Title not available (Why is that?)
- On the error of \textit{a priori} sampling: zero forcing sets and propagation time
- Title not available (Why is that?)
- Some Cayley graphs with propagation time of at most two
- Solving systems of linear equations through zero forcing set
- On leaky forcing and resilience
- Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
- Logic circuits from zero forcing
- Skew throttling
- Throttling for Zero Forcing and Variants
- A short proof for a lower bound on the zero forcing number
- On zero forcing number of graphs and their complements
- 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
- Propagation time for zero forcing on a graph
- A Differential Approach for Staged Trees
- Approximating the minimum rank of a graph via alternating projection
- Positive Zero Forcing and Edge Clique Coverings
- 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
- On the complexity of the positive semidefinite zero forcing number
- The zero forcing number of claw-free cubic graphs
- Positive semidefinite propagation time
- On the nullity of a connected graph in terms of order and maximum degree
- On the Adjacency-Jacobsthal numbers
- Some bounds on the zero forcing number of a graph
- On the relationships between zero forcing numbers and certain graph coverings
- Infection in hypergraphs
- Bounds on expected propagation time of probabilistic zero forcing
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)
