Bulletin T.CXXXVII de l’Académie serbe des sciences et des arts − 2008 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 33

NEW THEOREMS FOR SIGNLESS LAPLACIAN EIGENVALUES^{1}

D. CVETKOVIĆ

(Presented at the 3rd Meeting, held on April 24, 2008)

(Dedicated to Ivan Gutman on the occasion of his 1000-th published scientific paper)

A b s t r a c t. We extend our previous surveys of properties of spectra of signless Laplacians of graphs. Some new theorems for the signless Laplacian eigenvalues are given. In particular, a theorem on spectral characterization of graphs with Q-index not exceeding 4 is proved. The signless Laplacian eigenvalues of connected graphs on six vertices are given in Appendix.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: graph theory, graph spectra, signless Laplacian, subdivision graph, tree, unicyclic graph

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

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

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 wellknown

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

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

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

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

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 Q-spectrum, respectively.

To avoid possible confusion, the eigenvalues and the spectrum of the adjacency matrix will be sometimes called adjacency eigenvalues and the spectrum.

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}.

Let (q_{1}, q_{2}, …, q_{n}) be the spectrum of Q, where the eigenvalues are such that q_{1} ≥ q_{2} ≥ … ≥ q_{n}. The largest eigenvalue q_{1} is called the Q-index of G.

The matrix L = D − A, known as the Laplacian of G, features prominently in the literature (see, for example, [3]). The matrix D + A is called the signless Laplacian and it appears very rarely in published papers before 2003 [8]. Only recently has the signless Laplacian attracted the attention of researchers [2, 8, 9, 1, 11, 10, 14, 19].

The present paper extends the surveys [8, 9] by providing further results, comments and numerical data. The new results include some equalities for the eigenvalues of D + A, while [9] mainly contains inequalities.

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_{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}.

A unicyclic graph containing an even (odd) cycle is called even-unicyclic (odd-unicyclic). The union of disjoint graphs G and H is denoted by G ∪ H, while mG denotes the union of m disjoint copies of G. The subdivision graph S(G) of a graph G is obtained from G when each edge of G is subdivided by a new vertex.

The paper [9] contains 30 conjectures related to the Q-eigenvalues of a graph have been formulated after some computer experiments. Almost all the conjectures are in the form of inequalities which provide upper or lower bounds for spectrally based graph invariants.

For some conjectures we have indicated that they are, at least partially, resolved (previously in the literature or in the paper, explicitly or implicitly). The conjectures left unresolved appear to include some difficult research problems.

A few of the conjectures are related to the least Q-eigenvalue, and among them there is one according to which 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 oddunicyclic graph, and so we discuss the least eigenvalue in odd-unicyclic graphs. Investigations in [9] provide supporting evidence for this conjecture. The conjectire has been proved in [1].

The rest of this paper is organized as follows. Section 2 elaborates results from the survey paper [8] which will be required later. Section 3 contains several new results including those on trees, unicyclic graphs and subdsivision graphs. In Section 4 a theorem on spectral characterization of graphs with Q-index not exceeding 4 is given. Q-eigenvalues of connected graphs on six vertices are given in Appendix.

2. Preliminaries

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.1. 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.2. For any graph, the multiplicity of 0 as an eigenvalue of the signless Laplacian is equal to the number of bipartite components.

The following proposition can be found in many places in the literature (see, for example, [15]), usually without a proof.

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

P r o o f. Suppose that the graph G is bipartite, with parts U and V. Consider the determinant defining Q_{G}(x). Multiply by −1 all rows corresponding to vertices in U and then do the same with the corresponding columns. The transformed determinant now defines the characteristic polynomial of the Laplacian of G.

The multiplicity of the eigenvalue 0 in the Laplacian spectrum is equal to the number of components, while for the signless Laplacian, the multiplicity of 0 is equal to the number of bipartite components. Therefore in nonbipartite graphs the two polynomials cannot coincide. □

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 Usubgraphs of G (cf. [12], [8]).

Theorem 2.4. 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.

Definition 2.5. A semi-edge walk (of length k) in an (undirected) graph G is an alternating sequence v_{1}, e_{1}, v_{2}, e_{2}, …, v_{k}, e_{k}, v_{k+1} of vertices v_{1}, v_{2}, …, v_{k+1} and edges e_{1}, e_{2}, …, e_{k} such that for any i = 1, 2, …, k the vertices v_{i} and v_{i+1} are end-vertices (not necessarily distinct) of the edge e_{i}.

We shall say that the walk starts at the vertex v_{1} and terminates at the vertex v_{k+1}.

The well known theorem concerning the powers of the adjacency matrix [3, p.44] has the following counterpart for the signless Laplacian [8].

Theorem 2.6. 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.

Let T_{k} = ∑_{i=1}^{n} q_{i}^{k} (k = 0, 1, 2, …) be the k-th spectral moment for the Q-spectrum. Since T_{k} = tr Q^{k}, we have the following corollaries [8].

Corollary 2.7. The spectral moment T_{k} is equal to the number of closed semi-edge walks of length k.

Corollary 2.8. Let G be a graph with n vertices, m edges, t triangles and vertex degrees d_{1}, d_{2}, …, d_{n}. We have

T_{0} = n, T_{1} = ∑_{i=1}^{n} d_{i} = 2m, T_{2} = 2m + ∑_{i=1}^{n} d_{i}^{2}, T_{3} = 6t + 3 ∑_{i=1}^{n} d_{i}^{2} + ∑_{i=1}^{n} d_{i}^{3}.

3. Some new results

We shall prove a number of propositions on several, not quite related, topics.

* * *

1. The sum of graphs. There are very few formulas for Q-spectra of graphs obtained by some operations on other graphs. This happens in the case of the sum of graphs (for the definition and the corresponding result for the adjacency spectra see, for example, [3], pp. 65-72).

Let G_{1}, G_{2} be graphs with adjacency matrices A_{1}, A_{2}, degree matrices D_{1}, D_{2} and signless Laplacans Q_{1}, Q_{2}, respectively. We have Q_{1} = A_{1} + D_{1}, Q_{2} = A_{2} + D_{2}.

It is known that A_{1} ⊗ I_{2} + I_{1} ⊗ A_{2} is the adjacency matrix of the sum G_{1} + G_{2} of graphs G_{1} and G_{2}. Here I_{1}, I_{2} are identity matrices with the same order as G_{1}, G_{2} respectively. If λ_{i}^{(1)}, λ_{j}^{(2)} are eigenvalues of G_{1}, G_{2}, then the eigenvalues of G_{1} + G_{2} are all possible sums λ_{i}^{(1)} + λ_{j}^{(2)}.

In a quite analogous manner, (A_{1} + D_{1}) ⊗ I_{2} + I_{1} ⊗ (A_{2} + D_{2}) = Q_{1} ⊗ I_{2} + I_{1} ⊗ Q_{2} is the signless Laplacian of the sum G_{1} + G_{2} and 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)}.

* * *

2. The girth. The following proposition is easily obtained from Theorem 2.4, as noted in [9]. Let t_{i} be the number of vertices of the tree obtained by deleting an edge i outside the cycle in a unicyclic graph.

Proposition 3.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, where the summation goes over all edges i outside the cycle.

Hence 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 (cf. [7]). However, Laplacian eigenvalues perform best: the girth of a unicyclic graph can be determined in all cases.

In fact, we can formulate the following proposition.

Proposition 3.2. Given the Laplacian spectrum of a graph, we can establish whether or not the graph is unicyclic and, if the answer is positive, determine its girth.

P r o o f. From the Laplacian spectrum of a graph we can determine the number of vertices, the number of edges and the number of connected components. Suppose we have established that the graph is unicyclic. 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 coefficients p_{n}(G) and p_{n−1}(G) for some other classes of graphs, in particular for trees, have been obtained in [16]. Extremal results concerning the coefficients p_{i}(T) for a tree T have been obtained in [19]. 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.

* * *

3. Subdivision graphs. As pointed out in [9], the following formula appears implicitly in the literature (see e.g., [3, p. 63] and [18]):

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

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. Here we present some examples in this direction.

Let η(G) be the multiplicity of the eigenvalue 0 in the spectrum of a graph G.

Proposition 3.3. For any tree T we have η(S(T)) = 1.

P r o o f. If T is a tree on n vertices formula (3) yields P_{S(T)}(x) = x^{−1}Q_{T} (x^{2}). Since T is a bipartite graph Q_{T} (x) has a simple root 0 by Proposition 2.1 and this completes the proof. □

Proposition 3.3 has been proved in [17] in another way.

The quantity η(T) is an important parameter of a tree T since it determines the size of the maximal matching. By theorem 8.1 of [3], the size of the maximal matching of a tree T on n vertices is equal to \frac{1}{2}(n − η(T)).

Corollary 3.4. The subdivision of a tree with m edges has a matching of size m.

Two graphs are said to be Q-cospectral if they have the same polynomial Q_{G}(λ). By analogy with the notions of PING and cospectral mate we introduce the notions of Q-PING and Q-cospectral mate with obvious meaning.

Two graphs are called S-cospectral (L-cospectral) if their subdivision (line) graphs are cospectral.

Proposition 3.5. If two graphs are Q-cospectral, then they are Scospectral and L-cospectral.

P r o o f. Since Q-cospectral graphs have the same number of vertices and the same number of edges, their S-cospectrality and L-cospectrality follow from formulas (3) and (2), respectively. □

However, two L-cospectral graphs need not be Q-cospectral as noted in [8].

Example. The smallest Q-PING, consisting of the graphs K_{1,3} and C_{3} ∪ K_{1} on 4 vertices, yields by Proposition 3.5 the PING consisting of the graphs S(K_{1,3}) and C_{6} ∪ K_{1}. This PING provides the smallest example when a line graph is cospectral with a graph which is not a generalized line graph (cf. [5]) (while the Q-PING provides the smallest example when a line graph is Q-cospectral with a graph which is not a line graph). □

Note that the smallest PINGs (consisting of the graphs K_{1,4} and C_{4} ∪K_{1} on 5 vertices and the well known PING of two connected graphs on 6 vertices [3, p. 157]) are not Q-PINGs.

Proposition 3.5 explains partially the fact that PINGs are more frequent than Q-PINGs. Namely, for any Q-PING Proposition 3.5 yields two PINGs whose graphs belong to restricted classes of graphs (subdivision and line graphs).

There are cospectral unicyclic graphs with different girths (which are necessarily even in this case) [7]. By Proposition 3.1 these graphs are not Q-cospectral.

* * *

4. The diameter. Let e(G) be the number of distinct Q-eigenvalues of a graph G. As pointed out in [9], the diameter of G is bounded above by e(G) − 1. This statement and its proof is analogous to an existing result related to the adjacency spectrum [3, Theorem 3.13].

Theorem 3.6. Let G be a connected graph of diameter D and e(G) distinct Q-eigenvalues. Then D ≤ e(G) − 1.

P r o o f. By Theorem 2.6 the (i, j)-entry q_{i,j}^{(k)}of Q^{k} is the number of semi-edge walks of length k from i to j. By the definition of the diameter, for some vertices i and j there is no semiedge walk of length k connecting i and j for k < D, whereas there is at least one for k = D. Hence we have q_{i,j}^{(k)} = 0 for k < D and q_{i,j}^{(k)} > 0 for k = D. The minimal polynomial of the matrix Q is of degree e(G) = e and yields a recurence relation connecting e consecutive members of the sequence q_{i,j}^{(k)}, k = 0, 1, 2, . . .. The assumption D > e−1 would cause that all members of the sequence q_{i,j}^{(k)}, k = 0, 1, 2, … are equal to 0 what is impossible. This contradiction proves the proposition.

□

* * *

5. Eigenvectors. We shall also consider the eigenvectors.

Theorem 3.7. The eigenspace of the Q-eigenvalue 0 of a graph G determines sets of vertices and bipartitions in bipartite components of G.

P r o o f. Let x^{T} = (x_{1}, x_{2}, …, x_{n}). For a non-zero vector x we have Qx = 0 if and only if R^{T} x = 0. The later holds if and only if x_{i} = −x_{j} for every edge. If the graph is connected (and then necessarily bipartite), x is determined up to a scalar multiple by the value of its coordinate corresponding to any fixed vertex i. If G is disconnected, at least one component is bipartite. If a vertex i belongs to a non-bipartite component, then x_{i} = 0. Using Corollary 2.2 we determine the number of bipartite components as the multiplicity of eigenvalue 0. For each bipartite component we have an eigenvector with non-zero coordinates exactly for vertices in this component. Now, vertex sets of bipartite components are determined by non-zero coordinates in vectors of a suitably chosen ortogonal basis of the eigencpace of 0. The sign of these coordinates determines colour classes within bipartite components. □

4. Vertex degrees and graphs with Q-index not exceeding 4

Expressions for the spectral moments from Corollary 2.8 can be used to determine vertex degrees if we know that vertex degrees can take only a limited number of values. In particular, suppose that a graph has n_{i} vertices of degree e_{i} for i = 0, 1, 2, 3 and no other vertices. If we specify e_{0}, e_{1}, e_{2}, e_{3}, the corresponding numbers of vertices n_{0}, n_{1}, n_{2}, n_{3} can be determined from the system of equations (provided the spectral moments T_{0}, T_{1}, T_{2}, T_{3} are known)

∑_{i=0}^{3} n_{i} = T_{0} = n, ∑_{i=0}^{3} n_{i}e_{i} = T_{1} = 2m,

∑_{i=0}^{3} n_{i}e_{i}^{2} = T_{2} − 2m, ∑_{i=0}^{3} n_{i}e_{i}^{3} = T_{3} − 6t − 3(T_{2} − 2m).

Interesting conclusions could be made in the case e_{0} = 0, e_{1} = 1, e_{2} = 2, e_{3} = 3.

Such a situation occurs in graphs with vertex degrees at most 3. These graphs are of interest in chemical applications of graph theory. If such a graph is bipartite, we have t = 0 and vertex degrees are determined in terms of spectral moments by the above system. If the graph is connected, we have n_{0} = 0 and we can treat non-bipartite case as well. (The first three equations suffice to determine vertex degrees and, in addition, the fourth equation yields the number of triangles t).

* * *

A similar situation occurs in graphs with the Q-index not exceeding 4. By Proposition 6.1 of [8] components of such graphs are paths (including isolated vertices), cycles and stars K_{1,3}. In fact we have a subset of the set of chemically interesting graphs but we shall try here to say a little more.

We shall assume that the whole Q-spectrum of such a graph is given. Could we hope that the graph is determined up to isomorphism ?

The smallest Q-PING, consisting of the graphs K_{1,3} and C_{3} ∪ K_{1} on 4 vertices yields a counter example.

We can then, according to the suggestion in [8], assume that together with Q-spectrum also the number of components is given. This really distinguishes between the graphs in this Q-PING: if the number of components is eqal to 1 we get K_{1,3} and if the number of components is equal to 2 we get C_{3} ∪ K_{1}.

In order to treat the general case let us introduce the following notation: k_{q} multiplicity of the Q-eigenvalue q, c the number of components, b the number of bipartite components, s the number of components isomorphic to the star K_{1,3}, e the number of even circuits, u the number of of odd circuits of length greater or equal to 5, p the number of (non-trivial) paths, v the number of isolated vertices. We have the following relations connecting these parameters with the

spectum:

k_{0} = b, k_{4} = e + t + u + s.

Next, we have some relations connecting these parameters with quantities n_{0}, n_{1}, n_{2}, n_{3}:

v = n_{0}, p = \frac{n_{1} − 3n_{3}}{2} , s = n_{3},

Note also that b = v + p + e + s and c = b + t + u.

From all these relations it is easy to derive the following equation

2n_{0} + n_{1} − 3n_{3} = 2c − 2k_{4}.

Previous equations for n_{0}, n_{1}, n_{2}, n_{3} read now

n_{0} + n_{1} + n_{2} + n_{3} = T_{0} = n, n_{1} + 2n_{2} + 3n_{3} = T_{1} = 2m,

n_{1} + 4n_{2} + 9n_{3} = T_{2} − 2m, n_{1} + 8n_{2} + 27n_{3} = T_{3} − 6t − 3(T_{2} − 2m).

Using the above equations we can determine vertex degrees and, in particular, numbers of components of each type, provided the Q-spectrum and the number of components c are known. In fact, the first four out of these five equations are independent and yield unique values for n_{0}, n_{1}, n_{2}, n_{3} and the fifth equation yields t. Then gradually all other parameters can be calculated.

Hence, we have proved the following theorem.

Theorem 3.8. Let the Q-spectrum and the number c of components of a graph be given. If the Q-index does not exceed 4, then the numbers v, p, e, s, t, u, defined above, are uniquely determined.

However, all this is not sufficient to determine the graph up to isomorphism.

Example. Graphs C_{4} ∪ 2P_{3} and C_{6} ∪ 2K_{2} are Q-cospectral. This is the smallest of the following family of Q-PINGs: C_{2k} ∪ 2P_{l} and C_{2l} ∪ 2P_{k} for k, l ≥ 2, k ≠ l, what can be verified since the Q-spectra of circuits and paths are known [8]. □

This example shows that although the numbers of components of each type are determined, the distribution of vertices between components (in these cases between paths and even circuits) is not unique.

Remark. The paper [4] studies spectra of the adjacency matrix of graphs in which the largest eigenvalue does not exceed 2. This problem is analogous to the problem covered by Theorem 3.8, i.e., the problem of graphs with the Q-index not exceeding 4. There are more graphs in the first case and cospectral graphs appear more frequently. Once more we come across facts supporting the idea that Q-eigenvalues contain more information on graphs than the eigenvalues of the adjacency matrix.

Appendix

We have computed Q-spectra of graphs on 6 vertices. The graphs are ordered and labeled in the same way as in the paper [6] and the reader is referred to this paper for drawings of the graphs. (In fact, the graphs are ordered lexicographically by spectral moments of the adjacency matrix.) The number of edges m is given. The following 5 pairs of graphs form Q-PINGs: 5 6, 14 16, 53 56, 65 71, 82 88.

Q-spectra of graphs on up to 5 vertices are given in the appendix of [8].

Q-SPECTRA OF CONNECTED GRAPHS WITH 6 VERTICES

m=15       001.  10.0000   4.0000   4.0000   4.0000   4.0000   4.0000
m=14       002.   9.4641   4.0000   4.0000   4.0000   4.0000   2.5359
m=13       003.   9.0000   4.0000   4.0000   4.0000   3.0000   2.0000
004.   8.8284   4.0000   4.0000   4.0000   3.1716   2.0000
m=12       005.   8.6056   4.0000   4.0000   3.0000   3.0000   1.3944
006.   8.6056   4.0000   4.0000   3.0000   3.0000   1.3944
007.   8.4495   4.0000   4.0000   3.5505   2.0000   2.0000
008.   8.2588   4.0000   4.0000   3.2518   3.0000   1.4894
009.   8.0000   4.0000   4.0000   4.0000   2.0000   2.0000
m=11       010.   8.2749   4.0000   3.0000   3.0000   3.0000   0.7251
011.   8.1355   4.0000   3.6532   3.0000   2.0000   1.2113
012.   7.9651   4.0000   3.7180   3.0000   2.0000   1.3169
013.   8.0000   4.0000   4.0000   2.0000   2.0000   2.0000
014.   7.7588   4.0000   3.3054   3.0000   3.0000   0.9358
015.   7.7913   4.0000   3.6180   3.2087   2.0000   1.3820
016.   7.7588   4.0000   3.3054   3.0000   3.0000   0.9358
017.   7.5616   4.0000   3.4384   3.0000   3.0000   1.0000
018.   7.5047   4.0000   4.0000   3.1354   2.0000   1.3600
m=10       019.   7.7264   3.8577   3.0000   3.0000   1.7093   0.7066

020.   7.5446   3.8329   3.0000   3.0000   2.0000   0.6224
021.   7.7588   4.0000   3.3054   2.0000   2.0000   0.9358
022.   7.5742   3.7337   3.6180   2.5076   1.3820   1.1845
023.   7.3723   4.0000   3.0000   3.0000   1.6277   1.0000
024.   7.4279   4.0000   3.3757   2.0000   2.0000   1.1965
025.   7.3919   3.7904   3.2106   3.0000   1.6815   0.9256
026.   7.1859   3.7200   3.3007   3.0000   2.0000   0.7933
027.   7.1190   4.0000   3.6180   2.5684   1.3820   1.3126
028.   7.2361   3.6180   3.6180   2.7639   1.3820   1.3820
029.   7.0839   4.0000   3.2132   3.0000   2.0000   0.7029
030.   6.8951   4.0000   3.3973   3.0000   1.7076   1.0000
031.   6.8284   4.0000   4.0000   2.0000   2.0000   1.1716
032.   6.9095   3.6093   3.0000   3.0000   3.0000   0.4812
m=9        033.   7.2724   3.7245   3.0000   2.0000   1.3437   0.6594
034.   7.0604   3.6395   3.0000   2.4522   1.2270   0.6208
035.   6.9095   3.6093   3.0000   2.0000   2.0000   0.4812
036.   7.0000   4.0000   2.0000   2.0000   2.0000   1.0000
037.   7.4641   4.0000   2.0000   2.0000   2.0000   0.5359
038.   7.0839   3.2132   3.0000   3.0000   1.0000   0.7029
039.   6.7982   3.7904   3.0000   2.5025   1.3626   0.5463
040.   7.1156   3.6701   3.0971   2.0000   1.2393   0.8780
041.   6.7321   3.4142   3.2679   2.0000   2.0000   0.5858
042.   6.8284   3.6180   3.6180   1.3820   1.3820   1.1716
043.   6.9576   3.6180   3.1215   2.0000   1.3820   0.9209
044.   6.6458   4.0000   3.0000   2.0000   1.3542   1.0000
045.   6.6648   3.3011   3.0000   3.0000   1.5713   0.4628
046.   6.6058   3.7197   3.1897   2.4767   1.3225   0.6856
047.   6.4081   3.6180   3.2934   2.5573   1.3820   0.7411
048.   6.3234   4.0000   3.3579   2.0000   1.3187   1.0000
049.   6.4940   4.0000   3.1099   2.0000   2.0000   0.3961
050.   6.3419   3.5959   3.0000   3.0000   1.6324   0.4298
051.   6.0000   4.0000   3.0000   3.0000   1.0000   1.0000
052.   6.0000   3.0000   3.0000   3.0000   3.0000   0.0000
m=8        053.   6.9095   3.6093   2.0000   2.0000   1.0000   0.4812
054.   6.6728   3.4142   2.6481   2.0000   0.6791   0.5858
055.   6.3923   3.3254   2.0000   2.0000   2.0000   0.2823
056.   6.9095   3.6093   2.0000   2.0000   1.0000   0.4812
057.   6.4940   3.1099   3.0000   2.0000   1.0000   0.3961
058.   6.7494   3.1469   3.0000   1.4577   1.0000   0.6460
059.   6.4317   3.6180   2.7995   1.3820   1.2245   0.5443
060.   6.2422   3.5496   2.6524   2.0000   1.0855   0.4703
061.   6.6262   3.5151   2.0000   2.0000   1.0000   0.8587
062.   6.0000   4.0000   2.0000   2.0000   1.0000   1.0000
063.   6.1779   3.1905   3.0000   2.4204   0.7828   0.4284
064.   6.1159   3.7195   2.7379   2.0000   1.0648   0.3619

065.   5.8781   3.5834   3.0000   2.0000   1.2296   0.3089
066.   6.2491   3.4142   2.8536   2.0000   0.8972   0.5858
067.   6.0280   3.2953   3.0000   2.0000   1.2849   0.3918
068.   5.9452   3.6180   3.0856   1.3820   1.2963   0.6728
069.   5.7093   3.4142   3.1939   2.0000   1.0968   0.5858
070.   5.5616   4.0000   3.0000   1.4384   1.0000   1.0000
071.   5.8781   3.5834   3.0000   2.0000   1.2296   0.3089
072.   5.5887   3.5463   3.0000   2.4537   1.0000   0.4113
073.   6.0000   4.0000   2.0000   2.0000   2.0000   0.0000
074.   5.5616   3.0000   3.0000   3.0000   1.4384   0.0000
m=7        075.   6.4940   3.1099   2.0000   1.0000   1.0000   0.3961
076.   6.1563   3.4142   2.0000   1.3691   0.5858   0.4746
077.   5.9452   3.0856   2.6180   1.2963   0.6728   0.3820
078.   5.8781   3.5834   2.0000   1.2296   1.0000   0.3089
079.   6.3723   3.0000   2.0000   1.0000   1.0000   0.6277
080.   5.6458   3.4142   2.0000   2.0000   0.5858   0.3542
081.   5.8154   3.0607   2.0000   2.0000   0.8638   0.2602
082.   5.4893   3.2892   2.0000   2.0000   1.0000   0.2215
083.   5.7217   3.5127   2.0000   1.3098   1.0000   0.4558
084.   5.0000   4.0000   2.0000   1.0000   1.0000   1.0000
085.   5.6597   3.1461   2.7357   1.3736   0.7772   0.3077
086.   5.3615   3.1674   2.6180   2.0000   0.4711   0.3820
087.   5.2647   3.5378   2.6491   1.2987   1.0000   0.2497
088.   5.4893   3.2892   2.0000   2.0000   1.0000   0.2215
089.   5.0664   3.2222   3.0000   1.3478   1.0000   0.3636
090.   5.5141   3.5720   2.0000   2.0000   0.9139   0.0000
091.   5.2361   3.0000   3.0000   2.0000   0.7639   0.0000
092.   5.0000   3.0000   3.0000   2.0000   1.0000   0.0000
093.   4.9032   3.4142   2.8061   2.0000   0.5858   0.2907
m=6        094.   6.2015   2.5451   1.0000   1.0000   1.0000   0.2534
095.   5.5344   3.0827   1.5929   1.0000   0.4889   0.3010
096.   5.2361   2.6180   2.6180   0.7639   0.3820   0.3820
097.   5.3839   2.7424   2.0000   1.0000   0.6721   0.2015
098.   4.9809   3.0420   2.0000   1.2938   0.4629   0.2204
099.   4.8422   3.5069   1.4931   1.0000   1.0000   0.1578
100.   4.6554   3.2108   2.0000   1.0000   1.0000   0.1338
101.   5.2361   3.0000   2.0000   1.0000   0.7639   0.0000
102.   4.8136   3.0000   2.5293   1.0000   0.6571   0.0000
103.   4.7321   3.4142   2.0000   1.2679   0.5858   0.0000
104.   4.5616   3.0000   2.0000   2.0000   0.4384   0.0000
105.   4.4383   3.1386   2.6180   1.1798   0.3820   0.2434
106.   4.0000   3.0000   3.0000   1.0000   1.0000   0.0000
m=5        107.   6.0000   1.0000   1.0000   1.0000   1.0000   0.0000
108.   5.0861   2.4280   1.0000   1.0000   0.4859   0.0000

       109.   4.5616   3.0000   1.0000   1.0000   0.4384   0.0000
       110.   4.3028   2.6180   2.0000   0.6972   0.3820   0.0000
       111.   4.2143   3.0000   1.4608   1.0000   0.3249   0.0000
       112.   3.7321   3.0000   2.0000   1.0000   0.2679   0.0000

REFERENCES

[1] D. C a r d o s o, D. C v e t k o v i ć, P. R o w l i n s o n, S. S i m i ć, A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear Algebra Appl., to appear.

[2] D. C v e t k o v i ć, Signless Laplacians and line graphs, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math. 131 (2005), No. 30, 85–92.

[3] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg – Leipzig, 1995.

[4] D. C v e t k o v i ć, I. G u t m a n, On the spectral structure of graphs having the maximal eigenvalue not greater than two, Publ. Inst. Math. (Beograd), 18(32)(1975), 39–45.

[5] D. C v e t k o v i ć, M. L e p o v i ć, Cospectral graphs with least eigenvalue at least -2, Publ. Inst. Math. (Beograd), 78(92)(2005), 51–63.

[6] D. C v e t k o v i ć, M. P e t r i ć, A table of connected graphs on six vertices, Discrete Math., 50(1984), No. 1, 37–49.

[7] D. C v e t k o v i ć, P. R o w l i n s o n, Spectra of unicyclic graphs, Graphs and Combinatorics, 3(1987), 7–23.

[8] D. C v e t k o v i ć, P. R o w l i n s o n, S. K. S i m i ć, Signless Laplacians of finite graphs, Linear Algebra Appl., 423(2007), No. 1, 155–171.

[9] D. C v e t k o v i ć, P. R o w l i n s o n, S. S i m i ć,Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd), 81(95)(2007), 11–27.

[10] E. R. van D a m , W. H a e m e r s, Which graphs are determined by their spectrum?, Linear Algebra Appl., 373 (2003), 241–272.

[11] A. D a n e s h g a r, H. H a j i a b o l h a s s a n, Graph homomorphisms and nodal domains, Linear Algebra Appl., 418(2006), 44–52.

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

[13] M. D e s a i, V. R a o, A characterization of the smallest eigenvalue of a graph, J. Graph Theory 18 (1994), 181–194.

[14] W. H a e m e r s, E. S p e n c e, Enumeration of cospectral graphs, Europ. J. Comb. 25 (2004), 199–211.

[15] R. M e r r i s, Laplacian matrices of graphs, Linear Algebra Appl. 197–198(1994), 143–176.

[16] C. S. O l i v e i r a, N. M. M. d e A b r e u, S. J u r k i e w i c z, The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes, Linear Algebra Appl., 356(2002), 113–121.

[17] I. S c i r i h a, I. G u t m a n, Minimal configuration trees, Linear and Multilinear Algebra, 54(2006), No. 2, 141–145.

[18] B. Z h o u, I. G u t m a n, A connection between ordinary and Laplacian spectra of bipartite graphs, Linear and Multilinear Algebra, 56(2008), 305–310.

[19] P. Z h u, R. C. W i l s o n, A study of graph spectra for comparing graphs, British Machine Vision Conference, 5–8 September 2005, Oxford Brookes University, BMVA, 679–688.

Mathematical Institute SANU P.O. Box 367 11000 Belgrade Serbia

Email:ecvetkod@etf.bg.ac.yu