On a Conjecture on a Laplacian Matrix with Distinct Integral Spectrum

In a paper Fallat et al. (J Graph Theory 50 (2005), 162–174) consider the question of the existence of simple graphs on n vertices whose Laplacian matrix has an integral spectrum consisting of simple eigenvalues only in the range , 0 always being, automatically, one of the eigenvalues. They completely characterize the case when n is one of the eigenvalues, but for the case when n is not, they conjecture that there are no such graphs. In that paper it is shown that, indeed, there are no such graphs for . In this paper we show that the conjecture is true for We actually consider the nonexistence of graphs whose Laplacians are realized by more general spectra , with , , , , and , subject to certain trace conditions. We show that, indeed, for sufficiently large n such graphs do not exist. Our methods are both graph theoretical and algebraic. In certain cases we refine the Cauchy interlacing theorem. Finally, rather than work with Laplacians which have nonpositive off‐Diagonal entries, we transform the problems to the realizability of spectra of nonnegative matrices which we term anti‐Laplacians.     

图的代数连通度的界(英文)

本文首先给出了简单图的度序列的平方和的上界,利用这些结果,求出了简单图的代数连通度的几个上下界并确定了它们的临界图。另外,文章也给出了加权图的代数连通度的一个下界。     

Sharp lower bounds for the first eigenvalues of the bi-drifting Laplacian

In the present paper we study some kinds of the problems for the bi-drifting Laplacian operator and get some sharp lower bounds for the first eigenvalue for these eigenvalue problems on compact manifolds with boundary (also called a smooth metric measure space) and weighted Ricci curvature bounded inferiorly.     

Average distance in graphs and eigenvalues

Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree T and the eigenvalues of its Laplacian:

     

Approximate eigensolution of Laplacian matrices for locally modified graph products

Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.     

Perron components and algebraic connectivity for weighted graphs

The algebraic connectivity of a connected graph is the second-smallest eigenvalue of its Laplacian matrix, and a remarkable result of Fiedler gives information on the structure of the eigenvectors associated with that eigenvalue. In this paper, we introduce the notion of a perron component at a vertex in a weighted graph, and show how the structure of the eigenvectors associated with the algebraic connectivity can be understood in terms of perron components. This leads to some strengthening of Fiedler's original result, gives some insights into weighted graphs under perturbation, and allows for a discussion of weighted graphs exhibiting tree-like structure.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Algebraic connectivity of weighted trees under perturbation

We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree.     

Minimizing algebraic connectivity over graphs made with some given blocks

This article describes the structure of the graph minimizing the algebraic connectivity among all connected graphs made with some given blocks with fixed number of pendant blocks, the blocks that have exactly one point of articulation. As an application, we conclude that over all graphs made with given blocks, the algebraic connectivity is minimum for a graph whose block structure is a path.     

Lower bounds of the Laplacian spectrum of graphs based on diameter

Let G be a connected graph of order n. The diameter of G is the maximum distance between any two vertices of G. In the paper, we will give some lower bounds for the algebraic connectivity and the Laplacian spectral radius of G in terms of the diameter of G.     

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

On the lowest eigenvalue of the Hodge Laplacian on compact,negatively curved domains

We study the first eigenvalue of the Laplacian acting on differential forms on a compact Riemannian domain, for the absolute or relative boundary conditions. We prove a series of lower bounds when the domain is starlike or p-convex and the ambient manifold has pinched negative curvature. The bounds are sharp for starlike domains. We then compute the asymptotics of the first eigenvalue of hyperbolic balls of large radius. Finally, we give lower bounds also for Euclidean domains.      

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

The ordering of unicyclic graphs with the smallest algebraic connectivity

Fielder [M. Fielder, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305] has turned out that G is connected if and only if its algebraic connectivity a(G)>0. In 1998, Fallat and Kirkland [S.M. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74] posed a conjecture: if G is a connected graph on n vertices with girth g≥3, then a(G)≥a(C_n,g) and that equality holds if and only if G is isomorphic to C_n,g. In 2007, Guo [J.M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711] gave an affirmatively answer for the conjecture. In this paper, we determine the second and the third smallest algebraic connectivity among all unicyclic graphs with vertices.     

Operators with eigenvalues and extreme cases of stability

In the following, we consider some cases where the point spectrum of an operator is either very stable or very unstable with respect to small perturbations of the operator. The main result is about the shift operator on whose point spectrum is what we will call strongly stable. We also give some general perturbation results, including a result about the size of the set of operators that have an eigenvalue.

     

The effect on the algebraic connectivity of a tree by grafting or collapsing of edges

Let G=(V,E) be a tree on n?2 vertices and let v∈V. Let L(G) be the Laplacian matrix of G and μ(G) be its algebraic connectivity. Let G_k,l, be the graph obtained from G by attaching two new paths P:vv₁v₂…v_k and Q:vu₁u₂…u_l of length k and l, respectively, at v. We prove that if l?k?1 then μ(G_k-1,l+1)?μ(G_k,l). Let (v₁,v₂) be an edge of G. Let be the tree obtained from G by deleting the edge (v₁,v₂) and identifying the vertices v₁ and v₂. Then we prove that As a corollary to the above results, we obtain the celebrated theorem on algebraic connectivity which states that among all trees on n vertices, the path has the smallest and the star has the largest algebraic connectivity.     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

A simple approach for determining the eigenvalues of the fourth-order Sturm–Liouville problem with variable coefficients

In this paper, a simple and efficient approach is presented to compute the eigenvalues of the fourth-order Sturm–Liouville equations with variable coefficients. By transforming the governing differential equation to a system of algebraic equation, we can get the corresponding polynomial characteristic equations for kinds of boundary conditions based on the polynomial expansion and integral technique. Moreover, the lower and higher-order eigenvalues can be determined simultaneously from the multi-roots. Several examples for estimating eigenvalues are given. The convergence and effectiveness of the method are confirmed by comparing numerical results with the exact and other existing numerical results.     

Jimmie D. Lawson on the occasion of his 75th birthday

In this paper we consider the Schwarz radical of linear algebraic semigroups as defined in semigroup theory. We give some new characterizations of the complete regularity, regularity and solvability of irreducible linear algebraic monoids in terms of Schwarz radical data. Moreover, we give a generalization about the results of the kernel to the results of completely regular \(\mathscr {J}\)-classes.