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

DISTANCE SPECTRA AND DISTANCE ENERGIES OF ITERATED LINE GRAPHS OF REGULAR GRAPHS

H. S. Ramane, D. S. Revankar, I. Gutman, and H. B. Walikar

Communicated by Slobodan Simić

Abstract. The distance or D-eigenvalues of a graph G are the eigenvalues of its distance matrix. The distance or D-energy E_{D} (G) of the graph G is the sum of the absolute values of its D-eigenvalues. Two graphs G_{1} and G_{2} are said to be D-equienergetic if E_{D} (G_{1}) = E_{D} (G_{2}). Let F_{1} be the 5-vertex path, F_{2} the graph obtained by identifying one vertex of a triangle with one end vertex of the 3-vertex path, F_{3} the graph obtained by identifying a vertex of a triangle with a vertex of another triangle and F_{4} be the graph obtained by identifying one end vertex of a 4-vertex star with a middle vertex of a 3-vertex path. In this paper we show that if G is r-regular, with diam(G) ⩽ 2, and F_{i}, i = 1, 2, 3, 4, are not induced subgraphs of G, then the k-th iterated line graph L^{k}(G) has exactly one positive D-eigenvalue. Further, if G is r-regular, of order n, diam(G) ⩽ 2, and G does not have F_{i}, i = 1, 2, 3, 4, as an induced subgraph, then for k ⩾ 1, E_{D} (L^{k}(G)) depends solely on n and r. This result leads to the construction of non D-cospectral, D-equienergetic graphs having same number of vertices and same number of edges.

1. Introduction

Let G be a simple, undirected graph without loops and multiple edges. Let n be the number of vertices and m the number of edges of G. The vertices of G are labelled as v_{1}, v_{2}, …, v_{n}. The distance between the vertices v_{i} and v_{j} is the length of a shortest path between them, and is denoted by d(v_{i}, v_{j}). The diameter of G, denoted by diam(G), is the maximum distance between any pair of vertices of G [6, 15].

The adjacency matrix of a graph G is the square matrix A = A(G) = [a_{ij} ], in which a_{ij} = 1 if v_{i} is adjacent to v_{j} and a_{ij} = 0, otherwise. The eigenvalues of the adjacency matrix A(G) are the (adjacency or ordinary) eigenvalues of G, forming the (adjacency or ordinary) spectrum of G [8]. These will be labelled as λ_{1} ⩾ λ_{2} ⩾ ⋯⩾ λ_{n}.

2000 Mathematics Subject Classification: Primary 05C12, 05C50.

The distance matrix of a graph G is the square matrix D = D(G) = [d_{ij} ], in which d_{ij} is the distance between the vertices v_{i} and v_{j} in G. The eigenvalues of the distance matrix D(G), labelled as μ_{1} ⩾ μ_{2} ⩾ ⋯⩾ μ_{n}, are said to be the distance or D-eigenvalues of G and to form the distance or D-spectrum of G [6, 7].

Two connected graphs G and H are said to be D-cospectral if they have same D-spectra. The characteristic polynomial and eigenvalues of the distance matrix of graphs have been considered in [9, 10, 11, 16, 17, 18, 19, 34].

The distance or D-energy of a connected graph G is defined as

(1)  E_{D} = E_{D}(G) = ∑_{i=1}^{n} |μ_{i}| .

The D-energy was first time introduced by Indulal et al. [19], and was conceived in full analogy with the ordinary graph energy E(G), defined as [12, 13, 14]

(2)  E = E(G) = ∑_{i=1}^{n} |λ_{i}| .

Various bounds for the D-energy have been communicated in [19, 27].

Two graphs G_{1} and G_{2} are said to be equienergetic if E(G_{1}) = E(G_{2}). A large number of constructions of non-cospectral, equienergetic graphs was recently reported [1, 2, 3, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33].

Two graphs G_{1} and G_{2} are said to be D-equienergetic if E_{D}(G_{1}) = E_{D}(G_{2}). Of course D-cospectral graphs are D-equienergetic. We are interested in non Dcospectral, D-equienergetic graphs having same number of vertices. Recently Indulal et al. [19] constructed pairs of D-equienergetic graphs on n vertices for n ≡ 1 (mod 3) and n ≡ 0 (mod 6). In this paper we give one more class of D-equienergetic graphs.

We need the following results.

Theorem 1. [8] If G is an r-regular graph, then its maximum adjacency eigenvalue is equal to r.

Theorem 2. [7, 19] Let G be an r-regular graph of order n and diam(G)⩽2. If r, λ_{2}, …, λ_{n} are the adjacency eigenvalues of G, then its D-eigenvalues are 2n−r−2 and −(λ_{i} + 2), i = 2, 3, …, n.

2. On the line graph of a regular graph

The line graph of G will be denoted by L(G) [15]. For k = 1, 2, …, the k-th iterated line graph of G is L^{k}(G) = L(L^{k−1} (G)), where L^{0}(G) = G and L^{1}(G) = L(G).

The line graph of a regular graph is a regular graph. In particular, the line graph of a regular graph G of order n_{0} and of degree r_{0} is a regular graph of order n_{1} = (r_{0}n_{0})/2 and of degree r_{1} = 2r_{0} − 2. Consequently, the order and degree of L^{k}(G) are [4, 5]:

n_{k} = \frac{1}{2} r_{k−1} n_{k−1} and r_{k} = 2r_{k−1} − 2

where n_{i} and r_{i} stand for the order and degree of L^{i}(G) , i = 1, 2, . . .. Therefore,

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

and

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

Theorem 3. [31] If λ_{1}, λ_{2}, …, λ_{n} are the adjacency eigenvalues of a regular graph G of order n and of degree r, then the adjacency eigenvalues of L(G) are

λ_{i} + r − 2, i = 1, 2, …, n,  and
−2, n(r − 2)/2 times.

For any set S of vertices (edges) of G, the induced subgraph < S > is the maximal subgraph of G with vertex set (edge set) S.

Let F_{1} be the 5-vertex path, F_{2} the graph obtained by identifying a vertex of a triangle with one end vertex of the 3-vertex path, F_{3} the graph obtained by identifying a vertex of a triangle with a vertex of another triangle and F_{4} be the graph obtained by identifying one end vertex of a 4-vertex star with a middle vertex of a 3-vertex path, see Fig. 1.

Figure 1. The forbidden subgraphs.

Theorem 4. If diam(G) ⩽ 2 and if none of the three graphs F_{1}, F_{2} and F_{3} of Fig. 1 is an induced subgraph of G, then diam(L(G)) ⩽ 2.

Proof. The results can be easily verified for n ⩽ 4. We thus assume that n > 4.

Let e_{1}, e_{2}, …, e_{m} be the edges of a graph G. These are the vertices of L(G). If the edges e_{i} and e_{j} are adjacent in G, then the vertices e_{i} and e_{j} are adjacent in L(G). Therefore the distance between e_{i} and e_{j} in L(G) is 1.

If the edges e_{i} and e_{j} are not adjacent in G, then we consider two cases. Case 1: Suppose diam(G) = 1. Then G ≅ K_{n} a complete graph on n vertices.

In K_{n}, if the edges e_{i} and e_{j} are not adjacent then, because every vertex of K_{n} is adjacent to the remaining vertices, there exists an edge e_{k} in K_{n} adjacent to both e_{i} and e_{j}. Therefore in L(K_{n}), d(e_{i}, e_{j}) = d(e_{i}, e_{k}) + d(e_{k}, e_{j}) = 1 + 1 = 2. Hence diam(L(G)) = 2, for all n ⩾ 4.

Case 2: Suppose diam(G) = 2. Consider the conditions under which L(G) will have diameter greater than 2. For this G must possess two independent edges say e_{i} = (uv) (connecting the vertices u and v) and e_{j} = (xy) (connecting the vertices x and y), such that neither u nor v are adjacent to either x or y. If so, then because G has diameter 2, there must exist a vertex w adjacent to u and x. If w is not adjacent to either v or y, then G has F_{1} as induced subgraph (spanned by the vertices u, v, x, y and w). If w is adjacent to v, but not to y (or, what is the same, adjacent to y but not to v), then G has F_{2} as induced subgraph. If w is adjacent to both v and y, then G has F_{3} as induced subgraph. Hence, if none of F_{i} i = 1, 2, 3, is an induced subgraph of G, then diam(L(G)) ⩽ 2. □

Theorem 5. If diam(G) ⩽ 2 and if none of the four graphs of Fig. 1 is an induced subgraph of G, then none of the four graphs of Fig. 1 is an induced subgraph of L(G).

Proof. If diam(G) ⩽ 2 and none of the four graphs of Fig. 1 is an induced subgraph of G, then any 5-edge subset of the edges of G induces one of the graphs depicted in Fig. 2.

None of the line graphs of graphs depicted in Fig. 2 has F_{i}, i = 1, 2, 3, 4, as an induced subgraph. Hence the proof. □

Combining Theorems 4 and 5 we have following Theorem.

Theorem 6. If diam(G) ⩽ 2 and if none of the four graphs of Fig. 1 is an induced subgraph of G, then for k ⩾ 1,

(i) diam(L^{k}(G)) ⩽ 2 and (ii) none of the four graphs of Fig. 1 is an induced subgraph of L^{k}(G).

Theorem 7. If G is an r-regular graph of order n with diam(G) ⩽ 2 and if none of the three graphs F_{1}, F_{2} and F_{3} of Fig. 1 is an induced subgraph of G, then L(G) has exactly one positive D-eigenvalue, equal to nr − 2r.

Proof. Let r, λ_{2}, λ_{3}, …, λ_{n} be the adjacency eigenvalues of a regular graph G. Then from Theorem 3, the adjacency eigenvalues of of L(G) are

(5)

λ_{i} + r − 2, i = 1, 2, …, n,  and
−2, n(r − 2)/2 times

The graph G is regular of degree r and has order n. Therefore L(G) is a regular graph on nr/2 vertices and of degree 2r − 2. As diam(G) ⩽ 2 and none of the three

Figure 2. 5-edge graphs.

graphs F_{1}, F_{2} and F_{3} of Fig. 1 is an induced subgraph of G, from Theorem 4, diam(L(G)) ⩽ 2. Therefore from Theorem 2 and Eq. (5), the D-eigenvalues of L(G) are

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

All eigenvalues of a regular graph of degree r satisfy the condition −r ⩽ λ_{i} ⩽ r [8]. Therefore λ_{i} + r ⩾ 0, i = 1, 2, …, n. The theorem follows from Eq. (6). □

Corollary 7.1. Let G be an r-regular graph on n vertices with diam(G) ⩽ 2 and let none of the four graphs of Fig. 1 be an induced subgraph of G. Let n_{k} and r_{k} be the order and degree, respectively, of the k-th iterated line graph L^{k}(G) of G, k ⩾ 1. Then L^{k}(G) has exactly one positive D-eigenvalue equal to

n_{k−1} r_{k−1} − 2r_{k−1} = 2n_{k} − r_{k} − 2 = 2n ∏_{i=0}^{k−1} [2^{i−1} r − 2^{i} + 1] − [2^{k}r − 2^{k+1} + 4].

3. Distance energy

The D-energy E_{D}(G) of a graph G is defined via Eq. (1).

Theorem 8. If G is an r-regular graph of order n with diam(G) ⩽ 2 and if none of the three graphs F_{1}, F_{2} and F_{3} of Fig. 1 is an induced subgraph of G, then E_{D}(L(G)) = 2nr − 4r.

Proof. Bearing in mind Theorem 7 and Eq. (6), the D-energy of L(G) is computed as:

E_{D}(L(G)) = nr − 2r + ∑_{i=2}^{n} (λ_{i} + r) + |0| × \frac{n(r − 2)}{2} = 2nr − 4r

since ∑_{i=2}^{n} λ_{i} = −r. □

Corollary 8.1. Let G be an r_{0}-regular graph of order n_{0} with diam(G) ⩽ 2 and let none of the four graphs of Fig. 1 be an induced subgraph of G. Let n_{k} and r_{k} be the order and degree, respectively, of the k-th iterated line graph L^{k}(G) of G, k ⩾ 1. Then

E_{D}(L^{k}(G)) = 2n_{k−1} r_{k−1} − 4r_{k−1} = 4n_{k} − 2r_{k} − 4.

Corollary 8.2. Under the same conditions as in the previous corollary,

E_{D}(L^{k}(G)) = 4n_{0} ∏_{i=0}^{k−1} (2^{i−1} r_{0} − 2^{i} + 1) − 2(2^{k}r_{0} − 2^{k+1} + 4).

From Corollary 8.2 we see that the D-energy of the k-th iterated line graph of a regular graph G of diameter less than or equal to 2, that does not contain F_{i}, i = 1, 2, 3, 4, as an induced subgraph is fully determined by the order n_{0} and degree r_{0} of G.

4. Distance-equienergetic graphs

Lemma 9. Let G_{1} and G_{2} be two regular graphs of the same order and of the same degree. Let diam(G_{i}) ⩽ 2, and none of the four graphs of Fig. 1 be an induced subgraph of G_{i}, i = 1, 2. Then for any k ⩾ 1 the following holds:

(i) L^{k}(G_{1}) and L^{k}(G_{2}) are of the same order, same degree and have the same number of edges.

(ii) L^{k}(G_{1}) and L^{k}(G_{2}) are D-cospectral if and only if G_{1} and G_{2} are cospectral.

Proof. Statement (i) follows from Eqs. (3) and (4), and the fact that the number of edges of L^{k}(G) is equal to the number of vertices of L^{k+1} (G). Statement (ii) follows from Eqs. (5) and (6), and Theorem 6. □

Theorem 10. Let G_{1} and G_{2} be two non D-cospectral regular graphs of the same order and of the same degree. Let diam(G_{i}) ⩽ 2 and let none of the four graphs of Fig. 1 be an induced subgraphs of G_{i}, i = 1, 2. Then for any k ⩾ 1, the iterated line graphs L^{k}(G_{1}) and L^{k}(G_{2}) form a pair of non D-cospectral, Dequienergetic graphs of equal order and of equal number of edges.

Proof. follows from Lemma 9 and Corollary 8.2. □

Acknowledgement. The authors are thankful to referee for suggestions, especially for improving the proof of Theorem 5. One author (H. S. R.) thanks the Visvesvaraya Technological University, India, for support through Research Grants Scheme (No. VTU/Aca–RGS/2008–2009/7198). Another author (I. G.) thanks the support by the Serbian Ministry of Science, through Grant no. 144015G, and Project “Graph Theory and Mathematical Programming with Applications to Chemistry and Engineering”.

References

[1] R. Balakrishnan, The energy of a graph, Lin. Algebra Appl. 387 (2004), 287–295.

[2] A. S. Bonifácio, C. T. M. Vinagre, N. M. M. de Abreu, Constructing pairs of equienergetic and non-cospectral graphs, Appl. Math. Lett. 21 (2008), 338–341.

[3] V. Brankov, D. Stevanović, I. Gutman, Equienergetic chemical trees, J. Serb. Chem. Soc. 69 (2004), 549–553.

[4] F. Buckley, Iterated line graphs, Congr. Numer. 33 (1981), 390–394.

[5] F. Buckley, The size of iterated line graphs, Graph Theory Notes New York 25 (1993), 33–36.

[6] F. Buckley, F. Harary, Distance in Graphs, Addison–Wesley, Redwood, 1990.

[7] D. M. Cvetković, M. Doob, I. Gutman, A. Torgašev, Recent Results in the Theory of Graph Spectra, North–Holland, Amsterdam, 1988.

[8] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Application, third ed., Johann Ambrosius Barth Verlag, Heidelberg, 1995.

[9] M. Edelberg, M. R. Garey, R. L. Graham, On the distance matrix of a tree, Discr. Math. 14 (1976), 23–39.

[10] R. L. Graham, L. Lovász, Distance matrix polynomial of trees, Adv. Math. 29 (1978), 60–88.

[11] R. L. Graham, H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495–2519.

[12] I. Gutman, The energy of a graph, Ber. Math. Stat. Sekt. Forschungsz. Graz 103 (1978), 1–22.

[13] I. Gutman, The energy of a graph: Old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer–Verlag, Berlin, 2001, pp. 196–211.

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

[15] F. Harary, Graph Theory, Addison–Wesley, Reading, 1969.

[16] A. J. Hoffman, M. H. McAndrew, The polynomial of a directed graph, Proc. Amer. Math. Soc. 16 (1965), 303–309.

[17] H. Hosoya, M. Murakami, M. Gotoh, Distance polynomial and characterization of a graph, Nat. Sci. Rept. Ochanumizu Univ. 24 (1973), 27–34.

[18] G. Indulal, I. Gutman, On the distance spectra of some graphs, Math. Commun. 13 (2008), 123–131.

[19] G. Indulal, I. Gutman, A. Vijaykumar, On the distance energy of a graph, MATCH Commun. Math. Comput. Chem. 60 (2008), 461–472.

[20] G. Indulal, A. Vijaykumar, On a pair of equienergetic graphs, MATCH Commun. Math. Comput. Chem. 55 (2006), 83–90.

[21] G. Indulal, A. Vijaykumar, A note on the energy of some graphs, MATCH Commun. Math. Comput. Chem. 59 (2008), 269–274.

[22] G. Indulal, A. Vijaykumar, Equienergetic self-complementary graphs, Czechoslovak Math. J. 58 (2008), 451–461.

[23] J. Liu, B. Liu, Note on a pair of equienergetic graphs, MATCH Commun. Math. Comput. Chem. 59 (2008), 275–278.

[24] W. López, J. Rada, Equienergetic digraphs, Int. J. Pure Appl. Math. 36 (2007), 361–372.

[25] O. Miljković, B. Furtula, S. Radenković, I. Gutman, Equienergetic and almost–equienergetic trees, MATCH Commun. Math. Comput. Chem. 61 (2009), 451–461.

[26] H. S. Ramane, I. Gutman, H. B. Walikar, S. B. Halkarni, Equienergetic complement graphs, Kragujevac J. Sci. 27 (2005), 67–74.

[27] H. S. Ramane, D. S. Revankar, I. Gutman, S. B. Rao, B. D. Acharya, H. B. Walikar, Bounds for the distance energy of a graph, Kragujevac J. Math. 31 (2009), 59–68.

[28] H. S. Ramane, H. B. Walikar, Construction of equienergetic graphs, MATCH Commun. Math. Comput. Chem. 57 (2007), 203–210.

[29] H. S. Ramane, H. B. Walikar, S. B. Rao, B. D. Acharya, P. R. Hampiholi, S. R. Jog, I. Gutman, Equienergetic graphs, Kragujevac J. Math. 26 (2004), 5–13.

[30] H. S. Ramane, H. B. Walikar, S. B. Rao, B. D. Acharya, P. R. Hampiholi, S. R. Jog, I. Gutman, Spectra and energies of iterated line graphs of regular graphs, Appl. Math. Lett. 18 (2005), 679–682.

[31] H. Sachs, Über Teiler, Faktoren und charakteristische Polynome von Graphen, Teil II, Wiss. Z. TH Ilmenau 13 (1967), 405–412.

[32] D. Stevanović, Energy and NEPS of graphs, Lin. Multilin. Algebra 53 (2005), 67–74.

[33] H. B. Walikar, H. S. Ramane, I. Gutman, S. B. Halkarni, On equienergetic graphs and molecular graphs, Kragujevac J. Sci. 29 (2007), 73–84.

[34] B. Zhou, On the largest eigenvalue of the distance matrix of a tree, MATCH Commun. Math. Comput. Chem. 58 (2007), 657–662.

Harishchandra S. Ramane, Deepak S. Revankar (Received 20 12 2007) Department of Mathematics (Revised 21 06 2008) Gogte Institute of Technology Udyambag, Belgaum – 590008 India

hsramane@yahoo.com
revankards@rediffmail.com

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

gutman@kg.ac.rs

Hanumappa B. Walikar Department of Computer Science Karnatak University Dharwad – 580003 India

walikarhb@yahoo.co.in