Search

The inverse eigenvalue problem of a graph G is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of G. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al. in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form M = A ⊕ B and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices. [ABSTRACT FROM AUTHOR]

In this work, the inverse eigenvalue problem is completely solved for a subfamily of clique-path graphs, in particular for lollipop graphs and generalized barbell graphs. For a matrix A with associated graph G , a new technique utilizing the strong spectral property is introduced, allowing us to construct a matrix A ′ whose graph is obtained from G by appending a clique while arbitrary list of eigenvalues is added to the spectrum. Consequently, many spectra are shown realizable for block graphs. [ABSTRACT FROM AUTHOR]

Given a graph G , one may ask: "What sets of eigenvalues are possible over all weighted adjacency matrices of G ?" (The weight of an edge is positive or negative, while the diagonal entries can be any real numbers.) This is known as the Inverse Eigenvalue Problem for graphs (IEPG). A mild relaxation of this question considers the multiplicity list instead of the exact eigenvalues themselves. That is, given a graph G on n vertices and an ordered partition m = (m 1 , ... , m ℓ) of n , is there a weighted adjacency matrix where the i -th distinct eigenvalue has multiplicity m i ? This is known as the ordered multiplicity IEPG. Recent work solved the ordered multiplicity IEPG for all graphs on 6 vertices. In this work, we develop zero forcing methods for the ordered multiplicity IEPG in a multitude of different contexts. Namely, we utilize zero forcing parameters on powers of graphs to achieve bounds on consecutive multiplicities. We are able to provide general bounds on sums of multiplicities of eigenvalues for graphs. This includes new bounds on the sums of multiplicities of consecutive eigenvalues as well as more specific bounds for trees. Using these results, we verify the previous results above regarding the IEPG on six vertices. In addition, applying our techniques to skew-symmetric matrices, we are able to determine all possible ordered multiplicity lists for skew-symmetric matrices for connected graphs on five vertices. [ABSTRACT FROM AUTHOR]

Given a real symmetric n × n matrix, the sepr-sequence t 1 ⋯ t n records information about the existence of principal minors of each order that are positive, negative, or zero. This paper extends the notion of the sepr-sequence to matrices whose entries are of prescribed signs, that is, to sign patterns. A sufficient condition is given for a sign pattern to have a unique sepr-sequence, and it is conjectured to be necessary. The sepr-sequences of sign semi-stable patterns are shown to be well-structured; in some special circumstances, the sepr-sequence is enough to guarantee that the sign pattern is sign semi-stable. In alignment with previous work on symmetric matrices, the sepr-sequences for sign patterns realized by symmetric nonnegative matrices of orders two and three are characterized. [ABSTRACT FROM AUTHOR]

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]

There are profound relations between the zero forcing number and minimum rank of a graph. We study the relation of both parameters with a third one, the algebraic co-rank, which is defined as the largest i such that the i th critical ideal is trivial. This gives a new perspective for bounding and computing these three graph parameters. [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]

We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01, 10, which we call Slash. We provide an ordering characterization, a forbidden structure characterization, and a polynomial-time certifying recognition algorithm for the class. These results complete the picture in which in addition to, or instead of, the Slash matrix one forbids the \Gamma matrix (which has rows 11, 10). It is well known that in these two cases one obtains the class of interval graphs and the class of strongly chordal graphs, respectively. By complementation, we obtain the class of strong comparability graphs, whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the two-by-two identity submatrix. Thus our results give characterizations and algorithms for this class of irreflexive graphs as well. In other words, our results may be interpreted as solving the following problem: given a symmetric 0, 1-matrix with 0-diagonal, can the rows and columns of be simultaneously permuted to avoid the two-by-two identity submatrix? [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]

The inverse eigenvalue problem of a graph studies the real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of the graph. The strong spectral property (SSP) is an important tool for this problem. This note establishes the bifurcation lemma, which states that if a spectrum can be realized by a matrix with the SSP for some graph, then all the nearby spectra can also be realized by matrices with the SSP for the same graph. The idea of the bifurcation lemma also works for other strong properties and for not necessarily symmetric matrices. This is used to develop new techniques for verifying a spectrally arbitrary pattern or inertially arbitrary pattern. The bifurcation lemma provides a unified theoretical foundation for several known results, such as the stable northeast lemma and the nilpotent-centralizer method. [ABSTRACT FROM AUTHOR]

Given a graph G with vertices { v 1 , ... , v n } , we define S (G) to be the set of symmetric matrices A = [ a i , j ] such that for i ≠ j we have a i , j ≠ 0 if and only if v i v j ∈ E (G). Motivated by the Graph Complement Conjecture, we say that a graph G is complementary vanishing if there exist matrices A ∈ S (G) and B ∈ S (G ‾) such that A B = O. We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most 8 vertices are complementary vanishing. [ABSTRACT FROM AUTHOR]

We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai’s structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval 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]

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has little impact on a class of graphs; it however makes a big difference in this case. We call the new class strongly chordal graphs with possible loops. When all vertices have loops, we recover the usual strongly chordal graphs; when all vertices are loopless, we obtain the usual chordal bigraphs. Moreover, there is a surprizing wealth of graphs in the new class that have loops at some vertices and not at others. These graphs also admit the elegant algorithms previously only applied in the extreme two cases. Formulated in the language of adjacency matrices, we study the class of symmetric 0, 1 matrices that admit a simultaneous row and column permutation avoiding the Gamma matrix [1110]. We give ordering characterizations, matrix characterizations, and forbidden subgraph characterizations of the new class, and illustrate its usefulness by solving the minimum domination problem in this general context. This implies solutions of both the minimum dominating set in strongly chordal graphs and the minimum total dominating set in chordal bigraphs. [ABSTRACT FROM AUTHOR]

In light of recent interest in Hadamard diagonalisable graphs (graphs whose Laplacian matrix is diagonalisable by a Hadamard matrix), we generalise this notion from real to complex Hadamard matrices. We give some basic properties and methods of constructing such graphs. We show that a large class of complex Hadamard diagonalisable graphs have vertex sets forming an equitable partition, and that the Laplacian eigenvalues must be even integers. We provide a number of examples and constructions of complex Hadamard diagonalisable graphs, including two special classes of graphs: the Cayley graphs over Z r d , and the non–complete extended p –sum (NEPS). We discuss necessary and sufficient conditions for (α , β) –Laplacian fractional revival and perfect state transfer on continuous–time quantum walks described by complex Hadamard diagonalisable graphs and provide examples of such quantum state transfer. [ABSTRACT FROM AUTHOR]

Zero forcing is a combinatorial game played on a graph where the goal is to start with all vertices unfilled and to change them to filled at minimal cost. In the original variation of the game there were two options. Namely, to fill any one single vertex at the cost of a single token; or if any currently filled vertex has a unique non-filled neighbor, then the neighbor is filled for free. This paper investigates a q-analogue of zero forcing which introduces a third option involving an oracle. Basic properties of this game are established including determining all graphs which have minimal cost 1 or 2 for all possible q, and finding the zero forcing number for all trees when q = 1 . [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]

The LaTeX control sequence \deg is interpreted differently in the authors' and the publisher's LaTeX setting [ABSTRACT FROM AUTHOR]

The LaTeX control sequence \deg is interpreted differently in the authors’ and the publisher’s LaTeX setting [ABSTRACT FROM AUTHOR]