APM  Vol.7 No.6 , June 2017
The Energy and Operations of Graphs
ABSTRACT
Let G be a finite and undirected simple graph on n vertices, A(G) is the adjacency matrix of G, λ12,...,λn are eigenvalues of A(G), then the energy of G is . In this paper, we determine the energy of graphs obtained from a graph by other unary operations, or graphs obtained from two graphs by other binary operations. In terms of binary operation, we prove that the energy of product graphs is equal to the product of the energy of graphs G1 and G2, and give the computational formulas of the energy of Corona graph , join graph of two regular graphs G and H, respectively. In terms of unary operation, we give the computational formulas of the energy of the duplication graph DmG, the line graph L(G), the subdivision graph S(G), and the total graph T(G) of a regular graph G, respectively. In particularly, we obtained a lot of graphs pair of equienergetic.

1. Introduction

Let G be a finite and undirected simple graph, with vertex set V ( G ) and edge set E ( G ) . The number of vertices of G is n, and its vertices are labeled by v 1 , v 2 , , v n . The adjacency matrix A ( G ) of the graph G is a square matrix of order n, whose ( i , j ) -entry is equal to 1 if the vertices v i and v j are adjacent and is equal to zero otherwise. The characteristic polynomial of the adjacency matrix, i.e., d e t ( x I n A ( G ) ) , where I n is the unit matrix of order n, is said to be the characteristic polynomial of the graph G and will be denoted by ϕ ( G , x ) . The eigenvalues of a graph G are defined as the eigenvalues of its adjacency matrix A ( G ) , and so they are just the roots of the equation ϕ ( G , x ) = 0 . since A ( G ) is a real symmetric matrix, so its eigenvalues are all real. Denoting them by λ 1 , λ 2 , , λ n and as a whole, they are called the spectrum of G. Spectral pro- perties of graphs, including properties of the characteristic polynomial, have been extensively studied, for details, we refer to [1] . In the 1970s, I. Gutman in [2] introduced the concept of the energy of G by

ε ( G ) = i = 1 n | λ i | (1)

In the Hückel molecular orbital (HMO) theory, the energy approximates the the molecular orbital energy levels of π-electrons in conjugated hydrocarbons (see [3] [4] [5] [6] ). Up to now, the energy of G has been extensively studied, for details, we refer to [7] [8] [9] . In this paper, we determine the energy of graphs obtained from a graph by other unary operations, or graphs obtained from two graphs by other binary operations. In terms of binary operation, we prove that the energy of product graphs G 1 × G 2 is equal to the product of the energy of graphs G 1 and G 2 , and give the computational formulas of the energy of Corona graph G H , join graph G H of two regular graphs G and H, respectively. In terms of unary operation, we give the computational formulas of the energy of the duplication graph D m G , the line graph L ( G ) , the sub- division graph S ( G ) , and the total graph T ( G ) of a regular graph G, re- spectively. In particularly, we obtained a lot of graphs pair of equienergetic.

Two nonisomorphic graphs are said to be equienergetic if they have the same energy. Let G and H be two vertex disjoint graphs, G H denotes the union graph of G and H. m G denoted the union graph of m copies of G. K n denotes the complete graph with n vertices. For more notation and terminology, we refer the readers to standard textbooks [10] .

2. The Binary Operations of Graphs

Let G 1 and G 2 be two graphs with vertex set V ( G 1 ) and V ( G 2 ) respec- tively. the product G 1 × G 2 is the graph with vertex set V ( G 1 ) × V ( G 2 ) , in which two vertices, say ( x 1 , y 1 ) and ( x 2 , y 2 ) , are adjacent if and only if x 1 is adjacent to x 2 in G 1 and y 1 is adjacent to y 2 in G 2 . Let A = ( a i j ) m × n , B = ( b i j ) p × q be two matrices, the Kronecker product A B of A and B is the m p × n q matrix obtained from A by replacing each element a i j with the block a i j B .

Lemma 2.1. [1] Let A ( G 1 ) , A ( G 2 ) be adjacency matrices of graphs G 1 , G 2 , respectively. Then the product graph G 1 × G 2 has as adjacency matrix A ( G 1 ) A ( G 2 ) .

Lemma 2.2. [11] Let A, B, C, D be matrices and the products AC, BD exist. Then

( A B ) ( C D ) = ( A C ) ( B D ) . (2)

Theorem 2.1. Let G, H be two graphs. Then

ε ( G × H ) = ε ( G ) × ε ( H ) . (3)

Proof. Let λ 1 , λ 2 , , λ n and μ 1 , μ 2 , , μ m be the eigenvalues of G and H, respectively, suppose x i ( i = 1 , 2 , , n ) are linearly independent eigenvectors of A ( G ) corresponding to λ 1 , λ 2 , , λ n respectively, and y i ( i = 1 , 2 , , m ) are linearly independent eigenvectors of A ( H ) corresponding to μ 1 , μ 2 , , μ m respectively, Consider the vector z i j = x i y j ( i = 1 , 2 , , n , j = 1 , 2 , , m ) . Using Lemma 2.1, we see that

( A ( G ) A ( H ) ) z i j = ( A ( G ) x i ) ( A ( H ) y j ) = λ i μ j x i y j = λ i μ j z i j .

In this way ,we find m n linearly independent eigenvectors, and hence λ i μ j ( i = 1 , 2 , , n , j = 1 , 2 , , m ) are the eigenvalues of G × H .

And so

ε ( G × H ) = i = 1 n j = 1 m | λ i μ j | = i = 1 n | λ i | j = 1 m | μ j | = ε ( G ) ε ( H ) .

,

Corollary 2.1. Let G 1 , G 2 , , G k be k graphs. Then

ε ( G 1 × G 2 × × G k ) = ε ( G 1 ) ε ( G 2 ) ε ( G k ) . (4)

Let G be a graph with n vertices, and let H be a graph with m vertices. The Corona G H is the graph with n + m n vertices obtained from G and n copies of H by joining the i-th vertex of G to each vertex in i-th copy of H ( i = 1 , 2 , , n ) .

Lemma 2.3. [1] Let G be a graph with n vertices, and let H be an r-regular graph with m vertices. Then the characteristic polynomial of the corona G H is given by

ϕ ( G H , x ) = ϕ ( G , x m x r ) ( ϕ ( H , x ) ) n . (5)

Theorem 2.2. Let G be a graph with n vertices, and let H be an r-regular graph with m vertices. If λ 1 , λ 2 , , λ n and r , μ 2 , , μ m be the eigenvalues of G and H, respectively. then

ε ( G H ) = 1 2 i = 1 n ( | r + λ i + ( r λ i ) 2 + 4 m | + | r + λ i ( r λ i ) 2 + 4 m | ) + n ( ε ( H ) r ) . (6)

Proof. By Lemma 2.3, we have

ϕ ( G H , x ) = ( x r ) n ( x μ 2 ) n ( x μ m ) n i = 1 n ( x m x r λ i ) = ( x μ 2 ) n ( x μ m ) n i = 1 n ( x 2 ( r + λ i ) x + r λ i m ) .

And so

ε ( G H ) = 1 2 i = 1 n ( | r + λ i + ( r λ i ) 2 + 4 m | + | r + λ i ( r λ i ) 2 + 4 m | ) + n ( j = 2 m | μ j | ) = 1 2 i = 1 n ( | r + λ i + ( r λ i ) 2 + 4 m | + | r + λ i ( r λ i ) 2 + 4 m | ) + n ( ε ( H ) r ) .

,

Corollary 2.2. Let H 1 and H 2 be two equienergetic r-regular graph with m vertices, and let G be a graph with n vertices. Then G H 1 and G H 2 are equienergetic.

Corollary 2.3. Let m 2, n 3 . Then ε ( K n K m ) = m n + m 2 + ( n 1 ) m 2 + 4 m .

Proof. K m has spectrum n 1, 1 ( n 1 times). Since

( m 1 ) 1 ( m 1 + 1 ) 2 + 4 m 0 , and m 2, n 3 means

( m 1 ) + ( n 1 ) ( m n ) 2 + 4 m 0 . Hence

ε ( K n K m ) = 1 2 i = 1 n ( | ( m 1 ) + λ i + ( m 1 λ i ) 2 + 4 m | + | m 1 + λ i ( m 1 λ i ) 2 + 4 m | ) + n ( ε ( H ) ( m 1 ) ) = m + n 2 + ( n 1 ) m 2 + 4 m + n ( m 1 ) = m n + m 2 + ( n 1 ) m 2 + 4 m .

Let G and H be two graphs, The join G H of (disjoint) grapgs G and H is the graph obtained from G H by joining each vertex of G to each vertex of H.

Lemma 2.4. [1] If G 1 is r 1 -regular with n 1 vertices, and G 2 is r 2 - regular with n 2 vertices, then the characteristic polynomial of the join G 1 G 2 is given by

ϕ ( G 1 G 2 , x ) = ϕ ( G 1 , x ) ϕ ( G 2 , x ) ( x r 1 ) ( x r 2 ) ( ( x r 1 ) ( x r 2 ) n 1 n 2 ) . (7)

Corollary 2.4. Let G i be r i -regular graph with n i vertices, i = 1 , 2. Then

ε ( G 1 G 2 ) = ε ( G 1 ) + ε ( G 2 ) ( r 1 + r 2 ) + ( r 1 + r 2 ) 2 + 4 ( n 1 n 2 r 1 r 2 ) . (8)

Corollary 2.5. Let G 1 and H 1 be two equienergetic r 1 -regular graph with n 1 vertices, and let G 2 and H 2 be two equienergetic r 2 -regular graph with n 2 vertices, then G 1 G 2 and H 1 H 2 are equienergetic.

Lemma 2.5. [1] Let G 1 , G 2 , , G k be regular graphs, let G i have degree r i and n i vertices ( i = 1 , 2 , , k ) . where the relations

n 1 r 1 = n 2 r 2 = = n k r k = s hold. Then the graph G = G 1 G 2 G k has n = n 1 + n 2 + + n k vertices and is regular of degree r = n s , the charac- teristic polynomial of the join G is given by

ϕ ( G , x ) = ( x r ) ( x + n r ) k 1 i = 1 k ϕ ( G i , x ) x r i . (9)

By Lemma 2.5, we have following Corollary.

Corollary 2.6. Let G 1 , G 2 , , G k be regular graphs, let G i have degree r i and n i vertices ( i = 1 , 2 , , k ) . where the relations n 1 r 1 = n 2 r 2 = = n k r k = s hold. Then

ε ( G 1 G 2 G k ) = 2 ( k 1 ) s + i = 1 k ε ( G i ) . (10)

3. The Unary Operations of Graphs

Let G be a graph with vertex set V ( G ) = { v 1 , v 2 , , v n } , the duplication graph D m G is the graph with m n vertices obtained from m G by joining v i to each neighbors of v i in the j-th copy of G ( j = 1 , 2 , , m , i = 1 , 2 , , n ) .

Theorem 3.1. Let G be a graph. Then

ε ( D m G ) = m ε ( G ) . (11)

Proof. If A ( G ) is the adjacency matrix of graph G, then, it is obviously that the adjacency matrix of the duplication graph D m G is J m A ( G ) , where J m is all 1 matrix of order m. the spectrum of J m is m ,0 ( m 1 ) times, similar to the proof of Theorem 2.1, we have ε ( D m G ) = m ε ( G ) .

Corollary 3.1. Let G and H be two equienergetic graph, then D m G and D m H are equienergetic.

Let G be a graph, the line graph L ( G ) of graph G is the graph whose vertices are the edges of G, with two vertices in L ( G ) adjacent whenever the corre- sponding edge in G have exactly one vertex in common.

Lemma 3.1 [1] If G is a regular graph of degree r, with n vertices and

m ( = 1 2 n r ) edges, then

ϕ ( L ( G ) , x ) = ( x + 2 ) m n ϕ ( G , x r + 2 ) . (12)

Corollary 3.2. Let G be a regular graph of degree r, with n vertices and

m ( = 1 2 n r ) edges, If λ 1 ( = r ) , λ 2 , , λ n is the eigenvalues of G, then

ε ( L ( G ) ) = 2 ( m n ) + i = 1 n | r + λ i 2 | . (13)

Corollary 3.3.

ε ( L ( K n ) ) = { 2 n 2 6 n 4 n , 4 ( n 2 ) 2 n 3. (14)

Let G be a graph, the subdivision graph S ( G ) of graph G is the graph obtained by inserting a new vertex into every edge of G. The graph R ( G ) of graph G is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. The graph Q ( G ) of graph G is the graph obtained from G by inserting a new vertex into every edge of G, and joining by edges those pairs of new vertices which lie on adjacent edges of G. The total graph T ( G ) of graph G is the graph whose vertices are the vertices and edges of G, with two vertices of T ( G ) adjacent if and only if the corresponding element of G are adjacent or incident.

Lemma 3.2. [1] If G is a regular graph of degree r, with n vertices and

m ( = 1 2 n r ) edges, then

1) ϕ ( S ( G ) , x ) = x m n ϕ ( G , x 2 r ) ,

2) ϕ ( R ( G ) , x ) = x m n ( x + 1 ) n ϕ ( G , x 2 r x + 1 ) ,

3) ϕ ( Q ( G ) , x ) = ( x + 2 ) m n ( x + 1 ) n ϕ ( G , x 2 ( r 2 ) x r x + 1 ) .

4) The total graph T ( G ) has m n eigenvalues equal to −2 and the following 2n eigenvalues:

1 2 ( 2 λ i + r 2 ± 4 λ i + r 2 + 4 ) , ( i = 1 , 2 , , n ) .

Theorem 3.2. Let G be a regular graph of degree r, with n vertices and

m ( = 1 2 n r ) edges, If λ 1 ( = r ) , λ 2 , , λ n is the eigenvalues of G, then

1) ε ( S ( G ) ) = 2 i = 1 n r + λ i ,

2) ε ( R ( G ) ) = i = 1 n λ i 2 + 4 ( r + λ i ) ,

3) ε ( Q ( G ) ) = 2 ( m n ) + i = 1 n ( r + λ i ) 2 + 4 ,

4) ε ( T ( G ) ) = 2 ( m n ) + 1 2 i = 1 n ( | 2 λ i + r 2 + 4 λ i + r 2 + 4 | + | 2 λ i + r 2 4 λ i + r 2 + 4 | ) .

Proof. (1) By Lemma 3.2 (1), we know that the spectrum of S ( G ) is { 0 ( m n times ) , ± r + λ i ( i = 1 , 2 , , n ) } . So ε ( S ( G ) ) = 2 i = 1 n r + λ i .

(2) By Lemma 3.2 (2), we know that the spectrum of R ( G ) is

{ 0 ( m n times ) , λ i ± λ i 2 + 4 ( r + λ i ) 2 ( i = 1 , 2 , , n ) } . So ε ( R ( G ) ) = i = 1 n λ i 2 + 4 ( r + λ i ) .

(3), (4) Proof is similar to (1).

Corollary 3.4. 1) If n 2, then ε ( S ( K n ) ) = 2 ( 2 n 2 + ( n 1 ) n 2 ) .

2) If n 2, then ε ( R ( K n ) ) = n 2 + 6 n 7 + ( n 1 ) 4 n 7 .

3) ε ( Q ( K n ) ) = n 2 3 n + 2 n 2 2 n + 2 + ( n 1 ) n 2 4 n + 8 .

4) If n 2, then ε ( T ( K n ) ) = { 2 n 2 2 n 4 n 3 , 4 n = 2.

4. Conclusion

In this paper, we prove that ε ( G × H ) = ε ( G ) × ε ( H ) , ε ( D m G ) = m ε ( G ) . For regular graphs G and H, we give the computational formulas of ε ( G H ) , ε ( G H ) , ε ( L ( G ) ) , ε ( S ( G ) ) , ε ( R ( G ) ) , ε ( Q ( G ) ) , and ε ( T ( G ) ) re- spectively. In particularly, we obtained a lot of graphs pair of equienergetic.

Acknowledgements

This work is supported by National Natural Science Foundation of China (11561056, 11661066), National Natural Science Foundation of Qinghai Provence (2016-ZJ-914), and Scientific Research Fund of Qinghai University for Nationalities (2015G02).

Cite this paper
Ma, H. and Liu, X. (2017) The Energy and Operations of Graphs. Advances in Pure Mathematics, 7, 345-351. doi: 10.4236/apm.2017.76021.
References
[1]   Cvetković, D., Rowlinson, P. and Simić, S. (2010) An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge.

[2]   Gutman, I. (1978) The Energy of a Graph. Ber. Math.— Statist. Sekt. Forschungsz. Graz, 103, 1-22.

[3]   Cvetković, D. and Gutman, I. (Eds.) (2009) Applications of Graph Spectra. Mathematical Institution, Belgrade.

[4]   Graovac, A., Gutman, I. and Trinajstić, N. (1977) Topological Approach to the Che-mistry of Conjugated Molecules. Springer, Berlin.
https://doi.org/10.1007/978-3-642-93069-0

[5]   Gutman, I. and Polansky, O.E. (1986) Mathematical Concepts in Organic Chemistry. Springer, Berlin.
https://doi.org/10.1007/978-3-642-70982-1

[6]   Gutman, I. and Trinajstić, N. (1973) Graph Theory and Molecular Orbitals. Topics Curr. Chem., 42, 49-93.

[7]   Li, X.L., Shi, Y.T. and Gutman, I. (2012) Graph Energy. Springer, Berlin.
https://doi.org/10.1007/978-1-4614-4220-2

[8]   Balakrishnan, R. (2004) The Energy of a Graph. Linear Algebra and Its Applications, 387, 287-295.

[9]   Ramane, H.S. and Walikar, H.B. (2007) Construction of Eqienergetic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 57, 203-210.

[10]   Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. MacMllan, London.

[11]   Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon. Inc., Boston.

 
 
Top