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

TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I

Dragoš Cvetković and Slobodan K. Simić

Communicated by Žarko Mijajlović

Abstract. A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular with those based on the adjacency matrix A and the Laplacian L. The Q-theory can be composed using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, or with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. We present results on graph operations, inequalities for eigenvalues and reconstruction problems.

1. Introduction

The idea of spectral graph theory (or spectral theory of graphs) is to exploit numerous relations between graphs and matrices in order to study problems with graphs by means of eigenvalues of some graph matrices, i.e., matrices associated with graphs in a prescribed way. Since there are several graph matrices which can be used for this purpose, one can speak about several such theories so that spectral theory of graphs is not unique. Of course, the spectral theory of graphs consists of all these special theories including their interactions.

By a spectral graph theory we understand, in an informal sense, a theory in which graphs are studied by means of the eigenvalues of some graph matrix M. This theory is called M-theory. Hence, there are several spectral graph theories (for example, the one based on the adjacency matrix, that based on the Laplacian, etc.). In that sense, the title “Towards a spectral theory of graphs based on the signless Laplacian" indicates the intention to build such a spectral graph theory

2000 Mathematics Subject Classification: Primary 05C50. Key words and phrases: graph theory, graph spectra, adjacency matrix, signless Laplacian. Supported by the Serbian Ministry of Science and Technological Development, grant

144015G.

(the one which uses the signless Laplacian without explicit involvement of other graph matrices).

Recall that, given a graph, the matrix Q = D + A is called the signless Laplacian, where A is the adjacency matrix and D is the diagonal matrix of vertex degrees. The matrix L = D − A is known as the Laplacian of G.

In order to give motivation for such a choice we introduce some notions and present some relevant computational results.

Graphs with the same spectrum of an associated matrix M are called cospectral graphs with respect to M, or M-cospectral graphs. A graph H cospectral with a graph G, but not isomorphic to G, is called a cospectral mate of G. Let G be a finite set of graphs, and let G′ be the set of graphs in G which have a cospectral mate in G with respect to M. The ratio |G′|/|G| is called the spectral uncertainty of (graphs from) G with respect to M (or, in general, spectral uncertainty of the M-theory).

The papers [11], [17] provide spectral uncertainties r_{n} with respect to the adjacency matrix A, s_{n} with respect to the Laplacian L and q_{n} with respect to the signless Laplacian Q of sets of all graphs on n vertices for n ⩽ 11:

\begin{matrix}n & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ r_{n} & 0 & 0.059 & 0.064 & 0.105 & 0.139 & 0.186 & 0.213 & 0.211 \\ s_{n} & 0 & 0 & 0.026 & 0.125 & 0.143 & 0.155 & 0.118 & 0.090 \\ q_{n} & 0.182 & 0.118 & 0.103 & 0.098 & 0.097 & 0.069 & 0.053 & 0.038 \end{matrix}

We see that numbers q_{n} are smaller than the numbers r_{n} and s_{n} for n ⩾ 7. In addition, the sequence q_{n} is decreasing for n ⩽ 11 while the sequence r_{n} is increasing for n ⩽ 10. This is a strong basis for believing that studying graphs by Q-spectra is more efficient than studying them by their (adjacency) spectra.

Since the signless Laplacian spectrum performs better also in comparison to spectra of other commonly used graph matrices (Laplacian, the Seidel matrix), an idea was expressed in [11] that, among matrices associated with a graph (generalized adjacency matrices), the signless Laplacian seems to be the most convenient for use in studying graph properties.

This suggestion was accepted in [4] where it was also noted that almost no results in the literature on the spectra of signless Laplacian existed at that time. Moreover, connection with spectra of line graphs and the existence of a well developed theory of graphs with least eigenvalue −2 [8] were used as additional arguments for studying eigenvalues of the signless Laplacian.

In order to avoid repetitions and to reduce the list of references we shall refer to our previous papers, in particular to the survey paper [9]. (Concerning the papers on the signless Laplacian published before 2003, here we mention only [13]). The present paper extends the surveys [9] and [10] by providing further results and comments.

SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I 21

Only recently has the signless Laplacian attracted the attention of researchers. As our bibliography shows, several papers on the signless Laplacian spectrum (in particular, [2], [5], [10], [12], [14], [15], [16], [24], [26], [28], [29], [30], [31], [32], [35], where the signless Laplacian is explicitly used) have been published since 2005. We are also aware that several other papers are being prepared, or are already in the process of publication. Therefore, we are now in position to summarize the current development. We shall, in fact, outline a new spectral theory of graphs (based on the signless Laplacian), and call this theory the Q-theory.

The rest of this paper is organized as follows. Section 2 presents the main spectral theories, including the Q-theory, and their interactions. In this way, the Q-theory is mostly composed from several patches borrowed from other spectral theories. Section 3 contains several comparisons of the effectiveness of solving various classes of problems within particular spectral theories with an emphasis on the performance of the Q-theory. This survey will be continued in the second part of this paper.

2. Main spectral theories and their interactions

In 2.1 we list existing spectral theories including A-theory and L-theory as the most developed theories. In the rest of the section we show how the Q-theory can be composed using various connections to other theories:

• equivalency with A-theory and L-theory for regular graphs (Subsection 2.2),

• equivalency with L-theory for bipartite graphs (Subsection 2.3),

• general analogies with A-theory (Subsection 2.4),

• analogies with A-theory via line graphs (Subsection 2.5),

• analogies with A-theory via subdivision graphs (Subsection 2.6).

This fragmentation appears in this presentation because the Q-theory has attracted attention only after other theories had already been developed. It is quite possible to present the Q-theory smoothly if it is a primary goal.

The notions of enriched and restricted spectral theories will be considered in the second part of this paper.

2.1. Particular theories. We shall start with some definitions related to a general M-theory.

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

In particular, if M is equal to one of the matrices A, L and Q (associated to a graph G on n vertices), then the corresponding eigenvalues (or spectrum) are called the A-eigenvalues (or A-spectrum), L-eigenvalues (or L-spectrum) and Qeigenvalues (or Q-spectrum), respectively. Throughout the paper, these eigenvalues will be denoted by λ_{1} ⩾ λ_{2} ⩾ ⋯⩾ λ_{n}, μ_{1} ⩾ μ_{2} ⩾ ⋯⩾ μ_{n} and q_{1} ⩾ q_{2} ⩾ ⋯⩾ q_{n}, respectively. They are the roots of the corresponding characteristic polynomials P_{G}(x) = det(xI − A), L_{G}(x) = det(xI − L) and Q_{G}(x) = det(xI − Q) (note, P_{G}(x) stands for A_{G}(x)). The largest eigenvalues, i.e., λ_{1}, μ_{1} and q_{1}, are called the A-index, L-index and Q-index (of G), respectively.

Together with Q-theory we shall frequently consider the relevant facts from A-theory and L-theory as the most developed spectral theories and therefore useful in making comparisons between theories.

We shall mention in passing theories based on the matrix L̂ = D^{−1/2} LD^{−1/2} , the normalized (or transition) Laplacian matrix^{1}; (see [3]) and on the Seidel matrix S = J − I − 2A (see, for example, [6]).

Since the eigenvalues of the matrix D are just vertex degrees, the D-theory is not, in practice, a spectral theory although it formally is. This example shows that the study of graphs by any sequence of structural graph invariants can be formally represented as a spectral theory.

2.2. Regular graphs. An important characteristic of a spectral theory is whether or not regular graphs can be recognized within that theory. Such a question is answered for a broad class of graph matrices in [11]. The answer is positive for matrices A, L and Q, but it is negative for the matrix S. For the signless Laplacian see Proposition 3.1 of [9], where it is also stated that the number of components in regular graphs is equal to the multiplicity of the Q-index.

The following characterization of regular graphs, known in the A-theory (cf. [6, p. 104]), can be formulated also in the Q-theory.

Proposition 2.1. A graph G is regular if and only if its signless Laplacian has an eigenvector all of whose coordinates are equal to 1.

Of course, for regular graphs we can express the characteristic polynomial of the adjacency matrix and of the Laplacian in terms of the Q-polynomial and use them to study the graph. Thus for regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian (by a translate of the spectrum). It suffices to observe that if G is a regular graph of degree r, then D = rI, A = Q − rI and we have

P_{G}(x) = Q_{G}(x + r).

The mapping ϕ(q) = q − r maps the Q-eigenvalues to the A-eigenvalues and can be considered as an isomorphism of the Q-theory of regular graphs to the corresponding part of the A-theory.

Example. We give A-eigenvalues, L-eigenvalues and Q-eigenvalues^{2} for two representative classes of regular graphs: complete graphs and circuits. Provided one kind of eigenvalues is known, the other two kinds can be calculated by above formulas.

1Here we assume that G has no isolated vertices.

2Superscripts are used to denote the multiplicities of eigenvalues.

complete graph K_{n} (n ⩾ 2) :  cycle C_{n} (n ⩾ 3) :
A : n − 1, (−1)^{n−1}  A :  2 cos \frac{π}{2n} j (j = 0, 1, …, n − 1)
L :  0, n^{n−1}  L : 2 − 2 cos \frac{π}{2n} j (j = 0, 1, …, n − 1)
Q : 2n − 2, (n − 2)^{n−1}  Q : 2 + 2 cos \frac{π}{2n} j (j = 0, 1, …, n − 1)

For regular graphs many existing results from the A-theory can be reformulated in the Q-theory.

Proposition 2.2. 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 Q-eigen-value 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.

We can go on and reformulate in the Q-theory, for example, all results from Section 3.3 of [6] and several related results for regular graphs.

2.3. Bipartite graphs. For bipartite graphs we have L_{G}(x) = Q_{G}(x) (cf. Proposition 2.3 of [9]). In this way, the Q-theory can be identified with the Ltheory for bipartite graphs.

For non-regular and non-bipartite graphs the Q-polynomial really plays an independent role; for other graphs it can be reduced to either P_{G}(x) or L_{G}(x), or to both.

Unlike the situation with the regularity property, the problem here is that bipartite graphs cannot always be recognized by the Q-spectrum. This difficulty can be overcome by requiring that always, together with the Q-spectrum of a graph, the number of components is given, as explained in [4] (and [9]).

Among many results on bipartite graphs in the L-theory, let us mention a theorem from [20] (and [16]) saying that no starlike trees^{3} are cospectral. (It was known before that the same statement holds also in the A-theory [21].) Now this statement holds also in the Q-theory.

2.4. Analogies with A-theory. The results which we survey in this subsection are obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix.

For example, the well known theorem concerning the powers of the adjacency matrix [6, p. 44] has the following counterpart for the signless Laplacian.

Theorem 2.3. Let Q be the signless Laplacian of a graph G. The (i, j)-entry of the matrix Q^{k} is equal to the number of semi-edge walks of length k starting at vertex i and terminating at vertex j.

3A starlike tree is a tree with exactly one vertex of degree greater than two.

For the proof and definition of semi-edge walks see [9].

The following statement and its proof is analogous to an existing result related to the adjacency spectrum [6, Theorem 3.13].

Theorem 2.4. Let G be a connected graph of diameter D with k distinct Qeigenvalues. Then D ⩽ k − 1.

The proof uses Theorem 2.3 (see [5]).

For other examples of analogies with A-theory, see also Theorems 3.2 and 3.3. Let G be a graph on n vertices with vertex degrees d_{1}, d_{2}, …, d_{n}. Let D(G)

be the (multi-)digraph obtained from G by adding d_{i} loops to the vertex i for each i = 1, 2, …, n. It was noted in [9] that the proof of Theorem 2.3 can be carried out by applying the theorem on powers of the adjacency matrix to the digraph D(G).

This observation can be generalized. In fact, the Q-theory of graphs G is isomorphic to the A-theory of digraphs D(G). In this way we have a useful tool in establishing analogies between the Q-theory and A-theory.

We shall provide some examples.

The interlacing theorem in its original form can be applied in a specific way in Q-theory. It is sufficient to use digraphs D(G) instead of graphs G.

Theorem 2.5. The Q-eigenvalues of a graph G and the A-eigenvalues of any vertex deleted subdigraph D(G) − v of D(G) interlace each other.

The same applies to the divisor concept (see [6, Chapter 4]). The theory of divisors anyway deals with multidigraphs. Hence we have the following theorem.

Theorem 2.6. The A-polynomial of any divisor of D(G) divides the Q-poly-nomial of G.

This theorem was implicitly used in [32] (cf. Lemma 5.6 from that paper). For some related questions concerning graph homomorphisms see [12].

2.5. Line graphs. Let G be a graph on n vertices, having m edges and let R be its vertex-edge incidence matrix. The following relations are well-known:

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

where A(L(G)) is the adjacency matrix of L(G), the line graph of G. Since the non-zero eigenvalues of RR^{T} and R^{T}R are the same, we immediately get that

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

Therefore it follows that

(2)  q_{1} − 2, q_{2} − 2, …, q_{n} − 2, and (−2)^{m−n}

are the A-eigenvalues of L(G); note, if m − n < 0 then q_{m+1} = ⋯= q_{n} = 0 and thus the multiplicity of −2 is non-negative.

The results which we survey in this subsection are obtained indirectly via line graphs using formula (1) and results from A-theory.

This method can be used to calculate Q-eigenvalues of some graphs.

Example. The A-eigenvalues of L(P_{n}) = P_{n−1} are 2 cos \frac{π}{n} j (j = 1, 2, …, n−1) and by (2) the Q-eigenvalues of P_{n} are 2 + 2 cos \frac{π}{n} j = 4 cos^{2} \frac{π}{2n} j (j = 1, 2, …, n). Alternatively, one can say that Q-eigenvalues of P_{n} are 4 sin^{2} \frac{π}{2n} j (j = 0, 1, ..., n−1).

Example. The A-eigenvalues of L(K_{m,n} ) are m+n−2,(n−2)^{m−1} , (m−2)^{n−1} ,

(−2)^{(m−1)(n−1)} and were obtained in [6, p. 175] via the sum of graphs. By formula (1) we see that the Q-eigenvalues of K_{m,n} are m + n, n^{m−1} , m^{n−1} , 0.

A specific form of the interlacing theorem for Q-eigenvalues was established in [9] and a proof using line graphs was given in [10]. In this version we delete edges instead of vertices.

Another example of deriving results on Q-eigenvalues via line graphs is Theorem 4.7 of [9] giving a lower and an upper bound on the Q-index in terms of vertex degrees.

The paper [23] contains a new and shorter proof of the fact (previously known in the literature) that the multiplicity of the A-eigenvalue 0 in line graphs of trees is at most 1. Having in mind formula (1) one can say that the multiplicity of the Q-eigenvalue 2 in trees is at most 1.

Suppose that G′ is obtained from G by splitting a vertex v: namely if the edges incident with v are vw (w ∈ W), then G′ is obtained from G−v by adding two new vertices v_{1} and v_{2} and edges v_{1}w_{1} (w_{1} ∈ W_{1}), v_{2}w_{2} (w_{2} ∈ W_{2}), where W_{1} ∪ W_{2} is a non-trivial bipartition of W.

The following theorem is analogous to a theorem for A-index, proved in [25] (see also [7, p. 56]).

Theorem 2.7. If G′ is obtained from the connected graph G by splitting any vertex then q_{1}(G′) < q_{1}(G).

Proof. We first note that L(G′) is a proper (spanning) subgraph of L(G). Thus λ_{1}(L(G′)) < λ_{1}(L(G)). Then the proof follows from (2). □

See also Subsection 3.1 for further examples of using line graphs to derive results in the Q-theory.

2.6. Subdivision graphs. Let G be a graph on n vertices, having m edges. Let S(G) be the subdivision graph of G. As noted in [10], the following formula appears implicitly in the literature (see e.g., [6, p. 63] and [34]):

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

Therefore it follows that

(4)  ± \sqrt{q_{1}}, ±\sqrt{q_{2}}, …, ±\sqrt{q_{n}}, and 0^{m−n}

are the A-eigenvalues of S(G) (with the same comment as with (2) if m − n < 0).

It is worth mentioning that formulas (1) and (3) provide a link between Atheory and Q-theory (and corresponding spectra, see (2) and (4)). While formula (1) has been already used in this context [9], the connection with subdivision graphs remains to be exploited. Some results in this direction have been obtained in [5].

Here we first have the following observation.

Theorem 2.8. Let G be a connected graph with A-index λ_{1} and Q-index q_{1}. If G has no vertices of degree 1 and is not a cycle, then q_{1} < λ_{1}^{2}. If G is a cycle, then q_{1} = λ_{1}^{2} = 4. If G is a starlike tree, then q_{1} > λ_{1}^{2}.

The proof of the theorem is based on the behaviour of the A-index when all edges are subdivided (see, [18], or [6, p. 79]). Subdividing an edge which lies in the path appended to the rest of a connected graph increases the A-index, otherwise decreases except if the graph is a cycle. Since the A-index of S(G) is equal to \sqrt{q_{1}} we are done.

Let deg(v) be the degree of the vertex v. An internal path in some graph is a path v_{0}, v_{1}, …, v_{k+1} for which deg(v_{0}), deg(v_{k+1} ) ⩾ 3 and deg(v_{1}) = ⋯= deg(v_{k}) = 2 (here k ⩾ 0, or k ⩾ 2 whenever v_{k+1} = v_{0}).

Theorem 2.9. Let G′ be the graph obtained from a connected graph G by subdividing its edge uv. Then the following holds:

(i) if uv belongs to an internal path then q_{1}(G′) < q_{1}(G); (ii) if G ≠ C_{n} for some n ⩾ 3, and if uv is not on the internal path then

q_{1}(G′) > q_{1}(G). Otherwise, if G = C_{n} then q_{1}(G′) = q_{1}(G) = 4.

Proof. Assume first that uv is on the internal path. Let w be a vertex inserted in uv (to obtain G′). Then S(G′) can be obtained from S(G) by inserting two new vertices, one in the edge uw the other in the edge wv. Note that both of these vertices are inserted into edges belonging to the same internal path. But then λ_{1}(S(G′)) < λ_{1}(S(G)) (by the result of Hoffman and Smith from A-theory). The rest of the proof of (i) immediately follows from (4).

To prove (ii), assume that uv is not on the internal path. Then, if G ≠ C_{n}, G is a proper subgraph of G′ and hence, q_{1}(G′) > q_{1}(G). Finally, if G = C_{n}, then q_{1}(G′) = q_{1}(G) = 4, as required. □

A direct proof of the above theorem has recently appeared in [15].

Theorem 2.10. Let G(k, l) (k, l ⩾ 0) be the graph obtained from a non-trivial connected graph G by attaching pendant paths of lengths k and l at some vertex v. If k ⩾ l ⩾ 1 then q_{1}(G(k, l)) > q_{1}(G(k + 1, l − 1)).

Proof. Consider the graphs S(G(k, l)) and S(G(k+1, l−1)). By using the corresponding result of [22] for the A-index, we immediately get that λ_{1}(S(G(k, l))) > λ_{1}(S(G(k + 1, l − 1))). The rest of the proof immediately follows from (4). □

Some other results of the same type will be considered in the second part of this paper.

3. Solving problems within Q-theory

Although the Q-theory has a smaller spectral uncertainty than other frequently used spectral theories (as can be expected by the computational results from [11]- see Section 1), it seems that we do not have enough tools at the moment to exploit this advantage. In this section we present some results supporting such feelings. Our results refer to graph operations, inequalities for eigenvalues and reconstruction problems.

3.1. Graph operations. There are very few formulas for Q-spectra of graphs obtained by some operations on other graphs. This is quite different from the situation with A-spectrum (see, for example, [6], where the whole Chapter 2 is devoted to such formulas). Even with the L-spectrum the situation is better than in the Q-spectrum.

First, in common with many other spectral theories, the Q-polynomial of the union of two or more graphs is the product of Q-polynomials of the starting graphs (i.e., the spectrum of the union is the union of spectra of original graphs). In other words, the Q-polynomial of a graph is the product of Q-polynomials of its components.

Formula (1) connects the Q-eigenvalues of a graph with the A-eigenvalues of its line graph, while formula (3) does the same thing with respect to its subdivision graph.

If G is a regular graph of degree r, then its line graph L(G) is regular of degree 2r − 2 and we have Q_{L(G)} (x) = P_{L(G)} (x − 2r + 2). Formula (1) yields

Q_{L(G)} (x) = (x − 2r + 4)^{m−n} Q_{G}(x − 2r + 4).

Thus if q_{1}, q_{2}, …, q_{n} are the Q-eigenvalues of G, then the Q-eigenvalues of L(G) are q_{1} + 2r − 4, q_{2} + 2r − 4, …, q_{n} + 2r − 4 and 2r − 4 repeated m − n times. We see that in line graphs of regular graphs the least Q-eigenvalue could be very large.

We do have a useful result in the case of the sum of graphs (for the definition and the corresponding result for the adjacency spectra see, for example, [6, pp. 65– 72]).

If q_{i}^{(1)}, q_{j}^{(2)} are Q-eigenvalues of G_{1}, G_{2}, then the Q-eigenvalues of G_{1} + G_{2} are all possible sums q_{i}^{(1)} + q_{j}^{(2)}, as noted in [5].

Example. The Q-eigenvalues of a path have been determined in Subsection 2.5. The sum of paths P_{m} + P_{n} has eigenvalues 4( sin^{2} \frac{π}{2m} i + sin^{2} \frac{π}{2n} j) (i = 0, 1, …, m − 1, j = 0, 1, …, n − 1).

For the product we have the following interesting formula

(5)  Q_{G×K_{2}} (x) = Q_{G}(x)L_{G}(x) = L_{G×K_{2}} (x).

The formula is easily obtained by elementary determinantal transformations. Therefore it follows that q_{1}, q_{2}, …, q_{n} and μ_{1}, μ_{2}, …, μ_{n} are the Q-eigenvalues (and as well the L-eigenvalues) of the graph G × K_{2}. In particular, we have that the Q-indices of G and G × K_{2} are equal (as is the case for A-indices of these graphs; see [6, p. 69]).

While for the L-polynomial there is a formula involving the complement of the graph (see, for example, [6, p. 58]), no similar formula for the Q-polynomial seems possible.

Let G be a graph rooted at vertex u and let H be a graph rooted at vertex v. GuvH denotes the graph obtained from disjoint union of graphs G and H by adding the edge uv. Let G + v be obtained from G by adding a pendant edge uv and let H +u be obtained from H by adding a pendant edge vu. Then the following formula holds

(6) Q_{GuvH} (x) = \frac{1}{x}(Q_{G+v} (x)Q_{H} (x) + Q_{G}(x)Q_{H+u} (x) − (x − 2)Q_{G}(x)Q_{H} (x))

This formula is derived by applying to the line graph L(GuvH) the well-known formula for the A-polynomial of the coalescence of two graphs (see, for example, [6, p. 159]).

If we put H = K_{1}, we get a useless identity for Q_{G+v} (x), indicating that no simple formula for Q_{G+v} (x) could exist (in contrast to the formula P_{G+v} (x) = xP_{G}(x) − P_{G−u} (x), see, for example, [6, p. 59]). However, if we take H = K_{2}, we obtain Q_{GuvH} (x) = (x − 2)Q_{G+v} (x) − Q_{G}(x), which is analogous to the mentioned formula in the A-theory.

We shall need the formula

(7)  P_{G}^{(k)}(x) = k! ∑_{S_{k}} P_{G−S_{k}} (x),

where the summation runs over all k-vertex subsets S_{k} of the vertex set of G. For k = 1 the formula is well-known [6, p. 60] and says that the first derivative of the A-polynomial of a graph is equal to the sum of A-polynomials of its vertex deleted subgraphs. We can obtain (7) by induction, as noted in [9]. If we apply (7) to the line graph L(G) of a graph G and use (2), we immediately obtain

(8)  Q_{G}^{(k)}(x) = k! ∑_{S_{k}} Q_{G−U_{k}} (x),

where the summation runs over all k-edge subsets U_{k} of the edge set of G. In particular, the first derivative of the Q-polynomial of a graph is equal to the sum of Q-polynomials of its edge deleted subgraphs. The last statement is of interest in reconstruction problems presented in Subsection 3.3.

3.2. Inequalities for eigenvalues. There are several ways to establish inequalities for Q-eigenvalues. This area of investigation is very promising as is the case of the other spectral theories.

Paper [10] is devoted to inequalities involving Q-eigenvalues. It presents 30 computer generated conjectures in the form of inequalities for Q-eigenvalues. Conjectures that are confirmed by simple results already recorded in the literature, explicitly or implicitly, are identified. Some of the remaining conjectures have been resolved by elementary observations; for some quite a lot of work had to be invested. The conjectures left unresolved appear to include some difficult research problems.

One of such difficult conjectures (Conjecture 24) has been confirmed in [2] by a long sequence of lemmas. The corresponding result reads:

Theorem 3.1. The minimal value of the least Q-eigenvalue among connected non-bipartite graphs of prescribed order is attained for the odd-unicyclic graph obtained from a triangle by appending a hanging path.

Many of the inequalities contain eigenvalues of more than one graph matrix. In particular, largest eigenvalues λ_{1}, μ_{1} and q_{1} of matrices A, L and Q, respectively, satisfy the inequalities μ_{1} ⩽ q_{1} and 2λ_{1} ⩽ q_{1}, with equality in the first place if and only if the graph is bipartite. See [10] for references (Conjectures 10 and 11).

These inequalities imply that any lower bound on μ_{1} is also a lower bound on q_{1} and that doubling any lower bound on λ_{1} also yields a valid lower bound on q_{1}. Similarly, upper bounds on q_{1} yield upper bounds on μ_{1} and λ_{1}. Paper [24] checks whether known upper bound on μ_{1} hold also for q_{1} and establishes that many of them do hold.

Best upper bounds for q_{1} under some conditions are given in an implicit way by the following two theorems. First we need a definition.

A graph G with the edge set E_{G} is called a nested split graph^{4} if its vertices can be ordered so that jq ∈ E_{G} implies ip ∈ E_{G} whenever i ⩽ j and p ⩽ q.

The following theorem can be proved in the same way as the corresponding result in A-theory [9].

Theorem 3.2. Let G be a graph with fixed numbers of vertices and edges, with maximal Q-index. Then G does not contain, as an induced subgraph, any of the graphs: 2K_{2}, P_{4} and C_{4}. Equivalently, G is a nested split graph.

Moreover, we also have [9]:

Theorem 3.3. Let G be a connected graph with fixed numbers of vertices and edges, with maximal Q-index. Then G does not contain, as an induced subgraph, any of the graphs: 2K_{2}, P_{4} and C_{4}. Equivalently, G is a nested split graph.

Theorems 3.2 and 3.3 have been announced in [9] and complete proofs appear in [10]. The result has been repeated independently in [32]. In particular, by Theorem 3.3 we easily identify the graphs with maximal Q-index within trees, unicyclic graphs and bicyclic graphs (of a fixed number of vertices). Namely, each of these sets of graphs has a unique nested split graph (see [10]). The result for bicyclic graphs has again been independently rediscovered in [14].

We see that both the A-index and Q-index attain their maximal values for nested split graphs. The question arises whether these extremal nested split graphs are the same in both cases. For small number of vertices this is true as existing graph data show. However, among graphs with n = 5 vertices and m = 7 edges there are two graphs (No. 5 and No. 6 for n = 5 in Appendix of [9]) with maximal Q-index while only one of them (No. 5) yields maximal A-index. In fact, for any n ⩾ 5 and m = n + 2 there are two graphs with a maximal Q-index [32].

In the next theorem we demonstrate another use of Theorem 3.3 by providing an analogue of Hong’s inequality from A-theory (see [19]) in Q-theory.

Theorem 3.4. Let G be a connected graph on n vertices and m edges. Then

q_{1}(G) ⩽ \sqrt{4m + 2(n − 1)(n − 2)} .

The equality holds if and only if G is a complete graph.

4This term was used in [10 ] with an equivalent definition. The present definition is used in [7], where the graphs in question were called graphs with a stepwise adjacency matrix.

Proof. Recall first that

λ_{1}(M) ⩽ max_{1⩽i⩽n} { ∑_{j=1}^{n} m_{ij} } ,

holds for any non-negative and symmetric n × n matrix M = (m_{ij} ). In addition, the equality holds if and only if all-one vector is an eigenvector for the M-index of M.

By Theorem 3.3 we may assume that G is a nested split graph. Consider the matrix Q^{2} (= (D + A)^{2} = D^{2} + DA + AD + A^{2}). Let d_{i} the degree of a vertex i of G. Consider next a multigraph G^{2} corresponding to matrix Q^{2}. Then, for the vertex i in the G^{2} we have

∑_{j=1}^{n} (Q^{2})_{ij} = (d_{i}^{2}) + ( ∑_{j∼i} d_{j} ) + (d_{i}^{2}) + ( ∑_{j∼i} (d_{j} − 1) + d_{i}) ,

or

∑_{j=1}^{n} (Q^{2})_{ij} = 2[d_{i}^{2} + ∑_{j∼i} d_{j} ].

Assume now that d_{i} < d_{k}. By the definition of nested split graphs we now have:

d_{i}^{2} + ∑_{j∼i} d_{j} < d_{k}^{2} + ∑_{l∼k} d_{l},

since this is equivalent to

d_{i}^{2} − d_{i} + ∑_{j∈Γ̄(i)} d_{j} < d_{k}^{2} − d_{k} + ∑_{l∈Γ̄(k)} d_{l},

where Γ̄(v) stands for the closed neighbourhood of v (observe also that Γ̄(i) ⊂ Γ̄(k) in our situation.

Let s be a vertex of G of maximum degree (= n − 1). such a vertex exists since G is a nested split graph. Then we have (for any vertex i)

∑_{j=1}^{n} (Q^{2})_{ij} ⩽ 2[d_{s}^{2} + ∑_{t∼s} d_{t}] = 4m + 2(n − 1)(n − 2),

and thus q_{1}(G)^{2} ⩽ 4m + 2(n − 1)(n − 2), as required.

The equality can hold only if G is a nested split graph (indeed, any other graph has the Q-index strictly less than some nested split graph). In addition, this nested split graph should be regular (otherwise, all-one vector is not its eigenvector of Q^{2} for q_{1}^{2}; note q_{1}^{2} = 2(d_{i}^{2} + ∑ _{j∼i} d_{j} ) should hold for each i). The only graph G with these properties is a complete graph. □

Next we prove an inequality relating the algebraic connectivity (the second smallest L-eigenvalue) and the second largest Q-eigenvalue of a graph.

Theorem 3.5. Let a be the second smallest L-eigenvalue and q_{2} the second largest Q-eigenvalue of a graph G with n (n ⩾ 2) vertices. We have a ⩽ q_{2} + 2 with equality if and only if G is a complete graph.

Proof. Since 2A = Q − L, the Courant–Weyl inequality for the third eigenvalue of 2A yields 2λ_{3} ⩽ q_{2} − a, i.e., a ⩽ q_{2} − 2λ_{3}. It was proved in [1] that for graphs with at least four vertices the inequality λ_{3} ⩾ −1 holds with equality if and only if G = \overline{K_{p,q} ∪ rK} _{1}. Now we obtain a ⩽ q_{2} + 2 but equality holds only for K_{n}. Namely, if p, q ⩾ 1 we have by direct calculation that a ⩽ n − 2 and q_{2} = n − 2. (In this case Q-eigenvalue 0 of \overline{G} has the multiplicity at least 2 with an eigenvector x orthogonal to all-one vector. The vector x is an eigenvector of q_{2} = n − 2 in G). For n = 2, 3 the theorem trivially holds. □

Theorem 3.5 confirms Conjecture 19 of [10].

We can treat in a similar way Conjecture 20 of [10] as well.

Theorem 3.6. Let a be the second smallest L-eigenvalue and q_{2} the second largest Q-eigenvalue of a non-complete graph G with n (n ⩾ 2) vertices. We have a ⩽ q_{2}.

Proof. The inequality a ⩽ q_{2} − 2λ_{3} immediately confirms the statement of the theorem for graphs with λ_{3} ⩾ 0. It was proved in [1] that for graphs with at least four vertices the inequality λ_{3} < 0 holds if and only if the complement of G has exactly one non-trivial component which is bipartite. The case G = \overline{K_{p,q} ∪ rK} _{1} from the previous theorem is excluded here. Hence \overline{G} contains a subgraph isomorphic to P_{3} whose Q-eigenvalues are 3, 1, 0. By the interlacing theorem the Q-index of \overline{G} is at least 3. As in the proof of previous theorem we have q_{2} = n − 2 while a ⩽ n − 3. □

The question of equality in Theorem 3.6 remains unsolved. Graphs for which equality holds are among the graphs with λ_{3} = 0. To this group belong the graphs mentioned with Conjecture 20 in [10] (stars, cocktail-party graphs, complete bipartite graphs with equal parts). We can add here regular complete multipartite graphs in general (cocktail-party graphs and complete bipartite graphs with equal parts are special cases).

3.3. Reconstruction problems. Studying graph reconstruction from collections of subgraphs of various kind is a traditional challenge in the graph theory.

It was proved in [13] that the Q-polynomial of a graph G is reconstructible from the collection of vertex deleted subgraphs G − v of G. The same result for the A-theory is well known [33].

Next result involves edge deleted subgraphs.

Theorem 3.7. The Q-polynomial of a graph G is reconstructible from the collection of the Q-polynomials of edge deleted subgraphs of G.

Proof. Given the Q-polynomials of edge deleted subgraphs of G, we can calculate by formula (2) the A-polynomials of vertex deleted subgraphs of the line graph L(G) of G. As is well-known, the A-eigenvalues of line graphs are bounded from below by −2. By results of [27] the A-polynomial of L(G) can now be reconstructed. Again by formula (2), we obtain the Q-polynomial of G. □

The reconstruction of the Q-polynomial of a graph G from the collection of the Q-polynomials of edge deleted subgraphs of G corresponds to the reconstruction of the A-polynomial of a graph G from the collection of the A-polynomials of vertex deleted subgraphs of G. While the first problem is positively solved by Theorem 3.7, the corresponding problem in the A-theory remains unsolved in the general case. Therefore Theorem 3.7 says much about the usefulness of the Q-theory.

References

[1] D. Cao, H. Yuan, The distribution of eigenvalues of graphs, Linear Algebra Appl. 216 (1995), 211–224.

[2] D. 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), No. 11–12, 2770–2780.

[3] F. R. K. Chung, Spectral Graph Theory, Amer. Math. Soc., Providence, Rhode Island, 1997.

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

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

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

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

[8] D. Cvetković, P. Rowlinson, S. Simić, Spectral generalizations of line graphs: On graphs with least eigenvalue −2, Cambridge University Press, Cambridge, 2004.

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

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

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

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

[13] E. Dedo, La ricostruibilità del polinomio caratteristico del commutato di un grafo, Boll. Unione Mat. Ital. 18A(5) (1981), 423–429.

[14] Fan Y.-Z., Tam B.-S., J. Zhou, Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs, Linear Multilinear Algebra 56(4) (2008), 381–397.

[15] L. Feng, Q. Li, Zhang X.-D., Minimizing the Laplacian spectral radius of trees with given matching number, Linear Multilinear Algebra 55(2) (2007), 199–207.

[16] L. Feng, G. Yu, No starlike trees are Laplacian cospectral, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 18 (2007), 46–51.

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

[18] A. J. Hoffman, J. H. Smith, On the spectral radii of topologically equivalent graphs, Recent Advances in Graph Theory, ed. M. Fiedler, Academia Praha, 1975, 273–281.

[19] Y. Hong, A bound on spectral radius of graphs, Linear Algebra Appl. 108 (1988), 135–140.

[20] M. Lepović, Some results on starlike trees and sunlike graphs, J. Appl. Math. Computing 11 (2003), 109–123.

[21] M. Lepović, I. Gutman, No starlike trees are cospectral, Discrete Math. 242 (2002), 292–295.

[22] Q. Li, K. Feng, On the largest eigenvalue of graphs (Chinese), Acta Appl. Sin. 2 (1979), 167–175.

[23] M. C. Marino, I. Sciriha, S. K. Simić, D. V. Tošić, More on singular line graphs of trees, Publ. Inst. Math., Nouv. Sér. 79(93) (2006), 1–12.

[24] C. S. Oliveira, L. S. de Lima, N. M. M. de Abreu, P. Hansen, Bounds on the index of the signless Laplacian of a graph, Les Cahiers du GERAD, G-2007-72.

[25] S. K. Simić, Some results on the largest eigenvalue of a graph, Ars Comb. 24A (1987), 211– 219.

[26] S. K. Simić, Z. Stanić, Q-integral graphs with edge-degrees at most five, Discrete Math. 308 (2008), 4625–4634.

[27] S. K. Simić, Z. Stanić, The polynomial reconstruction is unique for the graphs whose deck– spectra are bounded from below by −2, Linear Algebra Appl. 55(1) (2007), 35–43.

[28] S. K. Simić, Z. Stanić, On some forests determined by their Laplacian (signless Laplacian) spectrum, to appear.

[29] Z. Stanić, Some reconstructions in spectral graph theory and Q–integral graphs, (Serbian), Doctoral Thesis, Faculty of Mathematics, Belgrade, 2007.

[30] Z. Stanić, There are exactly 172 connected Q–integral graphs up to 10 vertices, Novi Sad J. Math. 37(2) (2007), 193–205.

[31] D. Stevanović, Research problems from the Aveiro Workshop on Graph Spectra, Linear Algebra Appl. 423(1) (2007), 172–181.

[32] Tam B.-S., Fan Y.-Z., J. Zhou, Unoriented Laplacian maximizing graphs are degree maximal, Linear Algebra Appl. 429 (2008), 735–758.

[33] W. T. Tutte, All the king’s horses: a guide to reconstruction, in: Graph theory and Related Topics, Proc. Conf. University of Waterloo, Waterloo, Ont. 1977, (eds. J. A. Bondy, U. S. R. Murty), Academic Press (New York), 1979, pp. 15–33.

[34] B. Zhou, I. Gutman, A connection between ordinary and Laplacian spectra of bipartite graphs, Linear Multilinear Algebra 56 (2008), 305–310.

[35] P. Zhu, R. C. Wilson, A study of graph spectra for comparing graphs, British Machine Vision Conference, 5–8 September 2005, Oxford Brookes University, BMVA, 679–688.

Matematički institut SANU (Received 15 08 2008) Kneza Mihaila 36 11000 Beograd, p.p. 367 Serbia

ecvetkod@etf.bg.ac.rs
sksimic@mi.sanu.ac.rs