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

SIGNLESS LAPLACIANS AND LINE GRAPHS

D. CVETKOVIĆ

(Presented at the 3rd Meeting, held on April 22, 2005)

A b s t r a c t. The spectrum of a graph is the spectrum of its adjacency matrix. Cospectral graphs are graphs having the same spectrum. In this paper we study the phenomenon of cospectrality in graphs by comparing characterizing properties of spectra of graphs and spectra of their line graphs. We present some arguments showing that the latter perform better. In this comparison we use spectra of signless Laplacians of graphs.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: graph theory, graph spectra, line graph , signless Laplacian

1. Introduction

The spectrum of a graph is the spectrum of its adjacency matrix. Cospectral (or isospectral) graphs are graphs having the same spectrum.

Cospectral graphs have been studied since very beginnings of the development of the theory of graph spectra. The subject, although present in the investigations all the time, has recently attracted special attention. It was the power of nowadays computers which enabled some investigations which were not possible in the past [8], [11].

In this paper we study the phenomenon of cospectrality in graphs by comparing characterizing properties of spectra of graphs and spectra of their line graphs. In this comparison we use spectra of signless Laplacians of graphs.

In the rest of this section we shall introduce some basic notions.

Let G be a simple graph with n vertices. The characteristic polynomial det(xI − A) of the 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 and the spectrum of G, respectively. The eigenvalues of G are usually denoted by λ_{1}, λ_{2}, …, λ_{n}; they are real because A is symmetric.

An overview of results on graph spectra is given in [1].

Graphs with the same spectrum are called isospectral or cospectral graphs. The term ”(unordered) pair of isospectral non–isomorphic graphs” will be denoted by PING. More generally, a ”set of isospectral non–isomorphic graphs” is denoted by SING. A two element SING is a PING. A graph H, cospectral but non–isomorphic to a graph G, is called a cospectral mate of G.

The matrix L = D − A is known as the Laplacian of G and is very much studied in the literature (see, e.g., [1]). The matrix A + D is called the signless Laplacian in [11] and appears very rarely in published papers (see [1]), the paper [9] being almost unique research paper related to this matrix.

As usual, K_{n}, C_{n} and P_{n} denote respectively the complete graph, the cycle and the path on n vertices. Further, K_{m,n} denotes the complete bipartite graph on m + n vertices. The union of (disjoint) graphs G and H is denoted by G ∪ H, while mG denotes the union of m disjoint copies of G.

In Section 2 we shall discuss some properties of the characteristic polynomial of the signless Laplacian. In Section 3 some evidence is given that this polynomial, together with the characteristic polynomial of the line graph, is more useful in studying graphs than the characteristic polynomial of the graph itself.

2. Signless Laplacians

Together with the spectrum of the adjacency matrix of a graph we shall consider the spectrum of another matrix associated to 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} = A + D, 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.

From relations (1) we immediately get

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

where Q_{G}(λ) is the characteristic polynomial of the signless Laplacian. The polynomial Q_{G}(λ) will be called the Q-polynomial of the graph G.

The signless Laplacian is a positive semidefinite matrix, i.e., all its eigenvalues are non-negative. Concerning the least eigenvalue we have the following proposition.

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

P r o o f. According to Theorem 2.2.4 of [7] the multiplicity of the eigenvalue −2 in L(G) is equal to m − n + 1 if G is bipartite and equal to m − n if G is not bipartite. This together with formula (2) yields the assertion of the proposition. □

Corollary. In any graph the multiplicity of eigenvalue 0 of the signless Laplacian is equal to the number of bipartite components.

The least eigenvalue of the signless Laplacan is studied in [9] as a measure of non-bipartiteness of a graph and Proposition 1 has been obtained as a corollary of a more general theorem.

Remark. In general, the Q-polynomial still does not contain information on the bipartiteness. It does if the graph is connected but we also cannot recognize a connected graph by its Q-polynomial. The smallest illustrative example is provided by graphs K_{1,3} and K_{3} ∪ K_{1}. These graphs have isomorphic line graphs (isomorphic to K_{3}) with the characteristic polynomial (λ − 2)(λ + 1)^{2} and by (2) the same Q-polynomial λ(λ − 4)(λ − 1)^{2}. Looking at this polynomial we can only say that the graph has exactly one bipartite component but neither that the graph is connected nor bipartite since the graph can contain one or more non-bipartite components as it really happens in K_{3} ∪ K_{1}. It is interesting to notice that the Q-polynomial together with the information on one of the properties in question (connectedness and bipartiteness) enables recovering the information on the other property: if we know the number of components we can decide whether the graph is bipartite and if we know whether the graph is bipartite we can find if it is connected. Note also that in bipartite graphs the Q-polynomial is equal to the characteristic polynomial of the Laplacian and for Laplacian eigenvalues it is known that the multiplicity of the eigenvalue 0 is equal to the number of components.

Proposition 2. . The number of edges of a graph G on n vertices is equal to −q_{1}/2 where q_{1} is the coefficient of λ^{n−1} in the Q-polynomial of G.

P r o o f. The trace of the signless Laplacian is equal to the sum of vertex degrees of G. □

Two graphs are said to be Q-cospectral if they have the same polynomial Q_{G}(λ) while they are called L-cospectral if their line graphs are cospectral.

Proposition 3. . If two graphs are Q-cospectral, then they are L-cospectral.

P r o o f. Q-cospectral graphs have the same number of vertices and the same number of edges. Then their L-cospectrality follows from formula (2). □

However, two L-cospectral graphs need not to be Q-cospectral. This is because two cospectral line graphs need not to have the same number of vertices in their root graph. Such an example is the PING given in Fig. 1. Hence we cannot conclude that the graphs are Q-cospectral.

[figure]

Fig. 1

Cospectral line graphs of Fig. 1 have the characteristic polynomial λ(λ^{2}− λ − 4)(λ − 1)(λ + 1)^{2}. The root graph of the first graph has 7 vertices with the Q-polynomial λ(λ−1)(λ−2)(λ−3)(λ^{2} −5λ+2) while in the second case we have 8 vertices and the Q-polynomial λ^{2}(λ−1)(λ−2)(λ−3)(λ^{2} −5λ+2).

The PING of Fig. 1 also shows that we cannot in general decide whether a graph is bipartite from the spectrum of its line graph while the Q-polynomial contains more information about that.

The PING in Fig. 1 is the PING No. 6.3 of the table of [2], [3].

Its least eigenvalue, approximately equal to −1.5616, is the least solution of the equation λ^{2} − λ − 4 = 0. It was proved in [5] that the only PING with largest least eigenvalue and a minimal number of vertices is the PING of Fig. 1.

3. The spectral uncertainty of graph sets and comparison of usefulness of spectra of various graph matrices

Let G be a finite set of graphs. Let G′ be the set of graphs in G which have a cospectral mate in G. The ratio r_{G} = |G′|/|G| is called the spectral uncertainty of G (w.r.t. the adjacency matrix).

The papers [8], [11] provide spectral uncertainties r_{n} of sets of all graphs on n vertices for n ≤ 11 (for n = 10 see [12] and [10] for n ≤ 9):

\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 \end{matrix}

The new value is r_{11}. It is smaller than r_{10} which perhaps indicates that r_{n} tends to 0 when n tends to the infinity. This is the first encouraging result in direction of possibility of using spectra in recognizing graphs since very beginnings of the study of the phenomenon of cospectrality.

It is well-known that if G and H are connected graphs then L(G) = L(H) implies G = H unless {G, H} = {K_{3}, K_{1,3}}. This result opens the possibility of studying graphs in terms of their line graphs, at least in principle. One could think whether it would be more efficient to consider the spectrum of L(G) instead of describing a graph G by its own spectrum.

Before discussing this idea we should like to remind the reader on some basic facts on the set of graphs with least eigenvalue greater than or equal to −2.

It is an elementary observation that line graphs have the least eigenvalue greater than or equal to −2. A natural problem arose to characterize the set L of graphs with such a remarkable property. It appeared that line graphs (LG) share this property with generalized line graphs (GLG) and with some exceptional graphs.

An exceptional graph is a connected graph with least eigenvalue greater than or equal to −2 which is not a generalized line graph. An exceptional graph has at most 36 vertices and each vertex has degree at most 28.

The situation is complicated by the existence of exceptional graphs which could be cospectral to line graphs and to generalized line graphs. Indeed, the uncertainty indices for L-graphs with a given number of vertices get high values as the following table (we are obliged to M. Lepović for computing these data) shows.

\begin{matrix}n & 6 & 7 & 8 & 9 & 10 \\ L & 0.093 & 0.153 & 0.214 & 0.232 & 0.280 \\ GLG & 0.091 & 0.152 & 0.184 & 0.150 & 0.143 \\ LG & 0.032 & 0.084 & 0.115 & 0.1037 & 0.1044 \end{matrix}

However, values for generalized line graphs and for line graphs, although not significant in this form, were an indication that it is worthwhile to extend this statistics to higher values of n.

It is reasonable to compare uncertainty indices for some (finite) sets E of graphs with given number of edges (and vertices) and for the corresponding sets of line graphs. Equivalently, we could consider spectral uncertainties of E w.r.t. adjacency matrix of the line graph. Since we know that graphs in E are L-cospectral if and only if they are Q-cospectral, the mentioned uncertainties are roughly equal to uncertainities q_{n} of E w.r.t. the signless Laplacian matrix A + D. The last uncertainities are given in [11] and we reproduce them here for n ≤ 11.

\begin{matrix}n & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 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 much smaller than the numbers r_{n}. In addition, the sequence q_{n} is decreasing for n ≤ 10 while the sequence r_{n} is increasing for n ≤ 9. This is a strong basis to believe that studying graphs by the spectra of their line graphs is more efficient than studying them by their own spectra.

Let us still note that values of q_{n} differ to some extent from the corresponding uncertainty indices for line graphs of the type considered in the above table. First, this is because cospectral line graphs distinguishable by Q-polynomials of their root graphs are not taken into account when calculating q_{n}. In other direction, some graphs with the same Q polynomial can have isomorphic line graphs hence being not relevant for the other index. But we can assume that these differences are not essential.

Having in mind the above facts one can think that the use of the polynomial Q_{G}(λ) would be even more useful than studying P_{L(G)}(λ). On the other hand, very few relations between Q_{G}(λ) and the structure of G are known. Since we have just the opposite situation with eigenvalues of the adjacency matrix, we would like still to use P_{L(G)}(λ) in spite of the fact that L(G) usually has more vertices than G.

However, we have seen in Section 2 that P_{L(G)}(λ) contains less information on the structure of G than Q_{G}(λ). This disadvantage can be eliminated if, in addition to P_{L(G)}(λ), we know the number of vertices of G. Then we know about G just the same as if we knew Q_{G}(λ) since Q_{G}(λ) can be calculated by formula (2) and any of the two polynomials can be considered.

In this way we can eliminate another uncertainty. Namely, by Theorem 4.3.1. of [7] a regular line graph could be cospectral to another line graph with the root having a different number of vertices and this fact would cause additional problems if (only) the polynomial P_{L(G)}(λ) would be given.

Example. The graph L(K_{6}) has the Q-polynomial (λ−16)(λ−10)^{5}(λ− 6)^{9} while the graph K_{10,6} has the Q-polynomial (λ − 16)(λ − 10)^{5}(λ − 6)^{9}λ. The line graph of either of these two graphs has the characteristic polynomial (λ − 14)(λ − 8)^{5}(λ − 4)^{9}(λ + 2)^{45}.

Now, for a graph G we should have either Q_{G}(λ) or P_{L(G)}(λ) plus the number n = n(G) of vertices (of G); these two are equivalent and either can be used as appropriate.

However, having in mind the remark in Section 2, for a graph G it seems reasonable to require its Q-polynomial and, in addition, the number of components of G to be known. (Normally, in majority of cases we would consider connected graphs). Then we can decide (by Proposition 1) whether G is bipartite and go on to calculate P_{L(G)}(λ).

Note that in regular graphs it is not necessary to give explicitly the number of components since it can be calculated from Q_{G}(λ). In addition, regular graphs can be recognized and their degree and the number of components calculated from Q_{G}(λ) (cf. [8] or [1], Theorems 3.22 and 3.23).

Of course, in regular graphs we can calculate the characteristic polynomial of the adjacency matrix and of the Laplacian and use them to study the graph.

The arguments given in this paper support the idea expressed in [8] that, among matrices associated to a graph (generalized adjacency matrices), the signless Laplacian seems to be most convenient to be used in studying graph properties.

REFERENCES

[1] 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.

[2] D. C v e t k o v i ć, M. L e p o v i ć,A table of cospectral graphs with least eigenvalue at least −2, http://www.mi.sanu.ac.yu/projects/results1389.htm

[3] D. C v e t k o v i ć, M. L e p o v i ć, Sets of cospectral graphs with least eigenvalue −2 and some related results, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 129(2004), No. 29, 85–102.

[4] D. C v e t k o v i ć, M. L e p o v i ć, Cospectral graphs with least eigenvalue at least −2, to appear.

[5] D. C v e t k o v i ć, M. L e p o v i ć, Towards an algebra of SINGs, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat., to appear.

[6] 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 ć, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

[7] 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 ć, Spectral Generalizations of Line Graphs, On Graphs with Least Eigenvalue −2, Cambridge University Press, Cambridge, 2004.

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

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

[10] C. D. G o d s i l, B. M c K a y, Some computational results on the spectra of graphs, Combinatorial Mathematics IV, ed. L.R.A.Casse, W.D.Wallis, Springer– Verlag, Berlin–Heidelberg–New York, 1976, 73–92.

[11] 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.

[12] M. L e p o v i ć, Some statistical data on graphs with 10 vertices, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat., 9(1998), 79–88.

Faculty of Electrical Engineering, University of Belgrade, P.O.Box 35–54, 11120 Belgrade, Serbia and Montenegro E-mail: ecvetkod@etf.bg.ac.yu