Search

Zero forcing is an iterative process on a graph used to bound the maximum nullity. The process begins with select vertices as colored, and the remaining vertices can become colored under a specific color change rule. The goal is to find a minimum set of vertices such that after iteratively applying the rule, all of the vertices become colored (i.e., a minimum zero forcing set). Of particular interest is the propagation time of a chosen set which is the number of steps the rule must be applied in order to color all the vertices of a graph. We give a purely linear algebraic view of zero forcing: Find a set of vertices S such that for any weighted adjacency matrix A , whenever Ax = 0 , the entirety of x can be recovered using only x S , the entries corresponding to S. The key here is that S must be chosen before A. In this light, we are able to give a linear algebraic interpretation of the propagation time: Any error in x S effects the error of x exponentially in the propagation time. This error can be quantitatively measured using newly defined zero forcing-related parameters, the error polynomial vector and the variance polynomial vector. In this sense, the quality of two zero forcing sets can objectively be compared even if the sets are the same size and their propagation times are the same. Examples and constructions are given. [ABSTRACT FROM AUTHOR]

Abstract This paper presents strong connections between four variants of the zero forcing number and four variants of the Grundy domination number. These connections bridge the domination problem and the minimum rank problem, providing a linear algebra approach to the domination problem. We show that several Grundy domination type parameters are bounded above by minimum rank type parameters. We also give a method to calculate the L -Grundy domination number by the Grundy total domination number, giving some linear algebra bounds for the L -Grundy domination number. [ABSTRACT FROM AUTHOR]

A sign pattern requires a unique inertia if every real matrix in the sign pattern class has the same inertia. Several sufficient or necessary conditions are given for a sign pattern to require a unique inertia. It is proved that a sign pattern requires a unique inertia if and only if it requires a unique refined inertia. All sign patterns of orders 2 and 3 that require a unique inertia are characterized. If the underlying graph of a sign pattern is a tree, then it is shown that any skew-symmetric sign pattern requires a unique inertia, and a linear-time algorithm is given to determine whether or not a symmetric sign pattern requires a unique inertia. [ABSTRACT FROM AUTHOR]

The maximum nullity M ( G ) and the Colin de Verdière type parameter ξ ( G ) both consider the largest possible nullity over matrices in S ( G ) , which is the family of real symmetric matrices whose i , j -entry, i ≠ j , is nonzero if i is adjacent to j , and zero otherwise; however, ξ ( G ) restricts to those matrices A in S ( G ) with the Strong Arnold Property, which means X = O is the only symmetric matrix that satisfies A ∘ X = O , I ∘ X = O , and A X = O . This paper introduces zero forcing parameters Z SAP ( G ) and Z vc ( G ) , and proves that Z SAP ( G ) = 0 implies every matrix A ∈ S ( G ) has the Strong Arnold Property and that the inequality M ( G ) − Z vc ( G ) ≤ ξ ( G ) holds for every graph G . Finally, the values of ξ ( G ) are computed for all graphs up to 7 vertices, establishing ξ ( G ) = ⌊ Z ⌋ ( G ) for these graphs. [ABSTRACT FROM AUTHOR]

We conjecture that all connected graphs of order n have von Neumann entropy at least as great as the star K 1 , n − 1 and prove this for almost all graphs of order n . We show that connected graphs of order n have Rényi 2-entropy at least as great as K 1 , n − 1 and for α > 1 , K n maximizes Rényi α -entropy over graphs of order n . We show that adding an edge to a graph can lower its von Neumann entropy. [ABSTRACT FROM AUTHOR]

The inverse eigenvalue problem of a given graph G is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in G. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph. Electron. J. Combin. , 2017]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue. [ABSTRACT FROM AUTHOR]

Zero forcing is an iterative coloring procedure on a graph that starts by initially coloring vertices white and blue and then repeatedly applies the following rule: if any blue vertex has a unique (out-)neighbor that is colored white, then that neighbor is forced to change color from white to blue. An initial set of blue vertices that can force the entire graph to blue is called a zero forcing set. In this paper we consider the minimum number of iterations needed for this color change rule to color all of the vertices blue, also known as the propagation time, for oriented graphs. We produce oriented graphs with both high and low propagation times, consider the possible propagation times for the orientations of a fixed graph, and look at balancing the size of a zero forcing set and the propagation time. [ABSTRACT FROM AUTHOR]

The distance matrix of a graph G is the matrix containing the pairwise distances between vertices. The distance eigenvalues of G are the eigenvalues of its distance matrix and they form the distance spectrum of G . We determine the distance spectra of double odd graphs and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs. [ABSTRACT FROM AUTHOR]