On the second largest eigenvalue of line graphs

In this paper all connected line graphs whose second largest eigenvalue does not exceed 1 are characterized. Besides, all minimal line graphs with second largest eigenvalue greater than 1 are determined. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 61–66, 1998     

On tricyclic graphs whose second largest eigenvalue does not exceed 1

A tricyclic graph of order n is a connected graph with n vertices and n + 2 edges. In this paper, all tricyclic graphs whose second largest eigenvalue does not exceed 1 are identified.     

On regular graphs and coronas whose second largest eigenvalue does not exceed 1

We characterize all regular graphs whose second largest eigenvalue does not exceed 1. In the sequel, we determine all coronas, different from cones, with the same property. Some results and examples regarding unsolved cases are also given.     

第二大特征值小于$\frac{\sqrt{5}-1}{2}$的平面图

若能将图$G$画在一个平面上,使得任何两条边仅在顶点处相交,则称$G$是平面图.本文刻画了第二大特征值小于$\frac{\sqrt{5}-1}{2}$的所有无孤立点的平面图.     

Some graphs whose second largest eigenvalue does not exceed 2

We determine all trees whose second largest eigenvalue does not exceed $\sqrt{2}$. Next, we consider two classes of bipartite graphs, regular and semiregular, with small number of distinct eigenvalues. For all graphs considered we determine those whose second largest eigenvalue is equal to $\sqrt{2}$. Some additional results are also given.     

On Trees Whose Second Largest Eigenvalue Does Not Exceed 1

1.IntroductionLetGbeasimplegraphandA(G)betheadjacencymatrixofagraphGwithnvenices.ThecharacteristicpolynomialofGisthecharacteristicpolynomialofitsadjacencymatriX,denotedbyP(G;A),henceP(G;A)=det(AI--A(G)).SinceA(G)isarealsymmeticmatrix,itseigenvaluesmustberealandorderedasThoseAl(A(G))arecalleditheigenvalueofG,denotedAl(A(G))byAl(G).ThereareinseparableconnectionbetweentheconstructionandtheeigenvalueofgraphG.Severalbooksandalotofliterariesoneigenvaluesofgraphsanditsapplicationhavebeenp…     

Discrete hyperbolic geometry

The aim of the paper is to make geometers and combinatorialists familiar with old and new connections between the geometry of Lorentz space and combinatorics. Among the topics treated are equiangular lines and their relations to spherical 2-distance sets; spherical and hyperbolic root systems and their relation to graphs whose second largest eigenvalue does not exceed one or two, respectively; and work of Niemeier, Vinberg, Conway and Sloane on Euclidean and Lorentzian unimodular lattices. The first author gratefully acknowledges the support of the Dutch organization for pure research, Z. W. O., during Sept.—Dec. 1980, thus allowing him to spend four months in Eindhoven (Netherlands).     

Non-bipartite Graphs with Third Largest Laplacian Eigenvalue Less Than Three

All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.     

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.     

Multicyclic treelike reflexive graphs

A simple graph is reflexive if its second largest eigenvalue does not exceed 2. A graph is treelike (sometimes also called a cactus) if all its cycles (circuits) are mutually edge-disjoint. In a lot of cases one can establish whether a given graph is reflexive by identifying and removing a single cut-vertex (Theorem 1). In this paper we prove that, if this theorem cannot be applied to a connected treelike reflexive graph G and if all its cycles do not have a common vertex (do not form a bundle), such a graph has at most five cycles (Theorem 2). On the same conditions, in Theorem 3 we find all maximal treelike reflexive graphs with four and five cycles.     

Graphs with two isomorphism classes of spanning unicyclic subgraphs

The graphs whose spanning unicyclic subgraphs partition into exactly two isomorphism classes are characterized.This work is a continuation of [6] where graphs with one isomorphism class of spanning unicyclic graphs are characterized. The analogous question for spanning trees was posed in [10] and graphs with one isomorphism class of spanning trees were characterized in [2], [3], [4], [7], [11] while graphs with two isomorphism classes of spanning trees were characterized in [4], [5]. Related topics are treated in [1], [8], [9].     

Two Necessary Conditions for λ 2 (G) = d 2 ( G )

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.     

On the largest kth eigenvalues of trees with n≡0 (mod k)

We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue of trees with n vertices. In 1995, Jia-yu Shao gave complete solutions for the cases k=2,3,4,5,6 and provided some necessary conditions for extremal trees in general cases (cf. [Linear Algebra Appl. 221 (1995) 131]). We further improve Shao's necessary condition in this paper, which can be seen as the continuation of [Linear Algebra Appl. 221 (1995) 131].     

The swap graph of the finite soluble groups

A graph is reflexive if the second largest eigenvalue of its adjacency matrix is less than or equal to 2. In this paper, we characterize trees whose line graphs are reflexive. It turns out that these trees can be of arbitrary order—they can have either a unique vertex of arbitrary degree or pendant paths of arbitrary lengths, or both. Since the reflexive line graphs are Salem graphs, we also relate some of our results to the Salem (graph) numbers.     

On the limit points of the smallest eigenvalues of regular graphs

In this paper, we give infinitely many examples of (non-isomorphic) connected k-regular graphs with smallest eigenvalue in half open interval ${[-1-\sqrt2, -2)}$ and also infinitely many examples of (non-isomorphic) connected k-regular graphs with smallest eigenvalue in half open interval ${[\alpha_1, -1-\sqrt2)}$ where α ₁ is the smallest root ${(\approx -2.4812)}$ of the polynomial x ³?+?2x ² ? 2x ? 2. From these results, we determine the largest and second largest limit points of smallest eigenvalues of regular graphs less than ?2. Moreover we determine the supremum of the smallest eigenvalue among all connected 3-regular graphs with smallest eigenvalue less than ?2 and we give the unique graph with this supremum value as its smallest eigenvalue.     

关于代数连通度的一个注记

图G=(V,E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤1/2|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图.     

Graphs whose signless Laplacian spectral radius does not exceed the Hoffman limit value

For a graph matrix M, the Hoffman limit value H(M) is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of M(H_n), where the graph H_n is obtained by attaching a pendant edge to the cycle C_n-1 of length n-1. In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of H(A) and H(L) were first determined by Hoffman and Guo, respectively. Since H_n is bipartite for odd n, we have H(Q)=H(L). All graphs whose A-index is not greater than H(A) were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed H(Q). The results obtained are determinant to describe all graphs whose L-index is not greater then H(L). This is done precisely in Wang et al. (in press) [21].     

The graphs with exactly two distance eigenvalues different from $$$$ and $$-3$$-3

In this paper, we completely characterize the graphs with third largest distance eigenvalue at most \(-1\) and smallest distance eigenvalue at least \(-3\). In particular, we determine all graphs whose distance matrices have exactly two eigenvalues (counting multiplicity) different from \(-1\) and \(-3\). It turns out that such graphs consist of three infinite classes, and all of them are determined by their distance spectra. We also show that the friendship graph is determined by its distance spectrum.     

A symmetrical plane partition correspondence

MacMahon conjectured the form of the generating function for symmetrical plane partitions, and as a special case deduced the following theorem. The set of partitions of a number n whose part magnitude and number of parts are both no greater than m is equinumerous with the set of symmetrical plane partitions of 2n whose part magnitude does not exceed 2 and whose largest axis does not exceed m. This theorem, together with a companion theorem for the symmetrical plane partitions of odd numbers, are proved by establishing 1-1 correspondences between the sets of partitions.     

On the extremal values of the second largest Q-eigenvalue

We study extremal graphs for the extremal values of the second largest Q-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest Q-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.