PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 85(99) (2009), 47–54 DOI:10.2298/PIM0999047S

ON RELATION BETWEEN SPECTRA OF GRAPHS AND THEIR DIGRAPH DECOMPOSITIONS

Dragan Stevanović and Sanja Stevanović

Communicated by Slobodan K. Simić

Abstract. A graph, consisting of undirected edges, can be represented as a sum of two digraphs, consisting of oppositely oriented directed edges. Gutman and Plath in [J. Serb. Chem. Soc. 66 (2001), 237–241] showed that for annulenes, the eigenvalue spectrum of the graph is equal to the sum of the eigenvalue spectra of respective two digraphs. Here we exhibit a number of other graphs with this property.

1. Introduction

Let G be a simple graph with vertex set V (G) and edge set E(G). Following [1], in the standard graph representation of organic molecules, edges represent covalent chemical bonds, which are assumed to be undirected, as is the entire graph. However, each undirected edge may be alternatively viewed as a pair of oppositely oriented directed edges. In this way, whole undirected graph G may always be decomposed into a pair of digraphs, \overrightarrow{G} and \overleftarrow{G}, consisting of oppositely oriented directed edges, such that V (\overrightarrow{G}) = V (\overleftarrow{G}) = V (G) and E(G) = E(\overrightarrow{G}) ∪ E(\overleftarrow{G}).

In [1], Gutman and Plath showed that graphs of annulenes, undirected cycles, have an interesting property: each eigenvalue of an undirected cycle is equal to the sum of the corresponding eigenvalues of directed cycles from its digraph decomposition.

The spectrum Sp[\overrightarrow{G}] of a digraph \overrightarrow{G} is the collection of eigenvalues of its adjacency matrix A(\overrightarrow{G}). The adjacency matrix A(\overleftarrow{G}) is the transpose of A(\overrightarrow{G}). Therefore, the digraphs \overrightarrow{G} and\overleftarrow{G} have equal spectra. Since A(\overrightarrow{G}) is not symmetric, its eigenvalues may be complex numbers. However, if a complex number z is an eigenvalue of \overrightarrow{G}, then also its complex conjugate \overline{z} is an eigenvalue of \overrightarrow{G}. Note that if \overrightarrow{G} does not possess directed cycles, then all its eigenvalues are equal to zero [1, Theorem 3.(a)]. Namely, if \overrightarrow{G} has n vertices, then the characteristic polynomial of A(\overrightarrow{G}) may be written in the form

2000 Mathematics Subject Classification: 05C50.

Key words and phrases: Adjacency matrix; Digraph; Decomposition; Eigenvalues.

The first author is supported by the research grant 144015G of the Serbian Ministry of Science and the research program P1-0285 of the Slovenian Agency for Research.

(1.1)  ϕ(G, λ) = λ^{n} + ∑_{k=1}^{n} a_{k}λ^{n−k} .

Then, by the Sachs’ theorem for digraphs [2, 3, 4],

a_{k} = ∑_{S} (−1)^{p(S)} ,

where the summation goes over all k-vertex subgraphs S of G that consist entirely of directed cycles, the number of directed cycles in S being p(S). Thus, if \overrightarrow{G} has no directed cycles, we have a_{k} = 0 for all k = 1, 2, …, n and the characteristic polynomial (1.1) is equal to ϕ(G, λ) = λ^{n}, whose all roots are equal to zero.

Next, denote the eigenvalues of \overrightarrow{G} by λ_{1}(\overrightarrow{G}), λ_{2}(\overrightarrow{G}), … λ_{n}(\overrightarrow{G}). The eigenvalues of\overleftarrow{G} may always be labelled such that λ_{k}(\overrightarrow{G}) + λ_{k}(\overleftarrow{G}) is a real number [1, Theorem 2]. Simply, if λ_{k}(\overrightarrow{G}) is real, choose λ_{k}(\overleftarrow{G}) to be equal to λ_{k}(\overrightarrow{G}), and if λ_{k}(\overrightarrow{G}) is not real, choose λ_{k}(\overleftarrow{G}) to be equal to the complex conjugate of λ_{k}(\overrightarrow{G}), which is also an eigenvalue of \overrightarrow{G}. Note that this labelling implies

λ_{k}(\overrightarrow{G}) + λ_{k}(\overleftarrow{G}) = 2 Reλ_{k}(\overrightarrow{G}).

We will implicitly assume this type of labelling for the eigenvalues of \overleftarrow{G} in the sequel.

In general, the eigenvalues λ_{k}(G) of undirected graph G are not related to the eigenvalues of digraphs from its digraph decomposition. Gutman and Plath [1, Theorem 4] showed that for the decomposition of undirected cycle C_{n} = \overrightarrow{C_{n}} ∪\overleftarrow{C_{n}} in two directed cycles, the eigenvalues of undirected cycle may be labelled such that

λ_{k}(C_{n}) = λ_{k}(\overrightarrow{C_{n}}) + λ_{k}(\overleftarrow{C_{n}}) = 2 Reλ_{k}(\overrightarrow{C_{n}}), for k = 1, 2, …, n,

or, shorter,

Sp[C_{n}] = 2 ReSp[\overrightarrow{C_{n}}].

Concluding [1], Gutman and Plath said: “The discovery of more graphs G satisfying

(1.2)  Sp[G] = 2 ReSp[\overrightarrow{G}]

would, however, be of much greater importance.”

Our main task here is to exhibit a number of graphs satisfying (1.2). The plan of the paper is as follows: in Section 2 we exhibit all such graphs with up to 8 vertices and 14 edges, in Section 3 we show how new instances may be obtained from existing ones using NEPS, and in Section 4 we present a family of graphs satisfying (1.2) which may not be obtained using the method of Section 3.

2. Small instances

We have enumerated all digraph decompositions of connected graphs with at most 8 vertices and 14 edges and, besides cycles, we have found seven other graphs satisfying (1.2). In addition, our experiments show that the complete bipartite graph K_{4,4} has two distinct decompositions each satisfying (1.2). For each of these eight graphs, a digraph \overrightarrow{G_{i}} is given in Figure 1, while the spectra of \overrightarrow{G_{i}} and G_{i} = \overrightarrow{G_{i}}∪ \overleftarrow{G_{i}} are as follows (where parenthesized numbers in exponents denote multiplicities):

Sp(\overrightarrow{G_{1}}) = [2, −0.5 ± i 1.538842, −0.5 ± i 0.363271]
Sp(G_{1}) = [4, −1^{(4)}]
Sp(\overrightarrow{G_{2}}) = [±1.414214, ±i 1.414214, 0^{(2)}]
Sp(G_{2}) = [2.828427, 0^{(4)}, −2.828427]
Sp(\overrightarrow{G_{3}}) = [1.618034, −0.618034, −0.809017 ± i 1.401259, 0.309017 ± i 0.535233]
Sp(G_{3}) = [3.236068, 0.618034^{(2)}, −1.236068, −1.618034^{(2)}]
Sp(\overrightarrow{G_{4}}) = [2, 0^{(3)}, −1 ± i 1.732051]
Sp(G_{4}) = [4, 0^{(3)}, −2^{(2)}]
Sp(\overrightarrow{G_{5}}) = [2, 0.400969±i 0.193096, −0.277479±i 1.215715, −1.123490±i 1.408812]
Sp(G_{5}) = [4, 0.801938^{(2)}, −0.554958^{(2)}, −2.246980^{(2)}]
Sp(\overrightarrow{G_{6}}) = [±1.732051, ±i 1.732051, 0^{(4)}]
Sp(G_{6}) = [3.464102, 0^{(6)}, −3.464102]
Sp(\overrightarrow{G_{7}}) = [±1.618034, ±i 1.618034, ±0.618034, ±i 0.618034]
Sp(G_{7}) = [3.236068, 1.236068, 0^{(4)}, −1.236068, −3.236068]
Sp(\overrightarrow{G_{8}}) = [±2, ±2i, 0^{(4)}]
Sp(G_{8}) = [4, 0^{(6)}, −4]
Sp(\overrightarrow{G_{9}}) = [±2, ±i \sqrt{2}^{(2)}, 0^{(2)}]
Sp(G_{9}) = [4, 0^{(6)}, −4]

Note that graphs G_{2} and G_{6} in Figure 1 are isomorphic to K_{2,4} and K_{2,6}, respectively. Having in mind that the cycle C_{4}, which satisfies (1.2), is isomorphic to K_{2,2}, we can arrive to our first expectation: graph K_{2,2n} should have a digraph decomposition satisfying (1.2). Indeed, denote by u and v vertices from two-vertex part of K_{2,2n} , and divide the vertices from 2n-vertex part of K_{2,2n} into two equally

\begin{matrix}\overrightarrow{G_{1}} & \overrightarrow{G_{2}} & \overrightarrow{G_{3}} \\ \overrightarrow{G_{4}} & \overrightarrow{G_{5}} & \overrightarrow{G_{6}} \\ \overrightarrow{G_{7}} & \overrightarrow{G_{8}} & \overrightarrow{G_{9}} \end{matrix}

Figure 1. Small instances satisfying (1.2).

sized sets A and B. Let \overrightarrow{K_{2,2n}} be the digraph obtained from K_{2,2n} by directing all edges from u to A, from A to v, from v to B and from B to u. Each directed cycle of \overrightarrow{K_{2,2n}} has length 4 and contains vertices u and v. Thus, there are no disjoint directed cycles in \overrightarrow{K_{2,2n}} and from Sachs’ theorem we get that the only nonzero coefficient in the characteristic polynomial (except with x^{2n+2} ) is the one with x^{(2n+2)−4} , which is equal to n^{2}. Thus, the characteristic polynomial of \overrightarrow{K_{2,2n}} is equal to

x^{2n+2} − n^{2}x^{2n−2} = x^{2n−2} (x^{4} − n^{2}) = x^{2n−2} (x^{2} − n)(x^{2} + n),

hence, its spectrum is [±\sqrt{n}, ±i \sqrt{n}, 0^{2n−2} ], and twice its real part is [±2\sqrt{n}, 0^{2n}], which is just the spectrum of K_{2,2n} .

Thus, the graphs K_{2,2n} form our first family of graphs satisfying (1.2), however, their maximum degree increases with the number of vertices, which may not be favorable in chemical applications.

3. NEPS with undirected graphs

The non-complete extended p-sum (NEPS) of graphs is a very general graph operation. Many graph operations are special cases of NEPS, to name just the sum, product and strong product of graphs. It is defined for the first time in [5], while the following definition is taken from [3, p. 66] with minor modification:

Definition. Let B be a set of binary k-tuples, i.e., B ⊆ {0, 1}^{k} ∖ {(0, …, 0)} such that for every j = 1, …, k there exists β ∈ B with β_{j} = 1. The NEPS of graphs G_{1}, …, G_{k} with basis B, denoted NEPS(G_{1}, …, G_{k}; B), is the graph with the vertex set V (G_{1}) × ⋯× V (G_{k}), in which two vertices (u_{1}, …, u_{k}) and (v_{1}, …, v_{k}) are adjacent if and only if there exists (β_{1}, …, β_{k}) ∈ B such that u_{j} is adjacent to v_{j} in G_{j} whenever β_{j} = 1, and u_{j} = v_{j} whenever β_{j} = 0.

Despite the fact that NEPS is mostly used with undirected graphs, its definition carries over to directed graphs in a straightforward way, as can be seen from the works of Petrić [6, 7, 8]. In particular, a relation between spectrum of NEPS and the spectra of its factors holds unchanged (see, e.g., Theorem 2.23 in [3]).

Theorem 3.1. The spectrum of NEPS(G_{1}, …, G_{k}; B) consists of all possible values Λ given by

Λ = ∑_{β∈B} λ_{1}^{β_{1}} ⋯ λ_{k}^{β_{k}} ,

where λ_{j} is an arbitrary eigenvalue of G_{j}, j = 1, …, k.

This enables us to prove the following

Theorem 3.2. Let G be an undirected graph with digraph decomposition G = \overrightarrow{G} ∪\overleftarrow{G}, and suppose that the eigenvalues of G and \overrightarrow{G} can be enumerated in such a way that λ_{j} (G) = 2 Reλ_{j} (\overrightarrow{G}) for each j. Further, let B be a set of binary k-tuples such that β_{1} = 1 for each β ∈ B, and let G_{2}, …, G_{k} be arbitrary undirected graphs. Then the eigenvalues of

G^{∗} = NEPS(G, G_{2}, …, G_{k}; B) and \overrightarrow{G^{∗}} = NEPS(\overrightarrow{G}, G_{2}, …, G_{k}; B)

may be enumerated in such a way that λ_{j} (G^{∗}) = 2 Reλ_{j} (\overrightarrow{G^{∗}}) for each j.

Proof. Let λ_{1}(\overrightarrow{G}) be an arbitrary eigenvalue of \overrightarrow{G}, and let λ_{j} be an arbitrary eigenvalue of G_{j} for j = 2, …, k. Then, since β_{1} = 1 for each β ∈ B,

Λ(\overrightarrow{G^{∗}}) = ∑_{β∈B} λ_{1}^{β_{1}} (\overrightarrow{G})λ_{2}^{β_{2}} ⋯ λ_{k}^{β_{k}} = λ_{1}(\overrightarrow{G}) ∑_{β∈B} λ_{2}^{β_{2}} ⋯ λ_{k}^{β_{k}} = Mλ_{1}(\overrightarrow{G})

is an eigenvalue of \overrightarrow{G^{∗}}, where M = ∑ _{β∈B} λ_{2}^{β_{2}} ⋯ λ_{k}^{β_{k}} is a real number (as the eigenvalues λ_{2}, …, λ_{k} of undirected graphs must be real [3]). Similarly, for λ_{1}(G) = 2 Reλ_{1}(\overrightarrow{G}),

Λ(G^{∗}) = ∑_{β∈B} λ_{1}^{β_{1}} (G)λ_{2}^{β_{2}} ⋯ λ_{k}^{β_{k}} = λ_{1}(G) ∑_{β∈B} λ_{2}^{β_{2}} ⋯ λ_{k}^{β_{k}} = Mλ_{1}(G)

is an eigenvalue of G^{∗}. The PROOF then follows from

Λ(G^{∗}) = Mλ_{1}(G) = 2M Reλ_{1}(\overrightarrow{G}) = 2 ReMλ_{1}(\overrightarrow{G}) = 2 ReΛ(\overrightarrow{G^{∗}}).  □

Theorem 3.2 enables us to construct arbitrarily many instances of graphs satisfying (1.2) starting from directed cycles or graphs from Figure 1. For example, the graph \overrightarrow{G_{8}} is isomorphic to NEPS(\overrightarrow{C_{4}}, K_{2}; \{(1, 0), (1, 1)\}) of directed cycle C_{4} and complete graph K_{2}. Similarly, for any n ⩾ 3, NEPS(\overrightarrow{C_{n}}, K_{2}; \{(1, 0), (1, 1)\}) is a graph satisfying (1.2), where each vertex has indegree and outdegree equal to two.

However, the edges of NEPS of \overrightarrow{G} with undirected graphs always follow the direction of edges of \overrightarrow{G}. Thus, the directed cycles in such NEPS mimic the directed cycles from \overrightarrow{G}, which may not be considered favorably in applications as well.

4. Family of twisted ladders

Inspired by graphs \overrightarrow{G_{2}} and \overrightarrow{G_{7}} from Figure 1, in this section we present a family of oriented graphs, which may not be represented as NEPS of an oriented graph with undirected graphs.

For n ⩾ 2, let P_{n} denote the path on n vertices whose vertices are labelled as 1, …, n, such that vertex j is adjacent to vertices j −1 and j +1 for j = 2, …, n−1. Next, denote the vertices of complete graph K_{2} by 0 and 1. Let

T L_{n} = NEPS(P_{n}, K_{2}; {(1, 0), (1, 1)}).

Let us form the directed graph \overrightarrow{T L_{n}} from T L_{n} by orienting edges from (j, k) to (j + 1, k) for j = 1, …, n − 1 and k = 0, 1, and from (j, k) to (j − 1, 1 − k) for j = 2, …, n and k = 0, 1, like in Figure 2. We call \overrightarrow{T L_{n}} the twisted ladder.

Figure 2. An example of a twisted ladder.

Theorem 4.1. For n ⩾ 2, Sp[T L_{n}] = 2 ReSp[\overrightarrow{T L_{n}}].

Proof. Let us recall that the eigenvalues of path P_{n} are 2 cos \frac{kπ}{n+1} for k = 1, …, n (see, e.g., [3, Section 2.7]), while Sp[K_{2}] = {1, −1}. Then from Theorem 1, to an arbitrary eigenvalue λ of P_{n} there correspond eigenvalues

λ^{1} · 1^{0} + λ^{1} · 1^{1} = 2λ and λ^{1} · (−1)^{0} + λ^{1} · (−1)^{1} = 0

of T L_{n}. Thus,

Sp[T L_{n}] = \{4 cos \frac{kπ}{n + 1} : k = 1, …, n\} ∪ \{0^{(n)} \}.

Next we show that

(4.1)  Sp[\overrightarrow{T L_{n}}] = \{2 cos \frac{kπ}{n + 1} , 2i cos \frac{kπ}{n + 1} : k = 1, …, n\},

from which equality Sp[T L_{n}] = 2 ReSp[\overrightarrow{T L_{n}}] will immediately follow.

Denote the adjacency matrix A(\overrightarrow{T L_{n}}) simply by A. Let λ = 2 cos \frac{kπ}{n+1} be an arbitrary eigenvalue of the path P_{n} and let x be an eigenvector of P_{n} corresponding to λ. We will use x to form two eigenvectors of \overrightarrow{T L_{n}}, one for eigenvalue λ and the other for eigenvalue iλ. First, recall that x satisfies

λx(1) = x(2),
λx(j) = x(j − 1) + x(j + 1), j = 2, …, n − 1,
λx(n) = x(n − 1).
Now, let x′ be a vector defined on vertices of \overrightarrow{T L_{n}} by
x′(j, 0) = x′(j, 1) = x(j), j = 1, …, n.

Then for j = 2, …, n − 1,

(Ax′)(j, k) = x′(j − 1, 1 − k) + x′(j + 1, k)
= x(j − 1) + x(j + 1)
= λx(j)
= λx′(j, k),

and similarly,

(Ax′)(1, k) = λx′(1, k), (Ax′)(n, k) = λx′(n, k).

Thus, λ is indeed an eigenvalue of \overrightarrow{T L_{n}}.

Next, let x′′be a vector defined on vertices of \overrightarrow{T L_{n}} by

x′′(j, k) = i^{j+2k} x(j),  j = 1, …, n,  k = 0, 1.

Then

(Ax′′)(j, k) = x′′(j − 1, 1 − k) + x′′(j + 1, k)
= i^{j+1−2k} x(j − 1) + i^{j+1+2k} x(j + 1)
= i^{j+1+2k} λx(j)
= iλ i^{j+2k} x(j)
= iλx′′(j, k),

and similarly,

(Ax′′)(1, k) = iλx′′(1, k), (Ax′′)(n, k) = iλx′′(n, k).

Thus, iλ is an eigenvalue of \overrightarrow{T L_{n}} as well, which shows that (4.1) holds. □

5. Concluding remarks

One might argue that no twisted ladders would be considered favourable for chemical applications, since all their directed cycles are still of length four only. Nevertheless, after exhibiting many graphs satisfying (1.2), other than the cycles, we are tempted to think that it is very likely that there exist graphs whose digraph decompositions will satisfy both (1.2) and the needs of potential chemical applications.

References

[1] I. Gutman, P. J. Plath, On molecular graphs and digraphs of annulenes and their spectra, J. Serb. Chem. Soc. 66 (2001), 237–241.

[2] H. Sachs, Publ. Math. (Debrecen) 11 (1964), 119.

[3] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs—Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, 1995.

[4] I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986.

[5] D. Cvetković, Graphs and their spectra (PhD thesis), Univ. Beograd Publ. Elektrotehn. Fak, Ser. Mat. Fiz. 354–356 (1971), 1–50.

[6] M. Petrić, Spectral properties of generalized direct product of graphs (in Serbian), Ph.D. thesis, University of Novi Sad, 1994.

[7] D. Cvetković, M. Petrić, Connectedness of the non-complete extended p-sum of graphs, Zb. Rad. Prir.-Mat. Fak, Univ. Novom Sadu, Ser. Mat. 13 (1983), 345–352.

[8] M. Petrić, On the generalized direct product of graphs, Graph Theory, Proc. 8th Yugosl. Semin., Novi Sad, Yugoslavia, 1987, pp. 99–105.

University of Niš—PMF (Received 12 05 2008) University of Primorska—FAMNIT (Revised 10 03 2009) Niš, Koper Serbia, Slovenia

dragance106@yahoo.com

Faculty of Civil Engineering and Architecture, University of Niš, Niš Serbia

sanja_stevanovic@yahoo.com