Search

In this article, we extend the notion of the Laplacian spread to simple directed graphs (digraphs) using the restricted numerical range. First, we provide Laplacian spread values for several families of digraphs. Then, we prove sharp upper bounds on the Laplacian spread for all polygonal and balanced digraphs. In particular, we show that the validity of the Laplacian spread bound for balanced digraphs is equivalent to the Laplacian spread conjecture for simple undirected graphs, which was conjectured in 2011 and proven in 2021. Moreover, we prove an equivalent statement for weighted balanced digraphs with weights between $0$ and $1$. Finally, we state several open conjectures that are motivated by empirical data.

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.

We conjecture a new lower bound on the algebraic connectivity of a graph that involves the number of vertices of high eccentricity in a graph. We prove that this lower bound implies a strengthening of the Laplacian Spread Conjecture. We discuss further conjectures, also strengthening the Laplacian Spread Conjecture, that include a conjecture for simple graphs and a conjecture for weighted graphs.

We investigate connections between the symmetries (automorphisms) of a graph and its spectral properties. Whenever a graph has a symmetry, i.e. a nontrivial automorphism ϕ, it is possible to use ϕ to decompose any matrix M ∈ C n × n appropriately associated with the graph. The result of this decomposition is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. Some of the matrices that can be decomposed are the graph's adjacency matrix, Laplacian matrix, etc. Because this decomposition has connections to the theory of equitable partitions it is referred to as an equitable decomposition. Since the graph structure of many real-world networks is quite large and has a high degree of symmetry, we discuss how equitable decompositions can be used to effectively bound both the network's spectral radius and spectral gap, which are associated with dynamic processes on the network. Moreover, we show that the techniques used to equitably decompose a graph can be used to bound the number of simple eigenvalues of undirected graphs, where we obtain sharp results of Petersdorf–Sachs type.

A spanning 2-forest separating vertices u and v of an undirected connected graph is a spanning forest with 2 components such that u and v are in distinct components. Aside from their combinatorial significance, spanning 2-forests have an important application to the calculation of resistance distance or effective resistance. The resistance distance between vertices u and v in a graph representing an electrical circuit with unit resistance on each edge is the number of spanning 2-forests separating u and v divided by the number of spanning trees in the graph. There are also well-known matrix theoretic methods for calculating resistance distance, but the way in which the structure of the underlying graph determines resistance distance via these methods is not well understood. For any connected graph G with a 2-separator separating vertices u and v , we show that the number of spanning trees and spanning 2-forests separating u and v can be expressed in terms of these same quantities for the smaller separated graphs, which makes computation significantly more tractable. An important special case is the preservation of the number of spanning 2-forests if u and v are in the same smaller graph. In this paper we demonstrate that this method of calculating resistance distance is more suitable for certain structured families of graphs than the more standard methods. We apply our results to count the number of spanning 2-forests and calculate the resistance distance in a family of Sierpinski triangles and in the family of linear 2-trees with a single bend.

For a given graph $G$ and an associated class of real symmetric matrices whose diagonal entries are governed by the adjacencies in $G$, the collection of all possible spectra for such matrices is considered. Building on the pioneering work of Colin de Verdière in connection with the Strong Arnold Property, two extensions are devised that target a better understanding of all possible spectra and their associated multiplicities. These new properties are referred to as the Strong Spectral Property and the Strong Multiplicity Property. Finally, these ideas are applied to the minimum number of distinct eigenvalues associated with $G$, denoted by $q(G)$. The graphs for which $q(G)$ is at least the number of vertices of $G$ less one are characterized.

We consider the graph G n with vertex set V ( G n ) = { 1 , 2 , … , n } and { i , j } ∈ E ( G n ) if and only if 0 | i − j | ≤ 2 . We call G n the straight linear 2-tree on n vertices. Using Δ –Y transformations and identities for the Fibonacci and Lucas numbers we obtain explicit formulae for the resistance distance r G n ( i , j ) between any two vertices i and j of G n . To our knowledge { G n } n = 3 ∞ is the first nontrivial family with diameter going to ∞ for which all resistance distances have been explicitly calculated. Our result also gives formulae for the number of spanning trees and 2-forests in a straight linear 2-tree. We show that the maximal resistance distance in G n occurs between vertices 1 and n and the minimal resistance distance occurs between vertices n ∕ 2 and n ∕ 2 + 1 for n even (with a similar result for n odd). It follows that r n ( 1 , n ) → ∞ as n → ∞ . Moreover, our explicit formula makes it possible to order the non-edges of G n exactly according to resistance distance, and this ordering agrees with the intuitive notion of distance on a graph. Consequently, G n is a geometric graph with entirely different properties than the random geometric graphs investigated in Luxburg, Radl and Hein (2010). These results for straight linear 2-trees along with an example of a bent linear 2-tree and empirical results for additional graph classes convincingly demonstrate that resistance distance should not be discounted as a viable method for link prediction in geometric graphs.

Given an n × n matrix, its principal rank characteristic sequence is a sequence of length n + 1 of 0s and 1s where, for k = 0 , 1 , … , n , a 1 in the kth position indicates the existence of a principal submatrix of rank k and a 0 indicates the absence of such a submatrix. The principal rank characteristic sequences for symmetric matrices over various fields are investigated, with all such attainable sequences determined for all n over any field with characteristic 2. A complete list of attainable sequences for real symmetric matrices of order 7 is reported.

Let F be a field, let G be an undirected graph on n vertices, and let SF(G) be the class of all F-valued symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. For each graph G, there is an associated minimum rank class MRF(G) consisting of all matrices A∈SF(G) with rankA=mrF(G). For most graphs G with connectivity 1 or 2, we give explicit decompositions of matrices in MRF(G) into sums of minimum rank matrices of simpler graphs (usually proper subgraphs) related to G. Our results can be thought of as generalizations of well-known formulae for the minimum rank of a graph with a cut vertex and of a graph with a 2-separation. We conclude by also showing that for these graphs, matrices in MRF(G) can be constructed from matrices of simpler graphs; moreover, we give analogues for positive semidefinite matrices.

Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdiere type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d'arborescence, path-width, and proper path-width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.

The minimum rank of a graph has been an interesting and well studied parameter investigated by many researchers over the past decade or so. One of the many unresolved questions on this topic is the so-called graph complement conjecture, which grew out of a workshop in 2006. This conjecture asks for an upper bound on the sum of the minimum rank of a graph and the minimum rank of its complement, and may be classified as a Nordhaus–Gaddum type problem involving the graph parameter minimum rank. The conjectured bound is the order of the graph plus two. Other variants of the graph complement conjecture are introduced here for the minimum semidefinite rank and the Colin de Verdiere type parameter ν . We show that if the ν -graph complement conjecture is true for two graphs then it is true for the join of these graphs. Related results for the graph complement conjecture (and the positive semidefinite version) for joins of graphs are also established. We also report on the use of recent results on partial k-trees to establish the graph complement conjecture for graphs of low minimum rank.

We consider the problem of computing inertia sets for graphs. By using tools for combining the inertia sets of smaller graphs we can reduce this problem to understanding the inertia sets for three-connected graphs that are not joins. We term such graphs atoms and give the inertia sets for all atoms on at most seven vertices. This can be used to compute the inertia sets for all graphs on at most seven vertices.

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity / minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z_+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented., Comment: 14 pages, 2 figures. To appear in Linear Algebra and its Applications.

Let G be an undirected graph on n vertices and let S ( G ) be the set of all real symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G . The inverse inertia problem for G asks which inertias can be attained by a matrix in S ( G ) . We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.

Our main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field., Comment: 40 pages, added Sage program and improvements from referee process

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.

Let R be the real numbers and R n the vector space of all column vectors of length n . Let C n be the convex set of all real correlation matrices of size n . If V is a subspace of R n of dimension k , we consider the face F V of C n consisting of all A∈ C n such that V⊂ N (A) , i.e., AV= 0 . If F V is nonempty, we say that V is realizable. We give complete geometric descriptions of F V in the cases k =1, n =4, and k =2, n =5. For k =2, n =5, we provide a simple algebraic method for describing F V .

Let G be a simple undirected graph on n vertices and let S(G) be the class of real symmetric n by n matrices whose nonzero off-diagonal entries correspond to the edges of G. Given 2n - 1 real numbers \lambda_1\geq \mu_1 \geq \lambda_2 \geq \mu_2 \geq \cdots \geq \lambda_{n-1} \geq \mu_{n-1} \geq \lambda_{n-1}, and a vertex v of G, the question is addressed of whether or not there exists A in S(G) with eigenvalues \lambda_1, \ldots, \lambda_ n such that A(v) has eigenvalues \mu_1, \ldots, \mu_{n-1}, where A(v) denotes the matrix with vth row and column deleted. A complete solution can be given for the path on n vertices with v a pendant vertex and also for the star on n vertices with v the dominating vertex. The main result is a complete solution to this "\lambda, \mu" problem for all connected graphs on 4 vertices.

Barrett et al. asked in [W. Barrett et al. Minimum rank of edge subdivisions of graphs. Electronic Journal of Linear Algebra, 18:530–563, 2009.], whether the maximum nullity is equal to the zero forcing number for all complete subdivision graphs. We prove that this equality holds. Furthermore, we compute the value of M(F, G) = Z(G) by introducing the bridge tree of a connected graph. Since this equality is valid for all fields, G has field independent minimum rank, and we also show that G has a universally optimal matrix.

Among various matrix completion problems that have been considered in recent years, the positive definite completion problem seems to have received the most attention. Indeed, in addition to being a problem of great interest, it is related to various applications as well as other completion problems. It may also be viewed as a fundamental problem in Euclidean geometry. A partial positive definite matrix A is "critical" if A has no positive definite completion, though every proper principal submatrix does. The graph G is called critical for the positive definite completion problem if there is a critical partial positive definite matrix A, the graph of whose specified entries is G. Complete analytical understanding of the general positive definite completion problem reduces to understanding the problem for critical graphs. Thus, it is important to try to characterize such graphs. The first, crucial step toward that understanding is taken here. A novel and restrictive topological graph theoretic condition necessary for criticality is identified. The condition, which may also be of interest on pure graph theoretic grounds, is also shown to be sufficient for criticality of graphs on fewer than 7 vertices, and the authors suspect it to be sufficient in general. In any event, the condition, which may be efficiently verified, dramatically narrows the class of graphs for which completability conditions on the specified data are needed. The concept of criticality and the graph theoretic condition extend to other completion problems, such as that for Euclidean distance matrices.

We establish the bounds $\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are the Nordhaus-Gaddum sum upper bound multipliers, i.e., $\nu(G)+\nu(\overline{G})\le b_\nu |G|$ and $\xi(G)+\xi(\overline{G})\le b_\xi | G|$ for all graphs $G$, and $\nu$ and $\xi$ are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for $\nu$ and $\xi$ is conjectured to be $|G| - 2$, and if these parameters are replaced by the maximum nullity $M(G)$, this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.

Let F be a field, let G be a simple graph on n vertices, and let S (G) be the class of all F -valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. For each graph G, there is an associated minimum rank class, M R (G) consisting of all matrices A ∈ S (G) with rankA = mr (G), the minimum rank among all matrices in S (G). Although no restrictions are applied to the diagonal entries of matrices in S (G), this work explores when the diagonal entries corresponding to specific vertices of G must be zero or nonzero for all matrices A ∈ M R (G). These vertices are denoted as nil or nonzero, respectively. Vertices whose corresponding diagonal entries are not similarily restricted for all matrices in M R (G) are called neutral. The minimum rank of a graph following an edge-subdivision is determined by the existence of a nil vertex, and several relations between diagonal restrictions and the rank-spread parameter are found. This is followed by the rather different approach of using the graph parameter Ẑ to identify nil and nonzero vertices. The nil, nonzero and neutral vertices of trees are classified in terms of rank-spread. Finally, it is shown that except for K3, 2-connected graphs with maximum nullity 2 have all neutral vertices and, moreover, the graphs with maximum nullity 2 that have nil or nonzero vertices are completely classified.

Several inequalities relating the rank of a positive semidefinite matrix with the ranks of various principal submatrices are presented. These inequalities are analogous to known determinantal inequalities for positive definite matrices, such as Fischer's inequality, Koteljanskii's inequality, and extensions of these associated with chordal graphs.

A complete solution of the matrix completion problem A ? ? B −1 = ? C D ? is obtained in terms of solutions of a Riccati-type matrix equation. Several special cases are described in detail.

Let G be an undirected graph on n vertices and let S(G) be the set of all real sym- metric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(G) denote the minimum rank of all matrices in S(G), and mr+(G) the minimum rank of all positive semidefinite matrices in S(G). All graphs G with mr(G) = 2 and mr+(G) = k are characterized; it is also noted that mr+(G) = α(G) for such graphs. This charac- terization solves the inverse inertia problem for graphs whose minimum rank is two. Furthermore, it is determined which diagonal entries are required to be zero, are required to be nonzero, or can be either for a rank minimizing matrix in S(G) when mr(G) = 2. Collectively, these results lead to a solution to the inverse eigenvalue problem for rank minimizing matrices for graphs whose minimum rank is two.

We consider the question of whether a real partial positive definite matrix (in which the specified off-diagonal entries consist of a full n-cycle) has a positive definite completion. This lies in contrast to the previously studied chordal case. We give two solutions. In one, we describe about n/2 independent conditions on angles associated with a normalization of the data that are necessary and sufficient. The second is more computational and allows presentation of all positive definite completions, as well as answering the existence question.

Given a complex n-by-n matrix A, and α⊆{1,2,…,n} denote by A[α] the principal submatrix of A lying in the rows and columns indicated by α. For a partition k=(k 1,…,kp ) of n k 1≥ċ≥kp , Σki =n, into p nonnegative integers, we define the symmetrized Fischer product If A is positive definite, each product in the sum is an upper bound for detA by Fischer's inequality. Thus, if we let be the normalized sum (Sk (A) divided by the number of terms in the sum) we have for each partition k. It is natural to ask what the relationship between these bounds is as k varies. Our main result is: for all positive definite matrices A if and only if k majorizes l. This resolves affirmatively a conjecture (the case p=2) that the authors made some time ago.

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G), a question which was previously answered when G is a tree. In this paper, a number of new techniques are developed in order to be able to determine possible inertias of general graphs: covers with cliques, covers with cliques and clique-stars, and the graph operations of edge subdivision, edge deletion, joins, and unions. Because most of the associated theorems require additional hypotheses, definitive criteria that apply to all graphs cannot be provided. Nevertheless, these results are strong enough to be able to determine the inertia set of each graph on 6 or fewer vertices and can be applied to many graphs with larger order as well. One consequence of the 1–6 vertex results is the fact that all of these graphs have balanced inertia. It is also mentioned which of these results guarantee or preserve balanced inertia, and explain how to modify them to include Hermitian matrices.

Define n × n matrices D n = ( d ij ) and C n = ( c ij ) by d ij = 1 if i | j , 0 otherwise, and C n = (0, 1, 1,…,1) T (1, 0, 0,…,0). Let A n = D n + C n . The matrix is of number-theoretic significance because det A n = M ( n ) is Mertens' function. We give a simplified derivation of the characteristic polynomial of A n , give precise asymptotic estimates for its two “large” eigenvalues, and use Rouche's theorem to significantly improve a previous bound on its “small” eigenvalues. Finally, we present some attractive conjectures about these small eigenvalues based on numerical evidence.

An n × n real matrix T ∈ Mk if T=D+A where D is diagonal and rank.A= k. For 0 ≤ k ≤ n − 1 and A diagonally symmetrizable, we prove that all but k eigenvalues of T lie in the closed interval between the minimum and maximum diagonal entry of D, but show that no such result holds for general A. This answers an open problem posed by Furth and Sierksma. We also correct their proof of the result that .

Let F be a finite field, G =( V, E) be an undirected graph on n vertices, and let S(F, G) be the set of all symmetric n × n matrices over F whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G.L et mr(F, G) be the minimum rank of all matrices in S(F, G). If F is a finite field with p t elements, p � , it is shown that mr(F, G) ≤ 2i f and only if the complement of G is the join of a complete graph with either the union of at most (p t +1)/2 nonempty complete bipartite graphs or the union of at most two nonempty complete graphs and of at most (p t − 1)/2 nonempty complete bipartite graphs. These graphs are also characterized as those for which 9 specific graphs do not occur as induced subgraphs. If F is a finite field with 2t elements, then mr(F, G) ≤ 2 if and only if the complement of G is the join of a complete graph with either the union of at most 2t + 1 nonempty complete graphs or the union of at most one nonempty complete graph and of at most 2 t−1 nonempty complete bipartite graphs. A list of subgraphs that do not occur as induced subgraphs is provided for this case as well.

Let F be a field, G =( V, E) be an undirected graph on n vertices, and let S(F, G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. For example, if G is a path, S(F, G )co nsists of the symmetric irreducible tridiagonal matrices. Let mr(F, G) be the minimum rank over all matrices in S(F, G). Then mr(F, G) = 1 if and only if G is the union of a clique with at least 2 vertices and an independent set. If F is an infinite field such that charF � , then mr(F, G) ≤ 2i f and only if the complement of G is the join of a clique and a graph that is the union of at most two cliques and any number of complete bipartite graphs. A similar result is obtained in the case that F is an infinite field with char F = 2. Furthermore, in each case, such graphs are characterized as those for which 6 specific graphs do not occur as induced subgraphs. The number of forbidden subgraphs is reduced to 4 if the graph is connected. Finally, similar criteria is obtained for the minimum rank of a Hermitian matrix to be less than or equal to two. The complement is the join of a clique and a graph that is the union of any number of cliques and any number of complete bipartite graphs. The number of forbidden subgraphs is now 5, or in the connected case, 3.

Let M n (F) denote the set of n-by-n matrices over the field F. We consider the following question: Among matrices A ∈ M n (F) with rank A = k < n, how many diagonal entries of A must be changed, at worst, in order to guarantee that the rank of A is increased. Our initial motivation arose from an error pointed out in [BOvdD], but we also view this problem as intrinsically important. The simplest example that shows that one entry does not suffice is the familiar Jordan block \( \left[ \begin{gathered} 0 1 \hfill \\ 0 0 \hfill \\ \end{gathered} \right]. \)

1. In their paper “Permutation Problems and Special Functions,” Askey and Ismail [1] give the following striking identity. Consider three boxes containing j, k, m distinguishable balls, and consider all possible rearrangements of these balls such that each box still has the same number of balls; i.e., j end up in the first, k in the second, m in the third. One disregards the order of the balls within a box so there are (j + k + m)!/(j!k!m!) possible rearrangements. Let RE be the number of rearrangements where an even number of balls change boxes and R0 the number of rearrangements where an odd number change boxes. The identity is(1.1)where(1.2)is the jth Laguerre polynomial. These polynomials are orthonormal with respect to the weight function e–x; i.e.

In this paper we use the properties of the covariance matrix of a Gaussian Markovian family to give a probabilistic proof of a theorem about inverses of tridiagonal matrices.