On the second largest Laplacian eigenvalues of graphs

The second largest Laplacian eigenvalue of a graph is the second largest eigenvalue of the associated Laplacian matrix. In this paper, we study extremal graphs for the extremal values of the second largest Laplacian eigenvalue and the Laplacian separator of a connected graph, respectively. All simple connected graphs with second largest Laplacian eigenvalue at most 3 are characterized. It is also shown that graphs with second largest Laplacian eigenvalue at most 3 are determined by their Laplacian spectrum. Moreover, the graphs with maximum and the second maximum Laplacian separators among all connected graphs are determined.     

Bounds for the second largest eigenvalue of a transition matrix

We find an upper bound, with general form, for the second largest eigenvalue of a transition matrix; special cases of which have previously been proposed as upper bounds and others which are new improvements.     

Variational analysis of convexly generated spectral max functions

Mathematical Programming - The spectral abscissa is the largest real part of an eigenvalue of a matrix and the spectral radius is the largest modulus. Both are examples of spectral max...     

Rank 1 real Wishart spiked model

In this paper, we consider N‐dimensional real Wishart matrices Y in the class \input amssym $W_{\Bbb R} (\Sigma ,M)$ in which all but one eigenvalue of Σ is 1. Let the nontrivial eigenvalue of Σ be 1+τ; then as N, M → ∞, with M/N → γ² finite and nonzero, the eigenvalue distribution of Y will converge into the Marchenko‐Pastur distribution inside a bulk region. When τ increases from 0, one starts to see a stray eigenvalue of Y outside of the support of the Marchenko‐Pastur density. As this stray eigenvalue leaves the bulk region, a phase transition will occur in the largest eigenvalue distribution of the Wishart matrix. In this paper we will compute the asymptotics of the largest eigenvalue distribution when the phase transition occurs. We will first establish the results that are valid for all N and M and will use them to carry out the asymptotic analysis. In particular, we have derived a contour integral formula for the Harish‐Chandra Itzykson‐Zuber integral $\int_{O(N)} {e^{{\rm tr}(XgYg^{\rm T} )} } g^{\rm T} dg$ when X and Y are real symmetric and Y is a rank 1 matrix. This allows us to write down a Fredholm determinant formula for the largest eigenvalue distribution and analyze it using orthogonal polynomial techniques. As a result, we obtain an integral formula for the largest eigenvalue distribution in the large‐ N limit characterized by Painlevé transcendents. The approach used in this paper is very different from a recent paper by Bloemenal and Virág, in which the largest eigenvalue distribution was obtained using a stochastic operator method. In particular, the Painlevé formula for the largest eigenvalue distribution obtained in this paper is new. © 2012 Wiley Periodicals, Inc.     

A general steady state distribution based stopping criteria for finite length genetic algorithms

We propose two general stopping criteria for finite length, simple genetic algorithms based on steady state distributions, and empirically investigate the impact of mutation rate, string length, crossover rate and population size on their convergence. Our first stopping criterion is based on the second largest eigenvalue of the genetic algorithm transition matrix, and the second stopping criterion is based on minorization conditions.     

The largest two Laplacian eigenvalues of a graph

In this article, we present lower bounds for the largest eigenvalue, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph.     

The largest two Laplacian eigenvalues of a graph

In this article, we present lower bounds for the largest eigenvalue, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

Recursive estimation for ordered eigenvectors of symmetric matrix with observation noise

The principal component analysis is to recursively estimate the eigenvectors and the corresponding eigenvalues of a symmetric matrix A based on its noisy observations Ak=A+Nk, where A is allowed to have arbitrary eigenvalues with multiplicity possibly bigger than one. In the paper the recursive algorithms are proposed and their ordered convergence is established: It is shown that the first algorithm a.s. converges to a unit eigenvector corresponding to the largest eigenvalue, the second algorithm a.s. converges to a unit eigenvector corresponding to either the second largest eigenvalue in the case the largest eigenvalue is of single multiplicity or the largest eigenvalue if the multiplicity of the largest eigenvalue is bigger than one, and so on. The convergence rate is also derived.     

A note on the second largest eigenvalue of the laplacian matrix of a graph

In this note, a lower bound for the second largest eigenvalue of the Laplacian matrix of a graph is given in terms of the second largest degree of the graph.     

A note on the second largest eigenvalue of the laplacian matrix of a graph ∗

In this note, a lower bound for the second largest eigenvalue of the Laplacian matrix of a graph is given in terms of the second largest degree of the graph.     

An inexact inverse iteration for large sparse eigenvalue problems

In this paper, we propose an inverse inexact iteration method for the computation of the eigenvalue with the smallest modulus and its associated eigenvector for a large sparse matrix. The linear systems of the traditional inverse iteration are solved with accuracy that depends on the eigenvalue with the second smallest modulus and iteration numbers. We prove that this approach preserves the linear convergence of inverse iteration. We also propose two practical formulas for the accuracy bound which are used in actual implementation. © 1997 John Wiley & Sons, Ltd.     

双圈图的无符号拉普拉斯谱半径和谱展

The signless Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the smallest eigenvalue of its signless Laplacian matrix. In this paper, we determine the first to llth largest signless Laplacian spectral radii in the class of bicyclic graphs with n vertices. Moreover, the unique bicyclic graph with the largest or the second largest signless Laplacian spread among the class of connected bicyclic graphs of order n is determined, respectively.     

Universality of the double scaling limit in random matrix models

We study unitary random matrix ensembles in the critical case where the limiting mean eigenvalue density vanishes quadratically at an interior point of the support. We establish universality of the limits of the eigenvalue correlation kernel at such a critical point in a double scaling limit. The limiting kernels are constructed out of functions associated with the second Painlevé equation. This extends a result of Bleher and Its for the special case of a critical quartic potential. The two main tools we use are equilibrium measures and Riemann‐Hilbert problems. In our treatment of equilibrium measures we allow a negative density near the critical point, which enables us to treat all cases simultaneously. The asymptotic analysis of the Riemann‐Hilbert problem is done with the Deift‐Zhou steepest‐descent analysis. For the construction of a local parametrix at the critical point we introduce a modification of the approach of Baik, Deift, and Johansson so that we are able to satisfy the required jump properties exactly. © 2005 Wiley Periodicals, Inc.     

More on Graph Perturbations

Various modifications of a connected graph G are regarded asperturbations of an adjacency matrix A of G. Several resultsconcerning the resulting changes to the largest eigenvalue ofA are obtained by solving intermediate eigenvalue problems ofthe second type.     

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

Some notes on graphs whose second largest eigenvalue is less than (√5-1)/2

It is well known in spectral graph theory that all (connected) graphs except complete graphs and complete multi-partite graphs have second largest eigenvalue greater than 0. Graphs whose second larges eigenvalue does not exceed 1/3 are characterized in [2]. Some characterizations of graphs whose second largest eigenvalue does not exceed (√5-1)/2 are given in [9]. In this paper we prove that graphs whose second largest eigenvalue is less than (√5-1)/2 can be characterized by a finite collection of forbidden (induced) subgraphs.     

Perturbation theory of selfadjoint matrices and sign characteristics under generic structured rank one perturbations

For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in the sense of algebraic geometry. Special attention is paid to the perturbation behavior of the sign characteristic. Typically, under such a perturbation, for every given eigenvalue, the largest Jordan block of the eigenvalue is destroyed and (in case the eigenvalue is real) all other Jordan blocks keep their sign characteristic. The new eigenvalues, i.e. those eigenvalues of the perturbed matrix that are not eigenvalues of the original matrix, are typically simple, and in some cases information is provided about their sign characteristic (if the new eigenvalue is real). The main results are proved by using the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky canonical form and on general results concerning rank one perturbations obtained.     

第二大根小于1的简单图

设G为n阶简单图,λ2(G)为G的第二大特征根．我们给出了所有使λ2(G)<1 的偶图,以及使λ2(G)<1、围长不小于4的非偶图．     

Using principal eigenvectors of adjacency matrices with added diagonal weights to compose centrality measures and identify bowtie structures for a digraph

Principal eigenvectors of adjacency matrices are often adopted as measures of centrality for a graph or digraph. However, previous principal-eigenvector-like measures for a digraph usually consider only the strongly connected component whose adjacency submatrix has the largest eigenvalue. In this paper, for each and every strongly connected component in a digraph, we add weights to diagonal elements of its member nodes in the adjacency matrix such that the modified matrix will have the new unique largest eigenvalue and corresponding principal eigenvectors. Consequently, we use the new principal eigenvectors of the modified matrices, based on different strongly connected components, not only to compose centrality measures but also to identify bowtie structures for a digraph.