PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 63 (77), 1998, 37–46

ON FORMAL PRODUCTS AND THE SEIDEL SPECTRUM OF GRAPHS

Mirko Lepović

Communicated by Slobodan Simić

Abstract. In [2] using the formal product and the so-called formal generating functions, we proved some results concerning cospectral graphs. In this paper, we define the Seidel formal product and investigate some properties of the Seidel spectrum. In particular, for any two overgraphs G_{S_{1}} and G_{S_{2}} of G we give necessary and sufficient conditions under which G_{S_{1}} and G_{S_{2}} have the same Seidel spectrum.

In this paper we consider only simple graphs. The vertex set of a graph G is denoted by V (G), and its order by |G|. The spectrum of such a graph is the collection λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} of eigenvalues of its (0,1) adjacency matrix and it is denoted with σ(G). The Seidel spectrum σ^{∗}(G) is the collection λ_{1}^{∗} ≥ λ_{2}^{∗} ≥ ⋯ ≥ λ_{n}^{∗} of eigenvalues of its Seidel (−1, 1, 0) adjacency matrix.

In the sequel, for any graph G denote by A = A(G) = [a_{ij}], A^{∗} = A^{∗}(G) = [a_{ij}^{∗}], P_{G}(λ) and P_{G}^{∗}(λ), the adjacency matrix, the Seidel adjacency matrix, the characteristic polynomial and the Seidel characteristic polynomial, respectively. If G and H are two graphs which have the same Seidel spectrum, we shall say that G and H are Seidel cospectral.

Let S be any (possibly empty) subset of the vertex set V (G). Denote by G_{S} the graph obtained from the graph G by adding a new vertex x (x ∉ V (G)), which is adjacent exactly to the vertices in S. The family of overgraphs G_{S} of the graph G is denoted by G(G), and it is called the overset of G.

For a matrix M denote by {M} the adjoint of M, and let sum M denote the sum of all elements in M.

Let G be an arbitrary graph of order n and let A = [A_{ij}] = {λI − A}. Of course, we have A_{ij} = A_{ji} (i, j = 1, 2,…, n). For any two subsets X, Y of the vertex set V (G), let ⟨X, Y ⟩ = ∑_{i∈X} ∑_{j∈Y} A_{ij}. In [2] the expression ⟨X, Y ⟩ was defined as the formal product of the sets X and Y, associated with the graph G. For any two subsets X, Y ⊆ V (G), define ⟨X, Y ⟩^{∗} = ∑_{i∈X} ∑_{j∈Y} A_{ij}^{∗}, where A^{∗} = [A_{ij}^{∗}] = {λI −A^{∗}}. In this paper ⟨X, Y ⟩^{∗} is called the Seidel formal product of the sets X and Y, associated with the graph G. Since A_{ij}^{∗} = A_{ji}^{∗} (i, j = 1, 2,…, n) we obtain that ⟨X, Y ⟩^{∗} = ⟨Y, X⟩^{∗} for any two subsets X, Y ⊆ V (G). If X ∩ Y = ∅, then the union of X and Y is denoted by X + Y. Let X, Y, Z ⊆ V (G) be any three subsets of V (G) such that X ∩ Y = ∅. Then we find the relation

AMS Subject Classification (1991): Primary 05C50 Key Words: Graph, overgraph, Seidel spectrum, cospectral graph Supported by Ministry of Science and Technology of Serbia, through Mathematical Institute

⟨X + Y, Z⟩^{∗} = ⟨X, Z⟩^{∗} + ⟨Y, Z⟩^{∗} .

Let S ⊆ V (G) and G_{S} be the corresponding overgraph of G. For any set S ⊆ V (G) let T = V (G) ∖ S. In [2] we proved the next result.

Theorem 1 [2]. For any graph G and any set S ⊆ V (G), we have

(1)  P_{G_{S}}(λ) = λP_{G}(λ) − ⟨S, S⟩ . □

Similar results were proved by E. Heilbronner (see [1, p. 59]) and by A. Schwenk (see [3]).

Using the same method as in the proof of Theorem 1, one can easily see that the Seidel characteristic polynomial of G_{S} reads

(2)  P_{G_{S}}^{∗}(λ) = λP_{G}^{∗}(λ) − ⟨S, S⟩^{∗} − ⟨T, T ⟩^{∗} + 2⟨S, T ⟩^{∗} .

Let S^{•} = V (G) and denote the corresponding overgraph of G by G^{•}. Since ⟨S^{•}, S^{•}⟩^{∗} = ⟨S + T, S + T ⟩^{∗}, using (2) we obtain that

(3)  P_{G_{S}}^{∗}(λ) = P_{G^{•}}^{∗}(λ) + 4 ⟨S, T ⟩^{∗} .

Further, let S be any subset of the vertex set V (G). To switch G with respect to S means:

• to remove all edges connecting S with T = V (G) ∖ S; and

• to introduce an edge between all nonadjacent vertices x, y such that one of them belongs to S and the other to T. Two graphs G and H are switching (Seidel switching) equivalent if one of them

is obtained from the other by switching. It is known that switching equivalent graphs have the same Seidel spectrum. We notice that, if S ⊆ V (G) then the corresponding graphs G_{S} and G_{T} are switching equivalent.

On the other hand, since ⟨S, T ⟩^{∗} = ⟨T, S⟩^{∗}, using relation (3) we obtain that G_{S} and G_{T} are Seidel cospectral graphs for any S ⊆ V (G). Also, by (3) we obtain the following statement.

Corollary 1. Let G_{S_{1}} and G_{S_{2}} be two arbitrary overgraphs of G. Then G_{S_{1}} and G_{S_{2}} are Seidel cospectral if and only if ⟨S_{1}, T_{1}⟩^{∗} = ⟨S_{2}, T_{2}⟩^{∗}. □

For any adjacency matrix A, let A^{k} = [a_{ij}^{(k)}]. In [2] was proved that the formal product ⟨S, S⟩ and the characteristic polynomial P_{G_{S}}(λ) (S ⊆ V (G)) can be expressed by the entries of A^{k} for all values of k. In this paper, we shall show that ⟨S, S⟩^{∗} and P_{G_{S}}^{∗}(λ) can be expressed by the entries of (A^{∗})^{k} = [(a_{ij}^{∗})^{(k)}], where, as usual, A^{∗} is the Seidel adjacency matrix of G.

We first recall some results and definitions concerning canonical graphs which are given in [4] and [5].

Let G be an arbitrary connected graph of order n. We say that two vertices x, y ∈ V (G) are equivalent in G and write x ∼ y if x is nonadjacent to y, and x and y have exactly the same neighbors in G. Relation ∼ is obviously an equivalence relation on the vertex set V (G). The corresponding quotient graph is denoted by G̃, and is called the canonical graph of G.

We say that G is canonical if G = G̃ or equivalently |G| = |G̃|, i.e., if G has no two equivalent vertices. Let G̃ be the canonical graph of G, |G̃| = k, and N_{1}, N_{2},…, N_{k} be the corresponding sets of equivalent vertices in G. Then we write G = G̃(N_{1}, N_{2},…, N_{k}), or simply G = G̃(n_{1}, n_{2},…, n_{k}), where |N_{i}| = n_{i} (i = 1, 2,…, k), understanding that G̃ is a labelled graph.

It was proved in [4] that the characteristic polynomial P_{G}(λ) of the graph G takes the form

(4)  P_{G}(λ) = n_{1} · n_{2} ·. . . · n_{k} λ^{n−k} | \begin{matrix}\frac{λ}{n_{1}} & − ã_{12} & … & − ã_{1k} \\ − ã_{21} & \frac{λ}{n_{2}} & … & − ã_{2k} \\ ⋮ & ⋮ & ... & ⋮ \\ − ã_{k1} & − ã_{k2} & … & \frac{λ}{n_{k}} \end{matrix} | ,

where [ã_{ij}] is the adjacency matrix of the canonical graph G̃.

Using the same method as in [4] for obtaining relation (4), one can see that the Seidel characteristic polynomial P_{G}^{∗}(λ) of the graph G reads

(5)  P_{G}^{∗}(λ) = (λ + 1)^{n−k} | \begin{matrix}λ + 1 − n_{1} & − n_{1} ã_{12}^{∗} & … & − n_{1} ã_{1k}^{∗} \\ − n_{2} ã_{21}^{∗} & λ + 1 − n_{2} & … & − n_{2} ã_{2k}^{∗} \\ ⋮ & ⋮ & ... & ⋮ \\ − n_{k} ã_{k1}^{∗} & − n_{k} ã_{k2}^{∗} & … & λ + 1 − n_{k} \end{matrix} | ,

where [ã_{ij}^{∗}] is the Seidel adjacency matrix of the canonical graph G̃.

Let G be any (not necessarily canonical) graph of order n. Let G_{x_{1},x_{2},...,x_{m}} be the overgraph of G obtained by adding new vertices x_{1}, x_{2},…, x_{m} equivalent to a vertex i of G, say i = 1, so that the vertices x_{1}, x_{2},…, x_{m}, 1 are mutually nonadjacent, and have the same neighbors in G. According to (5), applying the same method as in [4] for deriving relation (4), one can see that the Seidel characteristic polynomial of G_{x_{1},x_{2},...,x_{m}} reads

(6) P_{G_{x_{1},x_{2},...,xm}}^{∗} (λ) = (λ + 1)^{m} | \begin{matrix}λ − m & − (m + 1)a_{12}^{∗} & … & − (m + 1)a_{1n}^{∗} \\ − a_{21}^{∗} & λ & … & − a_{2n}^{∗} \\ ⋮ & ⋮ & ... & ⋮ \\ − a_{n1}^{∗} & − a_{n2}^{∗} & … & λ \end{matrix} | ,

where [a_{ij}^{∗}] is the Seidel adjacency matrix of the graph G.

Let S be any subset of V (G) and let G_{2S} be the overgraph of G obtained by adding two new non-adjacent vertices x, y which are both adjacent exactly to the vertices from S. Note that G_{2S} ∈ G(G_{S}), and G_{2S} is obtained from G_{S} by adding a new vertex y which is equivalent to x ∈ V (G_{S}). Therefore, using (2) we have the following relation

P_{G_{2S}}^{∗}(λ) = λP_{G_{S}}^{∗}(λ) − ⟨S, S⟩^{∗} − ⟨T, T ⟩^{∗} + 2 ⟨S, T ⟩^{∗} ,

where ⟨X, Y ⟩^{∗} is the Seidel formal product associated with G_{S}.

Proposition 1. The Seidel characteristic polynomial P_{G_{2S}}^{∗}(λ) of the graph G_{2S} reads

P_{G_{2S}}^{∗}(λ) = (λ + 1)[(λ − 1)P_{G}^{∗}(λ) − 2 ⟨S, S⟩^{∗} − 2 ⟨T, T ⟩^{∗} + 4 ⟨S, T ⟩^{∗}] ,

where ⟨X, Y ⟩^{∗} is the Seidel formal product associated with the graph G.

Proof. Without loss of generality we may assume that S = {1, 2,…, k} ⊆ V (G) (0 ≤ k ≤ n). Using relation (6), the Seidel characteristic polynomial P_{G_{2S}}^{∗}(λ) takes the form

P_{G_{2S}}^{∗}(λ) = (λ + 1) | \begin{matrix}λ & … & − a_{1k}^{∗} & … & − a_{1n}^{∗} & 1 \\ ⋮ & ... & ⋮ & ⋮ & ⋮ & ⋮ \\ − a_{k1}^{∗} & … & λ & … & − a_{kn}^{∗} & 1 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ − a_{n1}^{∗} & … & − a_{nk}^{∗} & … & λ & −1 \\ 2 & … & 2 & … & −2 & λ − 1 \end{matrix} | .

Applying the same method as in the proof of Theorem 1, one can easily obtain the required statement. □

Let S be any subset of V (G) and let G_{mS} be the overgraph of G obtained by adding m new mutually non-adjacent vertices x_{1}, x_{2},…, x_{m}, all adjacent exactly to the vertices in S.

Corollary 2. The Seidel characteristic polynomial P_{G_{mS}}^{∗}(λ) (m ∈ N) of the graph G_{mS} reads

P_{G_{mS}}^{∗}(λ) =

(λ + 1)^{m−1}[(λ − m + 1) P_{G}^{∗}(λ) − m ⟨S, S⟩^{∗} − m ⟨T, T ⟩^{∗} + 2m ⟨S, T ⟩^{∗} ]. □

By (2) we find that ⟨S, S⟩^{∗} + ⟨T, T ⟩^{∗} − 2 ⟨S, T ⟩^{∗} = λ P_{G}^{∗}(λ) − P_{G_{S}}^{∗}(λ). Using Corollary 2 we have the following result.

Corollary 3. Let S ⊆ V (G). Then

P_{G_{mS}}^{∗}(λ) = (λ + 1)^{m−1} [m P_{G_{S}}^{∗}(λ) − (m − 1)(λ + 1) P_{G}^{∗}(λ) ] ,

for any m ∈ N. □

Corollary 4. Let G_{S_{1}} and G_{S_{2}} be any two overgraphs of G (S_{1}, S_{2} ⊆ V (G)). If G_{S_{1}} and G_{S_{2}} are Seidel cospectral then G_{mS_{1}} and G_{mS_{2}} are also Seidel cospectral for every m ∈ N. □

Now, we shall need some well-known notions and results from the spectral theory of graphs (see [1]).

Theorem 2 [1]. Let A be the adjacency matrix of a multi-digraph G with vertices 1, 2,…, n, and A^{k} = [a_{ij}^{(k)}]; further, let N_{k}(i, j) denote the number of walks of length k starting at vertex i and terminating at vertex j. Then

N_{k}(i, j) = a_{ij}^{(k)} (k = 0, 1, 2,…) . □

Theorem 3 [1]. Let G be a graph with complement \overline{G} and let H_{G}(t) =

∑_{k=0}^{+∞} N_{k}t^{k} be the generating function of the numbers N_{k} of walks of length k in

the graph G. Then

(7)  H_{G}(t) = \frac{1}{t} [( − 1)^{n} \frac{P\overline{G} (−1 − 1/t)}{P_{G}(1/t)} − 1] ,

where N_{k} = sum A^{k} (k = 0, 1, 2,…). □

Theorem 4 [1]. If P_{G}(λ) is the characteristic polynomial of a graph G and P_{G}^{∗}(λ) is the characteristic polynomial of the Seidel adjacency matrix A^{∗}(G) of G, then

(8)  P_{G}(λ) = \frac{(−1)^{n}}{2^{n}} \frac{P_{G}^{∗}(−2λ − 1)}{1 + \frac{1}{2λ} H_{G}(\frac{1}{λ})} . □

According to (7) and (8), by a straightforward calculation we obtain the relation

(9)  P_{G}^{∗}(−2λ − 1) = 2^{n−1} (P\overline{G}(−λ − 1) + (−1)^{n}P_{G}(λ)) .

Since P_{G_{S}}^{∗}(λ) = P_{G_{T}}^{∗} (λ) for any S ⊆ V (G), then using (9) the next result follows.

Corollary 5. Let S ⊆ V (G). Then

P_{G_{S}}(λ) − P_{G_{T}} (λ) = (−1)^{n} (P\overline{G_{S}}(−λ − 1) − P\overline{G_{T}} (−λ − 1)) . □

In [2] using the so-called generalized adjacency matrices, we proved that for any S ⊆ V (G) the formal product

(10)  ⟨S, S⟩ = \frac{P_{G}(λ)}{λ} 𝔉_{S}( \frac{1}{λ} ) ,

where 𝔉_{S}(t) = ∑_{k=0}^{+∞} d^{(k)} t^{k} (|t| < λ_{1}^{−1}; λ_{1} ∈ σ(G)), and d^{(k)} = ∑_{i∈S} ∑_{j∈S} a_{ij}^{(k)} for any

non-negative integer k. We note that d^{(k)} is the number of walks of length k with endpoints in S.

The function 𝔉_{S}(t) is called the“formal generalized function” associated with the graph G_{S}. Similarly, the function

𝔉_{S,T}^{∗} (t) = ∑_{k=0}^{+∞} e_{∗}^{(k)} t^{k} (|t| < (λ_{1}^{∗})^{−1}; λ_{1}^{∗} ∈ σ^{∗}(G)) ,

will be called the “Seidel formal generating function” associated with the graph

G_{S}, where T = V (G) ∖ S and e_{∗}^{(k)} = ∑_{i∈S} ∑_{j∈T}(a_{ij}^{∗})^{(k)} (k = 0, 1, 2,…).

We shall prove that for any S ⊆ V (G), the Seidel formal product

(11)  ⟨S, T ⟩^{∗} = \frac{P_{G}^{∗}(λ)}{λ} 𝔉_{S,T}^{∗} ( \frac{1}{λ} ) .

The last relation may be proved by using some “Seidel generalized matrices”, in a way similar to that used to prove (10). However, in this paper we shall give an alternative proof of relation (11), as follows.

First, let

H_{G}^{∗}(t) = ∑_{k=0}^{+∞} N_{k}^{∗} t^{k} (|t| < (λ_{1}^{∗})^{−1}; λ_{1}^{∗} ∈ σ^{∗}(G)) ,

On formal products and the Seidel spectrum of graphs 43

where N_{k}^{∗} = ∑_{i=1}^{n} ∑_{j=1}^{n}(a_{ij}^{∗})^{(k)} (k = 0, 1, 2,…). In this paper, H_{G}^{∗}(t) is called the “Seidel generating function”. If we set

(12) [H_{G}^{∗}(t)] = ∑_{k=0}^{+∞}(A^{∗})^{k}t^{k} (|t| < (λ_{1}^{∗})^{−1}) ,

then, it is clear that H_{G}^{∗}(t) = sum [H_{G}^{∗}(t)].

Proposition 2. Let X, Y be any two sets of the vertex set V (G). Then

⟨X, Y ⟩^{∗} = \frac{P_{G}^{∗}(λ)}{λ} 𝔉_{X,Y}^{∗} ( \frac{1}{λ} ) ,

where 𝔉_{X,Y}^{∗} (t) = ∑_{k=0}^{+∞} c_{∗}^{(k)}t^{k} and c_{∗}^{(k)} = ∑_{i∈X} ∑_{j∈Y} (a_{ij}^{∗})^{(k)} (k = 0, 1, 2,…).

Proof. Using (12) we find that

[H_{G}^{∗}(t)] = (I − t A^{∗})^{−1} = \frac{\{I − t A^{∗}\}}{|I − t A^{∗}|} .

If we set [B_{ij}^{∗}] = {I − t A^{∗}}, then from the previous relation we obtain

B_{ij}^{∗} = t^{n} P_{G}^{∗}( \frac{1}{t} ) ∑_{k=0}^{+∞}(a_{ij}^{∗})^{(k)}t^{k} (1 ≤ i, j ≤ n) .

If we set t = 1/λ and substitute t in the last relation, we can easily see that

\frac{1}{λ^{n−1}} A_{ij}^{∗} = \frac{1}{λ^{n}} P_{G}^{∗}(λ) ∑_{k=0}^{+∞}(a_{ij}^{∗})^{(k)} \frac{1}{λ^{k}} ,

where [A_{ij}^{∗}] = {λI −A^{∗}}. Consequently, for any two sets X, Y ⊆ V (G) the following relation is obtained

⟨X, Y ⟩^{∗} = ∑_{i∈X} ∑_{j∈Y} A_{ij}^{∗} = \frac{P_{G}^{∗}(λ)}{λ} ∑_{i∈X} ∑_{j∈Y} [ ∑_{k=0}^{+∞}(a_{ij}^{∗})^{(k)} \frac{1}{λ^{k}} ]

= \frac{P_{G}^{∗}(λ)}{λ} ∑_{k=0}^{+∞} [ ∑_{i∈X} ∑_{j∈Y}(a_{ij}^{∗})^{(k)}] \frac{1}{λ^{k}}

= \frac{P_{G}^{∗}(λ)}{λ} 𝔉_{X,Y}^{∗} ( \frac{1}{λ} ) . □

In particular, for Y = X we denote the corresponding Seidel formal generating function 𝔉_{X,X}^{∗}(t) by 𝔉_{X}^{∗}(t). Therefore, according to (10), for any S ⊆ V (G) we have

⟨S, S⟩^{∗} = \frac{P_{G}^{∗}(λ)}{λ} 𝔉_{S}^{∗}( \frac{1}{λ} ) ,

where 𝔉_{S}^{∗}(t) = ∑_{k=0}^{+∞} d_{∗}^{(k)} t^{k} and d_{∗}^{(k)} = ∑_{i∈S} ∑_{j∈S}(a_{ij}^{∗})^{(k)}.

Corollary 6. Let X, Y ⊆ V (G). Then the formal product

⟨X, Y ⟩ = \frac{P_{G}(λ)}{λ} 𝔉_{X,Y} ( \frac{1}{λ} ) ,

where 𝔉_{X,Y} (t) = ∑_{k=0}^{+∞} c^{(k)}t^{k} and c^{(k)} = ∑_{i∈X} ∑_{j∈Y} a_{ij}^{(k)} (k = 0, 1, 2,…). □

We note that 𝔉_{X,Y} (t) is the generating function for the number of walks of length k with starting point in X and endpoint in Y.

As an immediate consequence of Proposition 2 and Corollary 1, we get:

Corollary 7. Let G_{S_{1}} and G_{S_{2}} be two arbitrary overgraphs of G. Then G_{S_{1}} and G_{S_{2}} are Seidel cospectral if and only if 𝔉_{S_{1},T_{1}}^{∗}(t) = 𝔉_{S_{2},T_{2}}^{∗}(t). □

For any S ⊆ V (G), we shall define a function

𝔉_{[S]}^{∗}(t) = 𝔉_{S}^{∗}(t) + 𝔉_{T}^{∗}(t) − 2 𝔉_{S,T}^{∗} (t) ,

where T = V (G) ∖ S. Now, using (2) and (11) we can easily see that the Seidel characteristic polynomial of G_{S} reads

(13)  P_{G_{S}}^{∗}(λ) = P_{G}^{∗}(λ) [λ − \frac{1}{λ} 𝔉_{[S]}^{∗}( \frac{1}{λ} ) ] .

Let S^{•} = V (G) and denote the corresponding overgraph of G by G^{•}. Using Proposition 2, we find that 𝔉_{S^{•}}^{∗}(t) = H_{G}^{∗}(t). Since T^{•} = V (G) ∖ S^{•} = ∅, it follows that ⟨T^{•}, X⟩^{∗} = 0 for any X ⊆ V (G). Whence we obtain 𝔉_{[S^{•}]}^{∗}(t) = 𝔉_{S^{•}}^{∗}(t). Using (13) and the last relation, we have

P_{G^{•}}^{∗}(λ) = λ P_{G}^{∗}(λ) − \frac{P_{G}^{∗}(λ)}{λ} H_{G}^{∗}( \frac{1}{λ} ) .

Finally, using the Seidel formal generating functions, we shall prove an elementary result.

Let G be the complete graph K_{n} and S be any subset of V (K_{n}). Denote by K(m) the corresponding overgraph of K_{n}, where |S| = m (0 ≤ m ≤ n).

On formal products and the Seidel spectrum of graphs 45

Proposition 3. If S ⊆ V (K_{n}) and |S| = m, then

P_{K(m)}^{∗}(λ) = (λ − 1)^{n−2} [λ^{3} + (n − 2)λ^{2} − (2n − 1)λ + 4m^{2} − 4mn + n] .

Proof. Since K_{n} is a regular graph of degree n − 1, we obtain that N_{k}^{∗} = (−1)^{k}n(n − 1)^{k}. Let α_{k} = (a_{11}^{∗})^{(k)} and β_{k} = (a_{12}^{∗})^{(k)} (k = 0, 1, 2,…). It is clear that (a_{ii}^{∗})^{(k)} = α_{k} (i = 1, 2,…, n) and (a_{ij}^{∗})^{(k)} = β_{k} (i ≠ j). Therefore, (−1)^{k}n(n − 1)^{k} = nα_{k} + (n^{2} − n)β_{k}. Since α_{k} = − (n − 1)β_{k−1}, the expression for

α_{k} = \frac{(−1)^{k}(n − 1)^{k} + (n − 1)}{n} and β_{k} = \frac{(−1)^{k}(n − 1)^{k} − 1}{n} ,

can be obtained by solving the linear recursions

β_{k} = β_{k−1} + (−1)^{k}(n − 1)^{k−1} and α_{k} = − (n − 1)β_{k−1} ,

with α_{0} = 1 and β_{0} = 0.

Since d_{∗}^{(k)} = ∑_{i∈S} ∑_{j∈S}(a_{ij}^{∗})^{(k)} and |S| = m, we have d_{∗}^{(k)} = mα_{k} + (m^{2} − m)β_{k}.

Whence we get

(14)  d_{∗}^{(k)} = \frac{(−1)^{k}m^{2}(n − 1)^{k} − m^{2} + mn}{n} .

Further, using (14) we find

(15)  𝔉_{S}^{∗}(t) = \frac{m^{2}}{n(1 + (n − 1)t)} − \frac{m^{2}}{n(1 − t)} + \frac{m}{1 − t} .

Similarly, we obtain

(16)  𝔉_{T}^{∗}(t) = \frac{(n − m)^{2}}{n(1 + (n − 1)t)} − \frac{(n − m)^{2}}{n(1 − t)} + \frac{n − m}{1 − t} .

Now, denote by e_{∗}^{(k)} the corresponding coefficients of the function 𝔉_{S,T}^{∗} (t). Since e_{∗}^{(k)} = m(n − m)β_{k}, we can see that

𝔉_{S,T}^{∗} (t) = \frac{m(n − m)}{n(1 + (n − 1)t)} + \frac{m^{2}}{n(1 − t)} − \frac{m}{1 − t} .

Using (15), (16) and the last relation, by an easy calculation we obtain that the corresponding function 𝔉_{[S]}^{∗}(t) reads

𝔉_{[S]}^{∗}(t) = \frac{(4mn − 4m^{2} − n) t + n}{(1 + (n − 1)t)(1 − t)} .

Finally, if we set t = 1/λ in the previous relation, then by using (13), having in mind that

P_{K_{n}}^{∗}(λ) = (−1)^{n}P_{K_{n}}(− λ) = (λ − 1)^{n−1}(λ + (n − 1)) ,

we obtain the statement. □

References

[1] D. Cvetković, M. Doob, H. Sachs, Spectra of graphs – Theory and applications, 3rd revised and enlarged edition, J.A. Barth Verlag, Heidelberg–Leipzig, 1995.

[2] M. Lepović, On formal products and spectra of graphs, Discrete Math., to appear.

[3] A. Schwenk, Computing the characteristic polynomial of a graph, Graphs and Combinatorics, R. Bari and F. Harary, Eds, Springer-Verlag, Berlin, 1974, pp. 153–172.

[4] A. Torgašev, On infinite graphs with three and four non-zero eigenvalues, Bull. Serb. Acad. Sci. Arts 64 Sci. Math. 11 (1981), 39–48.

[5] A. Torgašev, Graphs with the reduced spectrum in the unit interval, Publ. Inst. Math. (Belgrade) 36(50) (1984), 17–28.

Prirodno-matematički fakultet (Received 27 01 1997) 34000 Kragujevac (Revised 10 11 1997) Yugoslavia