On the multiplicity of Laplacian eigenvalues for unicyclic graphs

Let G be a connected graph of order n and U a unicyclic graph with the same order. We firstly give a sharp bound for m_G(μ), the multiplicity of a Laplacian eigenvalue μ of G. As a straightforward result, m_U(1) ? n ? 2. We then provide two graph operations (i.e., grafting and shifting) on graph G for which the value of m_G(1) is nondecreasing. As applications, we get the distribution of m_U (1) for unicyclic graphs on n vertices. Moreover, for the two largest possible values of m_U(1) ∈ {n ? 5, n ? 3}, the corresponding graphs U are completely determined.

     

Minimizing the least eigenvalue of unicyclic graphs with fixed diameter

Let U(n,d) be the set of unicyclic graphs on n vertices with diameter d. In this article, we determine the unique graph with minimal least eigenvalue among all graphs in U(n,d). It is found that the extremal graph is different from that for the corresponding problem on maximal eigenvalue as done by Liu et al. [H.Q. Liu, M. Lu, F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007) 449-457].     

The smallest values of algebraic connectivity for unicyclic graphs

The algebraic connectivity of G is the second smallest eigenvalue of its Laplacian matrix. Let U_n be the set of all unicyclic graphs of order n. In this paper, we will provide the ordering of unicyclic graphs in U_n up to the last seven graphs according to their algebraic connectivities when n≥13. This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315-4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711].     

Eigenvalues of the Manifold Sp（n）/U（n）

In this paper, we give the eigenvalues of the manifold Sp(n)/U(n). We prove that an eigenvalue λ _s (f ₂, f ₂, …, f _n ) of the Lie group Sp(n), corresponding to the representation with label (f ₁, f ₂, ..., f _n ), is an eigenvalue of the manifold Sp(n)/U(n), if and only if f ₁, f ₂, …, f _n are all even.     

Upper Bounds for the Laplacian Graph Eigenvalues

We first apply non-negative matrix theory to the matrix K = D A, where D and A are the degree-diagonal and adjacency matrices of a graph G, respectively, to establish a relation on the largest Laplacian eigenvalue λ1 (G) of G and the spectral radius p(K) of K. And then by using this relation we present two upper bounds for λ1(G) and determine the extremal graphs which achieve the upper bounds.     

Some results on the ordering of the Laplacian spectral radii of unicyclic graphs

A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices.     

Some graft transformations and its application on a distance spectrum

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, we give some graft transformations that decrease and increase ?(G) and prove that the graph (obtained from the star S_n on n (n is not equal to 4, 5) vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while (obtained from a triangle K₃ by attaching pendent path P_n−3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices.     

Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

On graphs with the largest Laplacian index

Let G be a connected simple graph on n vertices. The Laplacian index of G, namely, the greatest Laplacian eigenvalue of G, is well known to be bounded above by n. In this paper, we give structural characterizations for graphs G with the largest Laplacian index n. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on n and k for the existence of a k-regular graph G of order n with the largest Laplacian index n. We prove that for a graph G of order n ⩾ 3 with the largest Laplacian index n, G is Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results. The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006). The work was done when Z. Chen was on sabbatical in China.     

The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

On the least eigenvalue of a unicyclic mixed graph

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3.     

Asymptotic behavior of eigenvalues of two-parameter nonlinear Sturm-Liouville problems

The nonlinear two-parameter Sturm-Liouville problemu ^"+μg(u)=λf(u) is studied for μ, λ>0. By using Ljusternik-Schnirelman theory on the general level set developed by Zeidler, we shall show the existence of ann-th variational eigenvalue λ=λ_n(μ). Furthermore, for specialf andg, the asymptotic formula of λ₁(μ)) as μ→∞ is established.     

On Edge Singularity and Eigenvectors of Mixed Graphs

Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L（G） of G. As L（G） is positive semidefinite, the singularity of L（G） is determined by its least eigenvalue λ1 （G）. This paper introduces a new parameter edge singularity εs（G） that reflects the singularity of L（G）, which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs（G） and λ1 （G） （and other parameters） of G. In the case of εs（G） = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 （G）, which is similar to the property of Fiedler vectors of a simple graph given by Fiedler.     

An edge-grafting theorem on Laplacian spectra of graphs and its application

Let 𝒰(n,?d) be the class of unicyclic graphs on n vertices with diameter d. This article presents an edge-grafting theorem on Laplacian spectra of graphs. By applying this theorem, we determine the unique graph with the maximum Laplacian spectral radius in 𝒰(n,?d). This extremal graph is different from that for the corresponding problem on the adjacency spectral radius as done by Liu et al. [Q. Liu, M. Lu, and F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007), 449–457].     

On eigenvalues of symmetric (+1, −1) matrices

To every symmetric matrixA with entries ±1, we associate a graph G(A), and ask (for two different definitions of distance) for the distance ofG(A) to the nearest complete bipartite graph (cbg). Letλ ₁(A),λ ¹ (A) be respectively the algebraically largest and least eigenvalues ofA. The Frobenius distance (see Section 4) to the nearest cbg is bounded above and below by functions ofn −λ ₁ (A), wheren=ord A. The ordinary distance (see Section 1) to the nearest cbg is shown to be bounded above and below by functions ofλ ¹ (A). A curious corollary is: there exists a functionf (independent ofn, and given by (1.1)), such that |λ _i (A) | ≦f(λ ¹(A), whereλ _i (A) is any eigenvalue ofA other thanλ _i (A). This work was supported (in part) by the U.S. Army under contract #DAHC04-C-0023.     

Degree series of the 3-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant λ such that the equality λd（vi） = Σ（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,..., ｜V（G）｜, where d（vi） denotes the degree of vertex vi. Let ni denote the number of vertices with degree i. This paper deals with the 3-Hgraphs and determines their degree series. Moreover, the 3-Hgraphs with bounded ni （1 ≤ i ≤ 7） are studied and some interesting results are obtained.     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

Extremal probabilities for Gaussian quadratic forms

 Denote by Q an arbitrary positive semidefinite quadratic form in centered Gaussian random variables such that E(Q)=1. We prove that for an arbitrary x>0, inf _Q P(Q≤x)=P(χ² _n /n≤x), where χ _n ² is a chi-square distributed rv with n=n(x) degrees of freedom, n(x) is a non-increasing function of x, n=1 iff x>x(1)=1.5364…, n=2 iff x[x(2),x(1)], where x(2)=1.2989…, etc., n(x)≤rank(Q). A similar statement is not true for the supremum: if 1<x<2 and Z ₁ ,Z ₂ are independent standard Gaussian rv's, then sup_0≤λ≤1/2 P{λZ ₁ ² +(1−λ)Z ₂ ² ≤x} is taken not at λ=0 or at λ=1/2 but at 0<λ=λ(x)<1/2, where λ(x) is a continuous, increasing function from λ(1)=0 to λ(2)=1/2, e.g. λ(1.5)=.15…. Applications of our theorems include asymptotic quantiles of U and V-statistics, signal detection, and stochastic orderings of integrals of squared Gaussian processes. Received: 24 June 2002 / Revised version: 26 January 2003 Published online: 15 April 2003 Research supported by NSA Grant MDA904-02-1-0091 Mathematics Subject Classification (2000): Primary 60E15, 60G15; Secondary 62G10