Geometrical significance of Graph energy.

178 Views Asked by At

The following definition of the energy of graph is taken from an article entitled "Energy of Graphs. A few open problems and some suggestions" by Dragan Stevanovic of University of Nis, Serbia.

It says that the notion of energy of a graph is defined in $1978$ and originating from theoretical chemistry. For an $n$-vertex graph $G$ with adjacency matrix $A$ having eigenvalues $\lambda_1 \geq \lambda_2 \geq . . . \geq \lambda_n$, the energy $E(G)$ is defined as

$E(G) =\sum_{i=1}^{n} |\lambda_i|$. It is related to the total $\pi$-electron energy in a molecule represented by a (molecular) graph.

I am considering only simple undirected graphs and have specifically, two questions as follows:

Is the energy of a graph $G$ always greater than that of all its subgraphs? In other words, is the energy of a super graph always greater than its subgraphs?

What is the geometrical significance of the energy of a graph representing social network like facebook? Or, what is the geometrical significance of the energy of a graph representing a food web in ecosystem?

1

There are 1 best solutions below

3
On

The energy of a graph $G$ is always greater than the energy of an induced subgraph $H$ (where we take a subset of $G$'s vertices, and include all the edges $G$ had between them).

This follows from an interlacing result: if the adjacency matrix of $G$ has eigenvalues $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$, and the adjacency matrix of $G-v$ (where we delete vertex $v$ and all its edges) has eigenvalues $\mu_1 \ge \mu_2 \ge \dots \ge \mu_{n-1}$, then $$ \lambda_1 \ge \mu_1 \ge \lambda_2 \ge \mu_2 \ge \dots \ge \lambda_{n-1} \ge \mu_{n-1} \ge \lambda_n. $$ When $\mu_i$ is positive, $|\mu_i| \le |\lambda_i|$; when $\mu_i$ is negative, $|\mu_i| \le |\lambda_{i+1}|$. This tells us that the sum $|\mu_1| + \dots + |\mu_{n-1}|$ is less than $|\lambda_1| + \dots + |\lambda_n|$: the energy of $G-v$ is less than the energy of $G$.

In general, for an induced subgraph, we may delete multiple vertices, in which case we just apply this result repeatedly.

For non-induced subgraphs, this might not apply. Examples 4.5 and 4.6 in the paper Graph Energy Change due to Edge Deletion by Day and So prove that the energy of $K_n-e$ is less than the energy of $K_n$ (where $e$ is an arbitrary edge) but the energy of $K_{n,n}-e$ is greater than the energy of $K_{n,n}$ (where $e$ is an arbitrary edge), so the change can go in both directions.