PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 81(95) (2007), 11–27 DOI 102298/PIM0795011C

EIGENVALUE BOUNDS FOR THE SIGNLESS LAPLACIAN

Dragoš Cvetković, Peter Rowlinson, and Slobodan K. Simić

Abstract. We extend our previous survey of properties of spectra of signless Laplacians of graphs. Some new bounds for eigenvalues are given, and the main result concerns the graphs whose largest eigenvalue is maximal among the graphs with fixed numbers of vertices and edges. The results are presented in the context of a number of computer-generated conjectures.

1. Introduction

Let G be a simple graph with n vertices. The characteristic polynomial det(xI− A) of a (0,1)-adjacency matrix A of G is called the characteristic polynomial of G and denoted by P_{G}(x). The eigenvalues of A (i.e., the zeros of det(xI −A)) and the spectrum of A (which consists of the n eigenvalues) are also called the eigenvalues of G and the spectrum of G, respectively. The eigenvalues of G are real because A is symmetric, and the largest eigenvalue is called the index of G.

Together with the spectrum of an adjacency matrix of a graph we shall consider the spectrum of another matrix associated with the graph.

Let n, m, R be the number of vertices, the number of edges and the vertex-edge incidence matrix of a graph G. The following relations are well-known:

(1)  RR^{T} = D + A, R^{T} R = A(L(G)) + 2I,

where D is the diagonal matrix of vertex degrees and A(L(G)) is the adjacency matrix of the line graph L(G) of G.

Since the non-zero eigenvalues of RR^{T} and R^{T} R are the same, we deduce from the relations (1) that

(2)  P_{L(G)}(x) = (x + 2)^{m−n}Q_{G}(x + 2),

where Q_{G}(x) is the characteristic polynomial of the matrix Q = D + A.

2000 Mathematics Subject Classification: Primary 05C50.

Key words and phrases: graph theory, graph spectra, line graph, signless Laplacian.

Research supported by the Serbian Ministry of Science, grant 144015G.

The polynomial Q_{G}(x) will be called the Q-polynomial of the graph G. The eigenvalues and the spectrum of Q will be called the Q-eigenvalues and the Qspectrum respectively.

The matrix L = D − A, known as the Laplacian of G, features prominently in the literature (see, for example, [5] and [18]). The matrix D + A is called the signless Laplacian in [16], and it appears very rarely in published papers (see [5]), the paper [13] being almost the only relevant research paper published before 2003. Only recently has the signless Laplacian attracted the attention of researchers [4, 8, 11, 10, 16, 26]. The present paper extends the survey [8] by providing further comments, proofs and conjectures. The new results include some bounds for the eigenvalues of D + A. The starting point is a series of conjectures that were formulated using a computer program called AutoGraphiX (AGX). This program, which was developed to find extremal (or near-extremal) graphs with respect to certain properties, is described in [2]. That paper was the first of a sequence of articles, including [1], which feature results obtained with the assistance of AGX.

As usual, K_{n}, C_{n} and P_{n} denote respectively the complete graph, the cycle and the path on n vertices. We write K_{n} + e for the graph obtained from K_{n} by adding a pendant edge, and K_{m,n} for the complete bipartite graph with parts of size m and n. The graph K_{n−1,1} is called a star and is denoted by S_{n}. The double star DS(m, n) is obtained from two disjoint stars K_{m−1,1}, K_{n−1,1} by adding an edge between their central vertices. The double comet DC(n, r, s) is the graph of order n obtained from two disjoint stars K_{r−1,1}, K_{s−1,1} by adding a path (of length n − r − s + 1) between their central vertices.

A unicyclic graph containing an even (odd) cycle is called even-unicyclic (oddunicyclic). The union of disjoint graphs G and H is denoted by G ˙∪ H, while mG denotes the union of m disjoint copies of G.

We write Γ(v) for the neighbourhood of v, and we call {v} ∪ Γ(v) the closed neighbourhood of v. Vertices with the same neighbourhood are called duplicate vertices; they necessarily induce a co-clique. Vertices with the same closed neighbourhood are called co-duplicate vertices; they necessarily induce a clique.

A complete split graph with parameters n, q (q ⩽ n), denoted by CS(n, q), is a graph on n vertices consisting of a clique on q vertices, a co-clique on the remaining n − q vertices, and all q(n − q) possible edges between the clique and the co-clique. (In the notation of [6], CS(n, q) is the join K_{q}∇\overline{K}_{n−q}.)

The vertex-set of a nested split graph G has a partition U ˙∪ V_{1} ˙∪ ⋯ ˙∪ V_{k} with the following properties:

(i) U induces a clique, and V_{1} ˙∪ ⋯ ˙∪ V_{k} induces a co-clique; (ii) U has subsets U_{1}, …, U_{k} such that U_{1} ⊃ U_{2} ⊃ ⋯ ⊃ U_{k} and the neigh-

bourhood of each vertex in V_{i} is U_{i} (i = 1, …, k).

The rest of the paper is organized as follows. Section 2 elaborates results from the survey paper [8] which will be required later. Section 3 contains the list of conjectures on Q-eigenvalues which have been formulated using the system AGX. Section 4 contains comments on the conjectures and their relation to known results.

Those conjectures related to the largest Q-eigenvalue are investigated in Section 5, while other conjectures are considered in Section 6.

2. Basic properties of Q-spectra

Let G be a graph with Q-eigenvalues q_{1}, q_{2}, …, q_{n} (q_{1} ⩾ q_{2} ⩾ ⋯ ⩾ q_{n}). The largest eigenvalue q_{1} is called the Q-index of G.

When applying the Perron–Frobenius theory of non-negative matrices (see, for example, Section 0.3 of [5]) to the signless Laplacian Q, we obtain the same or similar conclusions as in the case of the adjacency matrix. In particular, in a connected graph the largest eigenvalue is simple with a positive eigenvector. The Q-index of any proper subgraph of a connected graph is smaller than the Q-index of the original graph, an observation which follows from Theorems 0.6 and 0.7 of [5].

The interlacing theorem holds in a specific way, namely the interlacing of the Q-eigenvalues of a graph with the Q-eigenvalues of an edge-deleted subgraph. This can be seen by considering the corresponding line graph, for which the ordinary interlacing theorem holds, and shifting attention to the root graph. In fact, we have the following theorem.

Theorem 2.1. Let G be a graph on n vertices and m edges and let e be an edge of G. Let q_{1}, q_{2}, …, q_{n} (q_{1} ⩾ q_{2} ⩾ ⋯ ⩾ q_{n}) and s_{1}, s_{2}, …, s_{n} (s_{1} ⩾ s_{2} ⩾ ⋯ ⩾ s_{n}) be Q-eigenvalues of G and G − e respectively. Then

0 ⩽ s_{n} ⩽ q_{n} ⩽ ⋯ ⩽ s_{2} ⩽ q_{2} ⩽ s_{1} ⩽ q_{1}.

Proof. We shall prove the assertion in the case that both G and G − e are connected and m ⩾ n + 1. In other cases the argument remains valid with some technical modifications.

By formula (1) the eigenvalues of L(G) and L(G − e) are q_{1} − 2, q_{2} − 2, …, q_{n} − 2, −2^{(m−n)} and s_{1} − 2, s_{2} − 2, …, s_{n} − 2, −2^{(m−1−n)} respectively. Since L(G − e) is an induced subgraph of L(G) the interlacing theorem yields

q_{1} − 2 ⩾ s_{1} − 2 ⩾ q_{2} − 2 ⩾ s_{2} − 2 ⩾ ⋯ ⩾ q_{n} − 2 ⩾ s_{n} − 2 ⩾ −2

and the result follows. □

The following proposition has been proved in [8].

Proposition 2.2. Let q_{1} be the largest Q-eigenvalue of a graph G. The following statements hold:

(i) q_{1} = 0 if and only if G has no edges;

(ii) 0 < q_{1} < 4 if and only if all components of G are paths;

(iii) for a connected graph G we have q_{1} = 4 if and only if G is a cycle or K_{1,3}.

In virtue of (1), the signless Laplacian is a positive semi-definite matrix, i.e., all its eigenvalues are non-negative. Concerning the least eigenvalue we have the following proposition (see [8, Proposition 2.1] or [13, Proposition 2.1]).

Proposition 2.3. The least eigenvalue of the signless Laplacian of a connected graph is equal to 0 if and only if the graph is bipartite. In this case 0 is a simple eigenvalue.

Corollary 2.4. For any graph, the multiplicity of 0 as an eigenvalue of the signless Laplacian is equal to the number of bipartite components.

For a subset S of the vertex set V = V (G) of a graph G, let ⟨S⟩ be the subgraph of G induced by S. Let e_{min}(S) be the minimum number of edges whose removal from ⟨S⟩ results in a bipartite subgraph of ⟨S⟩. Let cut(S) be the set of edges with one vertex in S and the other in its complement V ∖ S. Thus |cut(S)| + e_{min}(S) is the minimum number of edges whose removal from E(G) disconnects S from V ∖S and results in a bipartite subgraph induced by S. For any graph G let ψ = ψ(G) be the minimum over all non-empty proper subsets S of V (G) of the quotient

\frac{|cut(S)| + e_{min}(S)}{|S|}.

The parameter ψ was introduced in [13] as a measure of non-bipartiteness. It is shown that the least eigenvalue q_{n} of the signless Laplacian Q is bounded above and below by functions of ψ. In particular, it is proved that, for a connected graph,

(3)  \frac{ψ^{2}}{4Δ} ⩽ q_{n} ⩽ 4ψ,

where Δ is the maximal vertex degree.

Remark. In general, the Q-polynomial of a graph does not tell us whether or not the graph is bipartite. It does if the graph is connected but we cannot recognize a connected graph by its Q-polynomial. It is interesting to note that if we know the number of components we can determine from the Q-polynomial whether the graph is bipartite and if we know that the graph is bipartite we can determine the number of components. Therefore it was suggested in [4, 8] that, when handling graphs by means of Q-spectra, we should assume or require that in addition to the Q-eigenvalues, the number of components is also prescribed.

The proof of the following proposition can be found in many places in the literature (see, for example, [19]).

Proposition 2.5. The Q-polynomial of a graph is equal to the characteristic polynomial of the Laplacian if and only if the graph is bipartite.

Regular graphs can be recognized, and the degree of regularity and the number of components calculated, from Q_{G}(λ), as noticed in [10]. In particular, we have the following proposition [8].

Proposition 2.6. Let G be a graph with n vertices and m edges and let q_{1} be its largest Q-eigenvalue. Then G is regular if and only if 4m = nq_{1}. If G is regular, then its degree is equal to q_{1}/2 and the number of components is equal to the multiplicity of q_{1}.

The proof is carried out in the same way as in the case of the adjacency matrix (cf. [5, Theorems 3.8, 3.22 and 3.23]): one compares q_{1} with the value of the Rayleigh quotient for the all-1 vector.

In regular graphs it is not necessary to give explicitly the number of components since it can be calculated from Q_{G}(x) using Proposition 2.6. Of course, for regular graphs the whole existing theory of spectra of the adjacency matrix and the Laplacian matrix is transferred directly to the signless Laplacian by a translate of the spectrum. In particular, we have:

Proposition 2.7. Let G be a regular bipartite graph of degree r. Then the Q-spectrum of G is symmetric with respect to the point r.

This symmetry property is an immediate consequence of the well-known symmetry about 0 of the adjacency eigenvalues in bipartite graphs. Thus q is a Qeigenvalue of multiplicity k if and only if 2r−q is also a Q-eigenvalue of multiplicity k; moreover, the eigenvalues 0 and 2r are always present.

Let G be a connected graph with n vertices, and let

Q_{G}(x) = ∑_{j=0}^{n} p_{j}(G)x^{n−j} = p_{0}(G)x^{n} + p_{1}(G)x^{n−1} + ⋯ + p_{n}(G).

A spanning subgraph of G whose components are trees or odd-unicyclic graphs is called a TU-subgraph of G. Suppose that a T U-subgraph H of G contain c unicyclic graphs and trees T_{1}, T_{2}, …, T_{s}. Then the weight W (H) of H is defined by W (H) = 4^{c} ∏_{i=1}^{s}(1+|E(T_{i})|). Note that isolated vertices in H do not contribute to W (H) and may be ignored.

We shall express coefficients of Q_{G}(x) in terms of the weights of T U-subgraphs of G (cf. [12], [8]).

Theorem 2.8. We have p_{0}(G) = 1 and

p_{j}(G) = ∑_{H_{j}}(−1)^{j}W (H_{j}), j = 1, 2, …, n,

where the summation runs over all T U-subgraphs of G with j edges.

Note that the new proof of this theorem from [8] is formulated for technical reasons for graphs in which the number of edges is not smaller than the number of vertices. However, the result holds also for trees since by Proposition 2.5 the statement is reduced to the known result for the Laplacian matrix.

The following formula appears implicitly in the literature (see e.g., [5, p. 63] and [25]):

P_{S(G)}(x) = x^{m−n}Q_{G}(x^{2}),

where G is a graph with n vertices and m edges, and S(G) is the subdivision graph of G. Together with (2), this formula provides a link to the theory of the adjacency spectra. While formula (2) has been used to some effect in this context (cf. [8]), the connection with subdivision graphs remains to be exploited.

3. AGX Conjectures

The following 30 conjectures related to the Q-eigenvalues of a graph have been formulated after some experiments with the system AGX. Almost all the conjectures are in the form of inequalities which provide upper or lower bounds for spectrally based graph invariants. The notation is as follows.

As above, Q denotes the signless Laplacian of a graph G and (q_{1}, q_{2}, …, q_{n}) the spectrum of Q, where the eigenvalues are such that q_{1} ⩾ q_{2} ⩾ ⋯ ⩾ q_{n}.

Let P denote the Laplacian of a graph G and (μ_{1}, μ_{2}, …, μ_{n}) the spectrum of P, where the eigenvalues are such that μ_{1} ⩾ μ_{2} ⩾ ⋯ ⩾ μ_{n}.

Let A denote the adjacency matrix of a graph G and (λ_{1}, λ_{2}, …, λ_{n}) the spectrum of A, where the eigenvalues are such that λ_{1} ⩾ λ_{2} ⩾ ⋯ ⩾ λ_{n}.

Sometimes we shall use the notation q_{i} = q_{i}(G), i = 1, 2, …, n. Also, we write a for μ_{n−1}, called the algebraic connectivity of G (see [5, p. 265]).

The conjectures apply to graphs with at least 4 vertices, and they are classified according to the graph invariants involved. For some conjectures we have indicated that they are, at least partially, resolved (previously in the literature or in this paper). The letters C, L, U with a superscript + or − indicate that the whole conjecture, or the lower bound, or the upper bound, has been confirmed or refuted respectively. In addition we refer to the section of this paper where relevant information or proof is given.

3.1. Conjectures on the largest eigenvalue.

Conjecture 1 (L^{+}, U^{+}, Section 4). If G is a connected graph of order n ⩾ 4, then

2 + 2 cos \frac{π}{n} = q_{1}(P_{n}) ⩽ q_{1}(G) ⩽ q_{1}(K_{n}) = 2n − 2

with equality if and only if G is the path P_{n} for the lower bound, and if and only if G is the complete graph K_{n} for the upper bound.

Conjecture 2 (L^{+}, U^{+}, Section 5). If T is a tree of order n ⩾ 4, then

2 + 2 cos \frac{π}{n} = q_{1}(P_{n}) ⩽ q_{1}(T) ⩽ q_{1}(S_{n}) = n

with equality if and only if T is the path P_{n} for the lower bound, and if and only if T is the star S_{n} for the upper bound.

Conjecture 3 (L^{+}, U^{+}, Section 5). Let S_{n}^{+} denote the graph consisting of a star and an additional edge. If G is a unicyclic graph of order n ⩾ 4, then

4 = q_{1}(C_{n}) ⩽ q_{1}(G) ⩽ q_{1}(S_{n}^{+})

with equality if and only if G is the cycle C_{n} for the lower bound, and if and only if G is S_{n}^{+} for the upper bound.

Conjecture 4 (C^{+}, Section 5). If G is a connected graph of order n ⩾ 4 and maximum degree Δ, then

q_{1} ⩾ Δ + 1

with equality if and only if G is the star S_{n}.

Conjecture 5 (L^{+}, U^{+}, Section 4). If G is a connected graph of order n ⩾ 4, with minimum, average and maximum degree δ, \overline{d} and Δ respectively, then

2δ ⩽ 2\overline{d} ⩽ q_{1} ⩽ 2Δ

with equality in any instance if and only if G is regular.

Conjecture 6. If G is a connected graph of order n ⩾ 4 and average degree \overline{d}, then

q_{1} − 2\overline{d} ⩽ n − 4 + 4/n

with equality if and only if G is the star S_{n}.

Conjecture 7 (L^{+}, Section 5). If G is a connected graph of order n ⩾ 5 and average degree \overline{d}, then

2 ⩽ q_{1} − \overline{d} ⩽ n − 1

with equality if and only if G is the cycle C_{n} for the lower bound, and if and only if G is the complete graph K_{n} for the upper bound.

Conjecture 8 (L^{+}, Section 5). If G is a connected graph of order n ⩾ 4, index λ_{1} and average degree \overline{d}, then

0 ⩽ q_{1} − \overline{d} − λ_{1} ⩽ n − 2 + 2/n − \sqrt{n − 1}

with equality if and only if G is regular for the lower bound, and if and only if G is the star S_{n} for the upper bound.

Conjecture 9 (L^{+}, Section 5). If G is a connected graph of order n ⩾ 4, index λ_{1} with maximum Laplacian eigenvalue μ_{1}, then

1 ⩽ μ_{1} + λ_{1} − q_{1} ⩽ \sqrt{⌈n/2⌉⌊n/2⌋}

with equality if and only if G is the complete graph K_{n} for the lower bound, and if and only if G is the complete bipartite graph K_{⌈ \frac{n}{2} ⌉,⌊ \frac{n}{2} ⌋} for the upper bound.

Conjecture 10 (L^{+}, Section 4). If G is a connected graph of order n ⩾ 4 with maximum Laplacian eigenvalue μ_{1}, then

0 ⩽ q_{1} − μ_{1} ⩽ n − 2

with equality if and only if G is bipartite for the lower bound, and if and only if G is the complete graph K_{n} for the upper bound.

Conjecture 11 (L^{+}, Section 4). If G is a connected graph of order n ⩾ 4 and index λ_{1}, then

0 ⩽ q_{1} − 2λ_{1} ⩽ n − 2\sqrt{n − 1}

with equality if and only if G is regular for the lower bound, and if and only if G is the star S_{n} for the upper bound.

3.2. Conjectures on the second largest eigenvalue.

Conjecture 12 (C^{+}, Section 4). If G is a connected graph of order n ⩾ 4, then

q_{2} ⩾ 1,

with equality if and only if G is the star S_{n}.

Conjecture 13 (C^{+}, Section 4). Over all trees on n ⩾ 4 vertices, q_{2} is maximum for the graphs DS(\frac{1}{2}n, \frac{1}{2}n) and DC(n, \frac{1}{2}n − 1, \frac{1}{2}n − 1) if n is even (in which case q_{2} = \frac{1}{2}n), and for the graph DC(n, \frac{1}{2}(n − 1), \frac{1}{2}(n − 1)) if n is odd.

Conjecture 14. If G is a connected graph of order n ⩾ 7, then

−1 ⩽ q_{2} − \overline{d} ⩽ n − 6 + 8/n

with equality if and only if G is the complete graph K_{n} for the lower bound, and if and only if G is the complete bipartite graph K_{n−2,2} for the upper bound.

Conjecture 15. If G is a connected graph of order n ⩾ 7, then

−1 ⩽ q_{2} − δ ⩽ n − 3

with equality if and only if G is the complete graph K_{n} for the lower bound, and if and only if G is K_{n−1} + e for the upper bound.

Conjecture 16. If G is a connected graph of order n ⩾ 4, then

Δ − q_{2} ⩽ n − 2,

with equality if and only if G is the star S_{n}.

Conjecture 17. Over all connected graphs on n ⩾ 4 vertices, the graph H, described below, minimizes Δ − q_{2}.

If n is even, H is constructed as follows from two copies of K\frac{n}{2} . Delete an edge uv from one copy and an edge u′v′ from the other; then add the two edges uu′ and vv′.

If n is odd, H is constructed as follows from two copies of K_{\frac{n−1}{2}} and an isolated vertex w. Delete an edge uv from one copy of K_{\frac{n−1}{2}} and an edge u′v′ from the other; then add the four edges uw,vw, u′w and v′w.

Conjecture 18. If G is a connected graph of order n ⩾ 9, then

1 − \sqrt{n − 1} ⩽ q_{2} − λ_{1} ⩽ n − 2 − \sqrt{2n − 4}

with equality if and only if G is the star S_{n} for the lower bound, and if and only if G is the complete bipartite graph K_{n−2,2} for the upper bound.

Conjecture 19. If G is a connected graph of order n ⩾ 9 and algebraic connectivity a, then

q_{2} − a ⩾ −2

with equality if and only if G is the complete graph K_{n}.

Conjecture 20. If G is a connected graph and not complete of order n ⩾ 9 and algebraic connectivity a, then

q_{2} − a ⩾ 0.

The bound is attained by the star S_{n}, by the complement of a matching of ⌊n/2⌋ edges and, if n is even, by the complete bipartite graph K_{\frac{n}{2} , \frac{n}{2}} .

Conjecture 21. Over all connected graphs on n ⩾ 4 vertices, the graph K, described below, maximizes q_{2} − a.

If n is even, K is obtained from two copies of K\frac{n}{2} by adding a single edge connecting the two cliques.

If n is odd, K is obtained from two copies of K_{\frac{n−1}{2}} and an isolated vertex w by adding two edges between w and each clique K_{\frac{n−1}{2}} .

Conjecture 22. If G is a connected graph of order n ⩾ 4, then

q_{1} − q_{2} ⩽ n

with equality if and only if G is the complete graph K_{n}.

Conjecture 23. If T is a tree order n ⩾ 4, then

q_{1} − q_{2} ⩽ n − 1

with equality if and only if T is the star S_{n}.

3.3. Conjectures on the least eigenvalue.

Conjecture 24. If G is a connected and not bipartite of order n ⩾ 4, then

q_{n} ⩾ q_{n}(E_{3,n−3})

where E_{e,f} is a unicyclic graph with e + f vertices obtained by a coalescence of a vertex in C_{e} with an endvertex of P_{f+1}.

Conjecture 25. Over the set of all connected graphs of order n ⩾ 6, q_{1} − q_{n} is minimum for a path P_{n} and for an odd cycle C_{n}, and is maximum for the graph K_{n−1} + e.

Conjecture 26. For any connected graph G of order n ⩾ 4 with independence number α,

q_{1} + q_{n} + 2α ⩽ 3n − 2

with equality if and only if G is a complete split graph CS(n, n − α). If G has m edges then q_{1} + q_{2} + ⋯ + q_{n} = 2m, and so the conjecture is equivalent to:

∑_{i=2}^{n−1} q_{i} ⩾ 2(m + α + 1) − 3n

with equality if and only if G is a complete split graph CS(n, n − α).

3.4. Conjectures related to the multiplicities of eigenvalues.

Conjecture 27 (C^{+}, Section 6). Let e(Q) denote the number of distinct eigenvalues of the matrix Q and m(q_{i}) the multiplicity of the eigenvalue q_{i}. Then

e(Q) = 2 ⇔ m(q_{2}) = n − 1 ⇔ G ≡ K_{n} .

In this case, q_{2} = n − 2.

Conjecture 28 (C^{+}, Section 6). If G has k duplicate vertices (k > 1), with neighbourhood of size d, then d is an eigenvalue of Q with m(d) ⩾ k − 1.

Conjecture 29 (C^{+}, Section 6). If G has k co-duplicate vertices (k > 1), with closed neighbourhood of size d, then d−1 is an eigenvalue of Q with m(d−1) ⩾ k−1.

Conjecture 30 (C^{−}, Section 6). If G is a connected graph of order n ⩾ 4 with at least two dominating vertices, then q_{2} = Δ − 1 = n − 2 with multiplicity at most ⌈n/2⌉ − 2.

4. Comments on the conjectures

In this section, we identify conjectures in Section 3 that are confirmed by simple results already recorded in the literature, explicitly or implicitly. Some of the remaining conjectures can also be resolved by elementary observations; these and other new results are presented in the following two sections. The conjectures left unresolved appear to include some difficult research problems.

Several elementary inequalities for Q-eigenvalues are given in [3]. Among other things, it is proved that the Q-index q_{1} of a connected graph on n vertices satisfies the inequalities

2 + 2 cos \frac{π}{n} ⩽ q_{1} ⩽ 2n − 2.

The lower bound is attained in P_{n}, and the upper bound in K_{n}.

This double inequality is the content of Conjecture 1, which is therefore confirmed.

The following theorem is a direct reformulation of a well known theorem from the Perron–Frobenius theory of non-negative matrices (cf. [14, Vol. II, p. 63] or [5, p. 83]).

Theorem 4.1. Let G be a graph on n vertices with vertex degrees d_{1}, d_{2}, …, d_{n} and largest Q-eigenvalue q_{1}. Then

2δ = 2 min d_{i} ⩽ q_{1} ⩽ 2 max d_{i} = 2Δ.

If G is connected, then equality holds in either of these inequalities if and only if G is regular.

However, stronger inequalities can be derived using the very same result from the theory of non-negative matrices, as indicated in [8]:

Theorem 4.2. Let G be a graph on n vertices with vertex degrees d_{1}, d_{2}, …, d_{n} and largest Q-eigenvalue q_{1}. Then

min(d_{i} + d_{j}) ⩽ q_{1} ⩽ max(d_{i} + d_{j}),

where (i, j) runs over all pairs of adjacent vertices of G. If G is connected, then equality holds in either of these inequalities if and only if G is regular or semiregular bipartite.

Now let \overline{d} be the mean degree of G, and recall that

(4)  q_{1} = sup_{x∈ℝ^{n}∖\{0\}} \frac{x^{T} Q x}{x^{T} x} = sup_{∥x∥=1} x^{T} Q x,

with equality if and only if x is an eigenvector of G corresponding to q_{1} (see, for example, [6]). Taking x to be the all-1 vector, we see that q_{1} ⩾ \overline{d}, with equality if and only if G is regular. In conjunction with with Theorem 4.1, this observation confirms Conjecture 5.

The following theorem was proved implicitly in [22].

Theorem 4.3. For a graph G, let μ_{1} and q_{1} be the largest eigenvalues of the Laplacian and the signless Laplacian, respectively. We have μ_{1} ⩽ q_{1} with equality if and only if G is bipartite.

This inequality confirms the lower bound in Conjecture 10.

The lower bound in Conjecture 11 is confirmed by Theorem 3.4 of [3].

Conjecture 12 is verified by Theorem 3.2 of [3]. Note that equality holds also for the graph K_{3}. (Theorem 3.2 of [3] contains also the inequality q_{2} ⩽ n − 2 with equality if the graph is complete. Theorem 3.7 of [3] provides an upper bound for q_{2} in the case of bipartite graphs, namely again n − 2, which is attained solely for K_{2,n−2}).

Conjecture 13 is resolved by results of [21](see also references cited therein). The result is obtained in the context of the Laplacian spectrum but in view of Proposition 2.5 it can be immediately reformulated for the signless Laplacian. It turned out that there are three extremal graphs for n even.

5. The largest eigenvalue

Our main goal in this section is to prove Theorem 5.6, which describes the form of graphs with maximal Q-index among graphs with given numbers of vertices and edges. This will resolve two of the AGX conjectures. We also deal with other conjectures related to the largest Q-eigenvalue.

First we consider how q_{1} changes when some edges of G are relocated. For any modification G′ of G, let Q′ be the corresponding signless Laplacian A′ + D′, with largest eigenvalue q′_{1}. If x is a unit eigenvector corresponding to q_{1} then from (3) we obtain:

(5)  q′_{1} − q_{1} = max_{∥y∥=1} y^{T} Q′y − x^{T} Q x ⩾ x^{T} (A′ − A)x + x^{T} (D′ − D)x,

with equality if and only if x is an eigenvector of Q′ corresponding to q_{1}(= q′_{1}). When G is connected, we can take x to be the principal eigenvector of G (that is, the unit positive eigenvector corresponding to q_{1}). Then we can prove (cf. [17]):

Lemma 5.1. Let G′ be a graph obtained from a connected graph G (of order n) by rotating the edge rs (around r) to a position of the non-edge rt. Let x = (x_{1}, x_{2}, …, x_{n})^{T} be the principal eigenvector of G. If x_{t} ⩾ x_{s}, then q′_{1} > q_{1}.

Proof. From (4) we immediately obtain

(6)  q′_{1} − q_{1} ⩾ (x_{t} − x_{s})(2x_{r} + x_{s} + x_{t}).

Since x_{r}, x_{s} and x_{t} are positive and x_{t} ⩾ x_{s} we obtain q′_{1} ⩾ q_{1}. Equality holds only if x is an eigenvector of G′ for q′_{1} = q_{1}. But then, from the eigenvalue equations applied to the vertex t in G′ and G we find (q′_{1} − q_{1})x_{t} = x_{r} + x_{t}, and this is a contradiction.

This completes the proof. □

Assume now that G is a graph whose Q-index is maximal among all graphs with n vertices and m edges (m > 0).

Lemma 5.2. Under the above assumptions, either G is a connected graph or G has exactly one non-trivial component.

Proof. Let C be a component of G with index μ_{1} = μ_{1}(G). Suppose, by the way of contradiction, that G has another non-trivial component C′. Then G has an eigenvector x = (x_{1}, x_{2}, …, x_{n})^{T} corresponding to μ_{1} such that x_{i} > 0 for all i ∈ V (C) and x_{i} = 0 for all i ∉ V (C).

Now let t be a vertex of C and let rs be an edge in C′. Consider the graph G′ obtained from G by replacing rs with the edge rt. Since x_{t} > 0 and x_{r} = x_{s} = 0, Equation (5) shows that q_{1}(G′) > q_{1}, a contradiction. □

In view of this lemma, it suffices to consider the unique non-trivial component of G, and so we now assume further that G is connected.

Lemma 5.3. The graph G does not contain P_{4}, 2K_{2} or C_{4} as an induced subgraph.

Proof. Suppose, by the way of contradiction, that G contains a graph F ∈ {P_{4}, 2K_{2}, C_{4}} as an induced subgraph. Let x be the principal eigenvector of G, and let r, s, t, w be the vertices of F. Without loss of generality, x_{s} = min_{v∈V (F)} x_{v}. Additionally, the structure of F allows us to assume that r is a neighbour of s but not of t. Now let G′ be the graph obtained from G by rotating the edge rs (around r) to the non-edge position rt. By Lemma 5.1, we have q_{1}(G′) > q_{1}(G). If G′ is connected, this is a contradiction and we are done.

Accordingly, suppose that G′ is not connected. Then rs is a bridge in G, F ≠ C_{4}, and G − rs has the form G_{r} ˙∪ G_{s}, where r, t ∈ V (G_{r}) and s ∈ V (G_{s}).

We first observe that x_{v} < x_{s} for any vertex v ∈ V (G_{s}) ∖ {s}, for otherwise the Q–index of G is not maximal by Lemma 5.1. Similarly, x_{u} < x_{r} for any vertex u ∈ V (G_{r}) ∖ {r}. Recall next that x_{s} ⩽ x_{r}. If deg(s) > 1, there exists a vertex v in G_{s} adjacent to s. In this case, we may replace the edge vs with vr to obtain a connected graph with larger Q-index. Thus it remains to deal with the case deg(s) = 1. Then either F is the path srut or F consists of the independent edges rs, tu. In the former case we may replace ru with rt to obtain a connected graph with larger Q-index. In the latter case, interchanging t and u if necessary, we may replace tu with ru to obtain a connected graph with larger Q-index. This final contradiction completes the proof. □

From the above considerations, we arrive at the following result (announced in [8]).

Theorem 5.4. Let G be a connected graph of fixed order and size, with maximal Q-index. Then none of the graphs 2K_{2}, P_{4}, C_{4} is an induced subgraph of G.

The graphs without 2K_{2}, P_{4}, C_{4} as an induced subgraph are precisely those with a stepwise adjacency matrix, as defined in [6, Section 3.3]. This assertion is equivalent to the following result proved in [23].

Proposition 5.5. To within isolated vertices, the graphs without 2K_{2}, P_{4}, C_{4} as an induced subgraph are precisely the nested split graphs.

From Theorem 5.4 we therefore have:

Theorem 5.6. Among the graphs of prescribed order and size, a graph with maximal Q-index is, to within isolated vertices, a nested split graph.

In particular, a graph with maximal Q-index among the connected graphs of prescribed order and size is a nested split graph. We can now use Theorem 5.6 to confirm two of the AGX conjectures.

Theorem 5.7. Let G be a graph with maximal Q-index among connected graphs with n vertices and m edges.

(i) If m = n − 1 then G is the star S_{n} = K_{1,n−1}.

(ii) if m = n then G is the graph S_{n}^{+} obtained from S_{n} by adding an edge; (iii) if m = n + 1 then G is the graph obtained from S_{n} by adding two adjacent

edges.

Thus Theorem 5.7 identifies the trees, the unicyclic graphs and the bicyclic graphs of order n with maximal Q-index. In particular, we can confirm the upper bounds in Conjectures 2 and 3: the only tree which is a nested split graph is a star and the only unicyclic graph which is a nested split graph is a star together with an additional edge. The lower bounds in Conjectures 1 and 2 are confirmed by Proposition 2.2: the graphs with minimal Q-index among trees and among unicyclic graphs are the path and the cycle respectively.

Next we confirm Conjecture 4. We label vertices of G so that vertex 1 has maximal degree Δ, and vertices 2, …, Δ+1 are the neighbours of vertex 1. Now consider the Rayleigh quotient x^{T} ((D+A)x)/x^{T} x, where x = (Δ, 1, …, 1, 1, 0, …, 0)^{T}, with Δ entries equal to 1. Since each vertex has degree at least 1, this quotient is at least (Δ(Δ^{2} + Δ) + Δ(Δ + 1))/(Δ^{2} + Δ) = Δ + 1. When equality holds, vertices 2, …, Δ + 1 have degree 1 and so G is a star.

Alternatively, we can confirm Conjecture 4 by citing Theorem 4.3 and the following result from [19] concerning the largest eigenvalue μ_{1} of the Laplacian matrix: μ_{1} ⩾ Δ + 1, with equality if and only if Δ = n − 1. We note that the case of equality for the signless Laplacian is more restrictive than that for the Laplacian.

Concerning Conjecture 7, the lower bound holds for graphs which are not trees because we can take the all-1 vector in a Rayleigh quotient for Q to obtain q_{1} ⩾ \overline{d}+2. In fact, for \overline{d} ⩾ 2 by Conjecture 5 (already confirmed) we have q_{1} ⩾ 2\overline{d} ⩾ \overline{d} + 2 and equality holds if and only if G is regular of degree 2. For trees of order n ⩾ 5 we use Conjecture 1 (already confirmed) to obtain q_{1} ⩾ 2 + 2 cos \frac{π}{n} > 4 − 2/n = \overline{d} + 2.

The upper bounds in Conjectures 6 and 7 may be regarded as upper bounds for q_{1} as a function of m and n, where m is the number of edges; in view of Theorem 5.6, it suffices to verify the bounds for nested split graphs.

The lower bound in Conjecture 8 is also verified using Conjecture 1 (already confirmed): we have q_{1} ⩾ 2λ_{1} ⩾ λ_{1} + \overline{d}, with equality if and only if G is regular.

The lower bound in Conjecture 9 follows from the lower bound in Conjecture 10 (already confirmed), since 1 ⩽ λ_{1} for graphs with at least one edge. We note that the upper bound holds for bipartite graphs, because then μ_{1} = q_{1} by Proposition 2.5.

6. Other conjectures

We may confirm Conjecture 16 as follows. Suppose first that Δ ⩽ n − 2. Since q_{2} ⩾ 0, we have Δ − q_{2} ⩽ n − 2, with equality if and only if q_{2} = 0 and Δ = n − 2. However, if q_{2} = 0 then Proposition 2.3 provides a contradiction. It remains to deal with the case Δ = n − 1, when the Conjecture reduces to: q_{2} ⩾ 1 with equality if and only if G is a star. This is just Conjecture 12, confirmed above.

A few of the conjectures are related to the least Q-eigenvalue, and among them is Conjecture 24. According to this conjecture, the minimal value of the least Qeigenvalue among connected non-bipartite graphs of prescribed order is attained for the odd-unicyclic graph obtained from a triangle by appending a path. By the Interlacing Theorem such an extremal graph is an odd-unicyclic graph, and so we discuss the least eigenvalue in odd-unicyclic graphs. Our investigations provide supporting evidence for Conjecture 24.

We use the notation of Sections 1 and 2, and write U_{e,f} for the set of unicyclic graphs on e + f vertices with a cycle of length e.

By the Interlacing Theorem we have

0 = q_{n}(P_{n}) ⩽ q_{n}(E_{e,n−e}) ⩽ q_{n−1}(P_{n}), e = 3, 5, …, e_{max} ⩽ n.

Hence

0 ⩽ q_{n}(E_{e,n−e}) ⩽ 2 (1 − cos \frac{π}{n}) = 4 sin^{2} \frac{π}{2n}.

For an odd-unicyclic graph we have ψ = 1/n and so we obtain the following double inequality from Equation (3):

\frac{1}{12n^{2}} ⩽ q_{n}(E_{e,n−e}) ⩽ \frac{4}{n}.

We conclude that

\frac{1}{12n^{2}} ⩽ q_{n}(E_{e,n−e}) ⩽ 4 sin^{2} \frac{π}{2n} ≈ \frac{π^{2}}{n^{2}} ,

i.e., n^{2}q_{n}(E_{e,n−e}) = O(1).

The following proposition is easily obtained from Theorem 2.8.

Proposition 6.1. For a graph G on n vertices, with girth g, we have:

p_{n}(G) = 0, (−1)^{n−1}p_{n−1}(G) = ng

if G is an even-unicyclic graph, and

(−1)^{n}p_{n}(G) = 4, (−1)^{n−1}p_{n−1}(G) = ng + 4 ∑ t_{i}

if G is an odd-unicyclic graph, t_{i} being the number of vertices of the tree obtained by deleting an edge i outside the cycle.

We mention in passing that the girth can be determined from the Q-eigenvalues in the case of even-unicyclic graphs but not in the case of odd-unicyclic graphs. For (adjacency) eigenvalues we have exactly the opposite situation. However, Laplacian eigenvalues perform best: the girth of a unicyclic graph can be determined in all cases. (Then the coefficient of the linear term in the characteristic polynomial is equal to −n times the number N of spanning trees, and for unicyclic graphs, N is equal to the girth. Note that results concerning such coefficients for some other classes of graphs, in particular for trees, have been obtained in [20].)

The following lemma is a straightforward consequence of Proposition 6.1.

Lemma 6.2. Let G be an odd-unicyclic graph on n vertices. Let u be a vertex of degree at least 3 and v a vertex of degree 1 in G. Let T be the tree attached at u. Let G′ be the graph obtained by relocating the tree T from u to v. Then

(−1)^{n−1}p_{n−1}(G′) > (−1)^{n−1}p_{n−1}(G).

Using Lemma 6.2 repeatedly, we obtain:

Proposition 6.3. For G ∈ U_{e,f}, e odd, and G ≠ E_{e,f} we have

(−1)^{n−1}p_{n−1}(E_{e,f}) > (−1)^{n−1}p_{n−1}(G),

where n = e + f.

In addition, we have the following observation.

Proposition 6.4. For n odd and e = 5, 7, …, n we have

(−1)^{n−1}p_{n−1}(E_{3,n−3}) > (−1)^{n−1}p_{n−1}(E_{e,n−e}).

Proof. From Proposition 6.1 we have

(−1)^{n−1}p_{n−1}(E_{e,n−e}) = ne+4((n−e)+(n−e−1)+⋯+1) = 2e^{2}−(3n+2)e+2n^{2}+2n,

and the maximum value of this function is attained when e = 3. □

Now, for sufficiently small x, the equation Q_{G}(x) = 0 can be reduced to p_{n−1}(G)x + p_{n}(G) = 0, whose solution −p_{n}(G)/p_{n−1}(G) could be considered as an approximation for q_{n}(G). By Propositions 6.1, 6.3 and 6.4, this approximation value is minimal for the graph E_{3,n−3}. These arguments support Conjecture 24.

We note in passing that extremal results concerning the coefficients p_{i}(T) for a tree T have been obtained in [26]. In particular, it is proved that for i = 3, 4, …, n − 1 the coefficient (−1)^{i}p_{i} is minimal in paths and maximal in stars.

Conjecture 25 seems to be interesting and difficult to resolve. It is related to the difference between the largest and the least eigenvalue which is known as spectral spread (for any matrix). The corresponding conjecture for eigenvalues of the adjacency matrix is identified in [1] as a hard conjecture (also produced by AGX). It seems that we have enough evidence that system AGX can produce difficult conjectures.

In contrast, we can deal easily with the conjectures concerning eigenvalue multiplicities. First, one can confirm Conjecture 27 as follows. If e(Q) = 2 then the minimal polynomial of Q has the form x^{2} + ax + b, and so A^{2} + AD + DA + D^{2} + aA + aD + bI = O. For distinct i, j this gives a_{ij}^{(2)} + (d_{j} + d_{i} + a)a_{ij} = 0, and so there are no vertices i, j at distance 2. Conjecture 27 has also been confirmed in [9].

More generally, as in [5, Theorem 3.13], the diameter of G is bounded above by e(Q) − 1, since (in the terminology of [8]), the (i, j)-entry of Q^{k} is the number of semi-edge walks from i to j [8, Theorem 4.1].

Conjecture 28 is true, because Q − dI has k repeated rows, and Conjecture 29 is true, because Q − (d − 1)I has k repeated rows. The validity of these conjectures follows also from a remark in [24].

Conjecture 30 is false, with K_{n} (n > 5) a counterexample since then d−1 = n−2 with multiplicity n − 1. (Note that the hypotheses are a special case of those of Conjecture 29.)

Remark. Together with some colleagues we continue to consider conjectures presented in this paper. In particular, we expect results related to Conjectures 6, 7, 22, 23 and 24.

Acknowledgement. We are grateful to P. Hansen who accepted our challenge to create some conjectures related to signless Laplacian eigenvalues using the programming package AGX [2], and to his collaborator M. Aouchiche whose experiments led to the formulation of the conjectures.

References

[1] M. Aouchiche, F. K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S. K. Simić, D. Stevanović, Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, Europ. J. Oper. Res., to appear.

[2] G. Caporossi, P. Hansen, Variable Neighborhood Search for Extremal Graphs I, Discrete Math., 212(2000), 29–44.

[3] Y. Chen, Properties of spectra of graphs and line graphs, Appl. Math. J. Chinese Univ. Ser. B 17(3) (2002), 371–376.

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

[5] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.

[6] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

[7] D. Cvetković, P. Rowlinson, S. K. Simić, Spectral Generalizations of Line Graphs, On Graphs with Least Eigenvalue −2, Cambridge University Press, Cambridge, 2004.

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

[9] E. R. van Dam, Graphs with few eigenvalues, Thesis, Tilburg University, Tilburg, 1996.

[10] E. R. van Dam, W. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241–272.

[11] A. Daneshgar, H. Hajiabolhassan, Graph homomorphisms and nodal domains, Linear Algebra Appl. 418(2006), 44–52.

[12] E. Dedo, La reconstruibilita del polinomio carrateristico del comutato di un grafo, Boll. Unione Mat. Ital. 18A (1981), No. 5, 423–429.

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

[14] F. R. Gantmacher, Theory of Matrices I, II Chelsea, New York, 1960.

[15] R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218–238.

[16] W. Haemers, E. Spence, Enumeration of cospectral graphs, Europ. J. Comb. 25 (2004), 199– 211.

[17] Y. Hong, X.-D. Zhang, Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees, Discrete Math. 296 (2005), 187–197.

[18] B. Mohar, Graph Laplacians, in: Topics in Algebraic Graph Theory (eds, L. W. Beineke, R. J. Wilson), Cambridge University Press, 2004, pp. 113–136.

[19] R. Merris, Laplacian matrices of graphs, Linear Algebra Appl. 197–198(1994), 143–176.

[20] C. S. Oliveira, N. M. M. de Abreu, S. Jurkiewicz, The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes, Linear Algebra Appl. 356(2002), 113–121.

[21] Jia-yu Shao, Li Zhang, Xi-ying Yuan, On the second Laplacian eigenvalues of trees of odd order. Linear Algebra Appl. 419 (2006), no. 2–3, 475–485.

[22] J.-L. Shu, Y. Hong, K. Wen-Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra Appl. 347(2002), 123–129.

[23] S. K. Simić, E. M. Li Marzi, F. Belardo, Connected graphs of fixed order and size with maximal index: Structural considerations, Le Matematiche 59 (2004), Nos. 1–2, 349–365.

[24] E. V. Vahovskiĭ, On the eigenvalues of the neighbourhood matrix of simple graphs (Russian), Sibir. Mat. J. 6 (1965), 44–49.

[25] B. Zhou, I. Gutman, A connection between ordinary and Laplacian spectra of bipartite graphs, Linear an Multilinear Algebra, to appear

[26] P. Zhu, R. C. Wilson, A study of graph spectra for comparing graphs, to appear.

Matematički institut SANU

Kneza Mihaila 36

11000 Beograd, p.p. 367

Serbia

    ecvetkod@etf.bg.ac.yu
    ssimic@raf.edu.yu

Department of Computing Science and Mathematics University of Stirling Stirling FK9 4LA Scotland

    p.rowlinson@stirling.ac.uk