/^creative ^commor
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) 397-402
No chemical graph on more than two vertices
is nuciferous
Irene Sciriha, Alexander Farrugia
Department of Mathematics, University of Malta, Msida, Malta Received 11 February 2016, accepted 15 April 2016, published online 23 August 2016
Abstract
A simple graph is nuciferous if its 0-1 adjacency matrix is nonsingular and if its inverse has zero entries on its main diagonal and a non-zero entry at each off-diagonal position. A nuciferous graph is a molecular graph that represents an ipso omni-insulating but distinct omni-conducting molecule. It has been conjectured in 2012 that only K2, the complete graph on two vertices, is nuciferous. We show that this conjecture is true for chemical graphs, that is, graphs whose vertex degree is at most three.
Keywords: Nuficerous graph, chemical graph, NSSD, non-singular graph, molecular conductivity. Math. Subj. Class.: 05C50, 05B20
1 Introduction
A molecular graph is a simple graph whose vertices represent the atoms of some molecule and whose edges represent the bonds between the atoms in the molecule. The subclass of molecular graphs that are connected and represent conjugated systems of unsaturated carbon atoms forms the class of chemical graphs, whose vertices represent the carbon atoms and whose edges represent the a-bonds between them [3]. Since the atoms are unsaturated, the degree of each vertex in a chemical graph is one, two or three.
The graph G — v is obtained from a graph G by removing the vertex v and all the edges incident to it. If v and w are vertices in G distinct from u, then we represent the graph (G — u) — v as G — u — v and the graph ((G — u) — v) — w as G — u — v — w. The deck of a graph G is the set {G — 1, G — 2,..., G — n} of its vertex-deleted subgraphs.
A n x n real symmetric matrix A with zero diagonal is the adjacency matrix of an edge-weighted graph G (without loops) on n vertices if a non-zero entry corresponds to an edge and a zero entry to a non-edge. An adjacency matrix of a simple graph G, referred to as a 0-1 adjacency matrix, has zero diagonal and each non-zero entry is 1.
E-mail addresses: irene.sciriha-aquilina@um.edu.mt (Irene Sciriha), alex.farrugia@um.edu.mt (Alexander Farrugia)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
398
Ars Math. Contemp. 11 (2016) 403-413
The characteristic polynomial ^(G, A) of a matrix M is the determinant |xI - M|, where I is the identity matrix. The eigenvalues of M are the roots of its characteristic polynomial. The nullity n(M) of M is the multiplicity of the zero root of the characteristic polynomial of M. The matrix M is singular if n(M) > 0 and is nonsingular if n(M) = 0.
If A is the adjacency matrix of a molecular graph G, then the characteristic polynomial, eigenvalues and nullity of G are the same as those of A. A graph is singular if its adjacency matrix is singular and non-singular otherwise. The nullity n(G) of a molecular graph G corresponds to the number of non-bonding orbitals (zero energy level) of the molecule represented by G.
The electron orbital energies given by the Huckel approximation of Schrodinger's equation on the quantum theory of molecules correspond to the eigenvalues of the 0-1 adjacency matrix. According to the Source and Sink Potential quantum mechanical model for molecular conduction in a chemical graph G [4,6], electron transmission T(E), at the energy E, is determined in terms of the characteristic polynomials of ^(G, E), ^(G-v, E), ^(G-w, E) and ^(G - v - w, E), where the carbon atoms v and w are in contact with wires in a circuit containing the molecule G [3, 7]. At the Fermi energy (E = 0), with a small bias voltage across the molecule, electron transmission or insulation was found to depend critically on the nullity of the adjacency matrices of the three aforementioned subgraphs of G relative to the nullity of the parent graph G [7].
In [3, Theorems 4.1 and 4.4], it was proved that for a nonsingular molecular graph G with adjacency matrix A, conduction between carbon atoms i and j at the Fermi energy occurs if and only if the j entry of A-1 is non-zero. This is true even if i = j, in which case the connection is said to be ipso. It is thus theoretically possible that, at the Fermi energy (E = 0), conduction occurs for all connecting vertex pairs i = j, but insulation occurs for all i = j. Such a molecule is called a distinct omni-conducting but ipso omni-insulating molecule in [3], and corresponds to a nonsingular molecular graph G whose 0-1 adjacency matrix A, with zero diagonal, has an inverse having zero entries on its diagonal and non-zero entries off its diagonal. In [7], such graphs are referred to as nuciferous.
Definition 1.1 ([7, Definition 7.8]). Let G be a nonsingular simple graph with the offdiagonal entries of the inverse A-1 of its 0-1 adjacency matrix A being nonzero and real, and all the diagonal entries of A-1 being zero. Then G is said to be a nuciferous graph.
The complete graph Kn has n vertices and every pair of distinct vertices is connected by
an involution (K2 = I). In [7], it was conjectured that there are no other nuciferous graphs.
Conjecture 1.2 ([7, Conjecture 7.11]). The graph K2 is the only nuciferous graph.
The purpose of this paper is to prove Conjecture 1.2 for the subclass of chemical graphs, whose vertex degree is at most three. In order to do this, we use the class of NSSDs (Non-Singular graphs with a Singular Deck) defined in [1], which is a superclass of that of nuciferous graphs.
Definition 1.3. A graph is a NSSD if both the real symmetric matrices A and A-1 have zero diagonal.
In this paper we use only simple NSSDs, that is NSSDs for which A is a 0-1 adjacency matrix. Simple NSSDs correspond to molecular graphs that represent ipso omni-insulating
an edge. The complete graph K2 is nuciferous, since its adjacency matrix K
I. Sciriha and A. Farrugia: No chemical graph on more than two vertices is nuciferous
399
carbon molecules. An ipso omni-insulator is a molecule that, at the Fermi energy, does not conduct when i = j, but may, or may not, conduct when i = j, for wires connecting at i and j [3].
We provide the following characterization of a nuciferous graph in relation to a NSSD.
Theorem 1.4. A graph G with 0-1 adjacency matrix A is nuciferous if and only if G is a simple NSSD and each off-diagonal entry of A-1 is non-zero.
The paper is organised as follows. Section 2 contains further notation used in this paper, together with preliminary results that lead to the main result. The nullity of subgraphs of NSSDs used for the proof of the main result are determined in Section 3. In Section 4, Conjecture 1.2 is proved to hold true for chemical graphs.
2 Preliminaries
We shall use a result by Fiedler and Markham [2] that relates the nullity of the blocks of a partitioned nonsingular matrix with those of its inverse.
Theorem 2.1 ([2, Theorem 2]). If M is a nonsingular matrix such that M and M-1 are partitioned as
for some conformable partitioning of M and M 1, then n(Mn) = n(N22).
In Theorem 2.1, the block matrices M11 and N22 are called complementary block submatrices of each other. Theorem 2.1 can be extended to any submatrix of M as follows.
Theorem 2.2. If M is a n x n nonsingular matrix, then the nullity of any p x q submatrix R of M is equal to the nullity of the (n — q) x (n — p) complementary block submatrix of R in M-1.
We shall also make use of the following elementary lemma.
Lemma 2.3. The rank of a non-zero real and symmetric matrix, with diagonal entries equal to zero, cannot be equal to 1.
If A is a non-singular symmetric matrix and has the integer entries 0 and 1, then A-1 is symmetric and has rational entries. Thus, we can associate a graph G-1 with A-1; such a graph would be a weighted, undirected graph and with rational edge weights. We call G-1
the inverse of G.
We now show that the zero diagonal entries of the inverse of the adjacency matrix of an ipso omni-insulator determine the nullity of the vertex-deleted subgraphs of G. By Theorem 2.1, the nullity of any (n — 1) x (n — 1) principal submatrix of A has nullity equal to that of its 1 x 1 complementary block submatrix (0) in A-1, that is, it has nullity one. Since each diagonal entry of A-1 is zero, it follows that each of the vertex-deleted subgraphs G — 1, G — 2,... ,G — n of an ipso omni-insulator (a simple NSSD) is singular
Theorem 2.4. The following statements are equivalent for a molecular graph G: 1. G is an ipso omni-insulator;
[1].
400
Ars Math. Contemp. 11 (2016) 403-413
2.	G is a simple NSSD;
3.	G is a simple, nonsingular graph G on n vertices whose vertex-deleted subgraphs G — 1, G — 2,... ,G — n are singular;
4.	G is a nonsingular simple graph whose inverse is an undirected weighted graph with no loops.
From Theorems 1.4 and 2.4, we have:
Theorem 2.5. A nuciferous graph is a simple NSSD whose inverse is a complete graph with rational edge weights and no loops.
3 The nullity of vertex-deleted subgraphs of simple NSSDs
We now make use of Theorem 2.1 again to obtain the nullity of vertex-deleted subgraphs of simple NSSDs after the removal of up to three of their vertices. In order to do so, we first require the following result, which follows directly from Lemma 2.3.
Proposition 3.1. For a simple NSSD, no q x q principal submatrix of the adjacency matrix A or of its inverse A-1 has nullity (q — 1).
Proof. Since a principal submatrix of A is a 0-1 symmetric matrix with zero diagonal, by Lemma 2.3, its rank cannot be one. By definition of a simple NSSD, A-1 exists and its diagonal is also zero. Furthermore, the entries of A-1 are rational. Thus, the result holds true for A-1 as well.	□
Together with the fact that only the zero q x q matrix has nullity q, we now show that the nullity of vertex-deleted subgraphs of simple NSSDs may be inferred from those of the complementary block submatrix in A-1 using Theorem 2.1 and Proposition 3.1.
3.1	Nullity of G - u
We have already proved, in the paragraph prior to Theorem 2.4, that the nullity of all the one-vertex-deleted subgraphs of any NSSD is one.
Theorem 3.2 ([1]). If G is a simple NSSD, then G — u has nullity one for any vertex u of G.
3.2	Nullity of G - u - v
The nullity of two-vertex-deleted subgraphs of NSSDs may be one of two values, as shown in Theorem 3.3 below. This result was proved in [1] for NSSDs which are not necessarily simple.
Theorem 3.3 ([1]). If G is a simple NSSD, then G — u — v has nullity zero if {u, v} is an edge of G-1 and has nullity two otherwise.
Thus, if G is a NSSD, then for i = j, the ijth entry of A-1 is zero if G — i — j is singular and is nonzero if G — i — j is nonsingular. This provides an interesting interpretation for the zero-nonzero pattern of the inverse of a simple NSSD.
I. Sciriha and A. Farrugia: No chemical graph on more than two vertices is nuciferous
401
3.3 Nullity of G — u — v — w
The nullity of three-vertex-deleted subgraphs of simple NSSDs relates to triangles (circuits of size three) present in their inverse.
Theorem 3.4. If G is a simple NSSD, then G — u — v — w has nullity
a)	zero, if the edges {u, v}, {u, w} and {v, w} form a triangle in G-1;
b)	three, if none of {u, v}, {u, w} or {v, w} is an edge in G-1;
c)	one, otherwise.
Proof. Let u, v, w be any three distinct vertices of the NSSD G. By Theorem 2.1, the nullity of G — u — v — w is equal to the nullity of the 3 x 3 complementary block submatrix V in A-1. By Proposition 3.1, the nullity of G — u — v — w must be 0,1 or 3. The nullity is three if and only if V = 0, which is equivalent to saying that none of {u, v}, {u, w} or
/0 ci cA
{v, w} is an edge of G-1. Since the matrix V is of the form I ci 0 c3 I for some real
\C2 C3 0j
numbers c1, c2, c3 and |V| = 2c1c2c3, n(V) = 0 if and only if none of c1, c2 or c3 is zero. In such a case, the edges {u, v}, {u, w} and {v, w} are all edges of G-1 and thus form a triangle in G-1. In any other case, n(V) > 0 and the result is established.	□
4 Nuciferous chemical graphs
In this section we prove Conjecture 1.2 for chemical graphs, that is, for graphs whose degree is at most three.
Theorem 4.1. The only nuciferous chemical graph is K2.
Proof. The 0-1 adjacency matrix K of an undirected graph K2 with no loops satisfies K = K-1 and can be readily verified to be a nuciferous chemical graph. Thus, let G be any simple graph different from K2. The trivial graph on a single vertex is not a simple NSSD, since it is singular, while the other graph on two vertices is disconnected, and hence singular. Graphs on three vertices are either singular or complete. Each vertex-deleted subgraph of K3 is K2 which is not singular. Hence G must have at least four vertices in order to be a simple NSSD. By Theorem 1.4, this is a necessary condition for G to be nuciferous. We now show that the vertex degrees of G must all be greater than three for G to be nuciferous.
Choose any arbitrary vertex v from among the vertices of G. If v is of degree one, then
/H r 0\
the adjacency matrix A of G can be partitioned into ( rT 0 11, where the last column
\0T 1 0/
portrays the adjacencf of v. Since A is nonsingular, there exists A-1 with conformal
/L y v\
partition I yT 0 pi . Consider \vT p 0/
H r 0f / L y vf /1 0 0f
rT 0 1 I ( yT 0 p I = I 0T 1 0 I .
0T 10/ \vT p 0/ V 0 1/
402
Ars Math. Contemp. 11 (2016) 403-413
By multiplying the last row of A by the first column of A-1, we obtain yT = 0T, and hence y = 0. Thus, not all of the off-diagonal entries of A-1 are nonzero. By Definition 1.1, A is not a nuciferous graph.
If v is of degree two and is adjacent to vertices u and w in G, then in the graph G-u-w, v is an isolated vertex. Thus G - u - w is singular. By Theorem 3.3, it must have nullity two, which implies that {u, w} is not an edge in G-1. Thus, there exists an off-diagonal entry of A-1 equal to zero, so G is not a nuciferous graph.
Now let the degree of v be three and let the three neighbours of v be u, w and z. Since v is again an isolated vertex of G - u - w - z, this vertex-deleted subgraph is singular. By Theorem 3.4, the nullity of G - u - w - z is either one or three, and in either case, at least one of {u, w}, {u, z} or {w, z} is not an edge in G-1. Again, this means that A-1 has a zero entry off its diagonal; thus G is not a nuciferous graph.
Hence the degree of all the vertices of a nuciferous graph G on at least four vertices must be greater than three. Consequently, the only nuciferous chemical graph is K2. □
Remark 4.2. After this work was completed, the authors were informed of the existence of the article by Ghorbani [5] in which examples of non-chemical nuciferous graphs were presented. This shows that Theorem 4.1 proved here cannot be strengthened to cover general graphs.
References
[1]	A. Farrugia, J. B. Gauci and I. Sciriha, On the inverse of the adjacency matrix of a graph, Special Matrices 1 (2013), 28-41.
[2]	M. Fiedler and T. L. Markham, Completing a matrix when certain entries of its inverse are specified, Linear Algebra Appl. 74 (1986), 225-237.
[3]	P. W. Fowler, B. T. Pickup, T. Z. Todorova, M. Borg and I. Sciriha, Omni-conducting and omni-insulating molecules, J. Chem. Phys. 140 (2014), 054115.
[4]	P. W. Fowler, B. T. Pickup, T. Z. Todorova and W. A. Myrvold, Selection rule for molecular conduction, J. Chem. Phys. 131 (2009), 044104.
[5]	E. Ghorbani, Nontrivial nuciferous graphs exist, Ars Math. Contemp. 11 (2016), 391-395.
[6]	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.
[7]	I. Sciriha, M. Debono, M. Borg, P. W. Fowler and B. T. Pickup, Interlacing-extremal graphs, Ars Math. Contemp. 6 (2012), 261-278.