PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 85(99) (2009), 35–38 DOI:10.2298/PIM0999035F

ON THREE CONJECTURES INVOLVING THE SIGNLESS LAPLACIAN SPECTRAL RADIUS OF GRAPHS

Lihua Feng and Guihai Yu

Communicated by Slobodan K. Simić

Abstract. We study the signless Laplacian spectral radius of graphs and prove three conjectures of Cvetković, Rowlinson, and Simić [Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math., Nouv. Sér. 81(95) (2007), 11–27].

1. Introduction

In this paper, we consider only simple connected graphs and follow the notation of [1]. Let G be a simple graph with vertex set V (G) and edge set E(G). The adjacency matrix of G is A(G) = (a_{ij} ), where a_{ij} = 1 if two vertices i and j are adjacent in G and a_{ij} = 0 otherwise. The characteristic polynomial of G is just P_{G}(x) = det(xI − A(G)). Let D(G) be the diagonal degree matrix of G. We call the matrix L(G) = D(G) − A(G) the Laplacian matrix of G, and the matrix Q(G) = D(G) + A(G) the signless Laplacian matrix or Q-matrix of G. We denote the largest eigenvalues of A(G), L(G), Q(G) by ρ(G), λ(G), μ(G), respectively, and call them the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius (or the Q-spectral radius) of G, respectively.

The study of the signless Laplacian spectral radius has recently attracted researchers’ attention. In [10], Fan et al. studied the signless Laplacian spectral radius of bicyclic graphs with fixed order. In [9], the authors discussed the smallest eigenvalue of Q(G) as a parameter reflecting the nonbipartiteness of the graph G. In [7], the authors studied the smallest signless Laplacian eigenvalue of non-bipartite graphs. In [11], the extremal graphs with maximal signless Laplacian spectral radius and fixed diameter were studied. More information about the signless Laplacian can be found in [2], [3], [5], [6]. For more information about the spectral radius of graphs, the reader can refer to [4].

2000 Mathematics Subject Classification: Primary 05C50.

Partially supported by Foundation of Education Department of Shandong Province (J07YH03), NSFSD (No.Y2006A17, Y2008A04).

In [5], the authors proposed the following conjectures and in this paper we confirm that they are true.

Theorem 1.1. [5, Conjecture 6] Let G be a connected graph of order n ⩾ 4. Then

μ(G) − \frac{4m}{n} ⩽ n − 4 + \frac{4}{n}.

Equality holds if and only if G = K_{1,n−1} .

Theorem 1.2. [5, Conjecture 7] Let G be a connected graph of order n ⩾ 5. Then

μ(G) − \frac{2m}{n} ⩽ n − 1.

Equality holds if and only if G = K_{n}.

Theorem 1.3. [5, Conjecture 10] Let G be a connected graph of order n ⩾ 4. Then

μ(G) − λ(G) ⩽ n − 2.

Equality holds if and only if G = K_{n}.

2. Lemmas and results

Let G be a connected graph. The degree of u in G is denoted by d_{u}, the average degree of u, denoted by m_{u}, satisfies d_{u}m_{u} = ∑ _{uv∈E} d_{v}, where E = E(G).

Lemma 2.1. [8] Let G be a graph with n vertices, and m edges. Then

max\{d_{v} + m_{v} | v ∈ V (G)\} ⩽ \frac{2m}{n − 1} + n − 2,

with equality if and only if K_{1,n−1} ⊆ G or G = K_{n−1} ∪ K_{1}.

Lemma 2.2. [12] Let M = (m_{ij} ) be an n × n irreducible nonnegative matrix with spectral radius ρ(M), and let R_{i}(M) be the ith row sum of M, i.e., R_{i}(M) = ∑ _{j=i}^{n} m_{ij} . Then

min{R_{i}(M) |⩽ i ⩽ n} ⩽ ρ(M) ⩽ max{R_{i}(M) | 1 ⩽ i ⩽ n}.

Moreover, if the row sums of M are not all equal, then both above inequalities are strict.

Lemma 2.3. Let G be a connected graph. Then μ(G) ⩽ max{d_{v} + m_{v} | v ∈ V (G)}, with equality holding if and only if G is either semiregular bipartite or regular.

Proof. We consider the matrix K = D^{−1} QD, where the row sum corresponding to the vertex u is d_{u} + m_{u}. From Lemma 2.2, we obtain the required upper bound for μ(G).

If equality holds, then by Lemma 2.2, for a neighbor v of u, d_{u} +m_{u} = d_{v} +m_{v}, thus ∑ _{uv∈E} (d_{u} +m_{u}) = ∑ _{uv∈E} (d_{v} +m_{v}), that is d_{u}^{2} +d_{u}m_{u} = d_{u}m_{u} +∑ _{uv∈E} m_{v}. So we get

d_{u}^{2} = ∑_{uv∈E} m_{v}.

Suppose d_{u} is the maximum degree. Then d_{v}m_{v} = ∑ _{wv∈E} d_{w} ⩽ d_{u}d_{v}, whence m_{v} ⩽ d_{u} for all v ∈ V (G). Since d_{u}^{2} = ∑ _{uv∈E} m_{v} ⩽ d_{u}^{2}, we have for any edge uv, d_{u} = m_{v}, and d_{u}d_{v} = d_{v}m_{v}, that is, ∑ _{wv∈E} (d_{u} − d_{w}) = 0. Since d_{u} is the maximum degree, we have d_{u} = d_{w} whenever there exists a vertex v such that uv, vw ∈ E.

If G does not contain odd cycles, then G is bipartite. Suppose V = S ∪ T is a bipartion and u ∈ T; then v ∈ S, w ∈ T. This implies that the vertices in T have the same degree. Similarly, the vertices in S also have the same degree. So G is semiregular bipartite.

If G contains odd cycles, then G must be regular.

The converse is easy to check. □

Lemma 2.4. Let G be a connected graph with n vertices and m edges. Then

μ(G) ⩽ \frac{2m}{n − 1} + n − 2,

with equality if and only if G is K_{1,n−1} or K_{n}.

Proof. By Lemmas 2.1 and 2.3, we can get the result. Note that K_{1,n−1} is the only semiregular bipartite graph and K_{n} is the only regular graph that arises in the case of equality. □

Now we can present the proof of the main results of this paper.

Proof of Theorem 1.1. By Lemma 2.4, we have

μ(G) − \frac{4m}{n} ⩽ \frac{2m}{n − 1} + n − 2 − \frac{4m}{n} = (n − 2)( 1 − \frac{2m}{n(n − 1)} )

⩽ (n − 2)( 1 − \frac{2(n − 1)}{n(n − 1)} ) = n − 4 + \frac{4}{n}.

The last inequality holds since G is connected and so has at least n − 1 edges. The equality case is easy to see from Lemma 2.4. □

Proof of Theorem 1.2. By Lemma 2.4, we have

μ(G) − \frac{2m}{n} ⩽ \frac{2m}{n − 1} + n − 2 − \frac{2m}{n} = \frac{2m}{n(n − 1)} + n − 2 ⩽ 1 + n − 2 = n − 1.

The last inequality holds since G has at most \frac{1}{2}n(n − 1) edges. When this bound is attained, G = K_{n}. □

Proof of Theorem 1.3. Note that the sum of all the Laplacian eigenvalues is 2m, so we have (n − 1)λ(G) ⩾ 2m and hence λ(G) ⩾ \frac{2m}{n−1} . By Lemma 2.4, we have

μ(G) − λ(G) ⩽ \frac{2m}{n − 1} + n − 2 − \frac{2m}{n − 1} = n − 2.

The equality case is easy to see from Lemma 2.4. □

Acknowledgments. The authors are grateful to the referees for their comments.

References

[1] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan Press, New York, 1976.

[2] D. Cvetković, Signless Laplacians and line graphs, Bull. Acad. Serbe Sci. Arts. Cl. Sci. Math. Nat. Sci. Math. 131(30) (2005), 85–92.

[3] D. Cvetković, P. Rowlinson, S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007), 155–171.

[4] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980.

[5] D. Cvetković, P. Rowlinson, S. K. Simić, Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd) 81 (95) (2007), 11–27.

[6] D. Cvetković, New theorems for signless Laplacians eigenvalues, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math. 137(33) (2008), 131–146.

[7] D. M. Cardoso, D. Cvetković, P. Rowlinson, S. K. Simić, A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear Algebra Appl. 429 (2008), 2770–2780.

[8] K. Ch. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004), 57–66.

[9] M. Desai, V. Rao, A characterizaion of the smallest eigenvalue of a graph, J. Graph Theory 18 (1994), 181–194.

[10] Y. Fan, B. S. Tam, J. Zhou, Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order, Linear Multilinear Algebra 56 (2008), 381–397.

[11] L. Feng, G. Yu, The signless Laplacian spectral radius of graphs with given diameter, 2008, Utilitas Math., accepted.

[12] R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985.

School of Mathematics (Received 26 12 2008) Shandong Institute of Business and Technology (Revised 10 03 2009) 191 Binhaizhong Road, Yantai, Shandong, 264005 P.R. China

fenglh@163.com