Nondiscriminatory Propagation on Trees

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.

5 pages, 7 figures

References in corpus (3)

• Quantum Communication through Spin Chain Dynamics: an Introductory Overview
• Full control by locally induced relaxation
• Bethe roots and refined enumeration of alternating-sign matrices

Cited by in corpus (9)

• Local controllability of quantum networks
• Propagation time for zero forcing on a graph
• Indirect Hamiltonian Identification through a small gateway
• Logic circuits from zero forcing
• Throttling positive semidefinite zero forcing propagation time on graphs
• Minimum rank and zero forcing number for butterfly networks
• On Zero Forcing Number of Graphs and Their Complements
• Bounds on expected propagation time of probabilistic zero forcing
• On the power domination number of de Bruijn and Kautz digraphs