Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 99–105
HL-index of a graph
Gašper Jaklič
FMF and IMFM, University of Ljubljana, and PINT, University of Primorska
Jadranska 19, 1000 Ljubljana, Slovenia
Patrick W. Fowler
Department of Chemistry, University of Sheffield, Sheffield S3 7HF, UK
Tomaž Pisanski
FMF and IMFM, University of Ljubljana, and PINT, University of Primorska
Jadranska 19, 1000 Ljubljana, Slovenia
Received 15 November 2010, accepted 26 April 2011, published online 12 December 2011
Abstract
Let G be a simple, connected graph with n vertices and eigenvalues λ1 > λ2 ≥ . . . ≥
λn. If n is even, define H = n/2 and L = H + 1. If n is odd, define H = L = (n+ 1)/2.
Define the HL-index of G to be R(G) = max(|λH |, |λL|). The eigenvalues λH and λL
appear in chemical graph theory in the study of molecular stability. In this paper, bounds on
HL-index for chemical and general graphs are studied. It is shown that there exist graphs
with arbitrarily large HL-index.
Keywords: HL-index, graph spectrum, HOMO-LUMO map.
Math. Subj. Class.: 15A18, 05C50, 05C90
1 Introduction
First, recall the definition of the graph spectrum. Let G be a simple, connected graph on
n vertices and A(G) its adjacency matrix. The collection of eigenvalues of A(G) is called
the spectrum, spec(G), of G. Since A(G) is a symmetric matrix, its spectrum is real and
can be described as follows: spec(G) = {λ1, λ2, . . . , λn}, where λ1 > λ2 ≥ . . . ≥ λn.
SinceA(G) has a zero diagonal,
∑
i λi = 0. To indicate eigenvalue multiplicities, spec(G)
can be rewritten as
spec(G) = {[µ1]a1 , [µ2]a2 , . . . , [µs]as} ,
E-mail addresses: gasper.jaklic@fmf.uni-lj.si (Gašper Jaklič), P.W.Fowler@sheffield.ac.uk (Patrick W.
Fowler), tomaz.pisanski@fmf.uni-lj.si (Tomaž Pisanski)
Copyright c© 2012 DMFA Slovenije
100 Ars Math. Contemp. 5 (2012) 99–105
where µ1 > µ2 > . . . > µs are distinct eigenvalues of A(G) and a1, a2, . . . , as are their
multiplicities. Note that a1 = 1 for connected graphs, since they have a simple principal
eigenvalue.
In linear algebra and in spectral graph theory, particular attention is paid to the prin-
cipal (Perron) eigenvalue λ1. In graph theory, the minimal eigenvalue λn and the second
eigenvalue, λ2, have also been studied. Apart from classical bounds, not much is known in
general about the remaining eigenvalues, although there has been a great deal of work on
spectra of specific classes of graphs of importance in chemistry and elsewhere [4, 10, 5, 3].
In theoretical chemistry the middle eigenvalues play an important role in the Hückel
model of π-electron systems. For even n we define H := n/2 and L := H + 1. If
n is odd, we define H := L := (n + 1)/2. In chemical graph theory, the eigenvalue
difference λH − λL is called the HOMO-LUMO gap of G and is related to the kinetic
stability of a molecule. HOMO and LUMO denote Highest Occupied Molecular Orbital
and Lowest Unoccupied Molecular Orbital, respectively. There is a direct correspondence
between eigenvalues and the corresponding eigenvectors of the molecular graph and the
orbital energies and molecular orbitals in the Hückel model.
Given the set of eigenvalues, the ground-state electron configuration of the molecule
and hence of the graph is determined by application of three rules: the Aufbau Principle
(fill orbitals in order of decreasing eigenvalue), the Pauli Principle (no orbital may contain
more than two electrons), and Hund’s Rule of Maximum Multiplicity (no orbital receives a
second electron before all orbitals degenerate with it have each received one). A molecule
and its graph are open shell if any orbitals/eigenvectors are partially occupied, and closed
shell otherwise. For neutral molecules, the order of the molecular graph, n, is equal to the
number of electrons in the π system. The (fully or partly) occupied orbital of highest energy
(corresponding to eigenvalue λH ) is the HOMO. The (partly or fully) occupied orbital
of lowest energy (corresponding to eigenvalue λL) is the LUMO. If there are partially
occupied orbitals, HOMO and LUMO coincide; a partially occupied orbital is also known
as a SOMO (singly occupied molecular orbital).
The pair of HOMO-LUMO eigenvalues (λH , λL) may be represented as a point in
a plane. Thus, for a family of graphs G we get a set of points. Such a diagram in the
HOMO-LUMO plane is called the HOMO-LUMO map of G (see [7, 8]). Furthermore,
the right triangle TC with vertices (−1,−1), (1,−1), (1, 1) is called the chemical triangle.
A connected graph with maximum valence at most 3 is a chemical graph. Experimental
evidence shows that most chemical graphs are mapped into the chemical triangle [7]. For
instance, in [8] the authors verify this for many fullerenes ([9]), and in particular, it can
be proved to be true for chemical trees, i.e., trees with maximal valence ≤ 3. However, it
is not true that all chemical graphs possess this property. The smallest counterexample is
the Heawood graph, a well-known 3-regular graph that is the Levi graph of the Fano plane,
the 6-cage, and the skeleton of the smallest “polyhedral” polyhex torus. Its spectrum is:{
[3]1, [
√
2]6, [−
√
2]6, [−3]1
}
(see, e.g., [1, 2]). Hence the Heawood graph falls outside the
chemical triangle TC . So far, this is the only chemical graph that we know to fall outside
TC . Exhaustive search reveals no other example with 19 or fewer vertices, and no other
exception amongst 3-regular graphs with 24 or fewer vertices. Once the degree constraint
is relaxed, graphs G with R(G) > 1 appear in large numbers (2 for n = 6, 119 for n = 8,
37 for n = 9, 151062 for n = 10, see [7]).
The HOMO-LUMO radius or HL-index ([7]) is defined as
R(G) := max {|λH |, |λL|} .
G. Jaklič, P. W. Fowler and T. Pisanski: HL-index of a graph 101
The theorem about chemical trees can be restated as follows.
Theorem 1.1 ([7]). For each chemical tree T , the HL-index is bounded by 1,
R(T ) ≤ 1.
For general graphs, no such bound is known. By the Gerschgorin and Cauchy interlac-
ing theorems one can easily prove that the HL-index of a graph is bounded by its maximal
degree or the average valence [4]. For bipartite and pseudo-bipartite graphs, tighter bounds
were obtained in [7]. (A pseudo-bipartite graph is not bipartite, but like a bipartite graph it
has λH = −λL.)
Theorem 1.2 ([7]). Let G be a bipartite or pseudo-bipartite graph with n vertices and m
edges, and let d̄ := 2m/n denote its average degree. Then
0 ≤ R(G) ≤
√
d̄.
Thus, in particular, if G is a chemical bipartite or pseudo-bipartite graph,
0 ≤ R(G) ≤
√
3.
Now let G be a family of graphs. Define the HL-index of G, R(G), to be the maximum
value of R(G) for G ∈ G.
Theorem 1.3. Let GD be the family of graphs with maximal degree at most D. Then
0 ≤ R(GD) ≤ D.
The equality in the lower bound is reached for many graphs, whilst the equality in the upper
bound is reached only for the complete graph K2.
Proof. The lower bound is obvious from the non-negativity of the HL-index. The equality
is reached for the complete bipartite graph K2,2, amongst many others. The Gerschgorin
theorem yields the upper bound. Here, equality is obviously reached for the complete graph
on 2 vertices K2. There are no other such graphs. In such a case, the absolute value of the
“middle” eigenvalue λH or λL should be D. But since |λi| ≤ D for all i, at least half of
the eigenvalues should be equal to D or −D. Since by the Perron-Frobenius theorem for
simple connected graphs the Perron eigenvalue is simple, this is possible only for n = 2
and the graph K2.
Since for the Heawood graphG, R(G) =
√
2, the upper bound is in general at least
√
2
and less than 3 for chemical graphs.
Theorem 1.4. Let C = G3 be the family of chemical graphs. Then
√
2 ≤ R(C) < 3.
102 Ars Math. Contemp. 5 (2012) 99–105
2 Main result
The HL-index of a family of graphs is bounded from above by a function of its maximum
degree. Here we show that the HL-index may be arbitrarily large.
Theorem 2.1. For each positive constant K > 0 there exists a connected graph G(K)
such that the HL-index of G(K) is greater than K,
R(G(K)) > K.
Proof. We will use Paley graphs and their spectral properties (see, e.g., [1, 2]). Let q = pm
be a prime power of the form q = 4t + 1, t ∈ N. The graph P (q) is defined on the finite
field F (q) with q elements. Its vertex set is F (q), and two vertices are adjacent if and only
if their difference is a square in the field. The Paley graph P (q) is self-complementary and
strongly regular. The eigenvalues of the Paley graph P (q) are{[
q − 1
2
]1
,
[
−1 +√q
2
] q−1
2
,
[
−1−√q
2
] q−1
2
}
.
Hence R(P (q)) = λH = λL = (
√
q − 1)/2. Take q > (2K + 1)2, and the proof is
concluded.
A Paley graph has an odd number of vertices and hence λH = λL by definition. One
can ask a natural question: Is it possible to find a sequence of even-order connected graphs
with increasing HL-index? The answer to this question is in the affirmative.
For instance, take any connected, regular, bipartite graph G that has exactly 4 distinct
eigenvalues. Cvetković, Doob, and Sachs [4, p. 166] proved that G has to be a Levi graph
of a symmetric 2− (v, k, λ) design. Its spectrum is (see [6]){
[k]1,
[√
k − λ
]v−1
,
[
−
√
k − λ
]v−1
, [−k]1
}
,
and therefore its HL-index is equal to
√
k − λ. For k = n + 1, v = n2 + n + 1, λ = 1,
the designs are finite projective planes, which exist for prime powers n = pm. Hence√
k − λ =
√
n is arbitrarily large.
3 Questions
Let us conclude the paper with some interesting questions.
1. Is the Heawood graph the only chemical graph outside the chemical triangle TC?
2. Let C = G3 be the family of chemical graphs. By Thm. 1.4,
√
2 ≤ R(C) < 3. How
large can R(C) be?
3. It would be interesting to determine the graphs G on n vertices with maximal HL-
index R(G). For small numbers of vertices, n, the graphs maximizing R(G) (or if
there are many, the numbers of such graphs) are listed in Table 1, and examples are
shown in Figure 1.
Here G6,1 is the pentagonal pyramid (wheel with 5 spokes), G8,1 is the two-dimen-
sional subdivision of the tetrahedron, and G10,1 is the complement of the Petersen
G. Jaklič, P. W. Fowler and T. Pisanski: HL-index of a graph 103
n R(G) graphs
2 1 K2
3 1 K3
4 1 K4 − e,K4
5 1 G5,1, G5,2, G5,3, G5,4, G5,5 = K5
6
√
6− 1 G6,1
7 1 109 graphs, the one with most edges being K7
8 φ = (1 +
√
5)/2 G8,1
9
√
2 G9,1, G9,2, G9,3
10 2 G10,1
Table 1: Graphs on n vertices with maximal HL-index.
graph. When the maximal HL-index for a given n is equal to 1, the complete graph
Kn achieves that maximum (as spec(Kn) = {[n− 1]1, [−1]n−1}), and clearly is the
unique graph with the maximal number of edges m that does so.
4. Determine the graphs G with n vertices and m edges with maximal HL-index R(G).
5. Since the number of adjacency matrices of chemical graphs is countable, the same
holds for the image of the HOMO-LUMO map. Does there exist a simply connected
region with positive area in the chemical triangle that contains no points (λH , λL)?
4 Acknowledgements
GJ and TP thank ARRS for a grant P1-294. PWF thanks the Royal Society for an award
under the RS/Wolfson Research Merit Scheme. TP thanks Peter Šemrl for a fruitful dis-
cussion.
104 Ars Math. Contemp. 5 (2012) 99–105
G5,1 G5,2 G5,3
G5,4 G5,5
G8,1
G9,1 G9,2 G9,3
G10,1
G6,1
Figure 1: Graphs Gn,i with maximal HL-index.
G. Jaklič, P. W. Fowler and T. Pisanski: HL-index of a graph 105
References
[1] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular Graphs, Ergebnisse der Math-
ematik 3.18, Springer, Heidelberg, 1989.
[2] A. E. Brouwer, Graph descriptions, http://www.win.tue.nl/˜aeb/graphs/
index.html, (last accessed 12.11.2010).
[3] F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics,
American Mathematical Society, 1997.
[4] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, V.E.B. Deutscher Verlag der
Wissenschaften, Berlin, 1979.
[5] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra,
London Mathematical Society Student Texts, Cambridge University Press, 2009.
[6] E. R. van Dam, Regular graphs with four eigenvalues, Linear Algebra Appl. 226-228 (1995)
139–162.
[7] P. W. Fowler and T. Pisanski, HOMO-LUMO maps for chemical graphs, MATCH Commun.
Math. Comput. Chem. 64 (2010), 373–390.
[8] P. W. Fowler and T. Pisanski, HOMO-LUMO maps for fullerenes, Acta Chim. Slov., 57 (2010),
513–517.
[9] P. W. Fowler and T. Pisanski, Leapfrog fullerenes and Clar polyhedra, J. Chem. Soc., Faraday
Trans. 90 (1994), 2865–2871.
[10] I. Gutman and O. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin,
1986.