On products and line graphs of signed graphs, their eigenvalues and energy

In this article we examine the adjacency and Laplacian matrices and their eigenvalues and energies of the general product (non-complete extended p-sum, or NEPS) of signed graphs. We express the adjacency matrix of the product in terms of the Kronecker matrix product and the eigenvalues and energy of the product in terms of those of the factor graphs. For the Cartesian product we characterize balance and compute expressions for the Laplacian eigenvalues and Laplacian energy. We give exact results for those signed planar, cylindrical and toroidal grids which are Cartesian products of signed paths and cycles.We also treat the eigenvalues and energy of the line graphs of signed graphs, and the Laplacian eigenvalues and Laplacian energy in the regular case, with application to the line graphs of signed grids that are Cartesian products and to the line graphs of all-positive and all-negative complete graphs.     

An explicit formula for differences between Laplacian-eigenvector components using coalesced graphs

We obtain an explicit formula for the absolute difference between two eigenvector components for a weighted graph’s Laplacian matrix, in terms of the Laplacian’s eigenvalues as well as the eigenvalues of matrices associated with certain coalesced graphs. We then briefly illustrate two uses of this formula, in analyzing graph modifications.     

Cyclic matrices of weighted digraphs

In this paper, we address several properties of the so-called augmented cyclic matrices of weighted digraphs. These matrices arise in different applications of digraph theory to electrical circuit analysis, and can be seen as an enlargement of basic cyclic matrices of the form BWB^T, where B is a cycle matrix and W is a diagonal matrix of weights. By using certain matrix factorizations and some properties of cycle bases, we characterize the determinant of augmented cyclic matrices, via Cauchy-Binet expansions, in terms of the so-called proper cotrees. In the simpler context defined by basic cyclic matrices, we obtain the dual result of Maxwell’s determinantal expansion for weighted Laplacian (nodal) matrices. Additional relations with nodal matrices are also discussed. We apply this framework to the characterization of the differential-algebraic circuit models arising from loop analysis, and also to the analysis of branch-oriented models of circuits including charge-controlled memristors.     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

On graphs whose Laplacian matrix’s multipartite separability is invariant under graph isomorphism

Normalized Laplacian matrices of graphs have recently been studied in the context of quantum mechanics as density matrices of quantum systems. Of particular interest is the relationship between quantum physical properties of the density matrix and the graph theoretical properties of the underlying graph. One important aspect of density matrices is their entanglement properties, which are responsible for many nonintuitive physical phenomena. The entanglement property of normalized Laplacian matrices is in general not invariant under graph isomorphism. In recent papers, graphs were identified whose entanglement and separability properties are invariant under isomorphism. The purpose of this note is to completely characterize the set of graphs whose separability is invariant under graph isomorphism. In particular, we show that this set consists of K_2,2 and its complement, all complete graphs and no other graphs.     

Oriented hypergraphs: Balanceability

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.     

The Laplacian spectra of graphs with a tree structure

Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n ? 1.     

On the Laplacian Eigenvalues of Signed Graphs

A signed graph is a graph with a sign attached to each edge. This article extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the largest Laplacian eigenvalue of a signed graph is investigated, which generalizes the corresponding results on the largest Laplacian eigenvalue of a graph.     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

Identities for minors of the Laplacian, resistance and distance matrices

It is shown that if L and D are the Laplacian and the distance matrix of a tree respectively, then any minor of the Laplacian equals the sum of the cofactors of the complementary submatrix of D, up to sign and a power of 2. An analogous, more general result is proved for the Laplacian and the resistance matrix of any graph. A similar identity is proved for graphs in which each block is a complete graph on r vertices, and for q-analogues of such matrices of a tree. Our main tool is an identity for the minors of a matrix and its inverse.     

Integer generalized inverses of incidence matrices

Graphical procedures are used to characterize the integral {1}- and {1, 2}-inverses of the incidence matrix A of a digraph, and to obtain a basis for the space of matrices X such that AXA = 0. These graphical procedures also produce the Smith canonical form of A and a full rank factorization of A using matrices with entries from {-1, 0, 1}. It is also shown how the results on incidence matrices of oriented graphs can be used to find generalized inverses of matrices of unoriented bipartite graphs.     

Some results on resistance distances and resistance matrices

In this paper, we obtain formulas for resistance distances and Kirchhoff index of subdivision graphs. An application of resistance distances to the bipartiteness of graphs is given. We also give an interlacing inequality for eigenvalues of the resistance matrix and the Laplacian matrix.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

Commute times for a directed graph using an asymmetric Laplacian

The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.     

Nouveau noyau de Green associé au problème de Poisson–Dirichlet sur un rectangle

This work is focused on the study of a ‘discretization’ method for the Laplacian operator, in the two-dimensional Poisson problem on a rectangle, with Dirichlet boundary conditions. The Laplacian operator is approximated by a block Toeplitz matrix, the blocks of which are Toeplitz matrices again, and a formula of the inverse matrix blocks is given. Then an asymptotic development of the inverse matrix trace and the Toeplitz matrix determinant are obtained. Finally, the continuum expression of the Laplacian operator is found by calculating the ergodic limit of the inverse matrix. A new asymptotic formula for the well known Green function for the Poisson problem that we obtain converges more rapidly than the usual one. To cite this article: J. Chanzy, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Divisible design graphs

A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. Divisible design graphs are a natural generalization of (v,k,λ)-graphs, and like (v,k,λ)-graphs they make a link between combinatorial design theory and algebraic graph theory. The study of divisible design graphs benefits from, and contributes to, both parts. Using information of the eigenvalues of the adjacency matrix, we obtain necessary conditions for existence. Old results of Bose and Connor on symmetric divisible designs give other conditions and information on the structure. Many constructions are given using various combinatorial structures, such as (v,k,λ)-graphs, distance-regular graphs, symmetric divisible designs, Hadamard matrices, and symmetric balanced generalized weighing matrices. Several divisible design graphs are characterized in terms of the parameters.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.