Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 217–229
Maximal core size in singular graphs
Irene Sciriha ∗
Department of Mathematics, Faculty of Science, University of Malta, Msida, Malta
Received 3 September 2009, accepted 5 November 2009, published online 30 November 2009
Abstract
A graph G is singular of nullity η if the nullspace of its adjacency matrix G has dimen-
sion η. Such a graph contains η cores determined by a basis for the nullspace of G. These
are induced subgraphs of singular configurations, the latter occurring as induced subgraphs
of G. We show that there exists a set of η distinct vertices representing the singular config-
urations. We also explore how the nullity controls the size of the singular substructures and
characterize those graphs of maximal nullity containing a substructure reaching maximal
size.
Keywords: Adjacency matrix, nullity, extremal singular graphs, singular configurations, core width.
Math. Subj. Class.: 05C50, 05C60, 05B20.
1 Introduction
A graph G = G(V, E) has vertex set V = VG = {1, 2, . . . , n} and edge set E consisting of
pairs of vertices. The order |G| of a graph G is the number n of vertices. The graphs we
consider are simple, that is, without multiple edges or loops. The complete graph Kn on n
vertices has edges between all distinct pairs of vertices.
The graph G − X denotes the graph obtained from G when the set X of vertices and
the edges incident to the vertices in X are deleted. The reverse process, starting from H
and adding a vertex set X results in H +X . Note that H +X is not unique for a particular
graph H and set X , since it varies with the choice of edges between X and VH and even
with the edges among the vertices ofX themselves. IfX = {v}, we writeG−v andG+v
for G−X and G+X respectively.
The adjacency matrix of a graph G, denoted by G, is (aij), where aij = 1 if {ij} is
an edge and 0 otherwise. Note that the set of matrices {G} for distinct labellings of the
vertices are permutationally similar and therefore a graph G is described completely (up
∗This research is supported by the AWRF and project fund R-39 of the University of Malta.
Web page http://staff.um.edu.mt/isci1/.
E-mail address: irene.sciriha-aquilina@um.edu.mt (Irene Sciriha)
Copyright c© 2009 DMFA Slovenije
218 Ars Math. Contemp. 2 (2009) 217–229
to isomorphism) by the corresponding G for a specific labelling. The spectrum Sp(G) of
a graph G consists of the collection, with repetitions, of the eigenvalues of G, which are
the solutions of the characteristic equation det(λI −G) = 0. The algebraic multiplicity
of an eigenvalue is the number of times it is repeated in Sp(G). The geometric multiplicity
is the dimension of the corresponding eigenspace. Since G is real and symmetric, the two
multiplicities for an eigenvalue have a common value. The multiplicity of the eigenvalue
zero is referred to as the nullity1, η(G), ofG. The rank ofG is rank(G), equal to n−η(G),
a result referred to as the Dimension Theorem.
A graph G on n vertices is said to be singular if η(G) > 0; that is, if there exists
x 6= 0,x ∈ Rn, such that Gx = 0, where each entry of the vector 0 is 0. Since G satisfies
Gx = λx for the eigenvalue λ = 0, we call x a kernel eigenvector of G.
This paper is motivated by the question:
How does the nullity control the size of the singular substructures within a graph?
This we address in section 4. To this end, we survey results on substructures in section 2
and on certain invariants of a graph in section 3, including proofs of theorems that facilitate
the reasoning of new results, leading to a clarification of the underlying concepts.
2 Singular graphs
Let x ∈ Rn, n ≥ 3, be a vector in the nullspace of G, which is labelled so that x =
(xF ,0)t, with each entry of xF being non-zero. The vertices corresponding to xF induce a
subgraph F whose adjacency matrix is the principal |F |×|F | submatrix F of G, satisfying
FxF = 0. We call (F,xF ), or simply F , a core of G. If x = xF , then G = F and G is
said to be a core graph. Note that a core of G is a core graph in its own right. Linearly
independent kernel eigenvectors determine distinct cores of G. The set CV of core vertices
consists of those vertices that lie on some core of G. If a vertex does not lie on any core of
G, then it is said to be core forbidden. A core graph without isolated vertices having nullity
one must be connected and is said to be a nut graph. Nut graphs exist for all orders from
seven onwards. There are three nut graphs of order seven and none for smaller order [10].
Figure 1: Two singular graphs of nullity one.
Consider the two graphs in Figure 1. The six vertex graph has a nullvector (1, 1,−1,
−1, 0, 0)t and its core is the four cycle C4 (labelled 1,2,3,4), induced by the solid black
vertices, while its core-forbidden vertices (labelled 5,6) are white. The nine vertex graph is
a nut graph and therefore has no core-forbidden vertices.
1The term corank(G) is also used for nullity(G) in the literature.
I. Sciriha: Maximal core size in singular graphs 219
Since it is the existence of xF ∈ R|F | that determines that a graph is singular, we
classify singular graphs according to core-order |F |. As shown in Figure 2, there are eight
possible cores of order six, three of order five, two of order four and one each of orders
three and two.
i Min-Max Core Min-rk Min-Max Core Min-rk 
2 • • 2 
3 • 0 • • 4 D 6 4 4 7 
4 • • • • 6 
5 D· 
6 
6 
8 
5 6 6 ~ 8 
5 • • <I> • 8 • • 6 6 [BJ 8 6 
6 <lTI 
6 D: 8 
6 
6 
• • 
• • 10 
• • 
7 6 to 12 
n>7 n -1 to 2n-2 
Figure 2: Minimum rank of graphs with core-width τ .
2.1 Singular configurations
Cauchy’s inequalities for a Hermitian matrix M , (also known as the Interlacing Theorem
[3]) control the multiplicity of the eigenvalues of principal submatrices relative to those of
M . Applied to graphs we have:
Theorem 2.1. Interlacing Theorem: LetG be an n-vertex graph and v ∈ V . If the eigenval-
ues ofG are λ1, λ2, . . . , λn and those ofG−v are µ1, µ2, . . . , µn−1, both in non-increasing
order of magnitude, then λ1 ≥ µ1 ≥ λ2 ≥ µ2 ≥ . . . ≥ µn−1 ≥ λn.
Thus when a vertex is added to a graph, the nullity, or multiplicity of the eigenvalue
zero, may change by at most one. Let us first consider a graph of nullity one. Such a graph
G with nullspace generator x has a unique core F as an induced subgraph determined by
the vertices corresponding to the non-zero restriction xF of x. We say the core is (F,xF )
when xF needs to be emphasized. By interlacing, to obtain a graph G of nullity one from
a core graph F of nullity η, at least η − 1 vertices are added. Thus a lower bound for the
order of a graph G of nullity one, with core (F,xF ), is |F |+ η(F )− 1.
220 Ars Math. Contemp. 2 (2009) 217–229
Definition 2.2. A graph G, |G| ≥ 3, is a singular configuration (SC), with core (F,xF ),
if it is a singular graph, of nullity one, having |F |+η(F )−1 vertices, with F as an induced
subgraph, satisfying |F | ≥ 2, FxF = 0 and G
(
xF
0
)
=
(
0
0
)
. The vector xF is said
to be the non-zero part of the kernel eigenvector
(
xF
0
)
of G.
Note that by interlacing, among singular graphs of nullity one, a singular configuration
G has the least number of vertices for its core (F,xF ). A core graph may be connected
as in the cycles C4k, k ∈ Z+ on 4k vertices or disconnected as in the empty graph rK1
consisting of r isolated vertices. An important combinatorial property of core graphs is that
they have no pendant edges.
Lemma 2.3. A singular configuration is a connected graph.
Proof. Suppose, for contradiction that a singular configuration S is disconnected. Without
loss of generality, S has a connected component S1, |S1| ≥ 3, having a non-zero kernel
eigenvector x1. If the vertices of S1 are labelled first, then S
(
x1
x2
)
=
(
0
0
)
and
S1x1 = 0. Note that S cannot have isolated vertices, since these would contribute to the
nullity, so that η(S) would be more than one. Since x1 6= 0, then x2 = 0, otherwise(
x1
0
)
and
(
0
x2
)
would be linearly independent kernel eigenvectors of S, again con-
tradicting that the nullity of S is one. Thus the unique core of S lies in S1. Suppose that
x2 corresponds to vertices in the non-singular components. But then S does not have a
minimum number of vertices for core F , a contradiction. Thus S = S1.
We now show the relevance of singular configurations. We prove that for nullity–one
graphs, of order larger than minimal with respect to core F , some singular configuration is
an induced subgraph.
Proposition 2.4. A graph G without isolated vertices, of nullity one, with core (F,xF ),
has (at least) one induced subgraph which is a singular configuration with the same core
(F,xF ).
Proof. Let the vertices of F be labelled first. Then the first |F | rows of G may be parti-
tioned as (F|C) and (F|C)t(xF ) = 0. Moreover the rank of (F|C) is |F | − 1. If F is not
itself a SC, its nullity η(F ) is more than one. There exist η(F ) − 1 column vectors of the
supplementary matrix C which are mutually linearly independent and also independent of
the columns of F . These form the matrix C′ such that rank((F|C′)) =rank((F|C)) =
|F | − 1. The principal submatrix of A(G) determined by (A(F )|C′) is of the form
A′ =
(
A(F ) C′
(C′)t Q
)
, where Q is a square matrix. The adjacency matrix A′ defines
an induced subgraph of G, satisfying Definition 2.2. Therefore G is a singular configura-
tion S(F,xF ).
I. Sciriha: Maximal core size in singular graphs 221
Figure 3: Verices 7 and 8 are core–forbidden.
Example 2.5. A singular configuration S has a unique core (F,xF ) whose vertices form
the full set CV in S. If the set P of core-forbidden2 vertices form an independent subset of
the vertices of S, then S is said to be a minimal configuration. In fact there are 2|P| singu-
lar configurations {S} obtained from a particular minimal configuration by adding edges
between some pairs of distinct vertices of P and they all satisfy S
(
xF
0
)
=
(
0
0
)
.
The complete list of minimal configurations of core order up to five may be found in
[5].
The singular graph G, of nullity one, shown in Figure 3, has only one core F which is
the subgraph (of order 6 and nullity 2) induced by the solid black vertices. By Definition
2.2, a singular configuration with core F is expected to have 7 vertices. There are two non-
isomorphic singular configurations, G − 7 and G − 8, having the same core as G. These
two distinct induced subgraphs of G are in fact minimal configurations. Moreover, G and
its two singular configurations share the same non-zero part xF = (1, 1,−1,−1,−1, 1)t
of a kernel eigenvector generating their nullspace.
3 Some new invariants of singular graphs
The study of singular graphs reveals invariants of a graph. One is the partition of the vertex
set V(G) into the set CV of vertices lying on some core of G and the set of core-forbidden
vertices, V(G)\CV. We show that this partition does not depend on the choice of basis for
the nullspace of G. Therefore CV is well defined.
Proposition 3.1. The set CV of core vertices is an invariant of a graph G.
Proof. A basis B for the nullspace can be transformed into another, B′, by linear combi-
nations of the vectors of B. However, the union of the collections of the positions of the
non-zero entries in the basis vectors is the same for all bases. Thus the partition of the ver-
tex set V(G) into CV and core-forbidden vertices, V(G)\CV, is independent of the basis
used for the nullspace.
2For a graph G of nullity more than one, the periphery with respect to F is the subset of vertices not on the
core F . For graphs of nullity more than one, the set of core-forbidden vertices is then the set–intersecton of the
peripheries over all cores F of G.
222 Ars Math. Contemp. 2 (2009) 217–229
From proposition 3.1, it follows that the set, V(G)\CV, of core-forbidden vertices is
also an invariant of G.
3.1 Fundamental system of cores
We now point out properties of subspaces in general that shed light on the structure of a
singular graph. For any vector space W , let wt(x) denote the weight or number of non-
zero entries of the vector x. We adopt the convention to write a basis for a vector space in
which the vectors are ordered according to the monotonic non-decreasing sequence of the
weights of its vectors.
A maximal set of linearly independent vectors x1,x2, . . . ,x`, with the smallest weight
sum
∑`
i=1 wt(xi), are said to form a minimal basis Bmin for W . We say a basis B for
W is reducible if linear combinations of the vectors of B can produce another basis for
W with lower weight sum. Thus for any vector space, a basis is not reducible if and only
if it is minimal. The monotonic non-decreasing sequence of weights of vectors (weight–
sequence) in a minimal basis provides an invariant of the vector space, a result that is
significant because of its generality to bases of any vector space:
Theorem 3.2. [8] Let W be a q−dimensional subspace of Rn. Let t1 be the least
weight of a non-zero vector in W and let B1 = (u1,u2, . . . ,uq), with weight–sequence
t1, t2, . . . , tq , be a basis with minimum weight-sum. If B2 = (w1,w2, . . . ,wq) is another
ordered basis for W with weight–sequence s1, s2, . . . , sq , then ∀i, ti ≤ si.
Although there may be various possible minimal bases for a vector space, by Propo-
sition 3.2, the sequence of weights of their members is unique for the vector space. The
following results are immediate.
Corollary 3.3. A basis for a vector space is not reducible if and only if the monotonic
non-decreasing sequence of the weights of its vectors is lexicographically minimal.
Corollary 3.4. The weight-sequence of a minimal basis for a vector space is an invariant
of the vector space.
The vertex space for a n-vertex graph G is considered to be Rn and the nullspace
ker(G), is a subspace of dimension η. Note that a minimal basis Bmin for ker(G) deter-
mines a fundamental system of cores of G. We now apply Corollary 3.4 to singular graphs
to obtain another invariant associated with the nullspace.
Proposition 3.5. The monotonic non–decreasing sequence of core-orders in a fundamental
system of cores is a graph invariant.
Remark 3.6. The following result proved in [7], provides a necessary condition, in terms
of admissible subgraphs, for a graph to be of a specific nullity η.
Proposition 3.7. Let H be a singular graph, without isolated vertices, having nullity η.
There exist η SCs as induced subgraphs of H whose cores form a fundamental system of
cores of H .
3.2 Increasing the nullity of a graph
Proposition 3.7 provides a necessary condition for a graph to be of nullity η. The following
proposition, which we shall use repeatedly in what follows, gives a necessary and sufficient
condition to increase the number of core vertices in a graph.
I. Sciriha: Maximal core size in singular graphs 223
Proposition 3.8. The nullity increases with the addition of a vertex v to a graphG forming
a connected graph G+ v if and only if v is a core vertex of (G+ v).
Proof. Suppose, for contradiction, that v does not lie on any core of the resulting graph
G + v but η(G) < η(G + v). Then all the cores of G + v lie in G. But then, interlacing
demands that η(G) ≥ η(G+ v), a contradiction.
Conversely, let v be a core vertex of (G+ v). Then there exists a kernel eigenvector x
with a non-zero entry corresponding to v. Let M be the k×n matrix whose rows are the k
vectors of a basis for the nullspace of G+ v, labelled so that the first row of M is x and the
first column corresponds to v. By row-reducing M to echelon form, with all entries in the
columns above and below a leading 1 (or pivot) being zero, a matrix M′ is produced, whose
rows give a new basisBY for the nullspace ofG+v, determining a system Y of cores. The
first row determines the only core F in this system with vertex v. Deleting v has the effect
of destroying F while retaining all the other cores in Y . Thus η(G) ≥ η(G+ v)− 1.
Moreover, if η(G) > η(G+ v)− 1, then there exists a kernel eigenvector z of G which
is linearly independent of those determined by Y . This kernel eigenvector becomes an
additional kernel eigenvector of G+ v by adding a zero as a first entry; but then the k + 1
vectors in BY ∪ {z} are linearly independent in the k–dimensional nullspace of G + v, a
contradiction. Hence η(G) = η(G+ v)− 1.
We now show that if a graph G of rank r is labelled so that the first r rows of G are
linearly independent, then G has a simple block form.
Proposition 3.9. Let the graph G be of order n and rank r, with adjacency matrix G. Let
the first r rows of G be linearly independent vectors. Then there exist a non–singular r× r
matrix B and a r × (n− r) matrix Y such that
A(G) =
(
B BY
YtB YtBY
)
.
Proof. The first r rows of G form a submatrix T of the adjacency matrix G and represent
a maximal set of linearly independent row vectors of G. Each of the η(G) row vectors
Rj , j > r, is linearly dependent on a subset of the first r row vectors of G. The adjacency
matrix G, of rank r and nullity η, can be expressed as
(
T
YtT
)
for a r× η matrix Y. To
see this, note that each linear relation between Rj , j > r and the rows of T corresponds
to a kernel eigenvector in the nullspace of G. Since each of these η(G) kernel eigenvec-
tors corresponds to a core with a unique vertex vj (described by row vector Rj , j > r),
these η(G) kernel eigenvectors are linearly independent and so their first r entries form the
columns of Y. Because of the symmetry of G, the block T can be expressed as (B BY),
where B is a r × r non-singular matrix. The result now follows immediately from the
symmetry of G.
Note that in general there are different choices of the first r rows. Also, each of the
last (n − r) vertices in this labelling of G lies on a core and are said to form a singular
configuration vertex- representation denoted by R. Thus |R| = n − r = η, by the
Dimension Theorem. The kernel eigenvectors, forming a basis for the nullspace of G,
define a system Y of η distinct cores that correspond to η singular configurations found
as induced subgraphs of G. There is a one-one correspondence between Y and R. The
concept of the singular–configuration–vertex–representation has been used in an ad hoc
manner in the literature and more formally in this paper.
224 Ars Math. Contemp. 2 (2009) 217–229
We can also identify a singular–configuration–vertex–representation as the set of ver-
tices corresponding to the pivots in the rows of matrix M′ in the proof of Proposition 3.8.
These define a vertex–representation of a fundamental system Y of η(G) distinct cores.
By Proposition 3.8, deleting a vertex v in a singular–configuration–vertex–representation
reduces the nullity by one and destroys a core in Y that has vertex v.
Note that any collection of h vectors in Bmin collectively cover at least h core-vertices
ofG. So the existence of a singular–configuration–vertex–representation is also guaranteed
by Hall’s Theorem (also known as the Marriage Problem).
Retaining the labelling of Proposition 3.9, there exist η(G) singular configurations
(with distinct spanning minimal configurations) which are induced subgraphs of G such
that each singular configuration corresponds to a unique vertex j, r < j ≤ n. By scaling
the corresponding kernel eigenvectors so that the last non-zero entry is 1, the following
result is immediate.
Corollary 3.10. Let G be of order n and rank r, with adjacency matrix G. Let the first r
rows of G be linearly independent vectors. There exists a matrix Mt =
(
K
I
)
whose
columns are the vectors of a basis for the nullspace ofG, where the order of identity matrix
I is n− r.
Note that if G =
(
B E
Et U
)
has rank r and B is a non–singular r × r matrix, then
K = B−1E = −Y in Proposition 3.9.
4 Nullity and core width
Remark 4.1. Henceforth we shall refer to a minimal basisBmin for ker(G) as (u1,u2, . . . ,
uη). The integers wt(u1) and wt(uη) are extremal values and have been referred to as the
graph singularity κ in [2, 9] and core-width τ in [6], respectively. We focus on the zero,
non-zero pattern of the entries of the vectors in ker(G), to show that the nullity controls
the core width.
The zero eigenvalue equation, Gx = 0, stipulates that the sum of the entries of x cor-
responding to neighbours of any vertex in G is zero. This is also known as the Zero Sum
Rule [9] which leads to a generic kernel eigenvector xgen in terms of η(G) independent
parameters. One way in which to obtain a basis of η(G) kernel eigenvectors is to set a
parameter in turn equal to one and the remaining parameters equal to zero. If η non-zero
entries of xgen, chosen so that they are collectively functions of all the η parameters, are
set to zero, then xgen is forced to vanish. This concept, which has been used in the theory
of singular graphs [4], will be expanded upon in this section.
The Lemma that follows appears in [1] for graphs with weighted edges. We give a
new proof for the (0− 1)–adjacency matrix, emphasising the role of the core vertices in a
singular graph. The result will enable us to relate the core-width τ to the nullity η, while
the proof helps to shed more light on the graph structure.
Lemma 4.2. If η(G) > k ≥ 1, then there exists x ∈ ker(G), such that x has zero entries
in any k specified positions.
Proof. Let v be a core–forbidden vertex. Then any kernel eigenvector has a zero entry
in that position. To prove this lemma, then, we need to show that there exists a kernel
eigenvector with zeros in any k positions corresponding to core vertices.
I. Sciriha: Maximal core size in singular graphs 225
Let the k chosen core vertices be labelled first, followed by the rest of the core vertices
and ending with the core-forbidden vertices. Let M be the matrix whose rows are the
vectors of a basis for the nullspace of G, ordered so that the ith entry in the ith row vector
is non-zero. The only non-zero entries lie in the first |CV| columns. Row-reducing M
to echelon form, with all entries in the columns above and below a leading 1 being zero,
produces a matrix M′, whose rows give a new basis for the nullspace of G. Thus each row
of M′ is non-zero. Furthermore, the pivots in the rows from the (k + 1)th up to the last
row have at least k zero entries preceding them. Thus the kernel eigenvectors represented
by each of the last η(G)− k rows of M′ satisfy the conditions of the required result.
Lemma 4.2 guarantees a kernel eigenvector with zero entries in any η(G)− 1 specified
positions. In the proof, the rows of M′ form a basis that can determine the minimum
weight sequence and one of a possible number of minimal bases. The determination of
the minimum rank of a (0 − 1)–adjacency matrix, as τ varies, is regarded as an extremal
problem. The minimum rank for various values of τ is given in Figure 2. The result that
follows holds for minimal bases.
Proposition 4.3. If x ∈ Bmin, then x has at least η(G)− 1 zero entries.
Proof. There exists a basis B of kernel eigenvectors which are the rows of the η × n
matrix M′, with all entries in the columns above and below a pivot being zero. Recall that
the set of vertices corresponding to the pivots represents a singular–configuration–vertex–
representation. Thus any row of M′ has at least |η(G)| − 1 zero entries corresponding to
all the other rows of M′. By Theorem 3.2, the weight-sequence of Bmin is entry-wise less
than that of B. Thus if x ∈ Bmin, then x has at least η(G)− 1 zero entries.
By Proposition 3.2, among all (ordered) bases for the nullspace of G, a minimal basis
has the maximum number of zeros in each vector in turn. The minimum number of zeros
in the vectors of a minimal basis is used to establish a method of obtaining an upperbound
for the nullity.
Proposition 4.4. If the number of zero entries in a vector x ∈ Bmin is less than k, then
η(G) ≤ k.
Proof. By Proposition 4.3, all the vectors in Bmin have η − 1 or more zero entries so that
k − 1 ≥ η − 1, as required.
Note that Proposition 4.4 can also be proved by using Lemma 4.2 directly. This guar-
antees a vector y in the nullspace with at least k zeros if η(G) > k. So suppose that
η(G) > k and the number of zero entries in each x ∈ Bmin is k − 1 or less. Since y is a
linear combination of the vectors in Bmin, by Theorem 3.2, it cannot have more than k− 1
zero entries, contradicting the necessary condition of Lemma 4.2. Hence η(G) ≤ k.
To determine the minimum number of zeros over all x ∈ Bmin, it suffices to determine
the core-width τ , an invariant of the graph. Figure 2 shows all the cores of order up to six
and the minimum rank of graphs with a min-max core-order (or core-width) τ .
We now show that τ and η exert mutual control.
Proposition 4.5. For a graph G on n vertices of nullity η and core width τ , τ +η ≤ n+1.
226 Ars Math. Contemp. 2 (2009) 217–229
Proof. By definition of core-width τ , there exists y ∈ Bmin having τ non-zero entries. If z
denotes the number of zero entries in y, then τ+z = n. By Proposition 4.3, z ≥ η(G)−1.
Thus τ + η(G)− 1 ≤ n, as required.
We may ask what the threshold order of a singular graph G needs to be for a particular
core F to lie in a fundamental system F of cores.
Corollary 4.6. A singular graph G of nullity η cannot have a core Ft of order t in F if
t > n+ 1− η.
Definition 4.7. Let the order of a singular graph G be n. If the nullity is η and the core
width is τ , then G is said to be extremal singular if η + τ reaches n+ 1.
Nut graph on 7 vertices Extremal Singular: K = 3, r =7 
Core-Order Sequence: 3, 3, 3, 4, 7 
Figure 4: The nut graph 7b and a extremal singular graph of nullity five.
To determine for which graphs τ+η reaches the upper bound n+1, we need to consider
as large a core width τ as is possible, for a given core–order n and nullity η. Figure 4 shows
a core graph which is extremal singular with the nut graph N7b in a fundamental system of
cores.
Proposition 4.8. A graphG is extremal singular of nullity η, if and only if it is a core graph
and the largest core in a fundamental system is a nut graph N and there are exactly η − 1
vertices of G not on N .
Proof. Let τ +η = n+1 and x ∈ Bmin have τ non-zero entries representing core Fτ . If z
denotes the number of zero entries in x, then τ + z = n and z needs to be η − 1. As in the
proof of Proposition 4.3, there exists a subset L consisting of η − 1 vertices in a singular–
configuration–vertex–representation representing the cores for Bmin other than Fτ , such
that at the vertex positions of L, the entries of x are zero, but the entries of the other η − 1
vectors in Bmin are collectively non-zero. Then corresponding to each vertex of G, there
is a kernel eigenvector with a non-zero entry in the associated position. Hence each vertex
I. Sciriha: Maximal core size in singular graphs 227
of G is a core vertex. Now deleting L destroys exactly η− 1 cores of G leaving a subgraph
H of G of order τ with core Fτ whose kernel eigenvector has τ non-zero entries. Thus G
is a core graph and H is a nut graph whose kernel eigenvector is the non-zero part of x.
Conversely, if in a core graph G, the core corresponding to the core–width τ is a nut
graph N , then τ + η(N) = |N | + 1. By Proposition 3.8, as each of the η − 1 vertices is
added to N to produce G, the graph proceeds through a series of core graphs. Both sides
of the equation increases by one at each stage. Thus τ + η(G) = |G|+ 1.
Proposition 4.9. A graph G is extremal singular of nullity one if and only if G is a nut
graph.
Proof. Recall that a nut graph is a core graph of nullity one. Thus τ = n and τ + η reaches
the upper bound. Now for a graph with nullity one which is not a nut graph, there exist
core-forbidden vertices so that τ < n.
Thus a nut graph of order n1 is extremal singular and may be grown into larger extremal
singular graphs with core width n1.
7 - nut /(=4 7:=7 /(=4 7:=5 
Add vertices to 7 - nut 
Figure 5: Non–extremal core graphs H1 and H2 of nullity two - with the nut graph N7a as
an induced subgraph.
When starting from a nut graph (N,xN ), to construct a singular graph of nullity η,
in such a way that the nullity increases with each vertex addition, the vector xN need not
remain in a minimal basis. Indeed, let us start with a nut graph N and add vertices to
produce a core graph. If with each vertex added, a core graph is created while (N,xN )
is preserved, then the nullity increases by one with each vertex addition and the equality
|N | + η(G) = n + 1 holds. If the core–width τ(G) = |N |, then G is extremal singular.
However, there are two other possibilities that might occur in the process of vertex addition
until the n-vertex core graph G is produced. With some vertex addition, either a core is
not created or the core (N,xN ) is not preserved in a basis Bmin for the enlarged graph G.
In the former case the nullity does not reach the maximum possible for n and τ , whereas
in the latter case xN does not remain the non–zero part of a vector in a basis Bmin for
the nullspace of the adjacency matrix of the enlarged graph obtained. If either of these
cases occurs, even though the nut graph N remains an induced subgraph and xN is still a
kernel eigenvector of the enlarged graph, τ + η < n + 1, and the core graph obtained is
not extremal singular. The graphs in Figure 5 illustrate these two cases. The nine-vertex
228 Ars Math. Contemp. 2 (2009) 217–229
graph H1 has κ = 4 and τ = 7, with Fτ being the nut graph N7a (the smallest nut graph
possible [10]). The nullity is two, however, not three as required for τ+η = n+1, because
the nullity did not increase on adding the first vertex to the nut graph N7a. Note that the
eight vertex graph H2, in Figure 5, has nullity two as well. Although the nut graph N7a
is an induced subgraph and a core of H2, τ is not preserved. Thus the nut graph N7a fails
to remain in a Fundamental System of cores (determined by a Bmin(H2) ) after the eighth
vertex is added.
Proposition 4.10. Let G be a singular graph of nullity η, having a fundamental system F
of cores. Then max
F∈F
(|F |+ η(F )) + η(G) ≤ n+ 2.
Proof. Let F ∈ F have kernel eigenvector xF . By Proposition 3.7, there exists a singular
configuration H of order |F |+ η(F )− 1 with core (F,xF ) as an induced subgraph of G.
By interlacing, G has at least |H|+ η(G)− 1 vertices. Hence n ≥ |F |+ η(F ) + η(G)− 2
for all F ∈ F .
A core in a fundamental system may be a nut graph in which case it is both a core of G
and an induced singular configuration of G. If G is extremal singular, then by Proposition
4.8, a core of maximum order τ inF is a nut graph. Recall that any coreF , in a fundamental
systemF of cores of a graphG is an induced subgraph of a singular configurationH which
is in turn an induced subgraph of G. Now by definition, |F | ≤ τ but is |H| ≤ τ? This is
extremely pertinent when a core in a fundamental system F of cores of a graph G is rK1.
In this case, the order, 2|F | − 1, of H is relatively large when compared to |F |, in contrast
with the case when F is a nut graph and |H| = |F |.
Lemma 4.11. Let G be an extremal singular graph with core width τ and nullity η. Let F
be a core in a fundamental system of cores of G. Then
τ ≥ |F |+ η(F )− 1.
Proof. SinceG is extremal singular, η(G)+τ = n+1. By Proposition 4.10, |F |+η(F )−
1 ≤ n+ 1− η(G) = τ.
Proposition 4.12. Let G be an extremal singular graph of nullity η and core–width τ . Let
F be a core having a fundamental system F of cores. If H is an induced subgraph of G
which is a singular configuration with core F , then |H| ≤ τ.
Proof. LetH be a singular configuration which is an induced subgraph ofG corresponding
to the core F . By Lemma 4.11, |H| = |F |+ η(F )− 1 ≤ τ .
Example 4.13. The singular configurations of the extremal singular graph of Figure 4,
associated with the cores 3K1, 3K1, 3K1, C4, and the nut graph N7a in a fundamental
system, have order 5, 5, 5, 5, 7 respectively, supporting Proposition 4.12.
The graphs H1 and H2 of Figure 5 are not extremal singular. The graph H1 has core–
order sequence {4, 7} corresponding to cores C4 and the nut graph N7a, associated to sin-
gular configurations of order 5 and 7 respectively. The graph H2 has core–order sequence
{4, 5} corresponding to cores 4K1 and C4∪̇K1, associated to singular configurations of
order 5 and 7 respectively.
Corollary 4.14. If core rK1 is in fundamental system of cores of an extremal singular
graph, then r ≤ d τ2 e.
I. Sciriha: Maximal core size in singular graphs 229
Proof. A singular configurationH with core rK1 has (2r−1) vertices. Then |H| = 2r−1.
By Proposition 4.12, |H| ≤ τ . Hence the integer r ≤ τ+12 .
5 Conclusion
The symmetry of the (0 − 1)–adjacency matrix G of rank r enables its representation as
a block matrix with a maximally non-singular (r × r)–principal submatrix of G. The
nullspace of G can be expressed in terms of submatrices of this representation.
The presence of singular configurations as induced subgraphs in a graph is a necessary
condition for a graph to be singular. In a graph G of nullity η, we showed that there is a
vertex representationR consisting of η vertices corresponding to η singular configurations
which are induced subgraphs ofG. The choice of the vertices inR, which are core vertices,
is not unique. A graph may have core-forbidden vertices that do not lie on any core of G.
Deletion of a core-forbidden vertex either increases the nullity or leaves it unchanged.
The core-width τ (maximum weight of the vectors in a minimal basis for the nullspace
of G) is an invariant of G and was shown to have extremal properties tied with the nullity η
in a n-vertex graph. Among all graphs on n vertices, τ +η reaches a maximum in extremal
singular graphs. Not only are the core–orders in a fundamental system F of cores bounded
above by τ but in extremal singular graphs, the orders of the singular configurations corre-
sponding to the cores of F are also bounded above by τ .
References
[1] AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank
of graphs, Linear Algebra Appl. 428 (2008), 1628–1648.
[2] M. Brown, J. W. Kennedy and B. Servatius, Graph singularity, Graph Theory Notes of New
York, The New York Academy of Sciences 25 (1993), 23–32.
[3] A. J. Schwenk and R. J. Wilson, On the eigenvalues of a graph, in: L. W. Beineke and R. J.
Wilson (eds.), Selected Topics in Graph Theory, Academic Press, London, 1978, 307–336.
[4] I. Sciriha, On the coefficient of λ in the characteristic polynomial of singular graphs, Util.
Math. 52 (1997), 97–111.
[5] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1998), 193–211.
[6] I. Sciriha, On the rank of graphs, in: Y. Alavi, D. R. Lick and A. Schwenk (eds.), Combina-
torics, graph theory and algorithms 2, New Issues Press, Kalamazoo, Michigan, 1999, 769–
778.
[7] I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007), 451–
462.
[8] I. Sciriha, S. Fiorini and J. Lauri, A minimal basis for a vector space, Graph Theory Notes of
New York, The New York Academy of Sciences 31 (1996), 21–24.
[9] I. Sciriha and I. Gutman, Graphs with maximum singularity, Graph Theory Notes of New York,
The New York Academy of Sciences 30 (1996), 17–20.
[10] I. Sciriha and I. Gutman, Nut graphs: maximally extending cores, Util. Math. 54 (1998), 257–
272.