Open Access
- 5 April 2019
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 26 (2) , P2.43
Abstract
Connections between vital linkages and zero forcing are established. Specifically, the notion of a rigid linkage is introduced as a special kind of unique linkage and it is shown that spanning forcing paths of a zero forcing process form a spanning rigid linkage and thus a vital linkage. A related generalization of zero forcing that produces a rigid linkage via a coloring process is developed. One of the motivations for introducing zero forcing is to provide an upper bound on the maximum multiplicity of an eigenvalue among the real symmetric matrices described by a graph. Rigid linkages and a related notion of rigid shortest linkages are utilized to obtain bounds on the multiplicities of eigenvalues of this family of matrices.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The Zero Forcing Number of GraphsSIAM Journal on Discrete Mathematics, 2019
- Fast–mixed searching and related problems on graphsTheoretical Computer Science, 2013
- A technique for computing the zero forcing number of a graph with a cut-vertexLinear Algebra and its Applications, 2012
- The structure of graphs with a vital linkage of order 2Journal of Graph Theory, 2011
- Minimum rank problemsLinear Algebra and its Applications, 2010
- Graph minors. XXI. Graphs with unique linkagesJournal of Combinatorial Theory, Series B, 2009
- Smith Normal Form and acyclic matricesJournal of Algebraic Combinatorics, 2008
- Full Control by Locally Induced RelaxationPhysical Review Letters, 2007
- Algebraic Graph Theory2001
- The Determinant of the Adjacency Matrix of a GraphSIAM Review, 1962