Bulletin T.CXXVII de l’Académie Serbe des Sciences et des Arts - 2003 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 28

SOME PROPERTIES OF LAPLACIAN EIGENVECTORS

I. GUTMAN

(Presented at the 6th Meeting, held on September 27, 2002)

A b s t r a c t. Let G be a graph on n vertices, Ḡ its complement and K_{n} the complete graph on n vertices. We show that if G is connected, then any Laplacian eigenvector of G is also a Laplacian eigenvector of Ḡ and of K_{n}. This result holds, with a slight modification, also for disconnected graphs. We establish also some other results, all showing that the structural information contained in the Laplacian eigenvectors is rather limited. An analogy between the theories of Laplacian and ordinary graph spectra is pointed out.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: Laplacian spectrum, Laplacian matrix, Laplacian eigenvector (of graph), Laplacian eigenvalue (of graph)

1. Introduction

In this work we are concerned with simple graphs, i. e., graphs without multiple or directed edges, and without loops. Let G be such a graph and let n be the number of its vertices. Denote the vertices of G by v_{1}, v_{2}, …, v_{n}.

The adjacency matrix A(G) of G is a square matrix of order n whose (i, j)-entry is unity if the vertices v_{i} and v_{j} are adjacent, and is zero otherwise.

The eigenvalues and eigenvectors of the adjacency matrix are called the (ordinary) graph eigenvalues and eigenvectors. Their theory, usually referred to as “graph spectral theory”, is nowadays well developed [1, 2].

The degree d_{i} of the vertex v_{i} is the number of first neighbors of this vertex. By D(G) we denote the square matrix of order n whose i-th diagonal element is equal to d_{i} and whose off–diagonal elements are zero.

The Laplacian matrix of the graph G is

L(G) = D(G) − A(G) .  (1)

Its eigenvalues and eigenvectors are the Laplacian eigenvalues and Laplacian eigenvectors of the respective graph. Their theory is also well elaborated and is outlined in a number of reviews [3, 4, 6, 7, 9].

The Laplacian eigenvalues of the graph G will be denoted by μ_{i} = μ_{i}(G) and the corresponding eigenvectors by X_{i} = X_{i}(G) , i = 1, 2, …, n, assuming that the equality

L(G) X_{i} = μ_{i} X_{i}

is obeyed for i = 1, 2, …, n. Thus, X_{i} , i = 1, 2, …, n, are n-dimensional column–vectors.

As usual, we label the Laplacian eigenvalues so that

μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n} .

The following are well known results of the theory of Laplacian spectra [3, 4, 6, 7, 9]:

The Laplacian eigenvalues are non-negative real numbers, and μ_{n} is always zero. The eigenvalue μ_{n−1}(G) , called the “algebraic connectivity” (of the graph G), is positive–valued if and only if G is connected

∗ ∗ ∗

Let X be an arbitrary n-dimensional vector. The sum of its elements will be denoted by σ(X) .

The n-dimensional column–vectors, whose all elements are equal to 1 and 0, are denoted by \underline{\underline{1}} and \underline{\underline{0}} , respectively. Clearly, σ(X) = X • \underline{\underline{1}} , where • indicates scalar product.

The unit matrix of order n is denoted by I. The square matrix of order n, whose all elements are equal to 1, is denoted by J .

2. Some Auxiliary Results

Lemma 1. If G is any n-vertex graph, then \underline{\underline{1}} is its Laplacian eigenvector, with eigenvalue zero.

P r o o f. From definition (1) there follows that the sum of any row of L(G) is zero. Therefore, L(G) \underline{\underline{1}} = \underline{\underline{0}} , i.e.,

L(G) \underline{\underline{1}} = 0 · \underline{\underline{1}} . _{□}

Without loss of generality we may set X_{n}(G) = \underline{\underline{1}} .

The eigenvectors, corresponding to different eigenvalues, are necessarily orthogonal. This, in particular means that whenever μ_{i} ≠ 0 , then X_{i} is orthogonal to \underline{\underline{1}} . This, in turn, implies X_{i} • \underline{\underline{1}} = 0 , i.e., σ(X_{i}) = 0 .

Lemma 2a. If G is a connected n-vertex graph, then σ(X_{i}(G)) = 0 holds for all i = 1, 2, …, n − 1 . _{□}

If μ_{i} = 0 for some i < n (which happens only in the case of disconnected graphs), then the Laplacian eigenvectors X_{i} and X_{n} need not be orthogonal. However, it is always possible to choose them orthogonal, i.e., so that condition (2) be fulfilled:

If μ_{i} = 0 and i < n , then X_{i} • \underline{\underline{1}} = 0 .  (2)

If condition (2) is obeyed, then σ(X_{i}) = 0 for all i = 1, 2, …, n − 1 .

Lemma 2b. If G is a disconnected n-vertex graph, then σ(X_{i}(G)) = 0 holds for every Laplacian eigenvector of G with non-zero eigenvalue. If, in addition, condition (2) is satisfied, then σ(X_{i}(G)) = 0 holds for all i = 1, 2, …, n − 1 . _{□}

We are now prepared to prove our main results, namely Theorems 3 and 4. Although these results are deduced by simple and elementary reasoning, and although they express fundamental and generally valid properties of Laplacian eigenvectors, they seem not to be (explicitly) stated in the mathematical literature. At least, these results are not mentioned in the reviews [3, 4, 6, 7, 9] and in a paper [8] solely devoted to Laplacian eigenvectors. Theorem 3 appears in a recent paper by the present author [5].

3. The Main Result

Theorem 3a. Let G be a graph and Ḡ its complement. If G is connected, then every Laplacian eigenvector of G is a Laplacian eigenvector of Ḡ.

P r o o f. We first have to observe that

L(Ḡ) = n I − J − L(G)

and that for any column–vector X,

J X = σ(X) \underline{\underline{1}} .

Now, that the eigenvector X_{n}(G) coincides with X_{n}(Ḡ) follows from Lemma 1. Therefore, consider an eigenvector X_{i}(G) for some i = 1, 2, …, n− 1 , and bear in mind Lemma 2a:

L(Ḡ) X_{i}(G) = [n I − J − L(G)] X_{i}(G)
= n X_{i}(G) − σ(X_{i}(G)) \underline{\underline{1}} − μ_{i}(G) X_{i}(G)
= [n − μ_{i}(G)] X_{i}(G) .

Thus, for i = 1, 2, …, n−1 , the Laplacian eigenvector X_{i}(G) of the graph G coincides with the Laplacian eigenvector X_{n−i}(Ḡ) of the complement of G. _{□}

The fact that the Laplacian eigenvalues of Ḡ are equal to n−μ_{n−i}(G) , i = 1, 2, …, n − 1 , and 0 is a well known result [3, 4, 6, 7, 9].

In a fully analogous manner we obtain:

Theorem 3b. Let G be a graph and Ḡ its complement. If G is disconnected, then every Laplacian eigenvector of G with non-zero eigenvalue is a Laplacian eigenvector of Ḡ. If, in addition, condition (2) is satisfied, then every Laplacian eigenvector of G is a Laplacian eigenvector of Ḡ.

With regard to Theorems 3a and 3b recall that either G or Ḡ (or both) are connected graphs.

Theorem 4a. Let G be an n-vertex graph and K_{n} the complete graph on n vertices. If G is connected, then every Laplacian eigenvector of G is a Laplacian eigenvector of K_{n}.

P r o o f. From Lemma 1 we know that X_{n}(G) coincides with X_{n}(K_{n}) . Bearing in mind Lemma 2a and L(K_{n}) = n I − J , we obtain for i = 1, 2, ..., n − 1 :

L(K_{n}) X_{i}(G) = n X_{i} − σ(X_{I}(G)) \underline{\underline{1}} = n X_{i} . _{□}

The analogous statement for disconnected graphs reads:

Theorem 4b. Let G be an n-vertex graph and K_{n} the complete graph on n vertices. If G is disconnected, then every Laplacian eigenvector of G with non-zero eigenvalue is a Laplacian eigenvector of K_{n}. If, in addition, condition (2) is satisfied, then every Laplacian eigenvector of G is a Laplacian eigenvector of K_{n}.

Denote by O_{n} the n-vertex graph without edges. All its Laplacian eigenvalues are equal to zero.

Corollary 5 (of Theorems 3b and 4b). If condition (2) is satisfied, then every Laplacian eigenvector of G is a Laplacian eigenvector of O_{n}.

4. Discussion

The theory of graph spectra (both ordinary and Laplacian) is concerned with discovering relations between eigenvalues and eigenvectors and the structure of the underlying graphs [1, 2]. It is known that in the general case the spectrum (either ordinary or Laplacian) does not fully determine a graph, but that numerous structural features of a graph can be deduced from its spectrum. Theorems 3 and 4 imply that the structural information contained in the Laplacian eigenvectors is much smaller. This is made clear in the below Corollaries 6 and 7.

In order to avoid unnecessary complications, in the following we shall assume that all Laplacian eigenvectors of the graph G are mutually orthogonal, i.e., that σ_{i}(G) = 0 for all i = 1, 2, …, n − 1 . Then we have

Corollary 6. For G being an arbitrary graph on n vertices, it is possible to find mutually orthogonal vectors X_{1}, X_{2}, …, X_{n}, such that each of these vectors is a Laplacian eigenvector of both G, Ḡ, K_{n}, and O_{n}.

Let G and H be two n-vertex graphs (with disjoint vertex sets) that are Laplacian–cospectral; G and H may be disconnected, and they may be isomorphic. Let G ∪ H be the (2n)-vertex graph whose components are G and H. As usual, K_{n,n} denotes the complete bipartite graph on n + n vertices.

Corollary 7. It is possible to find mutually orthogonal vectors X_{1}, X_{2}, …, X_{2n}, such that each of these vectors is a Laplacian eigenvector of both G ∪ H , Ḡ ∪ H̄ , \overline{G ∪ H} , \overline{Ḡ ∪ H̄} , K_{2n}, K_{n} ∪ K_{n}, K_{n,n}, and O_{2n}.

In the theory of ordinary graph spectra [1, 2] there are results analogous to Theorems 3 and 4, but valid only for regular graphs. Namely, \underline{\underline{1}} is an eigenvector of the adjacency matrix A(G) if and only if the graph G is regular. Then, using the facts that A(Ḡ) = J −I −A(G) and A(K_{n}) = J −I we arrive at:

Theorem 8. If the graph G is connected and regular, then every eigenvector (of the adjacency matrix) of G is an eigenvector (of the adjacency matrix) of Ḡ.

Theorem 9. If G is a connected regular graph on n vertices, then every eigenvector (of the adjacency matrix) of G is an eigenvector (of the adjacency matrix) of K_{n}.

If the graph G in Theorems 8 and 9 is not connected, then these Theorems need to be re-stated in line with Theorems 3b and 4b.

Comparison of Theorems 3 and 4 with Theorems 8 and 9 hints towards the possibility to view at the theory of Laplacian spectra as a kind of extension (to all graphs) of the ordinary spectral theory of regular graphs. In other words, it looks as if the Laplacian spectrum of any graph possesses properties which, within the theory of ordinary graph spectra, are restricted to regular graphs.

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 — theory and application, Barth, Heidelberg, 1995.

[2] D. C v e t k o v i ć, P. R o w l i n s o n, S. S i m i ć, Eigenspaces of graphs, Cambridge Univ. Press, Cambridge, 1997.

[3] R. G r o n e, R. M e r r i s, The Laplacian spectrum of a graph II , SIAM J. Discr. Math. 7 (1994), 221–229.

[4] R. G r o n e, R. M e r r i s, V. S. S u n d e r, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218–238.

[5] I. G u t m a n The star is the tree with greatest greatest Laplacian eigenvalue, Kragujevac J. Math. 24 (2002), in press.

[6] R. M e r r i s, Laplacian matrices of graphs: A survey, Lin. Algebra Appl. 197–198 (1994), 143–176.

[7] R. M e r r i s, A survey of graph Laplacians, Lin. Multilin. Algebra 39 (1995), 19–31.

[8] R. M e r r i s, Laplacian graph eigenvectors, Lin. Algebra Appl. 278 (1988), 221–236.

[9] B. M o h a r, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Ollermann, A. J. Schwenk (Eds.), Graph theory, combinatorics, and applications, Wiley, New York, 1991, pp. 871–898.

Faculty of Science University of Kragujevac P. O. Box 60 YU–34000 Kragujevac Serbia and Montenegro