PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 78(92) (2005), 51–63

COSPECTRAL GRAPHS WITH LEAST EIGENVALUE AT LEAST −2

Dragoš Cvetković and Mirko Lepović

Communicated by Slobodan Simić

Abstract. We study the phenomenon of cospectrality in generalized line graphs and in exceptional graphs. We survey old results from today’s point of view and obtain some new results partly by the use of computer. Among other things, we show that a connected generalized line graph L(H) has an exceptional cospectral mate only if its root graph H, assuming it is itself connected, has at most 9 vertices. The paper contains a description of a table of sets of cospectral graphs with least eigenvalue at least −2 and at most 8 vertices together with some comments and theoretical explanations of the phenomena suggested by the table.

1. Introduction

The spectrum of a graph is the spectrum of its adjacency matrix. Cospectral graphs are graphs having the same spectrum. Both subjects contained in the title, cospectral graphs and graphs with least eigenvalue −2, have been studied since very beginnings of the development of the theory of graph spectra.

Graphs with least eigenvalue −2 can be represented by sets of vectors at angles of 60 or 90 degrees via the corresponding Gram matrices. Maximal sets of lines through the origin with such mutual angles are closely related to the root systems known from the theory of Lie algebras. Using such a geometrical characterization one can show [2] that graphs in question are either generalized line graphs (representable in the root system D_{n} for some n) or exceptional graphs (representable in the exceptional root system E_{8}).

Both subjects of the title, cospectral graphs and the graphs with least eigenvalue −2, although present in the investigations all the time, have recently attracted special attention. In the first case it was the power of nowdays computers which enabled some investigations which were not possible in the past [10], [13], while in the second case the reason was the constructive enumeration of maximal exceptional graphs [7].

2000 Mathematics Subject Classification: Primary 05C50.

In this paper we consider the intersection of these two subjects and study the phenomenon of cospectrality in generalized line graphs and in exceptional graphs. We survey some old results from today’s point of view and obtain some new results partly by the use of computer. Among other things, we show that a connected generalized line graph L(H) has an exceptional cospectral mate only if its root graph H, assuming it is itself connected, has at most 9 vertices. The paper is to a great extent based on a table of sets of cospectral graphs with least eigenvalue at least −2 and at most 8 vertices. It is produced to support the study of cospectrality in graphs in question and is presented in [6] in an abbreviated form, while [5] contains the whole material. The paper [6] as well as the present paper contain some comments and theoretical explanations of the phenomena suggested by the table.

The rest of the paper is organized as follows. Section 2 contains some definitions. Section 3 describes a table of sets of cospectral graphs with least eigenvalue at least −2 and at most 8 vertices. Several comments on the table are given. Some spectral properties of graphs with least eigenvalue greater than −2 are established in Section 4. Section 5 contains several theorems on cospectral graphs with least eigenvalue greater than or equal to −2.

2. Some basic notions

Let G be a simple graph with n vertices. We write V (G) for the vertex set of G, and E(G) for the edge set of G. 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 cocktail-party graph CP (n) is the unique regular graph with 2n vertices of degree 2n − 2; it is obtained from K_{2n} by deleting n mutually non-adjacent edges. 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 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 reals λ_{1}, λ_{2}, …, λ_{n} and we shall assume that λ_{1} ⩾ λ_{2} ⩾ ⋯ ⩾ λ_{n}.

Graphs with the same spectrum are called isospectral or cospectral graphs. The term “unordered) pair of isospectral nonisomorphic graphs” will be denoted by PING. More generally, a “set of isospectral nonisomorphic 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 SINGs whose members belong to a set X of graphs are called X–SINGs.

If the set of graphs {G_{1}, G_{2}, …, G_{k}} is a SING and if G is any connected graph, then the set {G_{1} ∪ G, G_{2} ∪ G, …, G_{k} ∪ G} is also a SING. Each graph in the later SING has a component isomorphic to a fixed graph (to the graph G). A SING S is called reducible if each graph in S contains a component isomorphic to a fixed graph. Otherwise, S is called irreducible.

COSPECTRAL GRAPHS WITH LEAST EIGENVALUE AT LEAST −2 53

Let L (L^{+}, L^{0}) be the set of graphs whose least eigenvalue is greater than or equal to −2 (greater than −2, equal to −2). A graph is called an L-graph (L^{+}- graph, L^{0}-graph) if its least eigenvalue is greater than or equal to −2 (greater then −2, equal to −2). A special new terminology for L-graphs has been introduced in [6].

A pendant double edge is called a petal. A blossom B_{n} consists of n (n ⩾ 0) petals attached at a single vertex. An empty blossom B_{0} has no petals and is reduced to the trivial graph K_{1}. A graph in which to each vertex a blossom (possibly empty) is attached is called a graph with blossoms or a B-graph. The set of B-graphs includes as a subset the set of (undirected) graphs without loops or multiple edges. A graph G is a generalized line graph if G = L(H) is the line graph of a B-graph H called the root graph of G.

The line graph L(H) of any graph H is defined as follows. The vertices of L(H) are the edges of H and two vertices of L(H) are adjacent whenever the corresponding edges of H have exactly one vertex of H in common.

We have L(B_{n}) = CP (n). A GLG is called a line graph if there exists a Bgraph H with no petals such that G = L(H) while in the opposite case G is a proper generalized line graph.

An exceptional graph is a connected graph with least eigenvalue greater than or equal to −2 which is not a generalized line graph. A generalized exceptional graph is a graph with least eigenvalue greater than or equal to −2 in which at least one component is an exceptional graph.

A petal behaves as an odd cycle (see [8]). Therefore the term supercycle has been introduced to denote an odd cycle or a petal (2-cycle). A B-graph is called bipartite if it does not contain a supercycle.

The following theorem appears in [6] as a reformulation of some old results in the new terminology.

Theorem 1. Let H be a B-graph with n vertices and m edges. Then the multiplicity of the eigenvalue −2 in L(H) is m−n if H is not bipartite and m−n+1 if H is bipartite.

For other definitions and basic results the reader is referred to books: [3] for graph spectra in general and [9] for L-graphs.

3. A table of cospectral L-graphs

The table of cospectral graphs from [5], [6] contains irreducible L–SINGs in which the number of vertices n is at most 8. There are exactly 201 irreducible L-SINGs with at most 8 vertices. This number includes 178 pairs, 20 triplets and 3 quadruples of cospectral graphs.

For each SING, the table contains an identification number, followed by eigenvalues and a graph invariant called the star value (for the definition see Section 4). Next, a row is related to each member of the SING. The row first contains the rows of the lower triangle of an adjacency matrix of the graph. In addition, the number of components is given followed by the numbers c_{i}, i = 1, 2, 3 where c_{i} is the number of components with i vertices for i = 1, 2, 3. Further we find a graph classification mark: LG for line graphs, GL for proper generalized line graphs and EX for generalized exceptional graphs. For line graphs we come across a B if the root graph is bipartite and NB in the opposite case. In proper generalized line graphs the number of petals is given.

The smallest PING without the limitations on the least eigenvalue, which consists of graphs K_{1,4} and C_{4} ∪ K_{1}, is also the first graph in our table. Note that K_{1,4} is a proper GLG while C_{4} ∪ K_{1} is a line graph.

Here we reproduce only the part of the table related to graphs on 6 vertices.

              ********************************************************
                         Cospectral graphs with 6 vertices
              ********************************************************
              4 edges
                1.  1.7321  1.0000  0.0000  0.0000 -1.0000 -1.7321  12
                    0 01 101 0100 00000  2  1 0 0  LG B
                    0 01 100 0001 00010  2  0 1 0  GL 1
              5 edges
                2.  2.0000  1.0000  0.0000  0.0000 -1.0000 -2.0000  48
                    0 01 001 0101 10000  2  0 1 0  LG B
                    1 10 010 1000 01000  1  0 0 0  GL 2
              6 edges
                3.  2.5616  1.0000  0.0000 -1.0000 -1.0000 -1.5616  12
                    0 01 011 0011 10000  2  0 1 0  LG NB
                    0 01 011 0001 00011  2  1 0 0  LG B
              7 edges
                4.  2.7093  1.0000  0.1939 -1.0000 -1.0000 -1.9032  3
                    1 10 100 1100 10100  1  0 0 0  EX
                    1 10 010 0010 11100  1  0 0 0  EX

The SING on x vertices with the identification number y will be denoted by x.y. First few SINGs on 7 and 8 vertices are given in Fig. 1.

Although reducible SINGs should not be included in tables like our since they can easily be generated from irreducible ones, reducible SINGs are not quite uninteresting [6].

In this context interesting is also the (irreducible) SING No. 8.2. It is a quadruple consisting of two (cospectral) reducible PINGs (first and third graph can be reduced to PING No. 6.2 while the other two reduce to the PING No. 7.2).

The smallest PING with graphs beyond L consists of graphs with 7 vertices and 6 edges. One of them is {K_{1,6}, K_{2,3} ∪ K_{1}} with least eigenvalue −2.4455. The smallest such PING in which both graphs are connected consists of some bicyclic graphs on 7 vertices with least eigenvalue −2.0748. These examples, of course, do not belong to our table.

[figure: 7 vertices; 7.1; 7.2; 7.3]

[figure: 8 vertices; 8.1; 8.2; 8.3]

Figure 1

Using the abbreviations LG, GL, EX of the above table to indicate the type of (graphs in) a PING, we give in the next table the (identification numbers of the) smallest SINGs which contain a PING of the given type and the smallest SINGs in which the both graphs in the PING are connected. The later SINGs are given in Fig. 2.

       PING type            smallest          smallest connected
        LG - LG                6.3                   7.17
        LG - GL                5.1                   7.16
        LG - EX                7.2                   8.22
        GL - GL                7.1                   7.6
        GL - EX                8.2                   8.49
        EX - EX                6.4                   6.4

In Fig. 2 together with (generalized) line graphs the corresponding root graphs are given. In exceptional graphs a minimal exceptional induced subgraph is indicated by thick lines.

Note that graphs forming PING No. 7.2 are switching equivalent.

Next we note that PING No. 8.10 consists of a connected line graph and a generalized exceptional graph (having an isolated vertex) while in the PING No. 8.22 both graphs are connected one being a line graph and the other an exceptional graph. In the later case the least eigenvalue is equal to −2, since, by Theorem 7, this is not possible in L^{+}-graphs.

Observations concerning the number of petals in the root graph of GLGs are described in [6].

4. Graphs with least eigenvalue greater than −2

A new approach to the construction and study of L-graphs has been initiated in [8]. This approach uses the star complement technique [14], [12], [15], [9]. L^{0}- graphs are constructed by the star complement technique starting from L^{+}-graphs. Therefore L^{+}-graphs are very important. In this section we establish some spectral properties of these graphs.

All L^{+}-graphs are known and very well described as the following result of M. Doob and D. Cvetković [11] shows.

Theorem 2. If G is a connected graph with least eigenvalue greater than −2 then one of the following holds:

(i) G = L(T; 1, 0, …, 0) where T is a tree; (ii) G = L(H) where H is a tree or an odd unicyclic graph; (iii) G is one of 20 exceptional graphs on 6 vertices represented in the root

system E_{6}; (iv) G is one of 110 exceptional graphs on 7 vertices represented in the root

system E_{7}; (v) G is one of 443 exceptional graphs on 8 vertices represented in the root

system E_{8}.

The 573 exceptional graphs appearing in this theorem are given in Table A2 of [9].

As usual, we define L^{1}(H) = L(H) and L^{k}(H) = L(L^{k−1}(H)) for k = 2, 3, . . .. We can easily find which L^{+}-graphs are iterated line graphs L^{k}(H), k = 2, 3, . . ..

Proposition 1. Let H be a connected graph and let L^{2}(H) be an L^{+}-graph. Then H is a path or H is an odd cycle or H consists of three nontrivial paths meeting at a vertex.

Proof. Let H_{1} = L(H) which implies G = L(H_{1}). Then H_{1} is a tree or an odd unicyclic graph.

In the first case H has no vertices of degree greater then 2 and does not contain cycles. Hence, H = P_{n}.

In the second case, if the odd cycle has length more than 3 then H is reduced to this cycle, hence H = C_{2k+1} (k ⩾ 2). If H_{1} contains a triangle then either H = K_{3} or H consists of three nontrivial paths meeting at a vertex. □

The following proposition is now straightforward.

Proposition 2. Let k ⩾ 3 and let L^{k}(H) ∈ L^{+} be a connected graph. Then H is a path or an odd cycle.

An eigenvalue of an L-graph is called principal if it is greater than −2. If λ_{1}, λ_{2}, …, λ_{k} are principal eigenvalues of an L-graph G, then the principal polynomial Π_{G}(λ) is the monic polynomial of degree k whose zeros are λ_{1} + 2, λ_{2} + 2, …, λ_{k} + 2. Obviously, we have

P_{G}(λ − 2) = λ^{n−k}Π_{G}(λ),

where n is the number of vertices in G.

If G is a graph with least eigenvalue greater than −2, then n = k and Π_{G}(0) = P_{G}(−2).

Theorem 3. Let G be a connected L^{+}-graph on n vertices. We have Π_{G}(0) = (−1)^{n}d, where

1^{∘} d = 1 if G is exceptional on 8 vertices

(i.e., can be represented in the root system E_{8} but not in D_{n} for any n), 2^{∘} d = 2 if G is exceptional on 7 vertices

(i.e., can be represented in the root system E_{7} but not in D_{n} for any n), 3^{∘} d = 3 if G is exceptional on 6 vertices

(i.e., can be represented in the root system E_{6} but not in D_{n} for any n), 4^{∘} d = 4 if G can be represented in the root system D_{n} for some n, 5^{∘} d = n + 1 if G is the line graph of a tree.

The statements of this theorem can be, of course, verified on all L^{+}-graphs in our table of SINGs. Cases 1^{∘}, 2^{∘} and 3^{∘} correspond to the cases (v), (iv) and (iii) of Theorem 2 respectively. Case 4^{∘} includes case (i) and line graphs of odd unicyclic graphs from (ii). Case 5^{∘} covers the remaining part of (ii).

The quantity d is called the discriminant of the integral lattice generated by the corresponding root system and the whole theorem has been taken from the lattice theory (see, for example, [1, pp. 101–102]). If we put d = V^{2}, then V is, in fact, the volume of an elementary cell of the corresponding integral lattice.

[figure: 7.17]

[figure: 7.16]

[figure: 8.22]

[figure: 7.6]

[figure: 8.49]

Figure 2. (continued)

The quantity d will also be called the discriminant of the corresponding graph. In fact for an L-graph G on n vertices we define

d_{G} = (−1)^{n}P_{G}(−2)

to be the discriminant of G. We have d_{G} = 0 if the least eigenvalue is equal to −2 and d_{G} = (−1)^{n}Π_{G}(0) if G is an L^{+}-graph.

The following lemma is obvious.

Lemma 1. The discriminant of an L-graph is equal to the product of discriminants of its components.

Discriminants of various kinds of L^{+}-graphs on up to 10 vertices are given in the following table.

n 1 2 3 4 5 6 7 8 9 10
L(T) 2 3 4 5 6 7 8 9 10 11
representable in D_{n}  4 4 4 4 4 4 4
exceptional  3 2 1

L^{+}-graphs are star complements for −2 in L^{0}-graphs. L^{+}-graphs are distinguished from L^{0}-graphs by its positive discriminant and also can be well classified by this invariant possibly in conjunction with the number of vertices if necessary. Moreover, we have the following theorem.

Theorem 4. Let G be an L^{0}-graph on n vertices and having k principal eigenvalues. The coefficient a_{k} of λ^{n−k} in the polynomial P_{G}(λ − 2) is equal to (−1)^{k}S where S is the sum of discriminants of star complements of G for eigenvalue −2.

Proof. Up to the sign, a_{k} is equal to the sum of all minor of order k of det (A + 2I) where A is the adjacency matrix of G. Such a minor is essentially the value P_{G^{(k)}}(−2) for an induced subgraph G^{(k)} of G on k vertices. For subgraphs which are not star complements we have P_{G^{(k)}}(−2) = 0 and the theorem readily follows. □

Theorem 4 shows that S is an important graph invariant. We shall call it the star value of an L-graph G. Obviously, the following formulas hold

S = \frac{(−1)^{n}}{(n − k)!}P_{G}^{(n−k)}(−2) = (−1)^{n}Π_{G}(0) = (λ_{1} + 2)(λ_{2} + 2) ⋯ (λ_{k} + 2),

where f^{(p)}(x) denotes the p-th derivative of the function f(x).

Since the principal polynomial of a disconnected graph G is equal to the product of principal polynomials of its components, the star value of G is the product of star values of components of G as well.

5. Some theorems on cospectral L-graphs

Cospectral L-graphs could be line graphs, proper generalized line graphs and (generalized) exceptional graphs in all combinations. We shall first consider cospectrality of generalized line graphs with generalized exceptional graphs.

For regular L-graphs the following theorem (see, for example, [9, Theorem 4.2.9]) is of great importance.

Theorem 5. The spectrum of a graph G determines whether or not it is a regular connected line graph except for 17 cases. The exceptional cases are those in which G has the spectrum of L(H) where H is one of the 3-connected regular graphs on 8 vertices or H is a connected semiregular bipartite graph on 6 + 3 vertices.

It turns out that there are exactly 68 regular exceptional graphs which are cospectral with the 17 line graphs from Theorem 4. They are easily identified from the list of all 187 regular exceptional graphs given in Table A3 of [9]. Table A4 of [9] presents a construction of the these 68 graphs without recourse to a computer.

We shall point out what Theorem 5 says in the case of iterated line graphs.

Proposition 3. Let G = L^{2}(H) where G is regular and H is a connected graph. If G has an exceptional cospectral mate then H is either K_{1,8} or K_{2,4}. In the first case exceptional mates are the three Chang graphs and in the second case graphs Nos. 43–45 of Table A3 in [9].

Proof. Let L(H) = H_{1}. Then G = L(H_{1}) and by Theorem 1 the graph H_{1} should be one of the 17 graphs appearing in that theorem. Only two of them are line graphs: the complete graph K_{8} and the complement of the cube. In these cases we have H = K_{1,8} or H = K_{2,4}. By consulting a table of regular exceptional graphs (Table A3 in [9]) we can readily verify the last statement. □

For non-regular graphs little is known. We can prove the following generalization of Theorem 5.

Theorem 6. A connected generalized line graph G = L(H) has an exceptional cospectral mate only if its root graph H, assuming it is itself connected and has n vertices, satisfies one of the following conditions:

a) H is not bipartite and n is at most 8,

b) H is bipartite and n is at most 9.

Proof. By Proposition 4.1.2 of [9] exceptional graphs have p = 6, 7 or 8 principal eigenvalues. In order to have an exceptional cospectral mate, a GLG should have also p principal eigenvalues. The multiplicity of −2 as an eigenvalue of G is equal to m − p, where m is the number of edges of H. Then the conclusion of Theorem 6 follows from Theorem 1. □

Corollary. The graph H in Theorem 6 satisfies one of the following conditions:

i) H has at least one petal and the number of vertices after removing petals is at most 7,

ii) H has no petals: it has an odd cycle and n is at most 8, iii) H has no petals: it is bipartite and n is at most 9.

Note that a connected proper GLG can have a disconnected generalized exceptional mate as PING No. 8.10 shows for L^{+}-graphs and SING No. 8.44 for L^{0}-graphs.

Theorem 6 does not cover such cases. In connected regular (generalized) line graphs a (generalized) exceptional mate is necessary connected since (contrary to the non-regular case) the information on connectedness of a regular graph is contained in its spectrum (cf. eg. [3, Theorems 3.22 and 3.23]). This in particular means that a connected GLG with more than 36 vertices can have a disconnected generalized exceptional mate.

In Theorems 5 and 6 we have considered the cases when a (generalized) line graph is cospectral with a (generalized) exceptional graph. It is possible, of course, for two (generalized) line graphs to be cospectral. For regular line graphs which arise from nonisomorphic root graphs Theorem 4.3.1 from [9] specifies the possibilities.

In the case of L^{+}-graphs we have a non-existence result.

Theorem 7. Let G ∈ L^{+} be a connected GLG. Then G does not have an exceptional cospectral mate.

Proof. By Theorem 3 the discriminant d_{G} = (−1)^{n}P_{G}(−2) of G is equal to 1, 2 or 3 for an exceptional L^{+}-graph while in GLGs this quantity has other values. □

However, a connected GLG can have a (disconnected) generalized exceptional mate as PING No. 8.10 shows. This PING consists of a connected line graph having the discriminant equal to 4 while the second graph consists of an exceptional graph on 7 vertices and a trivial component each having the discriminant equal to 2 (cf. Lemma 1).

The argument with graph discriminants can be further exploited.

Within connected L^{+}-graphs the discriminant and the number of vertices are sufficient to distinguish between line graphs of trees, generalized line graphs representable in the root system D_{n} for some n and exceptional graphs. In some cases one can include also disconnected graphs as the following proposition shows.

Proposition 4. If n + 1 is a prime then any L^{+}-graph on n vertices having discriminant n + 1 is the line graph of a tree.

If n + 1 = 4k for some integer k, then we can construct a disconnected L^{+}- graph having the discriminant equal to n + 1. One of the components can be the line graph with k − 1 vertices of a tree while the other should be an L^{+}-graph of discriminant 4 with n − k + 1 vertices. However, if n + 1 is not divisible by 4 such constructions are very limited.

Although by Theorem 7 the iterated line graphs belonging to L^{+} cannot have exceptional cospectral mates, they may be cospectral to some GLGs. Such examples can be found in our table (cf.,e.g., SING No. 7.12 and SING No. 18.16).

The graphs with largest eigenvalue not exceeding 2 are identified in [16] and their spectra determined in [4]. These graphs are L-graphs. One should note that all PINGs consisting of these graphs have been classified in [4].

References

[1] A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

[2] P. J. Cameron, J. M. Goethals, J. J. Seidel, E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), 305–327.

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

[4] D. Cvetković, I. Gutman, On the spectral structure of graphs having the maximal eigenvalue not greater than two, Publ. Inst. Math., Nouv. Sér. 18(32) (1975), 39–45.

[5] V Cvetković, M. Lepović, A table of cospectral graphs with least eigenvalue at least −2, http://www.mi.sanu.ac.yu/projects/results1389.htm

[6] D. Cvetković, M. Lepović, Sets of cospectral graphs with least eigenvalue −2 and some related results, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 129(29) (2004), 85–102.

[7] D. Cvetković, M. Lepović, P. Rowlinson, S. Simić, The maximal exceptional graphs, J. Combinatorial Theory, Ser. B 86 (2002), 347–363.

[8] D. Cvetković, P. Rowlinson, S. K. Simić, Graphs with least eigenvalue −2: the star complement technique, J. Algebraic Combinatorics 14 (2001), 5–16.

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

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

[11] M. Doob, D. Cvetković, On spectral characterizations and embedding of graphs, Linear Algebra Appl. 27 (1979), 17–26.

[12] M. N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combinatorics 8 (1993), 247–265.

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

[14] P. Rowlinson, Eutactic stars and graph spectra, in: Combinatorial and Graph-Theoretic Problems in Linear Algebra, ed. Brueldi R.A., Friedland S., Klee V., Springer-Verlag, New York, 1993, 153–164.

[15] P. Rowlinson, Star complements in finite graphs: a survey, Rendiconti Sem. Mat. Messina, 8 (2002), 145–162.

[16] J. H. Smith, Some properties of the spectrum of a graph, Combinatorial Structures and Their Applications, Proc. of the Calgary Internat. Conf. on Combinatorial Structures and their Applications held at the Univ. of Calgary, June, 1969, ed. R.Guy, H.Hanani, N.Sauer, J.Schönheim, Gordon and Breach, New York–London–Paris, 1970, 403–406.

Elektrotehnički fakultet (Received 28 03 2005) 11120 Beograd, p.p. 35–54 (Revised 28 08 2005) Serbia and Montenegro

ecvetkod@etf.bg.ac.yu

Prirodno-matematički fakultet 34000 Kragujevac Serbia and Montenegro

lepovic@knez.uis.kg.ac.yu