Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 261–278
Interlacing–extremal graphs∗
Irene Sciriha †, Mark Debono , Martha Borg
Department of Mathematics, Faculty of Science, University of Malta, Msida, Malta
Patrick W. Fowler , Barry T. Pickup
Department of Chemistry, Faculty of Science, University of Sheffield, Sheffield S3 7HF, UK
Received 18 November 2011, accepted 13 September 2012, published online 19 November 2012
Abstract
A graph G is singular if the zero-one adjacency matrix has the eigenvalue zero. The
multiplicity of the eigenvalue zero is called the nullity of G. For two vertices y and z of G,
we call (G, y, z) a device with respect to y and z. The nullities of G, G − y, G − z and
G−y− z classify devices into different kinds. We identify two particular classes of graphs
that correspond to distinct kinds. In the first, the devices have the minimum allowed value
for the nullity of G− y − z relative to that of G for all pairs of distinct vertices y and z of
G. In the second, the nullity of G− y reaches the maximum possible for all vertices y in a
graph G. We focus on the non–singular devices of the second kind.
Keywords: Adjacency matrix, singular graphs, nut graphs, uniform–core graphs, nuciferous graphs,
interlacing.
Math. Subj. Class.: 05C50,05C35, 05C60, 05B20, 92E10, 74E40
1 Introduction
A graphG = G(V, E) of order n has a labelled vertex set V = {1, 2, ..., n}. The set E ofm
edges consists of unordered pairs of adjacent vertices. We write V(G) for a graph G when
the graph G needs to be specified. A subset of V is said to be independent if no two of its
vertices are adjacent, i.e., no two are connected by an edge. For a subset V1 of V , G − V1
denotes the subgraph of G induced by V\V1. The subgraph of G obtained by deleting a
particular vertex y is denoted by G − y and that obtained by deleting two distinct vertices
∗This research was supported by the Research Project Funds MATRP01-02 Graph Spectra and Fullerene
Molecular Structures of the University of Malta.
†Corresponding Author, http://staff.um.edu.mt/isci1/
E-mail addresses: irene.sciriha-aquilina@um.edu.mt (Irene Sciriha), debonomark@gmail.com (Mark
Debono), bambinazghira@gmail.com (Martha Borg), P.W.Fowler@sheffield.ac.uk (Patrick W. Fowler),
b.t.pickup@sheffield.ac.uk (Barry T. Pickup)
Copyright c© 2013 DMFA Slovenije
262 Ars Math. Contemp. 6 (2013) 261–278
y and z is denoted by G− y − z. A graph is said to be bipartite if its vertex set V may be
partitioned into two independent subsets V1 and V2. The cycle and the complete graph on
n vertices are denoted by Cn and Kn, respectively. The complete bipartite graph Kn1,n2
has a vertex partition into two subsets V1 and V2 of independent vertices of sizes n1 and
n2, respectively, and has edges between each member of V1 and each member of V2.
1.1 The adjacency matrix
The graphs we consider are simple, that is, without loops or multiple edges. We use A(G)
(or just A when the context is clear) to denote the 0-1 adjacency matrix of a graph G,
where the entry aik of the symmetric matrix A is 1 if {i, k} ∈ E and 0 otherwise. We note
that the graph G is determined, up to isomorphism, by A. The adjacency matrix AC of
the complement GC of G is J− I−A, where each entry of J is one and I is the identity
matrix. The degree of a vertex i is the number of non–zero entries in the ith row of A. If
the adjacency matrix A of a n-vertex graph G satisfies Ax = λx for some non-zero vector
x then x is said to be an eigenvector belonging to the eigenvalue λ. There are n linearly
independent eigenvectors. The eigenvalues of A are said to be the eigenvalues of G and to
form the spectrum of G. They are obtained as the roots of the characteristic polynomial
φ(G,λ) of the adjacency matrix of G, defined as the polynomial det(λI−A) in λ.
Cauchy’s inequalities for a Hermitian matrix M (also collectively known as the In-
terlacing Theorem) place restrictions on the multiplicity of the eigenvalues of principal
submatrices relative to those of M (See [6] for instance). When they are applied to graphs
we have:
Theorem 1.1. Interlacing Theorem: LetG be an n-vertex graph and w ∈ V . If the eigen-
values of G are λ1, λ2, . . . , λn and those of G − w are ξ1, ξ2, . . . , ξn−1, both in non-
increasing order, then λ1 ≥ ξ1 ≥ λ2 ≥ ξ2 ≥ . . . ≥ ξn−1 ≥ λn.
1.2 Cores of singular graphs
For the linear transformation A, the kernel, ker(A), of A is defined as the subspace of Rn
mapped to zero by A. It is also referred to as the nullspace of A. A graph G is said to be
singular of nullity ηG if the dimension of the nullspace ker(A) of A is ηG and ηG > 0. If
there exists a non-zero vector x in the nullspace of the adjacency matrix A, then x is said
to be a kernel eigenvector of the singular graph G and satisfies Ax = 0. It is therefore an
eigenvector of A for the eigenvalue zero whose multiplicity ηG is also the number of roots
of φ(G,λ) equal to zero. A vertex corresponding to a non-zero entry of x is said to be a
core vertex CV of G. The core vertices corresponding to x induce a subgraph of G termed
the core of G with respect to x. The core structure of a singular graph will be the basis of
our classification of all graphs relative to ηG.
A core graph is a singular graph in which every vertex is a core vertex. The empty
graph (K4)C and the four cycle C4 are examples of 4–vertex core graphs of nullity four
and two, respectively. A core graph of order at least three and nullity one is known as a nut
graph. It is connected and non–bipartite [12].
For singular graphs, the vertices can be partitioned into core and core-forbidden ver-
tices. The set CV of core vertices consists of those vertices lying on some core of G. A
core-forbidden vertex (CFV) corresponds to a zero entry in every kernel eigenvector. The
set V\CV is the set of CFVs. It follows that, in a core graph, the set of CFVs is empty.
I. Sciriha et al.: Interlacing–extremal graphs 263
Let y and z be two distinct vertices of a graph G. By interlacing, when a vertex y or z
is deleted from G, the nullity ηG−y or ηG−z , that is the multiplicity of the eigenvalue zero
of G − y or G − z, respectively, may take one of three values from ηG − 1 to ηG + 1. If
the two distinct vertices y and z are deleted, then the nullity ηG−y−z of G − y − z may
take values in the range from ηG − 2 to ηG +2. Let us call the graph having two particular
distinct vertices y and z a device (G, y, z). The set of devices can be partitioned into three
main varieties, namely variety 1 when both vertices are CVs, variety 2 when one vertex is a
CFV and one a CV and variety 3 when both vertices are CFVs. A device (G, y, z) is said
to be of kind (ηG, ηG−y, ηG−z, ηG−y−z). Since ηG−y and ηG−z can take three values each
and ηG−y−z can take five values, there are potentially 45 kinds of graphs relative to ηG.
Interlacing further restricts the values of ηG−y−z . Moreover, there are kinds of graphs that
exclude certain combinatorial properties, such as that of being bipartite, as we shall see in
Section 5. In Section 2, we express the characteristic polynomial of φ(G−y, λ) as the sum
of two terms in ληG and ληG − 1 with coefficients fa(λ) and fb(λ), respectively, each of
which is a polynomial expanded in terms of the entries of the eigenvectors of A forming an
orthonormal basis for Rn. By comparing the diagonal entries of the adjugate of (λI −A)
and of the spectral decomposition of (λI − A)−1 we obtain, in Section 3, an expression
for φ(G− y − z) as the sum of three terms in ληG , ληG − 1 , ληG − 2, respectively, with
polynomial coefficients. Moreover, the well known Jacobi’s identity (see, for instance,
[4]), relating the entries of the adjugate of (λI−A) with the characteristic polynomials of
a graph G and those of particular subgraphs of G, is used to determine which kinds are not
realized by any graph G.
In Section 4, the vertices of a graph are partitioned into three subsets of type lower,
middle or upper, respectively, according to the vanishing or otherwise of fa(0) and fb(0).
The Interlacing Theorem and Jacobi’s identity impose restrictions on the 45 kinds, so that
not all are possible. In Sections 5 and 6, we show why there exist exactly twelve kinds of
device (G, y, z) and how they are partitioned into the three main varieties. In Section 7,
we identify two interesting classes of graphs that in a certain sense have extremal nullities.
The first one has the minimum possible nullity ηG−y−z , that is ηG − 2, for all pairs of
distinct vertices y and z in a graph G. A graph G in the second class has the maximum
possible nullity ηG−y , that is ηG + 1, for all vertices y of G. We show that devices within
the second class can reach the maximum allowed ηG + 2 for the nullity ηG−y−z for some
but not for all pairs of distinct vertices y and z in a graph G. A characterization is given of
the non–singular devices within the second class having the inverse A−1 of the adjacency
matrix A with zero entries only on the diagonal.
2 Characteristic polynomials
We first need to define some necessary notation.
Associated with the n× n adjacency matrix A of a n–vertex graph of nullity ηG, there
is an ordered orthonormal basis xr, 1 ≤ r ≤ n, for Rn, consisting of eigenvectors of A,
with the ηG eigenvectors in the nullspace being labelled first. Let the n× 1 column vector
264 Ars Math. Contemp. 6 (2013) 261–278
xr be (xry), where for vertex y, 1 ≤ y ≤ n. If
P =

x11 x
2
1 · · · xn1
x12 x
2
2 · · · xn2
...
...
...
...
x1n x
2
n · · · xnn
 ,
where the ith column of P is the eigenvector xi belonging to the eigenvalue λi in the
spectrum of A, diagonalization of A is given by P−1AP = D[λi], where D[λi] is the
diagonal matrix having λi as the ith entry on the main diagonal. Expressing A in terms
of D and P leads to the spectral decomposition theorem, which can also be applied to
(λI−A)−1. This leads to an expression for the characteristic polynomial of the adjacency
matrix φ(G − y, λ) of G − y which is given explicitly in terms of the eigenvector entries
{xiy}. Together with Jacobi’s identity, it will serve as a basis for the characterization of
graphs according to those kinds that can exist.
Lemma 2.1.
φ(G− y, λ) =
n∑
i=1
(xiy)
2
(λ− λi)
φ(G,λ).
Proof. The characteristic polynomial of the adjacency matrix φ(G− y, λ) of G− y is the
yth diagonal entry (adj(λI−A))yy of the adjugate of (λI−A). For arbitrary λ, the matrix
(λI−A) is invertible and φ(G−y, λ) = ((λI−A)−1)yyφ(G,λ). Since P−1AP = D[λi],
it follows that
adj(λI−A)
φ(G,λ)
= (λI−A)−1 = PD[ 1
λ− λi
]P−1.
Taking the yth diagonal entry,
φ(G− y, λ)
φ(G,λ)
= (x1y x
2
y · · ·xny )D[
1
λ− λi
]

x1y
x2y
...
xny

=
n∑
i=1
(xiy)
2
(λ− λi)
. (2.1)
For a graph G with adjacency matrix A of nullity ηG, let s(λ) denote φ(G,λ). If the
spectrum of A is λ1, λ2, · · · , λn, starting with the zero eigenvalues (if any), we write
s(λ) =
n∏
`=1
(λ− λ`) = ληGs0(λ) with s0(0) 6= 0. (2.2)
Partitioning the range of summation in Equation (2.1),
φ(G− y, λ)
φ(G,λ)
=
ηG∑
i=1
(xiy)
2
λ
+
n∑
i=ηG+1
(xiy)
2
λ− λi
I. Sciriha et al.: Interlacing–extremal graphs 265
Hence
φ(G− y, λ) =
ηG∑
k=1
(xky)
2s0(λ)λ
ηG−1 +
n∑
k=ηG+1
(xky)
2s0(λ)λ
ηG
λ− λk
(2.3)
which we shall express as
φ(G− y, λ) = fbληG−1 + faληG . (2.4)
3 Jacobi’s Identity
Relative to (G, y, z), let us denote by j(λ), or j, the entry of the adjugate adj(λI−A)
in the yz position, obtained by taking the determinant of the submatrix of (λI−A) after
deleting row y and column z and multiplying it by (−1)y+z . We use the convention that
ηG−y ≥ ηG−z . Throughout the paper, where the context is clear, we may write s0 for
s0(λ), j for j(λ), etc.
Let s(λ), t(λ), u(λ), v(λ), often referred to simply as s, t, u and v respectively, be the
characteristic polynomials φ(G,λ), φ((G−y), λ), φ((G− z), λ), φ((G−y− z), λ) of the
graphs G, G− y, G− z and G− y − z, respectively, that is, the determinants
s(λ) = det(λI−A(G))
t(λ) = det(λI−A(G− y))
u(λ) = det(λI−A(G− z))
v(λ) = det(λI−A(G− y − z)). (3.1)
From Lemma 2.1,
t(λ) =
n∑
k=1
(xk
y
)2
∏
` 6=k
(λ− λ`) (3.2)
and
u(λ) =
n∑
k=1
(xk
z
)2
∏
` 6=k
(λ− λ`). (3.3)
We shall see that the characteristic polynomial v(λ) of G− y− z can also be expressed
in terms of the eigenvector entries {xry} and {xrz} associated with distinct vertices y and z.
Lemma 3.1. For y 6= z, Jacobi’s identity expresses the entry j of the adjugate of λI−A
in the yz position, for a symmetric matrix A, in terms of the characteristic polynomials s,
u, t and v:
j2 = ut− sv
Expressing Equations (3.2) and (3.3) as in (2.4),
t(λ) =
ηG∑
k=1
(xky)
2s0(λ)λ
ηG−1 +
n∑
k=ηG+1
(xky)
2s0(λ)λ
ηG
λ− λk
= tbλ
ηG−1 + taλ
ηG , (3.4)
and
u(λ) =
ηG∑
k=1
(xkz)
2s0(λ)λ
ηG−1 +
n∑
k=ηG+1
(xkz)
2s0(λ)λ
ηG
λ− λk
(3.5)
266 Ars Math. Contemp. 6 (2013) 261–278
= ubλ
ηG−1 + uaλ
ηG
Now we consider pairs of vertices of G.
Since
adj(λI −A)
φ(G,λ)
= (λI −A)−1 = PD[ 1
λ− λi
]P−1,
j(λ) =
n∑
k=1
(xk
y
xk
z
)
∏
` 6=k
(λ− λ`.) (3.6)
We can write
j(λ) =
ηG∑
k=1
xkyx
k
zs0(λ)λ
ηG−1 +
n∑
k=ηG+1
xkyx
k
zs0(λ)λ
ηG
λ− λk
(3.7)
= jbλ
ηG−1 + jaλ
ηG
The characteristic polynomial v(λ) can be written as v(λ) =
u(λ)t(λ)− j2(λ)
s(λ)
,
that is v(λ) = vaληG + vbληG−1 + vcληG−2, where
vc =
1
s0
(ubtb − j2b ) =
1
2
s0
ηG∑
i=1
ηG∑
`=1
(xizx
`
y − x`zxiy)2
vb =
1
s0
(uatb + ubta − 2jajb) = s0
ηG∑
i=1
n∑
`=ηG+1
(xizx
`
y − xiyx`z)2
λ− λ`
va =
1
s0
(uata − j2a) =
1
2
s0
n∑
i=ηG+1
n∑
`=ηG+1
(xiyx
`
z − x`yxiz)2
(λ− λi)(λ− λ`)
(3.8)
4 Three types of vertex
By interlacing, we can identify three types of vertex according to the effect on the nullity
on deletion. We call a vertex y lower, middle or upper if the nullity of G− y is ηG − 1, ηG
or ηG + 1, respectively. We shall distinguish among these three types of vertex according
to the values of the functions fa and fb in Equation (2.4).
In Table 1 we show the entries of the orthonormal eigenvectors {xr} in an ordered basis
for Rn as presented in Section 2. We choose a vertex labelling such that the core vertices
are labelled first. Note the zero submatrix corresponding to the CFVs.
We consider
φ(G− y, λ)
s0ληG
from Equation 2.3. It has poles at λ = µi, 1 ≤ i ≤ h, where,
for 1 ≤ i ≤ h, the µi are the h distinct non-zero eigenvalues of G. Moreover, the gradient
of
n∑
k=ηG+1
(xky)
2
λ− λk
is less than 0 for all λ 6= µi. It follows that
φ(G− y, λ)
s0ληG
has at most
(h − 1) roots strictly interlacing the h distinct eigenvalues of A. Note that
ηG∑
k=1
(xky)
2 ≥ 0
with equality if and only if y is a CFV. Thus at λ = 0, fb is non–zero if y is a CV and zero
I. Sciriha et al.: Interlacing–extremal graphs 267
hhhhhhhhhhhhhhhvertex-entries
eigenvector
x1 . . . xηG xηG+1 . . . xn
x1 ∗ . . . ∗ ∗ . . . ∗
x2 ∗ . . . ∗ ∗ . . . ∗
... ∗ . . . ∗ ∗ . . . ∗
x|CV | ∗ . . . ∗ ∗ . . . ∗
x|CV |+1 0 . . . 0 ∗ . . . ∗
...
...
...
...
...
...
...
xn 0 . . . 0 ∗ . . . ∗
Table 1: Ordered orthonormal basis of eigenvectors of A with * representing a possibly
non–zero entry.
if it is a CFV. For a CFV y,
n∑
k=ηG+1
(xky)
2
λ− λk
vanishes at λ = 0 when y is upper, and does
not vanish when y is middle. Note that when
ηG∑
k=1
(xky)
2 = 0, one of the (h− 1) interlacing
roots may be zero. (†)
Different cases occur depending on the vanishing or otherwise of the real constant
ηG∑
k=1
(xky)
2 and
n∑
k=ηG+1
(xky)
2
λ− λk
at λ = 0. Equation (2.3) and the analysis in the previous
paragraph (marked (†)) lead to the result that ηG − 1 ≤ ηG−y ≤ ηG + 1. This can be
generalized for the multiplicity of any eigenvalue of G other than zero by replacing the
cores and the nullspace of G by the µi–cores and µi–eigenspace of G (concepts introduced
in [10]), thus giving another proof of the Interlacing Theorem.
Proposition 4.1. The values of fb and fa of Expression (2.4) for φ(G − y, λ) at λ = 0
distinguish the three types of vertex as follows:
Vertex y Status of y The values of fb and fa
Lower CV fb(0) 6= 0
Middle CF fb(0) = 0 and fa(0) 6= 0
Upper CFV fb(0) = 0 and fa(0) = 0
Proof. Let y be a core vertex of a graph of nullity ηG > 0. There exists xky 6= 0 for some
k, 1 ≤ k ≤ ηG. Then fb(0) 6= 0, which is a necessary and sufficient condition for the
multiplicity of the eigenvalue zero to be ηG − 1 for G− y. It follows that a vertex is lower
if and only if it is a CV.
If y is a CFV, then fb(0) = 0. For G − y, the multiplicity of the eigenvalue zero is at
least ηG. If one of the roots of
n∑
k=ηG+1
(xky)
2
λ− λk
is zero, then λ divides
n∑
k=ηG+1
(xky)
2
λ− λk
, the
multiplicity of the eigenvalue zero is exactly ηG + 1 for G − y and the vertex y is upper.
Otherwise the multiplicity of the eigenvalue zero remains ηG for G− y and the vertex y is
middle.
268 Ars Math. Contemp. 6 (2013) 261–278
We consider three varieties of devices {(G, y, z)} with pairs (y, z) of vertices, namely
variety 1 with both y and z being CVs, variety 2 with z being a CV and y a CFV and variety
3 with both y and z being CFVs. Since a CFV can be upper or middle, varieties 2 and 3
are subdivided further, as seen in Table 3.
From Proposition 4.1,
for variety 1, ub 6= 0; tb 6= 0;
for variety 2, ub 6= 0; jb = tb = vc = 0;
for variety 3: ub = jb = tb = vb = vc = 0.
Some of these varieties can be further subdivided according to the values at λ = 0
of vc, vb and va or ja. From Proposition 4.1, tb(0) 6= 0 if and only if y is a core vertex.
Similarly ub 6= 0 if and only if z is a core vertex. If at least one of z or y is core forbidden,
then jb(0) = 0. However, there are ‘accidental’ cases where jb(0) vanishes when both z
and y are CVs, for example in C4 andK2,3 if the vertices y and z are connected by an edge.
Indeed this is true for all bipartite core graphs of nullity at least two, since each of u and t
has zero as a root. It follows that E2η is a factor of j2 = ut − sv = (jbEη−1 + jaEη)2
and therefore jb(0) = 0.
5 Restrictions on the nullity of G − y − z
It is our aim to classify all graphs according to their kind defined by the quadruple
(ηG, ηG−y, ηG−z, ηG−y−z).
Not all the 45 kinds mentioned in Section 1 exist, as we shall discover. The classification
will be given in Table 3 on Page 272. It is best possible since each kind is realized by some
graph.
5.1 Restrictions arising from interlacing
In a device (G, y, z) of kind (ηG, ηG−y, ηG−z, ηG−y−z), interlacing restricts the values that
ηG−y−z can take. The following result shows an instance when ηG−y−z is determined by
interlacing alone.
Lemma 5.1. For (ηG, ηG−y, ηG−z, ηG−y−z) = (ηG, ηG +1, ηG − 1, ηG−y−z), the nullity
ηG−y−z of G− y − z is ηG.
Hence, (ηG, ηG + 1, ηG − 1, ηG) is the only kind where the nullities ηG−y and ηG−z
differ by two. We say that it belongs to variety 2a.
In kinds where the nullities ηG−y and ηG−z differ by one, interlacing allows ηG−y−z
to take either the value ηG−y or ηG−z . All three possible values of ηG−y−z are allowed by
interlacing when ηG−y = ηG−z .
The symmetry about zero of the spectrum of a bipartite graph G (See for instance [8])
requires that the number of zero eigenvalues is 2k, if G has an even number of vertices and
2k+1 if G has an odd number of vertices, for some k ≥ 0. This implies that on deleting a
vertex from a bipartite graph, the nullity changes parity. Therefore if the nullity of a graph
G and of its vertex–deleted subgraph G − y are the same, then G is not bipartite. Since
on deleting a vertex a bipartite graph remains bipartite, it follows that a graph G of a kind
where ηG = ηG−y or ηG−y = ηG−y−z cannot be bipartite.
Lemma 5.2. If a vertex of a graph is middle, then the graph is not bipartite.
Figure 1 shows a device (G, y, z) with a middle vertex z which becomes upper inG−y.
I. Sciriha et al.: Interlacing–extremal graphs 269
Figure 1: A graph with two middle vertices y and z.
5.2 Restrictions arising from Jacobi’s Identity
Lemma 3.1 requires that ut− sv which is j2 has 2k, k ≥ 0, zero roots. Let gf denote the
number of zero roots of the real function f . Therefore, for kinds of graph that imply
(i) gut = gsv − 1 and gu 6= gt
or (ii) gut = gsv + 1 and gu = gt,
there is a contradiction and those kinds of graphs do not exist.
Lemma 5.3. The following kinds of graphs do not exist:
(i) (ηG, ηG, ηG − 1, ηG);
(ii) (ηG, ηG + 1, ηG + 1, ηG + 1);
(iii) (ηG, ηG, ηG, ηG − 1).
Furthermore, if gut = gsv and gut is odd, then a graph of that kind exists if ut − sv is
zero at λ = 0, otherwise j2 would have an odd number of zeros. Therefore, if gut = gsv
and gut is odd, jb = 0 at λ = 0.
Lemma 5.4. Graphs with gut = gsv and gut odd exist provided jb = 0 at λ = 0. They are
non–bipartite and of one of the following kinds:
(i) (ηG, ηG, ηG − 1, ηG − 1);
(ii) (ηG, ηG + 1, ηG, ηG + 1).
We shall call kinds (i) and (ii), in Lemma 5.4 above, variety 2b and 3b(i), respectively
(See Table 3).
Lemma 5.5. If (G, y, z) is a singular graph with gut < gsv and gsv odd, then (G, y, z) is
non–bipartite and of kind (ηG, ηG − 1, ηG − 1, ηG − 1).
Proof. If y and z are CVs, gut < gsv , then (ηG, ηG−y, ηG−z, ηG−y−z) is
(i) (ηG, ηG − 1, ηG − 1, ηG) or
(ii) (ηG, ηG − 1, ηG − 1, ηG − 1).
Now if furthermore, gsv is given to be odd, then ηG−y−z = ηG − 1. It follows that
ηG−y = ηG−y−z Therefore, G is not bipartite.
We shall call the graphs in Lemma 5.5 above, variety 1(iii) (See Table 3).
6 Kinds of graphs
In this section we determine the properties of a kind (ηG, ηG−y, ηG−z, ηG−y−z) within
each of the three varieties.
270 Ars Math. Contemp. 6 (2013) 261–278
6.1 Graphs of variety 1
Graphs of variety 1, are necessarily singular and therefore have at least one core. There are
at least two vertices in a core.
Lemma 6.1. For a device (G, y, z) of variety 1 and nullity one, jb(0) 6= 0 for core vertices
y and z.
Proof. For ηG = 1, a non-zero column of the adjugate adj(A) is a kernel eigenvector of G
[9]. The non–zero entries occur only at core vertices. Therefore, jb(0) 6= 0.
There are three types of pairs of vertices (CV,CV) for graphs of variety 1, depending
on the nullity of G − y − z. Since ηG ≥ 1 and gu = gt = ηG − 1, then the nullity gv of
G− y− z can take any of the three values ηG− 2, ηG and ηG− 1, corresponding to variety
1(i), 1(ii) and 1(iii), respectively.
Theorem 6.2. For a device (G, y, z) of variety 1(iii), j(0) 6= 0 for core vertices y and z.
Proof. For nullity one the result follows from Lemma 6.1. Now consider a graph with
ηG > 1 of variety 1(iii), that is when gv = ηG − 1. The number of zeros gut of ut is
2ηG− 2 and less than that of sv which is odd. If j2, which is ut− sv, is not to have an odd
number of zeros, it follows, from j = jbληG−1 + jaληG , that jb 6= 0 at λ = 0.
For variety 1(i), the vertices y and z are CVs. Moreover, without loss of generality, the
vertex z is a CV of the subgraph G− y. Only for variety 1(i) is vc 6= 0.
Definition 6.3. The connected graphsG in the devices {(G, y, z)}with all pairs of vertices
(y, z) ∈ V × V being of variety 1(i) are said to form the class of uniform–core graphs.
Equivalently, ηG−y−z = ηG − 2, that is z is a CV of G − y for all vertex pairs (y, z).
It is clear that all vertices of a uniform–core graph are CVs, and that they remain so even
in a vertex–deleted subgraph G − y for any vertex y of G. Note that this is not the case
in general; if y and z are two distinct core vertices of a graph G, then z need not remain a
core vertex of G− y. We shall consider uniform–core graphs in more detail in Section 7.
6.2 Graphs of variety 2
In a device (G, y, z) of variety 2, (y, z) is a mixed vertex pair, that is exactly one vertex z
of the pair (y, z) is a CV.
From Lemmas 5.1 and 5.3, the following result follows immediately.
Proposition 6.4. In a device (G, y, z) of variety 2,
(i) there is only one kind when y is upper, namely kind (ηG, ηG + 1, ηG − 1, ηG) in variety
2a
and (ii) only one kind when y is middle, namely kind (ηG, ηG, ηG − 1, ηG − 1) in variety
2b.
From Lemma 5.2, the graphs of variety 2b are non-bipartite.
Theorem 6.5. In a device (G, y, z) of variety 2b, the term in λ2ηG−1 of j2 is identically
equal to zero.
I. Sciriha et al.: Interlacing–extremal graphs 271
Proof. In variety 2b, a graph is of kind (ηG, ηG, ηG−1, ηG−1). The parameter vc vanishes
and vb(λ) =
ubta
s0
6= 0. The number of zeros of ut is the same as that of sv. Therefore,
j2 = ut− sv has at least 2ηG − 1 zeros. In variety 2b, the term in λ2ηG−1 in its expansion
is ubta − s0vb. Also vc vanishes and vb(λ) =
ubta
s0
6= 0. Hence, s0vb = ubta and the term
in λ2ηG−1 in the expansion of j2 is identically equal to zero, as expected from the fact that
j2 is a perfect square.
The parameter vb distinguishes between a graph in variety 2a and one in variety 2b.
Theorem 6.6. For a graph in variety 2a, vb vanishes at λ = 0. For a graph in variety 2b,
vb 6= 0 at λ = 0.
Proof. For both kinds in variety 2, ub 6= 0. For an upper vertex, ta = 0 at λ = 0 and for
a middle vertex ta 6= 0 at λ = 0. Since s0 6= 0, it follows that for a graph in variety 2a
vb = 0 at λ = 0 and, for a graph in variety 2b, vb 6= 0 at λ = 0.
6.3 Graphs of variety 3
We now consider variety 3 for (CFV,CFV) pairs, when tb, ub, jb, vb and vc all vanish.
Interlacing provides three types of vertex pairs depending on whether a CFV in the pair
(y, z) is upper or middle. When both vertices are upper (variety 3a), by Lemma 5.3 only
variety 3a(i) for gv = ηG and variety 3a(ii), when gv = ηG + 2 are allowed. The values at
λ = 0 of va or ja suffice to distinguish between graphs of variety 3(i) and 3(ii).
Theorem 6.7. For variety 3a(i), both va and ja are non–zero at λ = 0. For variety 3a(ii),
both va and ja vanish at λ = 0.
Proof. For variety 3, vb = 0. Variety 3a(i) is (ηG, ηG + 1, ηG + 1, ηG). Since v = vaληG
and ηG−y−z = ηG, va 6= 0 at λ = 0. Also gj2 = 2ηG so that ja 6= 0 at λ = 0. Variety
3a(ii) is (ηG, ηG+, ηG − 1, ηG − 1). Since gv = ηG + 2, λ2 divides va and λ divides all of
the functions ta, ua and ja.
For variety 3b, one vertex is upper and one is middle. Interlacing allows only gv =
ηG + 1 and ηG, corresponding to variety 3b(i) and variety 3b(ii), respectively. Both vb and
jb vanish at λ = 0. The value of ja at λ = 0 distinguishes between variety 3b(i) and variety
3b(ii).
Theorem 6.8. For variety 3b(i), ja vanishes at λ = 0. For variety 3a(ii), ja is non–zero at
λ = 0.
Proof. For variety 3b(i), λ divides ja, as otherwise ut − sv is not the perfect square j2.
variety 3b(ii) gv = ηG requires ja 6= 0 at λ = 0.
For variety 3c, both vertices are middle. The values at λ = 0 of ta and ua are non–
zero. By Lemma 5.3, gv = ηG + 1 or ηG, corresponding to variety 3c(i) and variety 3c(ii),
respectively.
For variety 3c(ii), when gv = ηG, va is non–zero at λ = 0. Two cases may occur.
Either ja 6= 0 at λ = 0 or the number of zeros of ja is at least one. The former case is
272 Ars Math. Contemp. 6 (2013) 261–278
Vertex y Vertex z variety
1 7 variety 1(i)
1 4 variety 1(ii)
1 2 variety 1(iii)
1 15 variety 2a
1 5 variety 2b
17 18 variety 3a(i)
15 17 variety 3a(ii)
5 15 variety 3b(i)
15 16 variety 3b(ii)
11 16 variety 3c(i)
5 6 variety 3c(iiA)
5 17 variety 3c(iiB)
Table 2: All varieties and kinds for the same graph G illustrated in Figure 2.
denoted by variety 3c(iiA). The latter case is variety 3c(iiB) for which the terms in λ2ηG−2
and in λ2ηG−1 of j2 vanish.
The remaining case is for variety 3c(i) when gv = ηG + 1 and λ divides va.
Figure 2: A device (G, y, z) of all possible kinds for various (y, z).
The graph in Figure 2 exhibits a device (G, y, z) of all varieties and kinds for different
choices of (y, z).
The classification of devices into kinds and varieties has an application in chemistry in
the identification of molecules (with carbon atoms in particular) that conduct or else bar
conduction at the Fermi level. In the chemistry paper [3], conductors and insulators are
classified into eleven cases that are essentially the twelve kinds of Table 3, with case 7 in
[3] corresponding to the kinds (ηG, ηG, ηG, ηG) in variety 3c(iiA) and (ηG, ηG, ηG, ηG) in
variety 3c(iiB). The latter two varieties are distinguishable by the non–vanishing or other-
wise of ja(0).
7 Graphs with analogous vertex pairs
In general, vertex pairs in a graph may be of different varieties and kinds. We shall explore
two interesting classes of graphs with the same extremal nullity (allowed by interlacing)
for all vertex–deleted subgraphs. These emerge in the classification of devices {(G, y, z)}
according to their kind (ηG, ηG−y, ηG−z, ηG−y−z). A pair of vertices y and z for which
ηG−y = ηG−z is said to be an analogous vertex pair.
I. Sciriha et al.: Interlacing–extremal graphs 273
Kind Characterization Variety G bipartite
Two CVs 1
(gs, gt, gu) = (ηG, ηG − 1, ηG − 1)
gv = ηG − 2 vc 6= 0 & tb 6= 0 & ub 6= 0 1(i) Allowed
& ηG ≥ 2
gv = ηG vc = 0 & tb 6= 0 & ub 6= 0 & vb(0) = 0 1(ii) Allowed
& ηG ≥ 1
gv = ηG − 1 vc = 0 & tb 6= 0 & ub 6= 0 & vb(0) 6= 0 1(iii) Forbidden
& ηG ≥ 1
CV and CFV 2
(gs, gt, gu) = (ηG, ηG + 1, ηG − 1) vc = 0 & tb = 0 & ub 6= 0 & vb(0) = 0 2a Allowed
gv = ηG & ηG ≥ 1
(gs, gt, gu, gv) = (ηG, ηG, ηG − 1) vc = 0 & tb = 0 & ub 6= 0 & vb(0) 6= 0 2b Forbidden
gv = ηG − 1 & ηG ≥ 1
Two CFVs 3
(gs, gt, gu) = (ηG, ηG + 1, ηG + 1) 3a
gv = ηG vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3a(i) Allowed
& ta(0) = 0 & ua(0) = 0 & va(0) 6= 0
gv = ηG + 2 vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3a(ii) Allowed
& ta(0) = 0 & ua(0) = 0 & va(0) = 0
(gs, gt, gu) = (ηG, ηG + 1, ηG) 3b
gv = ηG + 1 vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3b(i) Forbidden
& ta(0) = 0 & ua(0) 6= 0 & va(0) = 0
gv = ηG vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3b(ii) Forbidden
& ta(0) = 0 & ua(0) 6= 0 & va(0) 6= 0
(gs, gt, gu) = (ηG, ηG, ηG) 3c
gv = ηG + 1 vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3c(i) Forbidden
& ta(0) 6= 0 & ua(0) 6= 0 & va(0) = 0
gv = ηG vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3c(ii) Forbidden
& ta(0) 6= 0 & ua(0) 6= 0 & va(0) 6= 0
gv = ηG &ja(0) 6= 0 vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3c(iiA) Forbidden
& ta(0) 6= 0 & ua(0) 6= 0 & va(0) 6= 0
& ja(0) 6= 0
gv = ηG& ja(0) = 0 vc = 0 & tb = 0 & ub = 0 & vb(0) = 0 3c(iiB) Forbidden
& ta(0) 6= 0 & ua(0) 6= 0 & va(0) 6= 0
& ja(0) = 0
Table 3: A characterization of all devices (G, y, z) according to their variety and kind.
274 Ars Math. Contemp. 6 (2013) 261–278
The first of these two classes consists of graphs G with the minimum possible nullity
ηG−y−z for all pairs of distinct vertices y and z, (i.e., ηG − 2) and therefore also the
minimum possible nullities ηG−y and ηG−z (i.e., ηG − 1). By Definition 6.3, these graphs
form precisely the class of uniform–core graphs. On the other hand, the second of the two
classes consists of graphs with the maximum possible nullity ηG−y−z , that is ηG + 2, for
some pair of distinct vertices y and z, and therefore also the maximum possible nullities
ηG−y and ηG−z (i.e., ηG + 1).
7.1 Uniform–core graphs
By Definition 6.3, each vertex pair in a uniform–core graph corresponds to a graph of
variety (1i). Since the nullity of a graph is non–negative, and ηG−y−z = ηG − 2 for all
vertex pairs y, z of a uniform–core graph G, then the nullity of G is at least two. To
understand better the core–structure of uniform–core graphs and be able to characterize
them as a subclass of singular graphs, it is necessary to use their core structure with respect
to a basis for their nullspace.
Let B be a basis for the η–dimensional nullspace of A of a singular graph G (with no
isolated vertices) of nullity η ≥ 1. As seen in [11], Hall’s Marriage problem for sets,
or the Rado–Hall Theorem for matroids, guarantees a vertex–subset S of distinct vertex
representatives [1, 11], to represent a system SCores of cores corresponding to the vectors
of B. This implies that deleting a vertex v representing a core F eliminates the core F
from G− v, which will now have a new system of η − 1 cores. Also any k ≥ 1 cores in a
system SCores of ηG cores cover at least k + 1 vertices.
Theorem 7.1. A device (G, y, z) is of variety 1(i) if and only if the two vertices y and z do
not lie in one core only, i.e. at least two cores are needed to cover the vertices y and z.
Proof. Consider a basis B for the nullspace of A. The vertices y and z lie on at least one
core of G. There are two possibilities. Firstly, B has exactly one vector with non–zero
entries at positions associated with y and z. In this case ηG−y−z = ηG−y = ηG− 1, which
does not correspond to variety 1(i). Secondly, B has at least two vectors with non–zero
entries at positions associated with y or z, when ηG−y−z = ηG−y − 1 = ηG − 2, which
corresponds to variety 1(i). The two core vertices must represent two distinct cores in a
system SCores of ηG cores corresponding to a basis B for the nullspace [11].
A subclass U of uniform–core graphs can be constructed from nut graphs. A graph
G ∈ U is obtained from a nut graph H on n vertices and m edges by duplicating each of
the n vertices of H . Then G has 2n vertices and 4m edges. Figure 3 shows the uniform–
core graph G ∈ U obtained from the smallest nut graph H . The nullity of G is |V(G)|
2
+1.
Deletion of any
|V(G)|
2
+ 1 vertices reduces the graph to a non–singular graph.
Let the vertices of G be labelled 1, 2, ..., n, 1′, 2′, ...n′ where {1, 2, ...} are the vertices
of the nut graph H and {1′, 2′, ...} are the duplicate vertices of {1, 2, ...} in that order in G.
Note that a vertex labelled r for 1 ≤ r ≤ n is adjacent to the original neighbours in H and
also to precisely those primed vertices with the same numeric label. For instance, vertex 1
is adjacent to 2 and 7 in H and to 2, 2’, 7 and 7’ in G. The following result, expressing the
adjacency matrix of G ∈ U in terms of the adjacency matrix of H , is immediate.
I. Sciriha et al.: Interlacing–extremal graphs 275
Figure 3: The smallest nut graph H and the uniform–core graph G derived from H .
Theorem 7.2. If H is the adjacency matrix of the nut graph H , then the adjacency matrix
of the uniform–core graph G ∈ U is
(
H H
H H
)
. The spectrum of G consists of n eigen-
values equal in value to double the eigenvalues of H and an additional n zero eigenvalues
corresponding to the n duplicate vertex pairs. If (x1, x2, · · · , xn)t is an eigenvector of H
for an eigenvalue µ, then (x1, x2, · · · , xn, x1, x2, · · · , xn)t is an eigenvector of G for an
eigenvalue 2µ.
We shall now characterize uniform–core graphs by requiring that a set of vertex repre-
sentatives of a system SCores of cores be an arbitrary subset of the vertices for all systems
of cores.
Theorem 7.3. A graph of nullity ηG is a uniform–core graph if and only if it is a singular
graph such that the deletion of any subset of ηG vertices produces a non–singular graph.
Proof. Let us relate the nullspace of A to the vertices of a uniform–core graph G of nullity
ηG. Let S be any subset of ηG vertices of G labelled {1, 2, · · · , ηG} and let B be an
ordered basis for the nullspace of A. If all pairs of vertices give a graph of variety 1(i),
then no two vertices lie in only one core of SCores. Therefore, it is possible to obtain a
new ordered basis B′ for the nullspace of A, by linear combination of the vectors in B,
such that, for 1 ≤ i ≤ ηG, only the vector i of B′ has a non–zero entry at position i [11].
Removal of any vertex in S destroys precisely one eigenvector of B′ reducing the nullity
by one. Deletion of all the vertices in S destroys all the kernel eigenvectors and leaves a
non–singular graph.
A characterization of the subclass G ∈ U of uniform–core graphs uses the operation
NEPS (non–complete extended p-sum) of a nut graph and K2. The graph product NEPS is
described for instance in [2].
Definition 7.4. Given a collection {G1, G2, · · · , Gk, · · · , Gn} of graphs and a correspond-
ing set B ⊆ {0, 1}n\{(0, 0, ..., 0)}, called the basis, of non–zero binary n-tuples, the NEPS
of G1, G2, ..., Gn is the graph with vertex set V(G1) × V(G2) × · · · × V(Gn) in which
two vertices {w1, w2, · · · , wn} and {y1, y2, · · · , yn} are adjacent if and only if there ex-
ists (β1, β2, · · · , βn) ∈ B such that wi = yi whenever βi = 0 and wi is adjacent to yi
whenever βi = 1.
276 Ars Math. Contemp. 6 (2013) 261–278
Lemma 7.5. [2] If for 1 ≤ i ≤ n, λi1, λi2, · · · , λini is the spectrum of Gi, of order ni for
1 ≤ i ≤ n, then the spectrum of the NEPS of G1, G2, · · · , Gn with respect to basis B is
{
∑
β∈B
λβ11i1 , λ
β2
2i2
, · · · , λβnnin : ik = 1, 2, ..., nk & k = 1, 2, ..., n}.
The following result follows from the construction of a uniform–core graph G ∈ U .
Theorem 7.6. A uniform–core graph G ∈ U is the NEPS of a nut graph G1 and K2 with
basis {(1, 0), (1, 1)}.
From Lemma 7.5 and Theorem 7.6, the spectrum of the uniform–core graph G ∈ U
is λi + λiλj where {λi} is the spectrum of the nut graph H and {λj} = {1,−1} is the
spectrum of K2. This agrees with the result in Theorem 7.2.
7.2 Non-singular graphs with a complete weighted inverse
We shall now look into the second class of devices. Such a graph G is a device (G, y, z),
of variety 3a(ii), for some pair of distinct vertices y and z. Graphs which are devices
(G, y, z), of variety 3a(ii), for a particular pair of vertices y and z exist, as shown in the
example of Figure 2 for vertex connections 15 and 17. Can a graphG be a device (G, y, z),
of variety 3a(ii), for all vertex pairs {y, z}? The question amounts to determining whether
it is possible to have η(G− y − z) equal to the maximum allowed nullity relative to η(G),
that is η(G) + 2, for all vertex pairs {y, z}. The answer is in the negative.
Lemma 7.7. It is impossible that a graph G is a device (G, y, z) of variety 3a(ii) for all
pairs of distinct vertices y and z.
Proof. Suppose G is a graph which is a device (G, y, z) of variety 3a(ii) for all pairs of
distinct vertices y and z. This requires that each of the graphs G− y and G− z is singular
and therefore has CVs. Deletion of a CV from G − y, restores the nullity back to η(G).
Hence it is impossible to achieve η(G− y − z) = η(G) + 2, for all vertex pairs {y, z}.
By Lemma 5.3(ii), the kind (ηG, ηG−y, ηG−z, ηG−y−z)=(ηG, ηG+1, ηG, ηG+1) is im-
possible. Hence the only devices (G, y, z) within the second class that have the maximum
value of η(G − y) relative to ηG, for all vertices y, are of kind (ηG, ηG + 1, ηG + 1, ηG).
Our focus is on the non–singular graphs of this kind having the inverse A−1 equal to the
adjacency matrix of the complete graph with real non–zero weighted edges and no loops.
The smallest candidate is K2. Indeed A(K2) = A(K2))−1 =
(
0 1
1 0
)
.
Definition 7.8. Let G be a non–singular graph G with the off–diagonal entries of the in-
verse A−1 of its adjacency matrix A being non–zero and real, and all the diagonal entries
of A−1 being zero. Then G is said to be a nuciferous graph.
The motivation for the name nuciferous graph (meaning nut–producing graph) will
become clear from Theorem 7.9. To characterize this class of graphs, let us consider the
deck {G−v : v ∈ V} of subgraphs, as in the investigation of the polynomial reconstruction
problem [10].
Theorem 7.9. Let G be a nuciferous graph. Then G is either K2 or each vertex–deleted
subgraph G− v is a nut graph.
I. Sciriha et al.: Interlacing–extremal graphs 277
Proof. Let Q be the n − 1 × n matrix obtained from A−1 by suppressing the diagonal
entry from each column. Therefore each entry of Q is non–zero.
Let the ith column of Q be qi := (q(1)i, q(2)i, ..., q(i−1)i, q(i+1)i, q(i+2)i, ..., q(n)i)t
for 2 ≤ i ≤ n − 1. The first and last columns are q1 := (q(2)1, q(3)1, ..., q(n)1)t and
qn := (q(1)n, q(2)n, ..., q(n−1)n)
t, respectively.
Since AA−1 is the identity matrix I, then A(G−i)qi = 0 for all 1 ≤ i ≤ n. Therefore
qi is a kernel eigenvector (with non–zero entries) of G − i for all the vertices i. Hence
G− i is a core graph. By interlacing, it has nullity one. It follows that each vertex–deleted
subgraph is a nut graph.
From Lemma 7.7, nuciferous devices (G, y, z) are not of type of variety 3a(ii) for all
pairs of distinct vertices y and z. Moreover, from Theorem 7.9, for G 6= K2, each vertex–
deleted subgraph is a nut graph and therefore has nullity one. On deleting a vertex from a
nut graph, the nullity becomes zero. Hence a candidate graph G cannot be of variety 3a(ii)
for any pair of vertices y and z.
Theorem 7.10. Let G be a nuciferous graph G. If G is not K2, then
(i) it has order at least eight;
(ii) the device (G, y, z) is of variety 3a(i) for all pairs of distinct vertices y and z;
(iii) the graph G is not bipartite.
Proof. (i) Since nut graphs exist for order at least seven [12], it follows, from Theorem 7.9,
that a nuciferous graph G, of order at least three, has at least eight vertices.
(ii) From the proof of Lemma 7.7, a nuciferous graph G is of kind (ηG, ηG + 1, ηG +
1, ηG). Thus G is a device (G, y, z) of variety 3a(i) for all pairs of distinct vertices y and z.
(iii) From Theorem 7.9,G−y andG−z are nut graphs and therefore cannot be bipartite
[12]. Hence G has odd cycles and cannot be bipartite.
To date, no graph (except K2) has been found to satisfy the condition of Theorem 7.9.
An exhaustive search on all graphs on up to 10 vertices and all chemical graphs on up to
16 vertices reveals no counter example. We conjecture the following result.
Conjecture 7.11. There are no graphs for which every vertex–deleted subgraph is a nut
graph.
8 Chemical implications
Graph theory has strong connections with the study of physical and chemical properties of
all-carbon frameworks such as those in benzenoids, fullerenes and carbon nanotubes. The
eigenvalues and eigenvectors of the adjacency matrix of the molecular graph (the graph of
the carbon skeleton) are used in qualitative models of the energies and spatial distributions
of the mobile π electrons of such systems. Specifically, graphs and their nullities figure
in simple theories of ballistic conduction of electrons by conjugated systems. In the sim-
plest formulation [3] of the SSP (Source and Sink Potential ) [5] approach to molecular
conduction, the variation of electron transmission with energy is qualitatively modelled in
terms of the characteristic polynomials of G, G − y, G − z, G − y − z, where G is the
molecular graph and vertices y and z are in contact with wires. (This is the motivation
for the definition of a device in the present paper.) As a consequence, the transmission at
the Fermi level (corresponding here to λ = 0) obeys selection rules couched in terms of
278 Ars Math. Contemp. 6 (2013) 261–278
the nullities ηG, ηG−y , ηG−z , and ηG−y−z [7], motivating the definition of kinds here. In
terms of the varieties defined here, the SSP theory predicts conduction at the Fermi level for
connection across the vertex pair (y, z) for 1(ii), 1(iii), 3a(i), 3b(ii), 3c(i) and 3c(iiA),
and, conversely, insulation at the Fermi level for 1(i), 2a, 2b, 3a(ii), 3b(i) and 3c(iiB).
The two classes of graphs with analogous vertex pairs and certain extremal conditions
on the nullity of their vertex-deleted subgraphs, explored in Section 7 are envisaged to have
interesting developments in spectral graph theory. Moreover, the classification of graphs
into varieties and kinds has an application in chemistry in the identification of molecules
(with carbon atoms in particular) that conduct or else bar conduction at the Fermi level
that has already been investigated in [3]. According to the SSP theory, the first class, the
uniform–core graphs, corresponds to insulation at the Fermi–level for all two vertex con-
nections and the second class, the nuciferous graphs, to Fermi–level conducting devices
(G, y, z) for all pairs of distinct vertices y and z. The latter class has the additional prop-
erties that it consists of devices corresponding to non-singular graphs that are Fermi–level
insulators when y = z. Therefore nuciferous graphs have no non–bonding orbital and are
conductors for all distinct vertex connection pairs and insulators for all one vertex connec-
tions. We conjecture that the only nuciferous graph is K2.
References
[1] R. A. Brualdi, The mutually beneficial relationship of graphs and matrices, volume 115 of
CBMS Regional Conference Series in Mathematics. American Mathematical Society, Provi-
dence, RI, 2011.
[2] D. M. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of Graphs, CUP, Cambridge, 1997.
[3] P. W. Fowler, B. T. Pickup, T. Z. Todorova and W. Myrvold, A selection rule for molecular
conduction, J. Chem. Phys. 131 (2009), 044104 (7 pages).
[4] F. R. Gantmacher, The Theory of Matrices, volume 1, AMS Chelsea, 2010.
[5] F. Goyer, M. Ernzerhof and M. Zhuang, Source and sink potentials for the description of open
systems with a stationary current passing through. J. Chem. Phys., 126 (2007), 144104.
[6] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities, volume 115 of
CBMS Regional Conference Series in Mathematics, Allyn and Bacon, Inc., Boston, Mass.,
1964.
[7] B. T. Pickup and P. W. Fowler, An analytical model for steady-state currents in conjugated
systems, Chem. Phys. Lett. 459 (2008), 198–202.
[8] A. J. Schwenk and R. J. Wilson, On the eigenvalues of a graph, in: L. W. Beineke, R. J. Wilson
(eds), Selected Topics in Graph Theory I, Academic Press, London, 1978.
[9] I. Sciriha, On the coefficient of λ in the characteristic polynomial of singular graphs, Util.
Math., 52 (1997), 97–111.
[10] I. Sciriha, Graphs with a common eigenvalue deck, Linear Algebra Appl. 430 (2009), 78–85.
[11] I. Sciriha, Maximal core size in singular graphs, Ars Math. Contemp. 2 (2009), 217–229.
[12] I. Sciriha and I. Gutman, Nut graphs – maximally extending cores, Util. Math. 54 (1998),
257–272.