ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 231-245
Complete graphs with zero diagonal inverse
Alexander Farrugia, John Baptist Gauci, Irene Sciriha *
Department of Mathematics, Faculty of Science, University of Malta
Received 19 March 2014, accepted 23 October 2014, published online 15 November 2015
If the inverse of a non-singular real symmetric matrix that represents an edge-weighted graph with no loops has zero diagonal, then the inverse itself is the matrix of a loopless graph. Here we show that such graphs having non-zero weight on each edge always exist if their number of vertices is at least 6.
Keywords: NSSD, G-nutful graph, circulant matrix, complete graph. Math. Subj. Class.: 05C90, 05B20
1 Introduction
Since the discovery of fullerenes in 1985, an intimate relationship has matured between these carbon molecules and mathematics. The combinatorial, graph theoretical and algebraic properties of fullerenes have been exploited by many researchers (see, for example [1, 3]) to classify the structures of fullerenes and to predict the unique chemical and physical properties of these highly symmetric structures. In "classical" fullerenes, the structure is composed of solely pentagonal and hexagonal regions joined together to form 3-regular polyhedra [3]. However, over the years, non-traditional fullerenes composed of cycles of other sizes, which are general 3-regular polyhedra, have been studied, especially for their regularity properties. This current work is motivated mainly by the beauty of these structures, coupled with the elegance of the interplay between combinatorics, graph theory and algebra. In particular, we consider the algebraic and structural properties of a special family of graphs, termed G-nutful graphs, introduced in [8].
The graphs we consider have weighted edges and no loops. If a non-singular real symmetric matrix G representing such a graph has an inverse G-1 with each entry of its diagonal equal to zero, then the graph is referred to as a NSSD (Non-Singular graphs with
* Corresponding author.
E-mail addresses: alex.farrugia@um.edu.mt (Alexander Farrugia), john-baptist.gauci@um.edu.mt (John Baptist Gauci), isci1@um.edu.mt (Irene Sciriha)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
63
63	Ars Math. Contemp. 11 (2016) 231-245
a Singular Deck). This family of graphs has remarkable properties as explored in [2] and [8].
It is the purpose of this work to determine the existence of complete NSSDs. In [8], a characterisation of a graph G which is G-nutful is given. The inverse G-1 of a G-nutful graph is associated with a complete NSSD. If G is the matrix of a complete NSSD graph Kn on n vertices, then the graph of G-1 is said to be G-1-nutful.
As noted in [2, 4, 7], apart from K2, no other graph was known to be G-nutful. Are there any G-nutful graphs other than K2 ? In this paper, we establish that there exist G-nutful graphs of any order at least six. Some of these G-nutful graphs turn out to be also complete, in which case both G and the graph of G-1 are nutful.
2 Preliminaries
The characteristic polynomial ^(M, A) of a square n x n matrix M, over a field F, is the determinant det(AI - M), denoted also by | AI - M|, which is a polynomial of degree n in A, where I denotes the identity matrix. The roots of ^>(M, A) (in the algebraic closure of F) are the eigenvalues of M. For a real and symmetric n x n matrix M, the n eigenvalues are real, but not necessarily all distinct. The multiplicity of the eigenvalue 0 of M is called the nullity n(M) of M. The matrix M is said to be singular if n(M) > 0 and is said to be non-singular otherwise.
A graph G is a collection of points (called vertices) and lines (called edges) connecting pairs of vertices. If e is an edge connecting two distinct vertices u and v, then we write e = {u, v} and say that e is incident to u and to v, or, equivalently, that u and v are adjacent. The number of edges incident to a vertex is called the degree of the vertex. In a p-regular graph, each vertex has degree p. For each edge e of G, we associate a non-zero real number w, called the weight of e. For a real and symmetric matrix M whose entries on the leading diagonal are all zero, we can associate a graph G = r(M) with no loops and with weighted edges, such that {i, j} is an edge of G with weight w if and only if the ijth entry of M is w = 0. We say that M is an adjacency matrix representing the graph G, or, equivalently, that G is the graph associated with the adjacency matrix M. The complete graph Kn on n vertices and having weighted edges is represented by the matrix Kn. Although in the study of molecular structures, graphs usually have a maximum vertex degree of at most three, in this study we place no restriction on the maximum vertex degree. This allows us to consider complete graphs on any number of vertices.
In the sequel, we shall also consider vertex-deleted subgraphs of a graph and their associated adjacency matrices. For any vertex x of a graph G, the subgraph G - x obtained by deleting the vertex x and all the edges of G incident to x is associated with the (n -1) x (n - 1) matrix G - x obtained by deleting the xth row and column of the adjacency matrix G representing G.
An identity due to Jacobi [6] describes the possible changes in the nullity of an adjacency matrix G representing the graph G when any two vertices x and y are deleted from G. Denoting the adjugate of G by adj G and the entry in the x, y position of adj G by (adj G)xy, we have the following result.
Lemma 2.1. Let x and y be two distinct vertices of a graph G with associated adjacency matrix G, and let j = (adj (AI - G))xy be the entry in the x, y position of adj (AI - G). Then j2 = ut - sv, where s, t, u and v represent the characteristic polynomials of G, G - x, G - y and G - x - y, respectively.
A. Farrugia et al.: Complete graphs with zero diagonal inverse
233
In [2] and [8], the authors introduced a class of graphs termed NSSDs and analysed the properties of these graphs. Formally, NSSDs are defined as follows.
Definition 2.2 ([2]). A graph G = r(G) is a NSSD if G is a non-singular, real and symmetric matrix with each entry of the diagonal equal to zero, and such that all the (n — 1) x (n — 1) principal submatrices of G are singular.
The following is a necessary and sufficient condition for r(G) to be a NSSD.
Theorem 2.3 ([2]). The matrices G and G-1 are real and symmetric with each entry on the respective diagonals equal to zero if and only if r(G) and r(G-1) are both NSSDs.
Therefore, this class of graphs is closed under taking the inverse of the adjacency matrix, hence giving rise to a duality relationship between G and its inverse G-1, so that either one of the two can assume the principal role. For simplicity, we may refer to r(G-1) as the inverse of the graph G.
If the only zero entries in a n x n symmetric matrix are situated on the leading diagonal, then the graph associated with such a matrix is the complete graph Kn. Of special interest to us for this work are complete graphs which also happen to be NSSDs, referred to in the sequel as complete NSSDs. In Section 3 we show that the only complete NSSD on at most five vertices is K2. In Section 4 we extend the investigation to graphs on at least six vertices, and prove that we can find NSSDs on n vertices for any n > 6. In particular, the NSSDs we present are complete NSSDs with appropriate edge-weights. In our construction of these complete NSSDs we make use of spectral properties of circulant matrices.
Definition 2.4. A circulant matrix is an n x n matrix C = (ak,j : k,j = 1, 2,..., n)
where ak,j = aj-k(mod n), that is
I ao
C
&n-1
a i
ao
an-2 an_i \
a1
an-1 ao
a2 a1
denoted by C = (a0, a1,..., an-1).
an 2
a1
a2
an 1
ao
3 Complete Graphs On Less Than 6 Vertices
We treat the two cases for n < 4 and n = 5 separately.
3.1 Complete Graphs On Less Than 5 Vertices
For a graph not to be a NSSD for any associated adjacency matrix, it suffices to show that it has a non-singular vertex-deleted subgraph. This is shown to be the case for n = 3 and 4.
Proposition 3.1. The complete graph Kn on n < 4 vertices is a NSSD if and only if n = 2. Proof. Clearly K1 is not a NSSD since K1 is singular. The adjacency matrix representing K2 is f C C ) for some nonzero real number c. Thus K2 is a NSSD for any edge weight
234
Ars Math. Contemp. 11 (2016) 231-245
c by Definition 2.2. The vertex-deleted subgraphs of K3 are associated with the nonsingular matrices K2, and hence K3 cannot be a NSSD for any edge weights. Moreover,
(0 a i a2\
a1 0 a3 I for some nonzero real numbers
a2 a3 0 J
ai, a2, as, whose determinant is 2a1a2a3 = 0. This means that K3, which represents every vertex-deleted subgraph of K4, is always non-singular, implying that K4 cannot be a NSSD.	□
3.2 Complete Graphs On 5 Vertices
Since the weights of K4 can be assigned such that it can either be singular or non-singular, we cannot utilise the argument used in Proposition 3.1 to prove that K5 is not a NSSD.
We quote a result from [2] that characterises the nullity of a two-vertex-deleted subgraph of a NSSD depending on whether the two vertices form an edge in its inverse.
Theorem 3.2 ([2]). If r(G) is a NSSD on at least three vertices, then G — x — y has nullity zero if {x, y} is an edge in r(G-1), and has nullity two if {x, y} is not an edge in r(G-1).
With the aim to show that K5 cannot be a NSSD, we seek properties that a NSSD on five vertices could have.
Lemma 3.3. If a NSSD on five vertices exists, then it must be the complete graph K5 for appropriate edge weights, and its inverse must also be K5, possibly with different edge weights.
Proof. Suppose G is a NSSD on five vertices. Then, for any two vertices x and y, G - x - y has nullity zero or two by Theorem 3.2. But G - x - y has only three vertices. There are only four graphs on three vertices, none of which has nullity two, no matter what weights are assigned to their edges. It follows that n(G - x - y) = 0, and by Theorem 3.2, {x, y} is an edge in r(G-1) for all vertices x and y. Thus, r(G-1) is K5 for some particular edge weights. Since G-1 represents a NSSD on five vertices, we repeat the same argument and obtain that its inverse, which is the original matrix G, also represents a complete graph. □
It follows that if a NSSD on five vertices were to exist, it must be complete. Now we make use of Lemma 3.3 to show that K5 cannot be a NSSD.
Theorem 3.4. There are no NSSDs on five vertices.
Proof. By Lemma 3.3, if a NSSD on 5 vertices exists, it must be the graph K5 with some edge weights, and its inverse (which is also a NSSD on 5 vertices) must also be K5, with possibly different edge weights. Let
G = cM = c
0	90	91	92	93\
90	0	94	95	96
91	94	0	97	98
92	95	97	0	99
	96	98	99	0
A. Farrugia et al.: Complete graphs with zero diagonal inverse
235
where g = 0 for all i and c =	so that |M| = 1. Since G is a NSSD, so is M. The
NSSD
G

1 Mc
1
	ho	hi	h2	h3
ho	0	h4	h5	h6
hi	h4	0	h?	hi
h2	h5	h?	0	h9
h3	h6	hi	h9	0
where h =0 for all i. Using Jacobi's Theorem (Lemma 2.1), we have ((adj M)xy) = -|M||M — x — y| = -|M — x — y| for any two vertices x and y of G. But M — x — y = K3 for all vertices x and y, whose determinant is 2gigjgk for distinct values of i, j, k G
{0,..., 9}. Also M— i, j, k, Specifically:
—2gogig4 —2gig3g8
h9 h5
_ (adj M)^
- |M|
-2gog2g5 -2^25359 -2^55659
(adj M) , and thus hf = — 2ggj gk for some
hi h4 hi
—2gog356 —2g4g5g7 —2grgig9
h?
h3 h32o
—2gig2g7 —2g4g6gi
h6 h2
Considering M 1 as the NSSD, we have:
—2hohih4 = g2 —2hoh2 h-5 = g8 —2hih3h8 = g5 —2h2h3 hg = g4 —2h5h6 hg = g2
—2hoh3h6 = g2 —2h4h5h7 = g3 —2h?hih9 = g2
—2hih2h? = g2 — 2h4 h6 hi = g22
Squaring the last equation, we have 4h2 h8 hg = g4, and multiplying the first three equations
together, we obtain —8g3gig2g3g4g5g6 —2g7g8gg = hg, we can write
h?hih2. Thus — 32gig2g3g4g5g6 = go. Since
l6gogig2g3g4g5g6 grgig9 = g^O
This process can be repeated starting from another group of equations to obtain 16 rig=0 gj
= g2h2 for all i G {0,1,..., 9}. Thus g2h2 = g2h2 = 16 nLo gk for all i,j G {0,1,..., 9}.
Since MM- = I, we have, in particular, that g0h0 + gihi + g2h2 + g3h3 = 1. But
gihi = ±gjhj for all i, j, and hence g0h0(±1 ± 1 ± 1 ± 1) — 1	--ui
g0h0 = ±2. Since g2h2 = g2h2 for all i, j then either gihi = ±4 for all i or gih. for all i. Additionally, in order for g0h0 + gihi + g2h2 + g3h3 to be equal to 1, none of the gihi's can be equal to — 4, and thus either all gihi are equal to | or all gihi are equal to ± i.
1. Thus go ho = ± | or
4
± 2
Suppose gjhj
± i for all i. In the five equations
goho + gihi + g2h2 + g3 h3 goho + g4h4 + g5h5 + g6 h6 gihi + g4h4 + grh? g2h2 + g5h5 + grhr + ; g3h3 + g6h6 + gihi + g9 h9 =
three of the four terms gihi in each equation must have value i and the remaining one must be equal to — 2. Combinatorially, this is impossible, for suppose we choose, without loss
2 .
of generality, g0h0 = — i; then gi hi
g2h2 = g3h3 = g4h4 = g5h5 = g6h6
i
c
236
ArsMath. Contemp. 11 (2016) 231-245
From the last three equations, we obtain that g7h7 + g8h8 = 0, g7h7 + g9h9 =0 and g8h8 + g9h9 = 0, implying that g7h7 = g8h8 = g9h9 = 0, a contradiction.
The only remaining possibility is that gjhj = 4 for all i. Consider MM-1 = M-1M = I. In particular, by multiplying the first row of M by the second column of M-1, and by multiplying the first row of M-1 by the second column of M, we obtain
glft-4 +	+	= 0
hlg4 + h2g5 + h3g6 = 0
Since gjhj
we can write
+ #2 + #3 g4 g5 g6 #4 + 95 + #6 gl #2
#3
#l
Let p = —, q
#4
#2
— and r
#5
93 #6
— so that
p + q + r
1 1 1
- + - + -
p q r
(3.1)
(3.2)
4
0
0
From (3.2) we obtain pq + pr + qr = 0. Substituting (3.1) in this equation, we get (—q -r)q + (—q — r)(r) + qr = 0, or q2 + qr + r2 = 0. Fixing r to be any real number, this is a quadratic equation in q with a negative discriminant —3r2, and hence q must be a complex number, which is a contradiction.
Thus r(M) is not a NSSD, and hence neither is r(G).	□
From Proposition 3.1 and Theorem 3.4, the following result follows immediately.
Corollary 3.5. The complete graph Kn on n < 5 vertices is a NSSD if and only if n = 2.
4 Complete Graphs on at Least Six Vertices
In this section, we prove that there indeed exist complete NSSDs on at least six vertices by a direct construction.
Any complete graph on n > 6 vertices has at least one (Hamiltonian) cycle of length n on all the vertices. If we assign an arbitrary weight a = 0 to this cycle and a weight of 1 to every other edge of the graph, the matrix obtained is K^ of the form shown in (4.1):
K(a)
0
a
a 0
1 •••
a1
1
a
1
a 0
a
a 1
1
a 0
(4.1)
1
a
1
A. Farrugia et al.: Complete graphs with zero diagonal inverse
68
4.1 The Characteristic Polynomial of Circulant Matrices
We remark that the real and symmetric matrix shown in (4.1) is the circulant matrix (0, a, 1, ..., 1, a). The eigenvalues of such a matrix can thus be obtained by using well-known results on circulant matrices.
Lemma 4.1. The eigenvalues of the circulant matrix (0, a, 1,..., 1, a) are Ao = 2(a — 1) — 1 + n, and Aj = 2(a — 1)cos () — 1 for j € {1, ...,n — 1},a = 0.
Proof. It is well-known (see, for example, [5]) that the eigenvalues of the general circulant
n-1
matrix (a0, a1,..., an-1) are Aj = ^ akw|, for j € {0,..., n — 1} and w0,..., wn-1
k=0
are the nth roots of unity given by wj = e2nij/n. If we substitute a0 =0, a2 = a3 = • • • = an-2 = 1 and an-1 = a1 = a, then the eigenvalues of (0, a, 1,..., 1, a) are given
n-2
by Aj = a(wj + wn-1) + ^ wkk. But
k=2
n-1
k
-1
Yj 1k = n	if j = 0
5>j = <
k=0 n-1
k
k=0
—1)k =0	if n is even and j = n
0 otherwise
(wjk)n — 1 _ (wn)k — 1 wk — 1 wk — 1
Hence, if j = 0, then ^ w^ = n — 3, and thus
k=2
A0 = a(1 + 1) + (n — 3) = 2(a — 1) — 1 + n.
n- 2
If n is even and j = n, then ^ wn/2 =0 — 1 + 1 + 1 = 1. Thus
2	w
k=2
An/2 = a(( —1) + ( —1)n-1) + 1 = a(( —1)(1 + ( —1)n-2) + 1 = 2a(cos n) + 1
= 2(a — 1)(cos n) — 1 = 2(a — 1) cos () — 1.
n2
For any other case, ^ wk = —1 — wj — w5n 1, which means that
k=2
Aj = (a — 1)(wj + w™-1) — 1 = (a — 1)(wj + w-1) — 1 = 2(a — 1) cos (^) — 1,
completing the proof.	□
The eigenvalues of (0, a, 1,..., 1, a) satisfy several interesting properties. To order the eigenvalues, we use the notation of Lemma 4.1.
238
Ars Math. Contemp. 11 (2016) 231-245
Proposition 4.2. Let n > 6 and let the complete graph Kn have circulant matrix K given by K^ = (0, a, 1,..., 1, a), where the parameter a is a non-zero real number. Then the eigenvalues Ao,..., An-i of K{na) are such that
(i)	A0 > Aj for all j = 1,..., n — 1;
(ii)	Aj = An-j for j = 1,..., Ln-1 J;
(iii)	Aj > Aj+1 (j = 1,..., L1J ) when a > 1.
For K82), say, A0 = 15, A1 = A7 = —1 + 4V2, A2 = A6 = —1, A3 = A5 = —1 — 4V2 and A4 = —9.
The characteristic polynomial of Kna) = (0, a, 1,..., 1, a) can be obtained from Lemma 4.1. However, we can actually also determine the characteristic polynomials of all the vertex-deleted subgraphs of Kna). In the sequel, the characteristic polynomial ^(Kna), A) will be denoted by ^(Kna), x, c) where x = A and c = 2(a — 1), c = —2.
Proposition 4.3. Let n be any integer greater than 1 and let Kna) be a complete circulant symmetric matrix (0, a, 1,..., 1, a) on n vertices, a = 0. Then its characteristic polynomial is
^(K(»Uc) = j(x +1 - C -
I (x +1 — c — n)(x + 1 + and ^(K^ — v, x, c), the characteristic polynomial of each of its vertex-deleted subgraphs,
x +1 — c — n) (p(x, c))	ifn is odd
(x +1 — c — n)(x + 1 + c)(p(x, c))2 ifn is even
is
f p(x,c)
(p(x, c) + 2(x + 1 — c — n)q(x, c))	ifn is odd
\ p(n,c) ((2x + 2 — n)p(x, c) + 2(x + 1 — c — n)(x + 1 + c)q(x, c)) ifn is even
k
where k = |_^J, c = 2(a — 1), p(x, c) = JJ (x + 1 — ccos ()) and
j=i
k
, c) = = > |T (x-
q(x,c) = dg = £ fl (x + 1 — ccos (*?)) .
dx
J=1 9=1,9=j
Proof. By Lemma 4.1, the eigenvalues of K^ are A0 = 2(a — 1) — 1 + n and Aj = 2(a — 1) cos (^j) — 1 for j G {1,..., n — 1}. Furthermore, by Proposition 4.2 (ii), An-j = Aj for all j G {1,..., k}. Also, if n is even, then An/2 = — 2(a — 1) — 1. Hence, for c = 2(a — 1), the characteristic polynomial of K^ is
n—1	k	/ k
f (x—Aj ) = (x+1 —c—n) f (x—Aj )2 = (x+1—c—n) I f (x + 1 — c cos ( )) j=0 j=1 \j=1
2
A. Farrugia et al.: Complete graphs with zero diagonal inverse	70
when n is odd, and
n— 1	k
^ (x - Aj) = (x +1 - c - n)(x + 1 + c) ^(x - Aj)2
j=0 j=1
t k
= (x +1 - c - n)(x + 1 + c) I JJ (x + 1 - ccos ( when n is even.
Since every circulant matrix associated with a graph G renders G vertex-transitive, all the vertex-deleted subgraphs of G are isomorphic and hence have the same characteristic polynomial. But the sum of the characteristic polynomials of all the vertex-deleted subgraphs of G is equal to the derivative of the characteristic polynomial of G [9]1. Thus 1 d
^(Kna - v, x, c) = ——^(K^, x, c), so we now proceed to evaluate this partial derivan dx
tive.
When n is odd, we have
^(K^ - v, x, c)
= ndx(x + 1 - c - n)(p(x, c))2 1 /
= — (p(x, c))2 + 2(x +1 - c - n)p(x, c) — n V	dx y
P(x,c) ^ p(x,c) + 2(x +1 - c - n) f ddx J! (x + 1 - c cos ( 2nj ))
^(K^ - v, x, c)
p(x c) ' p(x, c) + 2(x +1 - c - n) JJ (x +1 - ccos (^))
j=1 q=1,q=j
When n is even, the result stated in the proposition statement is obtained in a similar manner.	□
4.2 The Construction of Complete NSSDs
We have noted in the proof of Proposition 4.3 that the characteristic polynomials of the adjacency matrices of all the vertex-deleted subgraphs of the graph associated with = (0, a, 1,..., 1, a) are equal. This means that the determinant of the matrix of each of these vertex-deleted subgraphs is the same. Thus, if the determinant of Kn^ is non-zero and the determinant of any one of its (n - 1) x (n - 1) principal submatrices is zero, then the matrix would represent a NSSD. This is the basis of our construction.
To illustrate the above, let us take the complete graph on seven vertices as an example. By Corollary 3.5 this is the smallest odd number of vertices we can take to possibly find a
1 This is a well-known result for graphs with 0-1 adjacency matrices. However, this result has been known to hold for any graph with a real and symmetric adjacency matrix from as early as 1968.
71
Ars Math. Contemp. 11 (2016) 231-245
NSSD. The matrix K7a) would be of the form
K
(a)
0	a	1	1	1	1	a
a	0	a	1	1	1	1
1	a	0	a	1	1	1
1	1	a	0	a	1	1
1	1	1	a	0	a	1
1	1	1	1	a	0	a
a	1	1	1	1	a	0
which has determinant
where
det(Ka)) = 2(2 + a)(f (a))2
f (a) = -1 + 2a + a2 - a3 The determinant of each (n - 1) x (n - 1) principal submatrix of Ka) is
det(Ka) - v) = f (a)(1 - 6a - a2 + a3)
We require a value of a such that det(Ka)) = 0 and det(Ka) - v) = 0. We have the conditions:
r(a)
a = 0 2 + a = 0 f(a) = 0
1 - 6a - a2 + a3
0
(4.2)
(4.3)
(4.4)
(4.5)
Thus if we find a value for a that satisfies (4.2), (4.3), (4.4) and (4.5), then a complete NSSD is obtained. We note that the cubic equation (4.5) has the real solutions a = -2.0938,0.16296, 2.9308, which also satisfy (4.2), (4.3) and (4.4). Indeed, if we take a = 2.9308, then the inverse of K0 is
K
(a)
	0	0.2327	0.068	-0.25	-0.25	0.068	0.2327
	0.2327	0	0.2327	0.068	-0.25	-0.25	0.068
l	0.068	0.2327	0	0.2327	0.068	-0.25	-0.25
	-0.25	0.068	0.2327	0	0.2327	0.068	-0.25
	-0.25	-0.25	0.068	0.2327	0	0.2327	0.068
	0.068	-0.25	-0.25	0.068	0.2327	0	0.2327
	0.2327	0.068	-0.25	-0.25	0.068	0.2327	0
which is the circulant symmetric matrix (0,0.2327,0.068, -0.25, -0.25,0.068,0.2327). For a = -2.0938 or 0.16296, a similar result is obtained.
We remark that the inverse of a non-singular circulant matrix is another circulant ma-
trix; this is evident in (^K^0^ above. Furthermore,	represents a complete
graph on seven vertices such that each one of its three edge-disjoint cycles has edges of weight 0.2327, 0.068 and -0.25, respectively.
Using a similar technique, we can show that if Kga) -1 ± V2 for K6a) to be a NSSD. Indeed, if we choose a
= (0, a, 1,1,1, a), then a = -1 - V2 « -2.4142, then
7
A. Farrugia et al.: Complete graphs with zero diagonal inverse
72
(k6o)) 1 = (0, -0.6306,1.5224, -1.5224,1.5224, -0.6306). Furthermore, if K^ = (0, a, 1,1,1,1,1, a), then, using the above method, we can show that when a = 2.1889, (k8o)) = (0, -0.2592, 0.3459,0.1898, -0.3082,0.1898,0.3459, -0.2592). Hence, we have:
Theorem 4.4. There exist complete NSSDs on 6, 7 and 8 vertices. 4.3 Existence of Complete NSSDs on at least Nine Vertices
The method described in the previous subsection may go wrong in the case that a polynomial equation £(a) =0 akin to (4.5) having only complex solutions is obtained. Indeed, this scenario happens if we apply our construction to K^; in this case the quadratic polynomial £(a) is a2 + a +1, which has complex roots. Thus, there is no guarantee that the above construction will always yield a complete NSSD unless we prove that £(a) has always at least one real root. This is what we do in the next theorem.
Theorem 4.5. Let n be any integer greater than 8 and let K^ be a complete circulant symmetric matrix (0, a, 1,..., 1, a) on n vertices, a = 0. Then there exists a value of the parameter a strictly between 1 and 1 + 1 sec (4^) such that Kn is a NSSD.
Proof. We can determine the characteristic polynomials of Kn and Kn - v from Proposition 4.3. For Kn to be a NSSD, we need to find a value of c such that ^(Kna), 0, c) = 0 and ^ - v, 0, c) = 0, recalling that c = 2(a - 1). Considering first the case when n is an odd number greater than 8, we obtain:
(1 - c - n)(p(0,c))2 = 0
P(0,c) 'p(0,c) + 2(1 - c - n) ]T ft i1 - ccos i^))
j=1 q=1,q=j
where k = n21 andp(0, c) is as defined in Proposition 4.3. Hence c =1 - n, p(0, c) = 0 and h(c) =0, where
h(c) = fl i1 - ccos i)) +2(1 - c - n) ]T fl i1 - ccos i^)) (4.6)
j=1	j=1 q=l,q=j
We note that h(c) in (4.6) is a polynomial in c with real coefficients and hence it is continuous. Thus, if we show that there exist two distinct values of c for which h(c) has opposite signs, then (4.6) has a real root by the intermediate value theorem.
(k \ k / k
fl 11 +2(1 - n) ^ I fl 1
3=1)	j=1 \q=1,q=j
= 1 + 2(1 - n) ( —- ) =1 - (n - 1)2 < 0 since n > 9.
We now substitute an appropriate value of c such that h(c) > 0. Note, first of all, that
73
Ars Math. Contemp. 11 (2016) 231-245
sec ( ) > 0 since n > 9. Substituting this value for c in (4.6), we obtain
h (sec ()) = n(l - sec (f) cos ())
j= 1
+ 2 (1 - sec () - n)£ n (1 - sec (4? ) cos (^)) .
j=1 q=1,q=j
For j = 2, (1 - sec (^) cos ()) = 0. Thus,
k
h (sec(4f)) =2(1 - sec(f) - n) ft (1 - sec (f) «« (**))
q=i,q=2
implying that
h (sec ( 4f )) =2 (1 - sec ( f ) - n) 1 -
cos
( )'
cos ( 4?)
n
\q=3

cos

. (4.7)
We now check the; signs of each bracket in (4.7). Since 1 < sec () < sec () < 6, we have that 1 - sec ( ) - n < 0. Thus the first bracket of (4.7) is negative. The second bracket of (4.7) is
1
cos(
cos
cos (4f ) - cos (n) -2 sin (^) sin (n)

cos

cos

which is negative since n > 9 and sin 0 > 0 when 0 < 0 < n. The third bracket of (4.7) is
n1
q=3

( )'
cos
(4f)
n f cos ( ) - cos ( ^ )■
q=3
cos
( )
2sin ( nSq+1) sin'
cos
(4f)
(4.8)
Since the highest value of q is k = , then the largest angle in (4.8) is
n(n + 3)
(n2 +2)
2n
< n. Because of this, all the products in (4.8) are positive, and this means
that the third bracket of (4.7) is positive. Thus, h (sec ( 4f )) in (4.7) is positive. We now consider the case when n is even. By Proposition 4.3, we obtain
p(0,c)
(1 - c - n)(1 + c)(p(0,c))2 = 0 k k ( ( ))
(2 - n)p(0, c) + 2(1 - c - n)(1 + c) ^ n (1 - ccos (^)) I = 0
j=1 q=1,q=j
V n
V n
n
cos
n
n
n
A. Farrugia et al.: Complete graphs with zero diagonal inverse
74
where k = . Hence c = 1 — n, c = -1, p(0, c) = 0 and g(c) = 0, where
k
g(c) = (2 — n) J(1 — ccos (^)) +	(4.9)
j=i
k k
+ 2(1 — c — n)(1 + c) £ n (1 — ccos (2nq))
j=1 q=1,q=j
As for the case when n was odd, since g(c) in (4.9) is a polynomial in c, we search for two values of c such that g(c) is positive for one value of c and negative for the other. We show that c = 0 and c = sec (4n) are again two such values of c. Substituting c = 0 in (4.9), we obtain
g(0) = (2 — n) m 11 +2(1 — n)(1) ]T I J^ 1l = (2 —n) + 2(1 — n) f^) =
\J = W	j = l \9=1,9=W
—n(n — 2) < 0 since n > 9.
Substituting c = sec (4^) in (4.9), we obtain
g (sec ()) = (2 — n) J (1 — sec (f) cos (2nj))
j= 1
+ 2 (1 — sec () — n)(1 + sec ()) £ J (1 — sec (4n) cos (^))
j=1 q=1,q=j
g (sec ()) =2 (1 — sec () — n)(1+sec (f)) J (1 — sec (f) cos (^))
q=1,q=2
cos ( 2n)
g (sec (4n)) = 2 (1 — sec (f) — n) (1 + sec (f)) ( 1 —
n
coH n / / ( cos ()\\
vq=3 v1 -	<4-10)
Since 1 + sec (4n) > 0 and the product of all the other brackets in (4.10) was shown to be positive in the proof for the case when n is odd, n > 9, then g (sec (4n)) in (4.10) is positive.
Consequently, the polynomials (4.6) and (4.9) both have a root between c = 0 and c = sec (4n). Since c = 2(a — 1), the graph associated with the matrix represents a NSSD for a value of a between 1 and 1 + 1 sec (4n), as required.	□
Remark 4.6. Observe that the lower bound for the parameter a in Theorem 4.5 can be improved to §. Since the upper bound tends to § as n increases, we know that the adjacency matrix corresponding to a complete NSSD on a large number of vertices is given by (0, a, 1,..., 1, a) where a = 1.5 + e for a sufficiently small positive real value of e.
75
Ars Math. Contemp. 11 (2016) 231-245
We thus have the following existence result from Theorem 4.4 and Theorem 4.5.
Corollary 4.7. For each n > 6, there always exists a complete NSSD on n vertices.
In [8], a subclass of NSSDs referred to as G-nutful graphs was introduced and defined as follows.
Definition 4.8. A G-nutful graph G is either K2 or a NSSD on at least three vertices having all two vertex-deleted subgraphs of the same nullity.
Recall that a necessary and sufficient condition for G to be a G-nutful graph is for its inverse to be a complete NSSD. We have established that besides K2, there exist other G-nutful graphs.
Theorem 4.9. There exist G-nutful graphs on any number of vertices greater than five. 5 Conclusion
The complete graph K2 has been well-known to be a complete NSSD. In this paper, we have shown that complete NSSDs exist for all positive integers at least six. This disproves a conjecture that appeared in [8] that NSSDs must have an even number of vertices. Indeed, NSSDs on an odd number vertices other than those that are complete graphs have also been found. An example is given by the graph with circulant adjacency matrix (0, -0.7549,1,0,0,1, -0.7549), whose inverse is given by the circulant matrix (0,0.1075,0.5812,0.3312,0.3312,0.5812,0.1075). However, we have also shown that no complete NSSDs exist on n vertices for 3 < n < 5.
In [4, 7] it was conjectured that K2 is the only nuciferous graph, that is a NSSD with 0-1 entries in its adjacency matrix whose inverse is complete. It is still an open problem whether a construction of complete NSSDs similar to that given in Section 4 may lead to an inverse with only 0-1 entries, which would then be nuciferous.
References
[1]	F. Cataldo, A. Graovac and O. Ori (eds.), The Mathematics and Topology ofFullerenes, Springer, New York, 2011.
[2]	A. Farrugia, J. B. Gauci and I. Sciriha, On the inverse of the adjacency matrix of a graph, Special Matrices 1 (2013), 28-41.
[3]	P. W. Fowler and D. E. Manolopoulos (eds.), An Atlas ofFullerenes, Clarendon Press, 1995.
[4]	P. W. Fowler, B. T. Pickup, T. Z. Todorova, R. de los Reyes and I. Sciriha, Omni-conducting fullerenes, Chemical Physics Letters (2013), 33-35.
[5]	R. M. Gray, Toeplitz and circulant matrices: a review, Foundations and Trends in Communications and Information Theory 2 (2006), 155-239.
[6]	I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986.
[7]	I. Sciriha, M. Debono, M. Borg, P. Fowler and B. T. Pickup, Interlacing-extremal graphs, Ars Mathematica Contemporanea (2013), 261-278.
[8]	I. Sciriha, A. Farrugia and J. B. Gauci, The adjacency matrices of complete and nutful graphs, Match Commun. Math. Comput. Chem 72 (2014), 165-178.
A. Farrugia et al.: Complete graphs with zero diagonal inverse
76
[9] R. C. Thompson, Principal submatrices v: some results concerning principal submatrices of arbitrary matrices, Journal of Research of the National Bureau of Standards-B. Mathematical Sciences 72B (1968), 115-125.