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

ESTRADA INDEX OF ITERATED LINE GRAPHS

TATJANA ALEKSIĆ, I. GUTMAN, M. PETROVIĆ

(Presented at the 2nd Meeting, held on March 23, 2007)

A b s t r a c t. If λ_{1}, λ_{2}, …, λ_{n} are the eigenvalues of a graph G, then the Estrada index of G is EE(G) = ∑_{i=1}^{n} e^{λ_{i}} . If L(G) = L^{1}(G) is the line graph

of G, then the iterated line graphs of G are defined as L^{k}(G) = L(L^{k−1}(G)) for k = 2, 3, . . .. Let G be a regular graph of order n and degree r. We show that EE(L^{k}(G)) = a_{k}(r) EE(G) + n b_{k}(r) , where the multipliers a_{k}(r) and b_{k}(r) depend only on the parameters r and k. The main properties of a_{k}(r) and b_{k}(r) are established.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: spectrum (of graph), Estrada index (of graph), regular graph, line graph, complex networks

1. Introduction

Let G be a graph of order n. The eigenvalues of the adjacency matrix of G, denoted by λ_{1}, λ_{2}, …, λ_{n}, are said to be the eigenvalues of G, and they form the spectrum of G [3]. As well known [3], the spectra of graphs have found numerous applications in various fields of science. One of the newest such application was put forward by Ernesto Estrada, who arrived at the conclusion that the graph–spectrum–based graph invariant

EE = EE(G) = ∑_{i=1}^{n} e^{λ_{i}}  (1)

can be used as a measure of the degree of folding of long–chain polymeric molecules, especially those of biological importance [5, 6, 7]. Somewhat later, Estrada and Rodríguez–Velázquez used the same quantity EE to describe certain properties (so-called “centrality”) of complex networks [9, 10]; some most recent results along these lines can be found in [8]. In what follows, EE will be called the Estrada index.

The study of the mathematical properties of the Estrada index started only quite recently [4, 11, 12], and relatively little is known on its dependence on the structure of the underlying graph. In this work we report on the properties of the Estrada index of iterated line graphs of regular graphs.

Let, as usual, L(G) denote the line graph of the graph G. For k = 1, 2, …, the k-th iterated line graph of G is defined as L^{k}(G) = L(L^{k−1}(G)) , where L^{0}(G) = G and L^{1}(G) = L(G) .

If G is a regular graph of degree r = 0 , then L^{k}(G) , k ≥ 1 , are graphs without vertices. In this case, EE(G) = n and EE(L^{k}(G)) = 0 for k ≥ 1 . If G is a regular graph of degree r = 1 , then L(G) consists of isolated vertices, and L^{k}(G) , k ≥ 2 , are graphs without vertices. In this case, EE(G) = (n/2)(e+1/e) , EE(L(G)) = n/2 , and EE(L^{k}(G)) = 0 for k ≥ 2 . If G is a regular graph of degree r = 2 , then L(G) ≅ G and, consequently, L^{k}(G) ≅ G for all k ≥ 1 . In this case, EE(L^{k}(G)) = EE(G) for all k ≥ 1 . Therefore, in order to avoid these trivial cases, in what follows we assume that the degree r of the regular graphs considered is at least three.

The line graph of a regular graph G of order n = n_{0} and of degree r = r_{0} is a regular graph of order n_{1} = nr/2 and of degree r_{1} = 2r − 2 . Consequently, all the iterated line graphs of a regular graph are regular graphs. In particular, the order n_{k} and degree r_{k} of L^{k}(G) , k ≥ 1 , obey the recurrence relations

n_{k} = \frac{1}{2} n_{k−1} r_{k−1} ; r_{k} = 2 r_{k−1} − 2  (2)

from which one directly obtains [1, 2]:

r_{k} = 2^{k} r − 2^{k+1} + 2  (3)

n_{k} = \frac{n}{2^{k}} ∏_{i=0}^{k−1} r_{i} = \frac{n}{2^{k}} ∏_{i=0}^{k−1} (2^{i} r − 2^{i+1} + 2) .  (4)

For the sake of simplicity we define

γ_{k}(r) := \{ \begin{matrix}1 & for k = 0 \\ \frac{1}{2^{k}} ∏_{i=0}^{k−1} (2^{i} r − 2^{i+1} + 2) & for k ≥ 1 \end{matrix}  (5)

and then Eq. (4) can be rewritten as

n_{k} = γ_{k}(r) n .  (6)

Both Eqs. (3) and (6) hold for k ≥ 0 .

According to a classical result of Sachs [13], if λ_{1}, λ_{2}, …, λ_{n} are the eigenvalues of a regular graph G of order n and of degree r, then the eigenvalues of its line graph L(G) are

\begin{matrix}λ_{i} + r − 2 & i = 1, 2, …, n & and \\ −2 & n(r − 2)/2 times . \end{matrix} \}  (7)

Combining formulas (1) and (7) one immediately arrives at

Lemma 1. If G is a regular graph of order n and degree r ≥ 3 , then the Estrada indices of G and L(G) are related as

EE(L(G)) = e^{r−2} EE(G) + \frac{r − 2}{2 e^{2}} n .  (8)

Lemma 2. If G = L^{0}(G) is a regular graph of order n = n_{0} and degree r = r_{0} ≥ 3 , then for k ≥ 0 , the Estrada indices of L^{k}(G) and L^{k+1}(G) are related as

EE(L^{k+1}(G)) = e^{r_{k}−2} EE(L^{k}(G)) + \frac{r_{k} − 2}{2 e^{2}} n_{k} .  (9)

Evidently, for k = 0 , Eq. (9) reduces to Eq. (8). It should be noted that Eqs. (8) and (9) hold also in the cases r = 0, 1, 2 .

By a two-fold application of Lemma 2 we get

EE(L^{2}(G)) = e^{r_{1}−2} EE(L^{1}(G)) + \frac{r_{1} − 2}{2 e^{2}} n_{1}

= e^{r_{1}−2} [e^{r_{0}−2} EE(L^{0}(G)) + \frac{r_{0} − 2}{2 e^{2}} n_{0}] + \frac{r_{1} − 2}{2 e^{2}} n_{1} ,

i.e.,

EE(L^{2}(G)) = e^{r_{1}−2} e^{r_{0}−2} EE(L^{0}(G)) + e^{r_{1}−2} \frac{r_{0} − 2}{2 e^{2}} n_{0} + \frac{r_{1} − 2}{2 e^{2}} n_{1} . (10)

In a similar manner,

EE(L^{3}(G)) = e^{r_{2}−2} e^{r_{1}−2} e^{r_{0}−2} EE(L^{0}(G)) + e^{r_{2}−2} e^{r_{1}−2} \frac{r_{0} − 2}{2 e^{2}} n_{0}

+ e^{r_{2}−2} \frac{r_{1} − 2}{2 e^{2}} n_{1} + \frac{r_{2} − 2}{2 e^{2}} n_{2}  (11)

EE(L^{4}(G)) = e^{r_{3}−1} e^{r_{2}−2} e^{r_{1}−2} e^{r_{0}−2} EE(L^{0}(G)) + e^{r_{3}−2} e^{r_{2}−2} e^{r_{1}−2} \frac{r_{0} − 2}{2 e^{2}} n_{0}

+ e^{r_{3}−2} e^{r_{2}−2} \frac{r_{1} − 2}{2 e^{2}} n_{1} + e^{r_{3}−2} \frac{r_{2} − 2}{2 e^{2}} n_{2} + \frac{r_{3} − 2}{2 e^{2}} n_{3} .  (12)

It is not difficult to see that Eqs. (10)–(12) are special cases of the formula:

EE(L^{k+1}(G)) = (∏_{i=0}^{k} e^{r_{i}−2}) EE(G)+∑_{p=0}^{k−1} ( ∏_{i=p+1}^{k} e^{r_{i}−2}) \frac{r_{p} − 2}{2 e^{2}} n_{p}+\frac{r_{k} − 2}{2 e^{2}} n_{k} .

(13)

2. The Main Result

According to Eq. (3), the terms r_{0}, r_{1}, …, r_{k} in the expression

∏_{i=0}^{k} e^{r_{i}−2}  (14)

occurring on the right–hand side of (13) are fully determined by the degree r of the graph G. Thus, (14) depends solely on r and k.

According to Eqs. (4) and (6), the terms n_{0}, n_{1}, …, n_{k} in the expression

∑_{p=0}^{k−1} ( ∏_{i=p+1}^{k} e^{r_{i}−2}) \frac{r_{p} − 2}{2 e^{2}} n_{p} + \frac{r_{k} − 2}{2 e^{2}} n_{k}  (15)

occurring on the right–hand side of (13) are fully determined by the order n and degree r of the graph G and are, in addition, linearly proportional to the parameter n. Consequently, (15) depends solely on n, r, and k, and is linearly proportional to n.

Bearing the above in mind we arrive at:

Theorem 3. The Estrada index of a regular graph G of order n and degree r ≥ 3 , and of its iterated line graphs are related in the following manner

EE(L^{k}(G)) = a_{k}(r) EE(G) + b_{k}(r) n

where a_{k}(r) and b_{k}(r) are functions depending solely on the variable r and parameter k , k ≥ 1 .

3. On the Functions a_{k}(r) and b_{k}(r)

From (8) we immediately see that

a_{1}(r) = e^{r−2}
b_{1}(r) = \frac{r − 2}{2 e^{2}} .

Using the relations (2), from (10) we obtain

a_{2}(r) = e^{3(r−2)}
b_{2}(r) = \frac{r − 2}{2 e^{2}} [e^{2(r−2)} + r] .

Analogously, from (11) there follows

a_{3}(r) = e^{7(r−2)}
b_{3}(r) = \frac{r − 2}{2 e^{2}} [e^{6(r−2)} + r e^{4(r−2)} + 2r(r − 1)] .

Using the relation (3), the general form of the function a_{k}(r) is easy to find. For k ≥ 1 , from (14),

a_{k}(r) = ∏_{i=0}^{k−1} e^{r_{i}−2} = ∏_{i=0}^{k−1} e^{(2^{i} r−2^{i+1}+2)−2} = ∏_{i=0}^{k−1} e^{(r−2) 2^{i}} = e^{∑_{i=0}^{k−1}(r−2) 2^{i}} ,

which finally yields

a_{k}(r) = e^{(r−2)(2^{k}−1)} .  (16)

The function b_{k}(r) cannot be transformed into a similarly simple form. For k = 1, 2, 3 , expressions for b_{k}(r) are given above. Therefore, in what follows we assume that k ≥ 4 . By combining (6) and (15) we get

b_{k}(r) = ∑_{p=0}^{k−2} ( ∏_{i=p+1}^{k−1} e^{r_{i}−2}) \frac{r_{p} − 2}{2 e^{2}} γ_{p} + \frac{r_{k−1} − 2}{2 e^{2}} γ_{k−1} ,

which after a lengthy calculation, taking into account (5), becomes

b_{k}(r) = \frac{r − 2}{2 e^{2}} e^{(r−2) 2^{k}} ×

× [e^{−2(r−2)} + r e^{−4(r−2)} + ∑_{p=2}^{k−2} r e^{−(r−2)2^{p+1}} 2^{p−1} ∏_{i=1}^{p−1} (2^{i−1} r − 2^{i} + 1)]

+ \frac{r(r − 2)}{8 e^{2}} 2^{k} ∏_{i=1}^{k−2} (2^{i−1} r − 2^{i} + 1) .

Both a_{k}(r) and b_{k}(r) are rapidly increasing functions of both r and k. From Eq. (16) it is immediately seen that for k → ∞,

a_{k}(r) = O (e^{(r−2) 2^{k}})

i.e., that for all values of r , 0 < r < ∞,

0 < lim_{k→∞} \frac{a_{k}(r)}{e^{(r−2) 2^{k}}} < ∞ .

We now show that the asymptotic behavior of the function b_{k}(r) is analogous, namely that

b_{k}(r) = O (e^{(r−2) 2^{k}}) .  (17)

In view of Eq. (4), the term [(r_{k} − 2)/(2 e^{2})] n_{k}, occurring in Eq. (9), can be written as K d_{k}, where

K = \frac{1}{4} nr(r − 2) e^{−2} = const

and

d_{k} := 2^{k} ∏_{i=1}^{k−1} [2^{i−1} (r − 2) + 1] .  (18)

Estrada index of iterated line graphs 39

Then

EE(L^{k+1}(G)) = e^{r_{k}−2} e^{r_{k−1}−2} ⋯ e^{r_{2}−2} EE(L^{2}(G)) + c_{k} ,

where

c_{k} := K ∑_{p=3}^{k} e^{r_{k}−2} ⋯ e^{r_{p}−2} d_{p−1} + K d_{k}
= K e^{(r−2) 2^{k+1}} ∑_{p=3}^{k} e^{−(r−2) 2^{p}} 2^{p−1} ∏_{i=1}^{p−2} [2^{i−1} (r − 2) + 1] + K d_{k} .

The sequence {f_{k}}, defined via

f_{k} := ∑_{p=3}^{k} e^{−(r−2) 2^{p}} 2^{p−1} ∏_{i=1}^{p−2} [2^{i−1} (r − 2) + 1]

is bounded from above. To see this note that for r > 2 and i ≥ 1 ,

(r − 2) 2^{i−1} + 1 ≤ (r − 2) 2^{i−1} + (r − 2) 2^{i−1} = (r − 2) 2^{i}

from which

∏_{i=1}^{p−2} [(r − 2) 2^{i−1} + 1] ≤ ∏_{i=1}^{p−2}(r − 2) 2^{i} = (r − 2)^{p−2} 2^{1+2+···+(p−2)}
= (r − 2)^{p−2} 2^{(p−1)(p−2)/2}

from which

f_{k} = ∑_{p=3}^{k} e^{−(r−2) 2^{p}} 2^{p−1} ∏_{i=1}^{p−2} [2^{i−1} (r − 2) + 1]
leq ∑_{p=3}^{k} e^{−(r−2) 2^{p}} 2^{p−1} (r − 2)^{p−2} 2^{(p−1)(p−2)/2}
= ∑_{p=3}^{k} \frac{(r − 2)^{p−2} 2^{p(p−1)/2}}{e^{(r−2) 2^{p}}} < ∑_{p=3}^{+∞} \frac{(r − 2)^{p−2} 2^{p(p−1)/2}}{e^{(r−2) 2^{p}}} .

The latter series converges by D’Alembert’s criterion. Indeed, let

g_{p} := \frac{(r − 2)^{p−2} 2^{p(p−1)/2}}{e^{(r−2) 2^{p}}} .

Then the quotient

\frac{g_{p+1}}{g_{p}} = \frac{(r − 2) 2^{p}}{e^{(r−2) 2^{p}}}

evidently tends to zero for p → ∞.

Since the series {g_{p}} converges, the sequence {f_{k}} is bounded. Therefore, for k → ∞,

c_{k} − K d_{k} = K e^{(r−2) 2^{k+1}} f_{k} = O (e^{(r−2) 2^{k+1}}) .

Using the above specified notation,

b_{k+1}(r) = h_{k} + K e^{(r−2) 2^{k+1}} f_{k} + K d_{k}  (19)

where

h_{k} := e^{(r−2)(2^{k+1}−4)} [\frac{r − 2}{2 e^{2}} e^{2(r−2)} + \frac{r(r − 2)}{2 e^{2}}] .

For k → ∞,

h_{k} = O (e^{(r−2) 2^{k+1}})

and, consequently,

h_{k} + K e^{(r−2) 2^{k+1}} f_{k} = O (e^{(r−2) 2^{k+1}}) .  (20)

Let p be the smallest integer for which r − 2 ≤ 2^{p} holds. Then from (18) there follows

d_{k} < 2^{k} ∏_{i=1}^{k−1} [2^{i} (r − 2)] ≤ 2^{k} ∏_{i=1}^{k−1} [2^{i} 2^{p}] = 2^{p(k−1)+k(k+1)/2}

for r > 2 , which implies

lim_{k→∞} \frac{d_{k}}{e^{(r−2) 2^{k+1}}} = 0 .

Therefore, for k → ∞,

d_{k} = o (e^{(r−2) 2^{k+1}}) ⇒ d_{k} = O (e^{(r−2) 2^{k+1}}) .  (21)

The property (17) of the function b_{k}(r) follows now when the relations (20) and (21) are combined with (19).

Acknowledgement. This work was also supported by the Serbian Ministry of Science and Environmental Protection, through Grant no. 144015G.

REFERENCES

[1] F. B u c k l e y, Iterated line graphs, Congr. Numer. 33 (1981) 390–394.

[2] F. B u c k l e y, The size of iterated line graphs, Graph Theory Notes New York 25 (1993) 33–36.

[3] 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, Academic Press, New York, 1980; 2nd revised ed.: Barth, Heidelberg, 1995.

[4] J. A. d e l a P e ñ a, I. G u t m a n, J. R a d a, Estimating the Estrada index, Lin. Algebra Appl. 427 (2007), 70–76.

[5] E. E s t r a d a, Characterization of 3D molecular structure, Chem. Phys. Lett. 319 (2000) 713–718.

[6] E. E s t r a d a, Characterization of the folding degree of proteins, Bioinformatics 18 (2002) 697–704.

[7] E. E s t r a d a, Characterization of the amino acid contribution to the folding degree of proteins, Proteins 54 (2004) 727–737.

[8] E. E s t r a d a, Topological structural classes of complex networks, Phys. Rev. E 75 (2007) 016103–1–12.

[9] E. E s t r a d a, J. A. R o d r í g u e z – Ve l á z q u e z, Subgraph centrality in complex networks, Phys. Rev. E 71 (2005) 056103–1–9.

[10] E. E s t r a d a, J. A. R o d r í g u e z – V e l á z q u e z, Spectral measures of bipartivity in complex networks, Phys. Rev. E 72 (2005) 046105–1–6.

[11] I. G u t m a n, Lower bounds for Estrada index, Publ. Inst. Math. (Beograd), in press [12] I. G u t m a n, A. G r a o v a c, Estrada index of cycles and paths, Chem. Phys.

Lett. 436 (2007), 294–296.

[13] H. S a c h s, Über Teiler, Faktoren und charakteristische Polynome von Graphen. Teil II , Wiss. Z. TH Ilmenau 13 (1967) 405–412.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia

taleksic@kg.ac.yu
gutman@kg.ac.yu
petrovic@kg.ac.yu