Search

We introduce the set G SSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G ∈ G SSP has the strong spectral property. We find several families of graphs in G SSP and, in particular, characterise the trees in G SSP. [ABSTRACT FROM AUTHOR]

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 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]