Electronic Journal of Graph Theory and Applications

Harishchandra S. Ramane, Ashwini S. Yalnaik

Department of Mathematics, Karnatak University, Dharwad - 580003, India

hsramane@yahoo.com, ashwiniynaik@gmail.com

The reciprocal complementary distance (RCD) matrix of a graph G is defined as \(RCD(G) = [rc_{ij}]\) where \(rc_{ij} = \frac{1}{1+D-d_{ij}}\) if \(i \neq j\) and \(rc_{ij} = 0\), otherwise, where D is the diameter of G and \(d_{ij}\) is the distance between the vertices \(v_i\) and \(v_j\) in G. The RCD-energy of G is defined as the sum of the absolute values of the eigenvalues of RCD(G). Two graphs are said to be RCD-equienergetic if they have same RCD-energy. In this paper we show that the line graph of certain regular graphs has exactly one positive RCD-eigenvalue. Further we show that RCD-energy of line graph of these regular graphs is solely depends on the order and regularity of G. This results enables to construct pairs of RCD-equienergetic graphs of same order and having different RCD-eigenvalues.

Keywords: Reciprocal complementary distance eigenvalues, adjacency eigenvalues, line graphs, reciprocal complementary distance energy

Mathematics Subject Classification: 05C50, 05C12

DOI: 10.5614/ejgta.2015.3.2.10

1. Introduction

Molecular matrices, encoding in various ways the topological infromation, are an important source of structural descriptors for quantitative structure property relationships (QSPR) and quantitative structure activity relationships (QSAR) models [6]. A large number of molecular matrices

Received: 01 June 2015, Revised: 08 September 2015, Accepted: 13 October 2015.

were defined in the chemical literature. One of these is reciprocal complementary distance (RCD) matrix.

Let G be a simple, undirected, connected graph with n vertices and m edges. Let the vertices of G be labeled as v1, v2, . . . , vⁿ . The adjacency matrix of a graph G is the square matrix A = A(G) = [aij ] , in which aij = 1 if vⁱ is adjacent to v^j and aij = 0 , otherwise. The eigenvalues of the adjacency matrix A(G) are the adjacency eigenvalues of G , and these will be labeled as λ¹ ≥ λ² ≥ · · · ≥ λⁿ and their collection is called as a adjacency spectra of G [3].

The distance between the vertices vⁱ and v^j , denoted by dij , is the length of the shortest path between them. The diameter of a graph G, denoted by diam(G), is the maximum distance between any pair of vertices of G. A graph G is said to be r-regular graph if all of its vertices have same degree equal to r.

The reciprocal complementary distance between the vertices vⁱ and v^j , denoted by rcij is defined as rcij = 1 1+D−dij , where D is the diameter of G and dij is the distance between vⁱ and v^j in G.

The reciprocal complementary distance matrix [6, 7] of a graph G is an n × n real symmetric matrix RCD(G) = [rcij ], where

\[rc_{ij} = \begin{cases} \frac{1}{1+D-d_{ij}}, & \text{if } i \neq j \\ 0, & \text{otherwise.} \end{cases}\]

The eigenvalues of RCD(G) labeled as µ¹ ≥ µ² ≥ · · · ≥ µⁿ are said to be the RCDeigenvalues of G and their collection is called RCD-spectra of G. Two non-isomorphic graphs are said to be RCD-cospectral if they have same RCD-spectra.

The reciprocal complementary distance energy (RCD-energy) of a graph G is defined as

\[RCDE(G) = \sum_{i=1}^{n} |\mu_i|.\] (1)

The Eq. (1) is defined in full analogy with the ordinary graph energy E(G), defined as [4]

\[E(G) = \sum_{i=1}^{n} |\lambda_i|.\] (2)

Two graphs G¹ and G² are said to be equienergetic if E(G1) = E(G2) [1, 2, 8, 11, 12, 16]. For more details on E(G) one can refer [8].

Two connected graphs G¹ and G² are said to be reciprocal complementary distance equienergetic or RCD-equienergetic if RCDE(G1) = RCDE(G2). Of course, RCD-cospectral graphs are RCD-equienergetic. In this paper we obtain the RCD-eigenvalues and RCD-energy of line

graphs of certain regular graphs. Further we show that the RCD-energy of line graphs of certain regular graphs is solely depends on the order and regularity of a graph. Thus infinitely many pairs of RCD-equienergetic graphs can be constructed such that they have equal number of vertices, equal number of edges and are non RCD-cospectral.

We need following results.

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

Theorem 1.2. [13] Let G be an r-regular graph of order n. If \(r, \lambda_2, \ldots, \lambda_n\) are the adjacency eigenvalues of G, then the adjacency eigenvalues of \(\overline{G}\), the complement of G, are n-r-1 and \(-\lambda_i-1\), \(i=2,3,\ldots,n\).

The line graph of G, denoted by L(G) is the graph whose vertices corresponds to the edges of G and two vertices of L(G) are adjacent if and only if the corresponding edges are adjacent in G [5]. If G is a regular graph of order n and of degree r then the line graph L(G) is a regular graph of order nr/2 and of degree 2r-2.

Theorem 1.3. [14] If \(\lambda_1, \lambda_2, \dots, \lambda_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

\[\lambda_i + r - 2, \qquad i = 1, 2, \dots, n,\] and \[-2, \qquad n(r-2)/2 \; \textit{times} \; .\]

Figure 1: The forbidden induced subgraphs

Theorem 1.4. [9, 10] For a connected graph G, \(diam(L(G)) \le 2\) if and only if none of the three graphs \(F_1\), \(F_2\) and \(F_3\) of Fig. 1 is an induced subgraph of G.

Lemma 1.1. [15] If for any two adjacent vertices u and v of a graph G, there exists a third vertex w which is not adjacent to any of u and v, then

• (i) \(\overline{G}\) is connected and
• (ii) \(diam(\overline{G}) \leq 2\).

2. RCD-eigenvalues

Theorem 2.1. Let G be an r-regular graph on n vertices and diam(G) = 2. If r, λ2, . . . , λⁿ are the adjacency eigenvalues of G , then its RCD-eigenvalues are n−1− r 2 and −1− λi 2 , i = 2, 3, . . . , n.

Proof. Since G is an r-regular graph, 1 = [1, 1, . . . , 1]⁰ is an eigenvector of A = A(G) corresponding to the eigenvalue r. Set z = ^√ 1 n 1 and let P be an orthogonal matrix with its first column equal to z such that P ⁰AP = diag(λ1, λ2, . . . , λn). Since diam(G) = 2, RCD(G) can be written as RCD(G) = J − I − (1/2)A, where J is the matrix whose all entries are equal to 1 and I is an identity matrix. It follows that

\[\begin{split} P'(RCD)P &= P'\left(J - I - \frac{1}{2}A\right)P \\ &= P'JP - I - \frac{1}{2}P'AP \\ &= \text{diag}\left(n - 1 - \frac{r}{2}, -1 - \frac{\lambda_2}{2}, \dots, -1 - \frac{\lambda_n}{2}\right), \end{split}\]

where we have used the fact that any column of P other than the first column is orthogonal to the first column. Hence the eigenvalues of RCD(G) are n − 1 − (r/2) and −1 − (λi/2), i = 2, 3, . . . , n.

Theorem 2.2. If G is an r-regular, connected graph of order n ≥ 4 and if none of the three graphs F1, F² and F³ of Fig. 1 is an induced subgraph of G , then L(G) has exactly one positive RCD-eigenvalue, equal to r(n − 2)/2.

Proof. Let r, λ2, λ3, . . . , λⁿ be the adjacency eigenvalues of a regular graph G . Then from Theorem 1.3, the adjacency eigenvalues of L(G) are

\[\lambda_i + r - 2, \qquad i = 1, 2, \dots, n,\] \[-2, \qquad n(r - 2)/2 \text{ times.}\] (3)

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 none of the three graphs F1, F² and F³ of Fig. 1 is an induced subgraph of G , from Theorem 1.4, diam(L(G)) = 2 . Therefore from Theorem 2.1 and Eq. (3), the RCD-eigenvalues of L(G) are

\[r(n-2)/2\], and \[-(\lambda_i + r)/2\], \(i = 2, 3, \dots, n\) and \[0\], \(n(r-2)/2\) times. (4)

All adjacency eigenvalues of a regular graph of degree r satisfy the condition −r ≤ λⁱ ≤ r [3]. Therefore λⁱ + r ≥ 0 , i = 1, 2, . . . , n . The theorem follows from Eq. (4).

3. RCD-energy

Theorem 3.1. If G is an r-regular, connected graph of order n ≥ 4 and if none of the three graphs F1, F² and F³ of Fig. 1 is an induced subgraph of G , then

\[RCDE(L(G)) = r(n-2).\]

Proof. Bearing in mind Theorem 2.2 and Eq. (4), the RCD-energy of L(G) is computed as:

\[RCDE(L(G)) = \frac{r(n-2)}{2} + \sum_{i=2}^{n} \frac{(\lambda_i + r)}{2} + |0| \times \frac{n(r-2)}{2}\]\[= r(n-2) \quad \text{since} \quad \sum_{i=2}^{n} \lambda_i = -r.\]

From Theorem 3.1, we see that the RCD-energy of the line graph of a regular graph G, that does not contain Fⁱ , i = 1, 2, 3, as an induced subgraph is fully determined by the order n and degree r of G.

Let Kⁿ be the complete graph on n vertices, Kk,k be the complete bipartite graph on 2k vertices and CP(k) be the cocktail party graph (a regular graph on n = 2k vertices and of degree 2k − 2) [3]. None of the three graphs F1, F² and F³ of Fig.1 is an induced subgraph of these graphs. Therefore from Theorem 3.1 we have following:

Corollary 3.1. (i) RCDE(L(Kn)) = n ² − 3n + 2, for n ≥ 4.

• (ii) RCDE(L(Kk,k)) = 2k(k − 1), for k ≥ 2.
• (iii) RCDE(L(CP(k))) = 4(k − 1)² , for k ≥ 2.

Theorem 3.2. Let G be an r-regular graph of order n. Let L(G) be the line graph of G such that for any two adjacent vertices u and v of L(G), there exists a third vertex w in L(G) which is not adjacent to any of u and v.

(i) If the smallest adjacency eigenvalue of G is greater than or equal to 3 − r, then

\[RCDE\left(\overline{L(G)}\right) = 3n(r-2)/2.\]

(ii) If the second largest adjacency eigenvalue of G is at most 3 − r, then

\[RCDE\left(\overline{L(G)}\right) = (nr/2) + 2r - 3.\]

Proof. Let the adjacency eigenvalues of G be r, λ2, . . . , λn. From Theorem 1.3, the adjacency eigenvalues of L(G) are

\[2r-2\], and \[\lambda_i+r-2, \qquad i=2,3,\ldots,n, \qquad \text{and}\] \(-2, \qquad n(r-2)/2 \text{ times.}\)

From Theorem 1.2 and the Eq. (5), the adjacency eigenvalues of \(\overline{L(G)}\) are

\[(nr/2) - 2r + 1\], and \(-\lambda_i - r + 1\), \(i = 2, 3, ..., n\), and \(1, n(r-2)/2\) times. \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Since for any two adjacent vertices u and v of L(G) there exists a third vertex w which is not adjacent to any of u and v in L(G), by Lemma 1.1, \(diam\left(\overline{L(G)}\right)=2\). Therefore by Theorem 2.1 and Eq. (6), the RCD-eigenvalues of \(\overline{L(G)}\) are

\[(nr/4) + r - (3/2),\] and \[\frac{\lambda_i + r - 3}{2}, \quad i = 2, 3, \dots, n,\] and \[(-3/2), \quad n(r-2)/2 \text{ times.}\] (7)

Therefore

\[RCDE\left(\overline{L(G)}\right) = \left|\frac{nr}{4} + r - \frac{3}{2}\right| + \sum_{i=2}^{n} \left|\frac{\lambda_i + r - 3}{2}\right| + \left|-\frac{3}{2}\right| \frac{n(r-2)}{2}.\] (8)

(i) By assumption, \(\lambda_i + r - 3 \ge 0\), \(i = 2, 3, \dots n\), then from Eq. (8)

\[RCDE\left(\overline{L(G)}\right) = \frac{nr}{4} + r - \frac{3}{2} + \sum_{i=2}^{n} \left(\frac{\lambda_i + r - 3}{2}\right) + \frac{3n(r - 2)}{4}\] \[= \frac{nr}{4} + r - \frac{3}{2} + \frac{1}{2} \sum_{i=2}^{n} \lambda_i + (n - 1) \left(\frac{r - 3}{2}\right) + \frac{3n(r - 2)}{4}\] \[= \frac{3n(r - 2)}{2} \quad \text{since} \quad \sum_{i=2}^{n} \lambda_i = -r.\]

(ii) By assumption, \(\lambda_i + r - 3 < 0\), \(i = 2, 3, \dots n\), then from Eq. (8)

\[\begin{split} RCDE\left(\overline{L(G)}\right) &= \frac{nr}{4} + r - \frac{3}{2} - \sum_{i=2}^{n} \left(\frac{\lambda_i + r - 3}{2}\right) + \frac{3n(r - 2)}{4} \\ &= \frac{nr}{4} + r - \frac{3}{2} - \frac{1}{2} \sum_{i=2}^{n} \lambda_i - (n - 1) \left(\frac{r - 3}{2}\right) + \frac{3n(r - 2)}{4} \\ &= \frac{nr}{2} + 2r - 3 \qquad \text{since} \qquad \sum_{i=2}^{n} \lambda_i = -r. \end{split}\]

Some of the examples of r-regular graphs whose second largest adjacency eigenvalue is at most 3-r and the diameter of the complement of their line graph is equal to two are a 5-vertex cycle \(C_5\), a 5-vertex complete graph \(K_5\), a 6-vertex cycle \(C_6\) and a complete bipartite graph \(K_{3,3}\).

Corollary 3.2. Let G be a cubic graph of order n. Let L(G) be the line graph of G such that for any two adjacent vertices u and v of L(G), there exists a third vertex w in L(G) which is not adjacent to any of u and v. Then

\[RCDE\left(\overline{L(G)}\right) = \frac{3n + E(G)}{2}.\]

Proof. Substituting r = 3 in Eq. (8) we get

\[RCDE\left(\overline{L(G)}\right) = \left| \frac{3n}{4} + \frac{3}{2} \right| + \sum_{i=2}^{n} \left| \frac{\lambda_i}{2} \right| + \left| -\frac{3}{2} \right| \frac{n}{2}\]\[= \frac{3n}{4} + \frac{3}{2} + \frac{1}{2}(E(G) - 3) + \frac{3n}{4}\]\[= \frac{3n + E(G)}{2}.\]

4. RCD-equienergetic graphs

Lemma 4.1. Let \(G_1\) and \(G_2\) be regular graphs of the same order and of the same degree. Then following holds:

• (i) \(L(G_1)\) and \(L(G_2)\) are of the same order, same degree and have the same number of edges.
• (ii) \(\overline{L(G_1)}\) and \(\overline{L(G_2)}\) are of the same order, same degree and have the same number of edges.

Proof. Statement (i) follows from the fact that the line graph of a regular graph is a regular and that the number of edges of G is equal to the number of vertices of L(G). Statement (ii) follows from the fact that the complement of a regular graph is a regular and that the number of vertices of a graph and its complement is equal.

Lemma 4.2. Let \(G_1\) and \(G_2\) be regular, connected graphs of the same order \(n \geq 4\) and of the same degree. Let none of the three graphs \(F_1\), \(F_2\) and \(F_3\) of Fig. 1 be an induced subgraph of \(G_i\), i = 1, 2. Then \(L(G_1)\) and \(L(G_2)\) are RCD-cospectral if and only if \(G_1\) and \(G_2\) are cospectral.

Proof. Follows from Eqs. (3) and (4). \(\Box\)

Lemma 4.3. Let \(G_1\) and \(G_2\) be regular graphs of the same order and of the same degree. Let for i=1,2, \(L(G_i)\) be the line graph of \(G_i\) such that for any two adjacent vertices \(u_i\) and \(v_i\) of \(L(G_i)\), there exists a third vertex \(w_i\) in \(L(G_i)\) which is not adjacent to any of \(u_i\) and \(v_i\). Then \(\overline{L(G_1)}\) and \(\overline{L(G_2)}\) are RCD-cospectral if and only if \(G_1\) and \(G_2\) are cospectral.

Proof. Follows from Eqs. (5), (6) and (7). Theorem 4.1. Let G¹ and G² be regular, connected, non cospectral graphs of the same order n ≥ 4 and of the same degree r. Let none of the three graphs F1, F² and F³ of Fig. 1 be an induced subgraph of Gⁱ , i = 1, 2. Then line graphs L(G1) and L(G2) form a pair of non RCD-cospectral, RCD-equienergetic graphs of equal order and of equal number of edges. Proof. Follows from Lemma 4.1, Lemma 4.2 and Theorem 3.1. Theorem 4.2. Let G¹ and G² be regular, non cospectral graphs of the same order and of the same degree r. Let for i = 1, 2, L(Gi) be the line graph of Gⁱ such that for any two adjacent vertices uⁱ and vⁱ of L(Gi), there exists a third vertex wⁱ in L(Gi) which is not adjacent to any of uⁱ and vⁱ . (i) If the smallest adjacency eigenvalue of Gⁱ , i = 1, 2 is greater than or equal to 3−r, then L(G1) and L(G2) form a pair of non RCD-cospectral, RCD-equienergetic graphs of equal order and of equal number of edges. (ii) If the second largest adjacency eigenvalue of Gⁱ , i = 1, 2 is at most 3 − r, then L(G1) and L(G2) form a pair of non RCD-cospectral, RCD-equienergetic graphs of equal order and of equal number of edges. Proof. Follows from Lemma 4.1, Lemma 4.3 and Theorem 3.2. Theorem 4.3. Let G¹ and G² be non cospectral, cubic equienergetic graphs of the same order. Let for i = 1, 2, L(Gi) be the line graph of Gⁱ such that for any two adjacent vertices uⁱ and vⁱ of L(Gi), there exists a third vertex wⁱ in L(Gi) which is not adjacent to any of uⁱ and vⁱ . Then L(G1) and L(G2) form a pair of non RCD-cospectral, RCD-equienergetic graphs of equal order and of equal number of edges. Proof. Follows from Lemma 4.1, Lemma 4.3 and Corollary 3.2.

Acknowledgement

Authors are thankful to anonymous referee for his/her valuable suggestions. The first author H. S. Ramane is thankful to the University Grants Commission (UGC), Govt. of India for support through research grant under UPE FAR-II grant No. F 14-3/2012 (NS/PE). Another author A. S. Yalnaik is thankful to the University Grants Commission (UGC), Govt. of India for support through Rajiv Gandhi National Fellowship No. F1-17.1/2014-15/RGNF-2014-15-SC-KAR-74909.

References

• [1] R. Balakrishnan, The energy of a graph, Linear Algebra Appl., 387 (2004), 287–295.
• [2] V. Brankov, D. Stevanovic, I. Gutman, Equienergetic chemical trees, ´ J. Serb. Chem. Soc., 69 (2004), 549–553.

• [3] D. M. Cvetkovic, M. Doob, H. Sachs, ´ Spectra of Graphs–Theory and Application, Academic Press, New York, 1980.
• [4] I. Gutman, The energy of a graph, Ber. Math. Stat. Sekt. Forschungsz. Graz, 103 (1978), 1–22.
• [5] F. Harary, Graph Theory, Addison–Wesley, Reading, 1969.
• [6] O. Ivanciuc, T. Ivanciuc, A. T. Balaban, The complementary distance matrix, a new molecular graph metric, ACH-Models Chem. 137(1) (2000), 57–82.
• [7] D. Jeneziˇ c, A. Mili ´ cevi ˇ c, S. Nikoli ´ c, N. Trinajsti ´ c,´ Graph Theoretical Matrices in Chemistry, Uni. Kragujevac, Kragujevac, 2007.
• [8] X. Li, Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012.
• [9] H. S. Ramane, I. Gutman, A. B. Ganagi, H. B. Walikar, On diameter of line graphs, Iranian J. Math. Sci. Inf., 8(1) (2013), 105–109.
• [10] H. S. Ramane, D. S. Revankar, I. Gutman, H. B. Walikar, Distance spectra and distance energies of iterated line graphs of regular graphs, Publ. Inst. Math. (Beograd), 85 (2009), 39–46.
• [11] H. S. Ramane, H. B. Walikar, Construction of equienergetic graphs, MATCH Commun. Math. Comput. Chem., 57 (2007), 203–210.
• [12] 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.
• [13] H. Sachs, Uber selbstkomplementare Graphen, ¨ Publ. Math. Debrecen. 9 (1962), 270–288.
• [14] H. Sachs, Uber Teiler, Faktoren und charakteristische Polynome von Graphen, Teil II, ¨ Wiss. Z. TH Ilmenau, 13 (1967), 405–412.
• [15] J. Senbagamalar, J. Baskar Babujee, I. Gutman, On Wiener index of graph complements, Trans. Comb., 3(2) (2014), 11–15.
• [16] L. Xu, Y. Hou, Equienergetic bipartite graphs, MATCH Commun. Math. Comput. Chem., 57 (2007), 363–370.