Search

Schur decompositions and the corresponding Schur forms of a single matrix, a pair of matrices, or a collection of matrices associated with the periodic eigenvalue problem are frequently used and studied. These forms are upper-triangular complex matrices or quasi-upper-triangular real matrices that are equivalent to the original matrices via unitary or, respectively, orthogonal transformations. In general, for theoretical and numerical purposes we often need to reduce, by admissible transformations, a collection of matrices to the Schur form. Unfortunately, such a reduction is not always possible. In this paper we describe all collections of complex (real) matrices that can be reduced to the Schur form by the corresponding unitary (orthogonal) transformations and explain how such a reduction can be done. We prove that this class consists of the collections of matrices associated with pseudoforest graphs. In other words, we describe when the Schur form of a collection of matrices exists and how to find it. [ABSTRACT FROM AUTHOR]

We consider a Leibniz algebra L = I ⊕ V over an arbitrary base field F , being I the ideal generated by the products [ x , x ] , x ∈ L . This ideal has a fundamental role in the study presented in our paper. A basis B = { v i } i ∈ I of L is called multiplicative if for any i , j ∈ I we have that [ v i , v j ] ∈ F v k for some k ∈ I. We associate an adequate graph Γ (L , B) to L relative to B . By arguing on this graph we show that L decomposes as a direct sum of ideals, each one being associated to one connected component of Γ (L , B). Also the minimality of L and the division property of L are characterized in terms of the weak symmetry of the defined subgraphs Γ (L , B I ) and Γ (L , B V ). [ABSTRACT FROM AUTHOR]

The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U = c 1 A + c 2 D + c 3 I + c 4 J , with c i ∈ R and c 1 ≠ 0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

The space of derivations of finite dimensional evolution algebras associated to graphs over a field with characteristic zero has been completely characterized in the literature. In this work we generalize that characterization by describing the derivations of this class of algebras for fields of any characteristic. [ABSTRACT FROM AUTHOR]

We study the existence of quantum state transfer on non-integral circulant graphs. We find that continuous-time quantum walks on quantum networks based on certain circulant graphs with 2 k k ∈ Z vertices exhibit pretty good state transfer when there is no external dynamic control over the system. We generalize a few previously known results on pretty good state transfer on circulant graphs, and this way we re-discover all integral circulant graphs on 2 k vertices exhibiting perfect state transfer. [ABSTRACT FROM AUTHOR]

We investigate the change in the multiplicities of an eigenvalue of an Hermitian matrix whose graph is a general undirected graph, when an edge is removed from the graph. The same question when the graph is a tree has been investigated in prior work. Here, we give possible classifications of edges in a general graph in terms of the statuses of adjacent vertices. It turns out that there are four cases that do occur in a general graph but cannot occur in a tree. [ABSTRACT FROM AUTHOR]

Evolution algebras are non-associative algebras inspired from biological phenomena, with applications to or connections with different mathematical fields. There are two natural ways to define an evolution algebra associated to a given graph. While one takes into account only the adjacencies of the graph, the other includes probabilities related to the symmetric random walk on the same graph. In this work we state new properties related to the relation between these algebras, which is one of the open problems in the interplay between evolution algebras and graphs. On the one hand, we show that for any graph both algebras are strongly isotopic. On the other hand, we provide conditions under which these algebras are or are not isomorphic. For the case of finite non-singular graphs we provide a complete description of the problem, while for the case of finite singular graphs we state a conjecture supported by examples and partial results. The case of graphs with an infinite number of vertices is also discussed. As a sideline of our work, we revisit a result existing in the literature about the identification of the automorphism group of an evolution algebra, and we give an improved version of it. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with m edges. Denote by D (G) the diagonal matrix of its vertex degrees and by A (G) its adjacency matrix. Then the signless Laplacian matrix of G is Q (G) = D (G) + A (G). Let q 1 ≥ q 2 ≥ ⋯ ≥ q n be the signless Laplacian eigenvalues of graph G and also let ν = ν (G) (1 ≤ ν ≤ n) be the largest positive integer such that q ν ≥ 2 m / n . Denote by G ¯ the complement graph of graph G. If G ≆ K n , K ¯ n , K n − 1 ∪ K 1 , K 1 , n − 1 , K n − e , K 2 ∪ (n − 2) K 1 , then we prove that q 2 (G) + q 2 (G ¯) ≥ n − 1. Moreover, if G ≆ K 1 , n − 1 , K n − 1 ∪ K 1 , K n − e , K 2 ∪ (n − 2) K 1 , then ν + ν ¯ ≥ 3. [ABSTRACT FROM AUTHOR]

The affine group scheme of automorphisms of an evolution algebra E with E 2 = E is shown to lie in an exact sequence 1 → D → A u t (E) → S , where D , diagonalizable, and S , constant, depend solely on the directed graph associated to E . As a consequence, the Lie algebra of derivations D e r (E) (with E 2 = E ) is shown to be trivial if the characteristic of the ground field is 0 or 2, and to be abelian, with a precise description, otherwise. [ABSTRACT FROM AUTHOR]

It is well-known that the space of derivations of n-dimensional evolution algebras with non-singular matrices is zero. On the other hand, the space of derivations of evolution algebras with matrices of rank n−1 have also been completely described in the literature. In this work, we provide a complete description of the space of derivations of evolution algebras associated to graphs, depending on the twin partition of the graph. For graphs without twin classes with at least three elements, we prove that the space of derivations of the associated evolution algebra is zero. Moreover, we describe the spaces of derivations for evolution algebras associated to the remaining families of finite graphs. It is worth pointing out that our analysis includes examples of finite dimensional evolution algebras with matrices of any rank. [ABSTRACT FROM AUTHOR]

We are interested in the geometric multiplicity of an identified eigenvalue of a matrix A over a general field with a given graph G for its off-diagonal entries. By the classification of a vertex (edge) of G, we refer to the change in the geometric multiplicity of when this vertex (edge) is removed from G to leave a principal submatrix (modification) of A. Such classification in the case of Hermitian matrices and trees has been strategic in the problem of determining the possible lists of multiplicities for the eigenvalues among matrices with the given graph. Here, our view of, and qualification of, the classification in the general setting provides a tool that makes some past arguments more transparent and provides new insight in both the classical and general setting. Some applications are given to general downer mechanisms for the recognition of Parter vertices and to the stability of geometric multiplicity under perturbation of a diagonal entry. [ABSTRACT FROM AUTHOR]

Let be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph. [ABSTRACT FROM PUBLISHER]

In this paper, we obtain the sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. We also apply these bounds to various matrices associated with a graph or a digraph, obtain some new results or known results about various spectral radii, including the adjacency spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph. [ABSTRACT FROM AUTHOR]

Letandbereal numbers that satisfy the strict second-order Cauchy interlacing inequalitiesforand the nondegeneracy conditionsfor. Given a connected graphonvertices with adjacent verticesand, it is proven that there is a real symmetric matrixwhose graph issuch thathas eigenvaluesandhas eigenvalues, provided some necessary combinatorial conditions onare satisfied. We also provide generalizations when the two deleted vertices are not adjacent, as well as interpretation of the results in terms of perturbing one or two diagonal entries. [ABSTRACT FROM PUBLISHER]

For-matrices in general, and for-matrices with a constant numberof 1s in each row and column, we determine the possible sets of traces of such matrices as its rows are permuted. Except for some special matrices, which are identified, the set of such traces is a consecutive set of integers from. [ABSTRACT FROM AUTHOR]

We classify the trees for which there is a nonsingular matrix where each vertex is a P-vertex. In particular, we show that such trees have an even number of vertices. Both results provide answers to questions proposed by Kim and Shader. In the end, related classifications on nonsingular trees with the size of a P-set bounded are addressed. [ABSTRACT FROM AUTHOR]

Let 𝒯(n, m) and ℱ(n, m) denote the classes of weighted trees and forests, respectively, of order n with the positive integral weights and the fixed total weight sum m, respectively. In this article, we determine the minimum energies for both the classes 𝒯(n, m) and ℱ(n, m). We also determine the maximum energy for the class ℱ(n, m). In all cases, we characterize the weighted graphs whose energies reach these extremal values. We also solve the similar maximum energy and minimum energy problems for the classes of (0, 1) weighted trees and forests. [ABSTRACT FROM AUTHOR]

We investigate the relation between perturbing the i-th diagonal entry of A ∈ ℳ n (𝔽) and extracting the principal submatrix A(i) from A with respect to the possible changes in multiplicity of a given eigenvalue. A complete description is given and used to both generalize and improve prior work about Hermitian matrices whose graph is a given tree. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and L(G) be its Laplacian matrix. In this note, we prove that L(G) is congruent by a unimodular matrix to its Smith normal form if and only if G is a tree. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n vertices, m edges, diameter D and degree sequence d1, d2, ..., dn, and let λ1(G) be the largest Laplacian eigenvalue of G. Denote Δ = max{di : 1 ≤ i ≤ n}, [image omitted] and [image omitted], where α is a real number. In this article, we first give an upper bound on λ1(G) for a non-regular graph involving Δ and D; next present two upper bounds on λ1(G) for a connected graph in terms of di and (αm)i; at last obtain a lower bound on λ1(G) for a connected bipartite graph in terms of di and (αt)i. Some known results are shown to be the consequences of our theorems. [ABSTRACT FROM AUTHOR]

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties. [ABSTRACT FROM AUTHOR]

Characterized are all simple undirected graphs G such that any real symmetric matrix that has graph G has no eigenvalues of multiplicity more than 2. All such graphs are partial 2-trees (and this follows from a result for rather general fields), but only certain partial 2-trees guarantee maximum multiplicity 2. Among partial linear 2-trees, they are only those whose vertices can be covered by two 'parallel' induced paths. The remaining graphs that guarantee maximum multiplicity 2 are composed of certain identified families of 'exceptional' partial 2-trees that are not linear. [ABSTRACT FROM AUTHOR]

Let G be the automorphism group of a graph Γ and let λ be an eigenvalue of the adjacency matrix of Γ. In this article, (i) we derive an upper bound for rank(G), (ii) if G is vertex transitive, we derive an upper bound for the extension degree of (λ) over , (iii) we study automorphism groups of graphs without multiple eigenvalues, (iv) we study spectra of quotient graphs associated with orbit partitions. [ABSTRACT FROM AUTHOR]

We are generally concerned with the possible lists of multiplicities for the eigenvalues of a real symmetric matrix with a given graph. Many restrictions are known, but it is often problematic to construct a matrix with desired multiplicities, even if a matrix with such multiplicities exists. Here, we develop a technique for construction using the implicit function theorem in a certain way. We show that the technique works for a large variety of trees, give examples and determine all possible multiplicities for a large class of trees for which this was not previously known. [ABSTRACT FROM AUTHOR]

In 7 (Johnson, C.R., Kroschel, B.K. and Lundquist, M., 1998, The totally nonnegative completion problem. In: P.M. Pardalos and H. Wolkowicz (Eds) Fields Institute Communications: Topics in Semidefinite and Interior Point Methods (Providence: AMS), pp. 97-108.), the labeled graphs G for which every combinatorially symmetric partial totally nonnegative (TN) matrix, the graph of whose specified entries is G, has a TN completion were identified. In this study, a technical assumption is removed from that work, and the implication is that for other graphs, additional conditions on the specified data must hold. Here, we begin the investigation of what those additional conditions are and for what graphs they suffice. For 3-by-3 partial matrices a complete solution is given, and the 'adjacent edge conditions' that arise in the 3-by-3 case are shown to suffice for certain other classes of graphs. Conditions for each of the 24 labeled paths on four vertices are also derived. [ABSTRACT FROM AUTHOR]

The transversals of a complex square matrix and the isolated set of transversals were used in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373) to study the ray-nonsingular matrices and the determinantal regions of square ray pattern matrices. Some necessary conditions of the isolated sets of transversals were obtained in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373). A characterization of the isolated sets of transversals in an important special case was also given in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373). The study of the isolated set of transversals is indeed equivalent to the study of the isolated set of permutations on the set {1, .., n}. In this article, we give a graph theoretical characterization of the isolated set of permutations. We also give an application of this characterization in a problem concerning the linear independence of the set of permutation matrices contained in a given square (0, 1) matrix. [ABSTRACT FROM AUTHOR]

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is called extremal . We also describe some properties and examples of extremal graphs. [ABSTRACT FROM AUTHOR]

Let A ( G ) be a Hermitian matrix whose graph is a given graph G . From the interlacing theorem, it is known that , where is the multiplicity of the eigenvalue???of A ( G ). In this note we improve this inequality for some paths with more than one vertex. [ABSTRACT FROM AUTHOR]

In this article, we present lower bounds for the largest eigen value, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph. [ABSTRACT FROM AUTHOR]

In this article, we determine upper bounds for the permanent of the adjacency matrix of a graph with cut vertices in terms of the order of the graph and the number of its cut vertices. [ABSTRACT FROM AUTHOR]

This article gives a survey of those results in the theory of graph spectra which can be described as characteriza-tions of sets of all graphs G such that both the graph G and its complement have a prescribed property. [ABSTRACT FROM AUTHOR]

In this article, two necessary conditions for a graph to have an equality of the second largest Laplacian eigenvalue λ 2 ( G ) and its lower bound d 2 ( G ) are presented. Some of the graphs who satisfy λ 2 ( G )= d 2 ( G ) are also described. [ABSTRACT FROM AUTHOR]