Advanced Search

Let $G$ be a graph on $n$ vertices and let ${\lambda }_1\ge {\lambda }_2\ge ...\ge {\lambda }_n$ be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues $s_k={\sum }_{i=1}^k{\lambda }_i$, for $1\le k\le n$, and show that a typical graph has $s_k\le (e\left(G\right)+k^2)/{(0.99n)}^{1/2}$, where $e\left(G\right)$ is the number of edges of $G$. We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix.

The perturbed Laplacian matrix of a graph $G$ is defined as $L^D=D-A$, where $D$ is any diagonal matrix and $A$ is a weighted adjacency matrix of $G$. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use...

Let $G$ be a $k$-connected graph with $k\ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric...