nach oben

2012 | Buch

Graph Energy

verfasst von: Xueliang Li, Yongtang Shi, Ivan Gutman

Verlag: Springer New York

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is about graph energy. The authors have included many of the important results on graph energy, such as the complete solution to the conjecture on maximal energy of unicyclic graphs, the Wagner-Heuberger’s result on the energy of trees, the energy of random graphs or the approach to energy using singular values. It contains an extensive coverage of recent results and a gradual development of topics and the inclusion of complete proofs from most of the important recent results in the area. The latter fact makes it a valuable reference for researchers looking to get into the field of graph energy, further stimulating it with occasional inclusion of open problems. The book provides a comprehensive survey of all results and common proof methods obtained in this field with an extensive reference section. The book is aimed mainly towards mathematicians, both researchers and doctoral students, with interest in the field of mathematical chemistry.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

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 ₁,v ₂,…,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., det(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 symmetric, its eigenvalues are all real. Denote them by λ₁,λ₂,…,λ_n, and as a whole, they are called the spectrum of G and denoted by Spec(G).

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 2. The Chemical Connection

Abstract

Research on what we call the energy of a graph can be traced back to the 1940s or even to the 1930s. In the 1930s, the German scholar Erich Hückel put forward a method for finding approximate solutions of the Schrödinger equation of a class of organic molecules, the so-called conjugated hydrocarbons. Details of this approach, often referred to as the “Hückel molecular orbital (HMO) theory” can be found in appropriate textbooks [76, 101].

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 3. The Coulson Integral Formula

Abstract

In the theory of graph energy, the so-called Coulson integral formula (3.1) plays an outstanding role. This formula was obtained by Charles Coulson as early as 1940 [73] and reads:

$$\mathcal{E}(G) = \frac{1} {\pi }\int\limits_{-\infty }^{+\infty }\left [n -\frac{\mathrm{i}x\,\phi ^{\prime}(G,\mathrm{i}x)} {\phi (G,\mathrm{i}x)} \right ]\mathrm{d}x = \frac{1} {\pi }\int\limits_{-\infty }^{+\infty }\left [n - x \frac{\mathrm{d}} {\mathrm{d}x}\ln \phi (G,\mathrm{i}x)\right ]\mathrm{d}x$$

(3.1)

where G is a graph, ϕ(G,x) is the characteristic polynomial of G, ϕ′(G,x)=(d∕dx)ϕ(G,x) its first derivative, and $\mathrm{i} = \sqrt{-1}$.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 4. Common Proof Methods

Abstract

After the concept of graph energy was proposed [149], there was much research on this topic. One basic problem is to find the extremal values or the best bounds for the energy within some special classes of graphs and graphs from these classes with extremal values of energy. Finding answers to such questions is often far from elementary. In this chapter we outline some fundamental methods that are frequently used for solving problems of this kind.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 5. Bounds for the Energy of Graphs

Abstract

A graph G of order n and size m is called an (n, m)-graph. In what follows we assume that the graph eigenvalues are labeled in a nonincreasing manner, i.e., λ₁≥λ₂≥⋯≥λ_n. If G is connected, then λ₁>λ₂ [81]. Because λ₁≥|λ_i|,i=2,…,n, the eigenvalue λ₁ is referred to as the spectral radius of G. Three well-known relations for the eigenvalues are

$$\begin{array}{rcl} & & \sum\limits_{i=1}^{n}{\lambda }_{ i} = 0\end{array}$$

(5.1)

$$\begin{array}{rcl} & & \sum\limits_{i=1}^{n}{\lambda }_{ i}^{2} = 2m\end{array}$$

(5.2)

$$\begin{array}{rcl} & & \sum\limits_{i<j}{\lambda }_{i}\,{\lambda }_{j} = -m.\end{array}$$

(5.3)

The following lemma [81] will be frequently used in the proofs:

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 6. The Energy of Random Graphs

Abstract

In the previous chapter, several lower and upper bounds have been established for various classes of graphs, among which bipartite graphs are of particular interest. But only a few graphs attain the equalities in these bounds. In [105], an exact estimate of the energy of random graphs G _n(p) was established, by using the Wigner semicircle law for any probability p. Furthermore, in [105], the energy of random multipartite graphs was investigated, by considering a generalization of the Wigner matrix, and some estimates of the energy of random multipartite graphs were obtained.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 7. Graphs Extremal with Regard to Energy

Abstract

One of the fundamental questions that is encountered in the study of graph energy is which graphs (from a given class) have greatest and smallest $\mathcal{E}$-values. The first such result was obtained for trees in[145], where it was demonstrated that the star has minimal and the path maximal energy. In the meantime, a remarkably large number of papers was published on such extremal problems: for general graphs [82, 242, 252, 253, 305, 306, 341, 416, 482], trees and chemical trees[141, 219, 268, 314, 316, 319, 324, 327, 339, 343, 344, 389, 390, 434, 435, 483, 487, 497, 498, 505, 506, 511, 517, 518, 543, 547], unicyclic[51, 58, 185, 191, 266, 270, 273–275, 277, 283, 312, 313, 330, 342, 480, 484–486, 488–490, 514], bicyclic[121, 267, 280, 340, 358, 500, 501, 522, 523], tricyclic [326, 329, 521], and tetracyclic graphs [325], as well as for benzenoid and related polycyclic systems [158, 243, 395, 399, 413–415, 519, 520, 526]. In this chapter we state a few of these results, selecting those that can be formulated in a simple manner or that otherwise deserve to be mentioned. We start with a few elementary results.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 8. Hyperenergetic and Equienergetic Graphs

Abstract

The energy of the n-vertex complete graph K _n is equal to 2(n − 1). We call an n-vertex graph Ghyperenergetic if ℰ(G) > 2(n − 1). From Theorem 5.24, we know that for almost all graphs, $\mathcal{E}(G) > \left (\frac{1} {4} + o(1)\right ){n}^{3/2}$, which means that almost all graphs are hyperenergetic. Therefore, any search for hyperenergetic graphs nowadays is a futile task. Yet, before Theorem 5.24 was discovered, a number of such results were obtained. We outline here some of them; for surveys, see [41, 178].

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 9. Hypoenergetic and Strongly Hypoenergetic Graphs

Abstract

A graph on n vertices, whose energy is less than n, i.e., ℰ(G) < n, is said to be hypoenergetic. Graphs for which ℰ(G) ≥ n are said to be nonhypoenergetic. In [441], a strongly hypoenergetic graph is defined to be a (connected) graph G of order n satisfying ℰ(G) < n − 1. In what follows, for obvious reasons, we assume that all graphs considered are connected.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 10. Miscellaneous

Abstract

In this chapter we have collected results on graph energy that could not be outlined elsewhere.

Xueliang Li, Yongtang Shi, Ivan Gutman

Chapter 11. Other Graph Energies

Abstract

Motivated by the large number of interesting and nontrivial mathematical results that have been obtained for the graph energy, several other energy-like quantities were proposed and studied in the recent mathematical and mathematico–chemical literature. These are listed and briefly outlined in this chapter. Details of the theory of the main alternative graph energies can be found in the references quoted, bearing in mind that research along these lines is currently very active, and new papers/results appear on an almost weekly basis.

Xueliang Li, Yongtang Shi, Ivan Gutman

Backmatter

Titel: Graph Energy
verfasst von: Xueliang Li
Yongtang Shi
Ivan Gutman
Verlag: Springer New York
Electronic ISBN: 978-1-4614-4220-2
Print ISBN: 978-1-4614-4219-6
DOI: https://doi.org/10.1007/978-1-4614-4220-2