ABSTRACT

Let G be a finite and undirected simple graph on n vertices, $A\left(G\right)$ is the adjacency matrix of G, ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_n$ are eigenvalues of $A\left(G\right)$ , then the energy of G is $\epsilon \left(\mathbb{G}\right)={\displaystyle {\sum }_{i=1}^n}\left|{\lambda }_i\right|$ . 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\times 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\circ H$ , join graph $G\nabla 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\left(G\right)$ , the subdivision graph $S\left(G\right)$ , and the total graph $T\left(G\right)$ of a regular graph G, respectively. In particularly, we obtained a lot of graphs pair of equienergetic.

Keywords:

Graph, Matrix, Energy, Operation

1. Introduction

Let G be a finite and undirected simple graph, with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$ . The number of vertices of G is n, and its vertices are labeled by $v_1\mathrm{,}{v}_2\mathrm{,}\cdots ,v_n$ . The adjacency matrix $A\left(G\right)$ of the graph G is a square matrix of order n, whose $\left(i\mathrm{,}j\right)$ -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., $det\left(x{I}_n-A\left(G\right)\right)$ , 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 $\varphi \left(G\mathrm{,}x\right)$ . The eigenvalues of a graph G are defined as the eigenvalues of its adjacency matrix $A\left(G\right)$ , and so they are just the roots of the equation $\varphi \left(G,x\right)=0$ . since $A\left(G\right)$ is a real symmetric matrix, so its eigenvalues are all real. Denoting them by ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_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

$\epsilon \left(G\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|{\lambda }_i\right|$ (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\times 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\circ H$ , join graph $G\nabla 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\left(G\right)$ , the sub- division graph $S\left(G\right)$ , and the total graph $T\left(G\right)$ 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\cup H$ denotes the union graph of G and H. $mG$ 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\left(G_1\right)$ and $V\left(G_2\right)$ respec- tively. the product $G_1\times G_2$ is the graph with vertex set $V\left(G_1\right)\times V\left(G_2\right)$ , in which two vertices, say $\left(x_1\mathrm{,}{y}_1\right)$ and $\left(x_2\mathrm{,}{y}_2\right)$ , 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={\left(a_{ij}\right)}_{m\times n}$ , $B={\left(b_{ij}\right)}_{p\times q}$ be two matrices, the Kronecker product $A\otimes B$ of A and B is the $mp\times nq$ matrix obtained from A by replacing each element $a_{ij}$ with the block $a_{ij}B$ .

Lemma 2.1. [1] Let $A\left(G_1\right)$ , $A\left(G_2\right)$ be adjacency matrices of graphs $G_1$ , $G_2$ , respectively. Then the product graph $G_1\times G_2$ has as adjacency matrix $A\left(G_1\right)\otimes A\left(G_2\right)$ .

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

$\left(A\otimes B\right)\left(C\otimes D\right)=\left(AC\right)\otimes \left(BD\right).$ (2)

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

$\epsilon \left(G\times H\right)=\epsilon \left(G\right)\times \epsilon \left(H\right).$ (3)

Proof. Let ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_n$ and ${\mu }_1\mathrm{,}{\mu }_2\mathrm{,}\cdots \mathrm{,}{\mu }_m$ be the eigenvalues of G and H, respectively, suppose $x_i\left(i=1,2,\cdots ,n\right)$ are linearly independent eigenvectors of $A\left(G\right)$ corresponding to ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_n$ respectively, and $y_i\left(i=1,2,\cdots ,m\right)$ are linearly independent eigenvectors of $A\left(H\right)$ corresponding to ${\mu }_1\mathrm{,}{\mu }_2\mathrm{,}\cdots \mathrm{,}{\mu }_m$ respectively, Consider the vector $z_{ij}=x_i\otimes y_j\left(i=1,2,\cdots ,n,j=1,2,\cdots ,m\right).$ Using Lemma 2.1, we see that

$\left(A\left(G\right)\otimes A\left(H\right)\right)z_{ij}=\left(A\left(G\right)x_i\right)\otimes \left(A\left(H\right)y_j\right)={\lambda }_i{\mu }_j{x}_i\otimes y_j={\lambda }_i{\mu }_j{z}_{ij}.$

In this way ,we find $mn$ linearly independent eigenvectors, and hence ${\lambda }_i{\mu }_j\left(i=1,2,\cdots ,n,j=1,2,\cdots ,m\right)$ are the eigenvalues of $G\times H$ .

And so

$\epsilon \left(G\times H\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}}\left|{\lambda }_i{\mu }_j\right|={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|{\lambda }_i\right|{\displaystyle \underset{j=1}{\overset{m}{\sum }}}\left|{\mu }_j\right|=\epsilon \left(G\right)\epsilon \left(H\right).$

,

Corollary 2.1. Let $G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k$ be k graphs. Then

$\epsilon \left(G_1\times G_2\times \cdots \times G_k\right)=\epsilon \left(G_1\right)\epsilon \left(G_2\right)\cdots \epsilon \left(G_k\right).$ (4)

Let G be a graph with n vertices, and let H be a graph with m vertices. The Corona $G\circ H$ is the graph with $n+mn$ 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\left(i=1,2,\cdots ,n\right).$

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\circ H$ is given by

$\varphi \left(G\circ H\mathrm{,}x\right)=\varphi \left(G\mathrm{,}x-\frac{m}{x-r}\right){\left(\varphi \left(H\mathrm{,}x\right)\right)}^n\mathrm{.}$ (5)

Theorem 2.2. Let G be a graph with n vertices, and let H be an r-regular graph with m vertices. If ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_n$ and $r\mathrm{,}{\mu }_2\mathrm{,}\cdots \mathrm{,}{\mu }_m$ be the eigenvalues of G and H, respectively. then

$\epsilon \left(G\circ H\right)=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left(\left|r+{\lambda }_i+\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|+\left|r+{\lambda }_i-\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|\right)+n\left(\epsilon \left(H\right)-r\right).$ (6)

Proof. By Lemma 2.3, we have

$\begin{array}{c}\varphi \left(G\circ H,x\right)={\left(x-r\right)}^n{\left(x-{\mu }_2\right)}^n\cdots {\left(x-{\mu }_m\right)}^n{\displaystyle \underset{i=1}{\overset{n}{\prod }}}\left(x-\frac{m}{x-r}-{\lambda }_i\right)\\ ={\left(x-{\mu }_2\right)}^n\cdots {\left(x-{\mu }_m\right)}^n{\displaystyle \underset{i=1}{\overset{n}{\prod }}}\left(x^2-\left(r+{\lambda }_i\right)x+r{\lambda }_i-m\right).\end{array}$

And so

$\begin{array}{c}\epsilon \left(G\circ H\right)=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left(\left|r+{\lambda }_i+\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|+\left|r+{\lambda }_i-\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|\right)+n\left({\displaystyle \underset{j=2}{\overset{m}{\sum }}}\left|{\mu }_j\right|\right)\\ =\frac{1}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left(\left|r+{\lambda }_i+\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|+\left|r+{\lambda }_i-\sqrt{{\left(r-{\lambda }_i\right)}^2+4m}\right|\right)+n\left(\epsilon \left(H\right)-r\right).\end{array}$

,

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\circ H_1$ and $G\circ H_2$ are equienergetic.

Corollary 2.3. Let $m\ge \mathrm{2,}n\ge 3$ . Then $\epsilon \left(K_n\circ K_m\right)=mn+m-2+\left(n-1\right)\sqrt{m^2+4m}.$

Proof. $K_m$ has spectrum $n-\mathrm{1,}-1$ ( $n-1$ times). Since

$\left(m-1\right)-1-\sqrt{{\left(m-1+1\right)}^2+4m}\le 0$ , and $m\ge \mathrm{2,}n\ge 3$ means

$\left(m-1\right)+\left(n-1\right)-\sqrt{{\left(m-n\right)}^2+4m}\ge 0$ . Hence

$\begin{array}{c}\epsilon \left(K_n\circ K_m\right)=\frac{1}{2}{\displaystyle {\sum }_{i=1}^n}(\left|\left(m-1\right)+{\lambda }_i+\sqrt{{\left(m-1-{\lambda }_i\right)}^2+4m}\right|\\ +\left|m-1+{\lambda }_i-\sqrt{{\left(m-1-{\lambda }_i\right)}^2+4m}\right|)+n\left(\epsilon \left(H\right)-\left(m-1\right)\right)\\ =m+n-2+\left(n-1\right)\sqrt{m^2+4m}+n\left(m-1\right)\\ =mn+m-2+\left(n-1\right)\sqrt{m^2+4m}.\end{array}$

Let G and H be two graphs, The join $G\nabla H$ of (disjoint) grapgs G and H is the graph obtained from $G\cup 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\nabla G_2$ is given by

$\varphi \left(G_1\nabla G_2,x\right)=\frac{\varphi \left(G_1,x\right)\varphi \left(G_2,x\right)}{\left(x-r_1\right)\left(x-r_2\right)}\left(\left(x-r_1\right)\left(x-r_2\right)-n_1{n}_2\right).$ (7)

Corollary 2.4. Let $G_i$ be $r_i$ -regular graph with $n_i$ vertices, $i=1,2.$ Then

$\epsilon \left(G_1\nabla G_2\right)=\epsilon \left(G_1\right)+\epsilon \left(G_2\right)-\left(r_1+r_2\right)+\sqrt{{\left(r_1+r_2\right)}^2+4\left(n_1{n}_2-r_1{r}_2\right)}.$ (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\nabla G_2$ and $H_1\nabla H_2$ are equienergetic.

Lemma 2.5. [1] Let $G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k$ be regular graphs, let $G_i$ have degree $r_i$ and $n_i$ vertices $\left(i=1,2,\cdots ,k\right)$ . where the relations

$n_1-r_1=n_2-r_2=\cdots =n_k-r_k=s$ hold. Then the graph $G=G_1\nabla G_2\nabla \cdots \nabla G_k$ has $n=n_1+n_2+\cdots +n_k$ vertices and is regular of degree $r=n-s$ , the charac- teristic polynomial of the join G is given by

$\varphi \left(G,x\right)=\left(x-r\right){\left(x+n-r\right)}^{k-1}{\displaystyle \underset{i=1}{\overset{k}{\prod }}}\frac{\varphi \left(G_i,x\right)}{x-r_i}.$ (9)

By Lemma 2.5, we have following Corollary.

Corollary 2.6. Let $G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k$ be regular graphs, let $G_i$ have degree $r_i$ and $n_i$ vertices $\left(i=1,2,\cdots ,k\right)$ . where the relations $n_1-r_1=n_2-r_2=\cdots =n_k-r_k=s$ hold. Then

$\epsilon \left(G_1\nabla G_2\nabla \cdots \nabla G_k\right)=2\left(k-1\right)s+{\displaystyle \underset{i=1}{\overset{k}{\sum }}}\epsilon \left(G_i\right).$ (10)

3. The Unary Operations of Graphs

Let G be a graph with vertex set $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\},$ the duplication graph $D_{m}G$ is the graph with $mn$ vertices obtained from $mG$ by joining $v_i$ to each neighbors of $v_i$ in the j-th copy of $G\left(j=1,2,\cdots ,m,i=1,2,\cdots ,n\right)$ .

Theorem 3.1. Let G be a graph. Then

$\epsilon \left(D_{m}G\right)=m\epsilon \left(G\right).$ (11)

Proof. If $A\left(G\right)$ 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\otimes A\left(G\right)$ , where $J_m$ is all 1 matrix of order m. the spectrum of $J_m$ is $m\mathrm{,0}\left(m-1\right)$ times, similar to the proof of Theorem 2.1, we have $\epsilon \left(D_{m}G\right)=m\epsilon \left(G\right).$

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\left(G\right)$ of graph G is the graph whose vertices are the edges of G, with two vertices in $L\left(G\right)$ 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\left(=\frac{1}{2}nr\right)$ edges, then

$\varphi \left(L\left(G\right)\mathrm{,}x\right)={\left(x+2\right)}^{m-n}\varphi \left(G\mathrm{,}x-r+2\right)\mathrm{.}$ (12)

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

$m\left(=\frac{1}{2}nr\right)$ edges, If ${\lambda }_1\left(=r\right),{\lambda }_2,\cdots ,{\lambda }_n$ is the eigenvalues of G, then

$\epsilon \left(L\left(G\right)\right)=2\left(m-n\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|r+{\lambda }_i-2\right|.$ (13)

Corollary 3.3.

$\epsilon \left(L\left(K_n\right)\right)=\{\begin{array}{ll}2n^2-6n\hfill & 4\le n,\hfill \\ 4\left(n-2\right)\hfill & 2\le n\le 3.\hfill \end{array}$ (14)

Let G be a graph, the subdivision graph $S\left(G\right)$ of graph G is the graph obtained by inserting a new vertex into every edge of G. The graph $R\left(G\right)$ 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\left(G\right)$ 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\left(G\right)$ of graph G is the graph whose vertices are the vertices and edges of G, with two vertices of $T\left(G\right)$ 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\left(=\frac{1}{2}nr\right)$ edges, then

1) $\varphi \left(S\left(G\right),x\right)=x^{m-n}\varphi \left(G,x^2-r\right),$

2) $\varphi \left(R\left(G\right),x\right)=x^{m-n}{\left(x+1\right)}^n\varphi \left(G,\frac{x^2-r}{x+1}\right),$

3) $\varphi \left(Q\left(G\right),x\right)={\left(x+2\right)}^{m-n}{\left(x+1\right)}^n\varphi \left(G,\frac{x^2-\left(r-2\right)x-r}{x+1}\right).$

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

$\frac{1}{2}\left(2{\lambda }_i+r-2\pm \sqrt{4{\lambda }_i+r^2+4}\right),\left(i=1,2,\cdots ,n\right).$

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

$m\left(=\frac{1}{2}nr\right)$ edges, If ${\lambda }_1\left(=r\right),{\lambda }_2,\cdots ,{\lambda }_n$ is the eigenvalues of G, then

1) $\epsilon \left(S\left(G\right)\right)=2{\displaystyle {\sum }_{i=1}^n}\sqrt{r+{\lambda }_i},$

2) $\epsilon \left(R\left(G\right)\right)={\displaystyle {\sum }_{i=1}^n}\sqrt{{\lambda }_i^2+4\left(r+{\lambda }_i\right)},$

3) $\epsilon \left(Q\left(G\right)\right)=2\left(m-n\right)+{\displaystyle {\sum }_{i=1}^n}\sqrt{{\left(r+{\lambda }_i\right)}^2+4},$

4) $\begin{array}{c}\epsilon \left(T\left(G\right)\right)=2\left(m-n\right)+\frac{1}{2}{\displaystyle {\sum }_{i=1}^n}(\left|2{\lambda }_i+r-2+\sqrt{4{\lambda }_i+r^2+4}\right|\\ +\left|2{\lambda }_i+r-2-\sqrt{4{\lambda }_i+r^2+4}\right|).\end{array}$

Proof. (1) By Lemma 3.2 (1), we know that the spectrum of $S\left(G\right)$ is $\left\{0\left(m-n\text{times}\right),\pm \sqrt{r+{\lambda }_i}\left(i=1,2,\cdots ,n\right)\right\}$ . So $\epsilon \left(S\left(G\right)\right)=2{\displaystyle {\sum }_{i=1}^n}\sqrt{r+{\lambda }_i}.$

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

$\left\{0\left(m-n\text{times}\right),\frac{{\lambda }_i\pm \sqrt{{\lambda }_i^2+4\left(r+{\lambda }_i\right)}}{2}\left(i=1,2,\cdots ,n\right)\right\}$ . So $\epsilon \left(R\left(G\right)\right)={\displaystyle {\sum }_{i=1}^n}\sqrt{{\lambda }_i^2+4\left(r+{\lambda }_i\right)}.$

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

Corollary 3.4. 1) If $n\ge \mathrm{2,}$ then $\epsilon \left(S\left(K_n\right)\right)=2\left(\sqrt{2n-2}+\left(n-1\right)\sqrt{n-2}\right).$

2) If $n\ge \mathrm{2,}$ then $\epsilon \left(R\left(K_n\right)\right)=\sqrt{n^2+6n-7}+\left(n-1\right)\sqrt{4n-7}.$

3) $\epsilon \left(Q\left(K_n\right)\right)=n^2-3n+2\sqrt{n^2-2n+2}+\left(n-1\right)\sqrt{n^2-4n+8}.$

4) If $n\ge \mathrm{2,}$ then $\epsilon \left(T\left(K_n\right)\right)=\{\begin{array}{ll}2n^2-2n-4\hfill & n\ge 3,\hfill \\ 4\hfill & n=2.\hfill \end{array}$

4. Conclusion

In this paper, we prove that $\epsilon \left(G\times H\right)=\epsilon \left(G\right)\times \epsilon \left(H\right),$ $\epsilon \left(D_{m}G\right)=m\epsilon \left(G\right).$ For regular graphs G and H, we give the computational formulas of $\epsilon \left(G\nabla H\right)$ , $\epsilon \left(G\circ H\right)$ , $\epsilon \left(L\left(G\right)\right)$ , $\epsilon \left(S\left(G\right)\right)$ , $\epsilon \left(R\left(G\right)\right)$ , $\epsilon \left(Q\left(G\right)\right)$ , and $\epsilon \left(T\left(G\right)\right)$ 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.C. and Liu, X.H. (2017) The Energy and Operations of Graphs. Advances in Pure Mathematics, 7, 345-351. https://doi.org/10.4236/apm.2017.76021

References