ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 141-155
https://doi.org/10.26493/1855-3974.1460.fd6
(Also available at http://amc-journal.eu)
The conductivity of superimposed key-graphs with a common one-dimensional adjacency nullspace
Irene Sciriha *
Department of Mathematics, Faculty of Science, University of Malta, Msida, Malta
Didar A. Ali
Department of Mathematics, Faculty of Science, University ofZakho, Duhok, Iraq
John Baptist Gauci
Department of Mathematics, Faculty of Science, University of Malta, Msida, Malta
Khidir R. Sharaf
Department of Mathematics, Faculty of Science, University ofZakho, Duhok, Iraq Received 9 August 2017, accepted 8 September 2018, published online 5 November 2018
Two connected labelled graphs Hi and H2 of nullity one, with identical one-vertex deleted subgraphs Hi - zi and H2 - z2 and having a common eigenvector in the nullspace of their 0-1 adjacency matrix, can be overlaid to produce the superimposition Z. The graph Z is Hi + z2 and also H2 + zi whereas Z + e is obtained from Z by adding the edge {zi, z2}. We show that the nullity of Z cannot take all the values allowed by interlacing. We propose to classify graphs with two chosen vertices according to the type of the vertices occurring by using a 3-type-code. Out of the 27 values it can take, only 9 are hypothetically possible for Z, 8 of which are known to exist. Moreover, the SSP molecular model predicts conduction or insulation at the Fermi level of energy for 11 possible types of devices consisting of a molecule and two prescribed connecting atoms over a small bias voltage. All 11 molecular device types are realizable for general molecules, but the structure of Z and of Z + e restricts the number to just 5.
Keywords: Nullity, core vertices, key-graphs, superimposition, circuit. Math. Subj. Class.: 05C50, 15A18, 47N70
* Corresponding author. Homepage: http://staff.um.edu.mt/isci1/
E-mail addresses: irene.sciriha-aquilina@um.edu.mt (Irene Sciriha), didar.ali@uoz.edu.krd (Didar A. Ali), john-baptist.gauci@um.edu.mt (John Baptist Gauci), khidir.sharaf@uoz.edu.krd (Khidir R. Sharaf)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
142
Ars Math. Contemp. 16 (2019) 141-155
1 Introduction
The graphs we consider are simple, that is they are undirected with no multiple edges or loops. The 0-1 adjacency matrix G = (a j) of a labelled graph G on n vertices is a n x n matrix such that a j = 1 if there is an edge between the vertices i and j, and aij = 0 otherwise. The degree of a vertex v is the number of non-zero entries in the vth row (or column) of G. A graph is singular if G has zero as an eigenvalue, and nonsingular otherwise. The multiplicity of zero in the spectrum of G is the nullity n = n(G) of the graph G. A kernel eigenvector x of G is a nonzero vector that satisfies Gx = 0. The nullspace ker(G) of G is generated by a basis of n linearly independent kernel eigenvectors. Thus, a graph G is singular if and only if dim(ker(G)) > 1.
A core vertex (CV) of G corresponds to a nonzero entry in some kernel eigenvector. The set of CVs is an invariant of G, that is, it is independent of the basis chosen for ker(G) [14, 15, 16]. A vertex which is not a CV is a core-forbidden vertex (CFV), recently referred to as a Fiedler vertex [1, 10]. Proposition 1.1 characterizes a CV in a singular graph, and Corollary 1.2 is its direct consequence for graphs of nullity one.
Proposition 1.1 ([18]). Let G + u be a graph obtained from G by adding a vertex u. Then n(G + u) = n(G) + 1 if and only if u is a CV of G + u.
Corollary 1.2 ([17]). Let v be a CV of a graph G of nullity one. Then the graph G — v is non-singular.
We make use of a result on the nullity of graphs derived from Cauchy's Interlacing Theorem for real symmetric matrices.
Theorem 1.3 ([11, p. 119]). Let v be any vertex of a graph G on n > 2 vertices. Then
n(G) — 1 < n(G — v) < n(G) + 1.
Theorem 1.3 permits the nullity of a graph to change by at most one on the deletion or addition of a vertex. Thus, a vertex u in a graph G can be one of three types, depending on the difference of the nullity of G — u from the nullity of G. Following the terminology used in [4], a vertex u is a CV, a middle core-forbidden vertex (CFVm¡d) or an upper core-forbidden vertex (CFVupp) if the nullity of the graph G — u obtained from G upon deleting the vertex u is n(G) — 1, n(G), or n(G) + 1, respectively. It follows from Proposition 1.1 that CFVs are vertices corresponding to a zero entry in each kernel eigenvector in the nullspace of G. For the eigenvalue zero, CFVs were renamed F-vertices. For the specific case of CFVupp, they were renamed and P-vertices [2]. Whether electricity flows through a molecule or not is mainly determined by the types of the two vertices (atoms of the molecule) chosen as terminals with a bias voltage across them [5].
From the definitions of the possible types of vertices in a graph, the following result is immediate.
Lemma 1.4. Let Hi and H2 be two graphs such that n(Hi) = n(H2). Then n(Hi — zi) = n(H2 — z2) if and only if zi and z2 are of the same type in Hi and in H2, respectively.
1.1 Superimpositions
To explore the structure of singular graphs, basic subgraphs of nullity one that are found in singular graphs are constructed in [14, 15, 16]. In Proposition 4.3 of [16], it is proved that a
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
143
singular graph of nullity n has n induced subgraphs of nullity one having the least possible number of vertices (called singular configurations).
The kernel eigenvectors are key to determining the substructures that make a singular graph. Focus is placed on singular graphs of nullity one; otherwise distinct singular configurations which are induced subgraphs in a singular graph of nullity more than one may be masked by others belonging to linearly independent kernel eigenvectors. The vertices of a singular configuration corresponding to the nonzero entries in a kernel eigenvector x are the CVs of G and the remaining vertices, if any, are CFVupp [16]. By Proposition 1.1, deleting a CV reduces the nullity, whereas deleting an CFVupp increases the nullity. The question then arises: what are the conditions that need to be satisfied by a graph H of nullity one so that, for some vertex v, the graph H + v retains nullity one and has the same nonzero entries of a kernel eigenvector as H ? The investigations in this paper stem from the quest to answer this question.
First we fix some notation. Two labelled graphs Gi and G2 are identical if they are isomorphic to a labelled graph G and have the same labelling as G; we write G1 = G2 = G. We consider pairs of graphs of nullity one which have a common kernel eigenvector for some labelling of their vertices, and such that each of the two graphs have a vertex which, when deleted, yields two identical graphs. One such example is illustrated in Figure 1, where x = (1, -1,1, -1,0,0,0)* is a kernel eigenvector of both H1 and H2 with the labelling shown, such that when the vertex labelled 7 is deleted from each, the resulting graphs are identical.
5 ¿>
à 6
Figure 1: A pair of non-isomorphic graphs G + 7 of nullity one having a common kernel eigenvector x = (1, -1,1, -1,0,0, 0)4.
1
2
3
4
1
3
6
7
5
2
If two graphs H and H2 are not isomorphic, but the deletion of a vertex zi of H yields a graph identical to that obtained by deleting a vertex z2 from H2, then the difference in the dimensions of the nullspaces of Hi and H2 is bounded as given in the following theorem.
Theorem 1.5. Let Hi and H2 be two graphs having vertices zi and z2, respectively, such that G = Hi — zi = H2 — z2. Then |n(Hi) — n(H2)| = 2 when one of the vertices is a CV and the other is an CFVupp, and |n(Hi) — n(H2)| < 1, otherwise.
Proof. By Theorem 1.3, n(G)-1 < n(Hi) < n(G) + 1 andn(G)-1 < ^(#2) < n(G) + 1. Thus, |n(Hi)-n(H2)| < 2. Equality holds only when, without loss of generality, n(Hi) = n(G) - 1 and n(H2) = n(G) + 1, in which case zi is an CFVupp in Hi and z2 is a CV in H2.	□
In the sequel, let Hi and H2 be two connected labelled graphs of order n > 3 whose 0-1 adjacency matrix has nullity one with a common kernel eigenvector x such that, for
144
Ars Math. Contemp. 16 (2019) 141-155
some vertex zi in Hi and some vertex z2 in H2, Hi - zi = H2 - z2 = G. The graphs Hi and H2 are termed key-graphs. It follows immediately that the label of z1 in H1 is the same as that of z2 in H2. We choose the labels of the vertices zi and z2 to be the last in the two graphs.
The superimposition of the key-graphs Hi and H2 is the graph Z obtained from G by adding both vertices zi and z2 adjacent to the same neighbours as those of zi in Hi and z2 in H2. The graph Z + e is obtained from Z by adding the edge e = ziz2.
In the next section, we look at some examples so that the concept of superimpositions and its possible effects on the type of vertices of a graph becomes clearer.
1.2 Motivation
A conjugated hydrocarbon molecule has a n-system where each carbon atom contributes a delocalized electron in the neutral molecule. The Huckel/Tight-Binding model simplifies Schrodinger's equation to Ax = Ex where A is the adjacency matrix of the carbon skeleton of the molecule, x represents a molecular orbital and E is the orbital energy. Since carbon has a valency of four, chemical graphs for n-systems have at most three sigma bonds per atom (edges meeting at any vertex). In this article we extend our study to any graph where the vertex degree (or valency) can be larger than three.
In chemistry, the role of the electrons in the molecule is crucial in determining the physical and chemical properties of the molecule. The discrete energy levels that an electron may occupy within a molecule are the solutions to Schrodinger's time-independent equation in quantum mechanics. The wave function as a solution of Schrodinger's equation predicts the electron probability density, which in Huckel theory is a sum of orbital densities.
The Hamiltonian for the n-atomic molecular system turns out to be a linear function of the 0-1 n x n adjacency matrix G of the labelled molecular graph G, whose eigenvalues give the energy E of the electron orbitals. The non-zero entries of G correspond to the sigma bonds between pairs of atoms.
In this article we investigate the change in nullity when forming Z and Z + e. The conduction of electricity through a molecular graph with a bias electrical potential across two vertices L and R depends on the nullities of G and of three of its induced subgraphs obtained by deleting L and R separately and jointly [4, 13]. Note that the deletion of a CFV typically preserves the chemical nature of the graph (unless it is a cut vertex), but addition typically does not. In Section 5, conductivity of molecular devices is discussed for examples of molecular graphs of the form Z and Z + e.
In Figure 2, the four vertices 1, 2,3 and 4 are CVs in both H and Z, but the vertex 5 is a CFVupp in H, whereas each of the vertices 5 and 6 is a CFVmid in Z. Each vertex of Z + e is a CV. Both H and Z have nullity one and, since H has a kernel eigenvector (1,1, -1, —1,0)4 and Z has a kernel eigenvector (1,1, -1, —1,0,0)4, there is a kernel eigenvector of H - 5 with the same nonzero entries as for H and Z. It is interesting to note that Z is obtained by superimposing two isomorphic copies Hi and H2 of the singular configuration H, but Z itself is not a singular configuration.
It is thus natural to ask whether Hi and H2 need to be isomorphic (as in the example discussed above) to retain nullity one in Z obtained from H1 by adding the vertex z2. Also, is this a condition that H1 and H2 must satisfy so that the nonzero entries of a kernel eigenvector are preserved in Z?
The graph Z shown in Figure 3 is obtained by superimposing the two graphs of Fig-
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
145
1 2 1 2 1 2
4	3 4	3 4	3
H	Z	Z + e
Figure 2: Two copies of H, of nullity one, are induced subgraphs of the superimposition Z, also of nullity one. The graph Z + e is of nullity two. For all three graphs, there is a vector in the respective nullspace with the same nonzero part 1,1, -1, -1 associated with the first four labelled vertices.
ure 1. Adding the edge e between z1 = 7 and z2 = 8 produces Z+e. The nullity of Z is two whereas that of Z + e is one. This example shows that H1 and H2 need not be isomorphic for the nullity to be one in Z + e. A kernel eigenvector of Z + e is (1, -1,1, —1,0,0,0,0)4, and thus the nonzero entries of a kernel eigenvector of H1 and H2 are also preserved, even though H1 and H2 are not isomorphic.
Figure 3: The graph Z + e with nullity one, having a kernel eigenvector (1, -1,1, -1,0,0,0,0)4, is obtained from the superimposition Z (which has nullity two) of the graphs in Figure 1.
Observe that the nullities of Z and of Z + e are different in the two examples discussed above. The vertices z1 in H1 and z2 in H2 in both examples are CFVupp. They become CFVmid in Z in the example of Figure 2 and also in Z + e in the example of Figure 3. However, z1 and z2 become CV in Z + e in the example of Figure 2 and also in Z in the example of Figure 3. The following results follow immediately from the definitions of CFVmid and CV.
Proposition 1.6. The vertices z1 and z2 are CFVmid in the superimposition Z (respectively in Z + e) if and only if n(Z ) = 1 (respectively n(Z + e) = 1).
Proposition 1.7. The vertices z1 and z2 are CV in the superimposition Z (respectively in Z + e) if and only if n(Z ) = 2 (respectively n(Z + e) = 2).
As we shall show, graphs satisfying Propositions 1.6 and 1.7 exist. However, is it possible that both z1 and z2 be CFVupp in Z or in Z + e? Do the types of the vertices z1
146
Ars Math. Contemp. 16 (2019) 141-155
and z2 determine the type in Z or Z + e? We shall investigate all possible combinations of the vertex type of z1 in H and z2 in H2.
By Lemma 1.4, the type of the vertex z1 in H1 and of the vertex z2 in H2 is the same. Moreover, as we shall see in Lemmas 2.2 and 3.1, vertices z1 and z2 are of the same type in Z and of the same type in Z + e (the type in the latter graph Z + e possibly different from that in the former Z). We thus propose a 3-type-code1 where a type is denoted by:
1.	C if it corresponds to a core vertex;
2.	M if it corresponds to a middle core-forbidden vertex; and
3.	U if it corresponds to an upper core-forbidden vertex.
The code consists of an ordered string of three types and, thus, it has three available positions, namely y1, y2 and y3. Each of the positions y1, y2 and y3 is filled with the symbol C, M or U, depending on the type of the vertices z1 and z2 in the key-graphs, in Z and in Z+e, in that order. The 3-type-code presents 27 classes of graphs. Algebraic considerations show that only 9 may exist.
The case when the two vertices z1 and z2 are both CFVs in the respective key-graphs is discussed in Section 2, yielding 8 possible classes of graphs. In Section 3, the case when they are both CVs produces just one class of graphs. For the graphs {Z} and {Z + e}, what factors determine that the nullity of a graph remains unchanged on deleting a vertex? When does the type of a pair of adjacent vertices remain unchanged after deleting the edge between them? These questions are answered in Section 4. Chemical implications for the conductivity of a molecule which has a graph that is a superimposition are discussed in Section 5.
2 Core-forbidden vertices in the key-graphs
In this section, the vertices zi and z2 are CFVs in the key-graphs H1 and H2, respectively. Thus, the last entry of the common kernel eigenvector x of H1 and of H2 (which corresponds to z1 and z2) is zero. We write x =	where v = 0. Letting z1 and z2 denote
the characteristic vectors representing the adjacencies of z1 and z2 to the vertices of G, we obtain
and
Hix = Hi —
H2X = H2 H-
	=	f G	Zi
0 J	=	V zi4	0
	=	f G	Z2
0 J		V Z24	0
v
"0
v
"F
Gv Zi4v
Gv Z2*v
0
0,
(2.1)
(2.2)
for some v = 0.
The following lemma explores the nullspaces of Z and of Z + e. On adding a vertex to the key graph Hi, of nullity one, the graph Z or Z + e produced is never non-singular.
Lemma 2.1. If z1 and z2 are CFVs in H1 and in H2, respectively, then
(i) (x, 0)4 = (v, 0, 0)4 is a kernel eigenvector of both Z and Z + e;
1 Different three letter acronyms are proposed in [6, 7] to classify classes of molecular graphs as conductors or insulators with respect to the graph-theoretical distance between two connecting vertices of the graph across which there is a small bias voltage.
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...	147
(ii) 1 < ) < 2 and 1 < n(Z + e) < 2.
Proof. Let Z be the adjacency matrix of the graph Z and let W be the adjacency matrix of Z + e, where z1 and z2 are respectively the nth and (n + 1)th labelled vertices of Z and of
Z + e.
(i) Since
and
Z
W
		G	Zi	z2
0 I	=	zi4	0	0
0		^ Z24	0	0
		G	zi	z2
0 I	=	zi4	0	1
0		^ z24	1	0
Gv ziiv
Z2tV
Gv
z^v
Z2tV
then by (2.1) and (2.2), (v, 0,0)* is a kernel eigenvector of Z and of W.
(ii) By Theorem 1.3, 0 < n(Z) < 2 and 0 < n(Z + e) < 2. From (i) above, n(Z) > 1
and n(Z + e) > 1. Thus, 1 < n(Z) < 2 and 1 < n(Z + e) < 2.	□
Next we show that the vertices z1 and z2 must be of the same type in each of the graphs Z and in Z + e, and that they cannot be CFVupp.
Lemma 2.2. Let z1 and z2 be CFVs in H1 and in H2, respectively. Then in each of the graphs Z and Z + e, the two vertices z1 and z2 are either both CFVmid or both CV.
Proof. Suppose first that z1 and z2 are not of the same type in Z. Then, deleting z1 from Z yields the graph H2 which has a different nullity from the graph H1 obtained on deleting z2 from Z, a contradiction since n(H1) = n(H2) = 1. A similar argument yields that the type of vertices z1 and z2 in Z + e must be the same. From Lemma 2.1,1 < n(Z) < 2 and 1 < n(Z + e) < 2, and thus by Propositions 1.6 and 1.7, z1 and z2 are either both CFVmid or both CV.	□
Remark 2.3. From Lemma 2.2 it follows that when z1 and z2 are CFVs in the key-graphs, each of the two positions y2 and in the 3-type-code can be filled in two ways, namely C and M. Therefore, there are only eight possible different classes of the 3-type-code graphs having the first position y1 filled with either M or U.
In the case when both z1 and z2 are CFVs in the key-graphs, we have the following necessary and sufficient condition.
Theorem 2.4. Let z1 and z2 be CFVs in H1 and in H2, respectively. In the graph Z or Z + e, z1 and z2 are CV if and only if they correspond to nonzero entries in exactly one kernel eigenvector of the basis of the nullspace of the graph Z or Z + e.
Proof. By Proposition 1.7, the dimension of the nullspace of Z and of Z + e is two. From Lemma 2.1, (x, 0)* = (v, 0,0)* is a kernel eigenvector of Z and of Z + e. Since z1 and z2 are CV in Z, they correspond to nonzero entries in a kernel eigenvector (yx, a1, ^1)t of Z, for a1 =0 and = 0. A similar argument holds for Z + e.	□
We note that although there are 18 possible 3-type-code classes of graphs when the first entry of the code is not C, Lemma 2.2 restricts the number of possible classes to just 8.
148
Ars Math. Contemp. 16 (2019) 141-155
3 Core vertices in key-graphs
In this section we show that for the case when z1 and z2 are both CV in the key-graphs H1 and H2, respectively, only one 3-type-code class may occur. This case is completely different from the case discussed in Section 2 in that, as we prove in Proposition 3.2 and Theorem 3.5, the nullity of each of the graphs Z and Z + e can take only one value and it is not the same value in the two graphs.
Recall that H1 and H2 have a common kernel eigenvector generating their nullspace. Since z1 and z2 are CVs, the last entry of a common kernel eigenvector x of H1 and of
H2 is nonzero, that is x = ( —— ) for v = 0 and a = 0. Thus, letting z1 and z2 denote
the characteristic vectors representing the adjacencies of z1 and z2 to the vertices of G, we obtain
and
"ar
H
G	Zi ^	(v]		( Gv + az1
zi4	0 )	[a)		V zi4v
	_	f G	z2
a	-	V z24	0
Gv + az2
tl
Z2 v
0
0,
(3.1)
(3.2)
for some v = 0 and a = 0.
An argument similar to that used in the proof of Lemma 2.2 yields the following result.
Lemma 3.1. Let z1 and z2 be CVin H1 and in H2, respectively. Then in each of the graphs Z and Z + e, the two vertices z1 and z2 are of the same type.
The unique value that the dimension of the nullspace of Z can take is given next.
Proposition 3.2. If z1 and z2 are CVin H1 and in H2, respectively, then n(Z) = 2.
Proof. Let Z be the adjacency matrix of the graph Z, where zi and z2 are the nth and (n + 1)th columns corresponding to the characteristic vectors of z1 and z2, respectively. Since
Z
M		G	zi	z2
a ]	=	zit	0	0
0		z2t	0	0
and
Z
		G	zi	z2
0 ]	=	zit	0	0
a		z2t	0	0
then by (3.1) and (3.2), (v, a, 0)4 and (v, 0, a)1 are two linearly independent kernel eigenvectors of Z and hence n(Z) > 2. By Theorem 1.3, 0 < n(Z) < 2. Thus n(Z) = 2, and
(v, a, 0)4 and (v, 0,a.)* span ker(Z).	□
A consequence which has important implications on the construction of Z and, eventually, of Z + e, is the following.
Corollary 3.3. If z1 and z2 are CV in H1 and in H2, respectively, then z1 and z2 are duplicates in Z and H1 = H2.
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
149
Proof. Since (v, a, 0)4 and (v, 0, a)4 are kernel eigenvectors of Z, then (0, a, —a)4 is also a kernel eigenvector of Z. Thus z1 = z2. Hence, z1 and z2 are duplicate vertices in Z, implying that H1 and H2 are equivalent graphs.	□
The dimension of the nullspace of Z + e turns out to be different from that of Z. The result is stated in Theorem 3.5 and the proof follows from Corollary 3.3 and the following lemma. We remark that the graph H in the following lemma plays the role of each of the key-graphs H1 and H2, and hence equations (3.1) and (3.2) still hold for H.
Lemma 3.4. Let z1 be a CV in a graph H of nullity one and let Z be obtained from H by duplicating the vertex z1 to obtain a new vertex z2. Then n(Z + e) =0, where e is the edge z1 z2 .
Proof. Let W be the adjacency matrix of Z + e, where z1 and z2 are the nth and (n + 1)th columns corresponding to the characteristic vectors of z1 and z2, respectively. Let x =
, where v = 0 and a = 0, be a kernel eigenvector of H and let G = H — z1. From
(3.1) and (3.2), it follows that W(v, a, 0)4 = (0,0,a)4 and W(v, 0,a)4 = (0,a, 0)4, and thus neither (v, a, 0)4 nor (v, 0, a)4 are kernel eigenvectors of Z + e.
We claim that Z + e does not have any kernel eigenvectors. For, suppose (u, p, J)4 is a kernel eigenvector of Z + e. Since z1 and z2 are duplicates in Z, and hence co-duplicates in Z + e, then
W
		G	z1	z1
p I	=I	z^	0	1
5			1	0
Gu + (p + ¿)zi ziiu + 5 zi fu + p
implying that p = Thus, a kernel eigenvector of Z + e must be of the form (u, p, p)4. If p = 0, then Gu = 0 and hence (u, 0)4 is another kernel eigenvector of H which is linearly independent of x = (v, a)4, a contradiction since n(H) = 1. Thus p = 0 and we can choose p = a such that an eigenvector of Z + e is (w, a, a)4. Thus,
W
w		G	z1	z1
a	=I	z^	0	1
a			1	0
Gw + 2az1 a I = I z1tw + a a / \ z1tw + a
But from (3.1), Gv + az1 = 0 and thus G(w - 2v) = 0. Hence
•	either w — 2v = 0, in which case v = i w. From (3.1), z1tv = 0, implying that z1tw = 0 and hence a = 0, a contradiction;
•	or w — 2v is a kernel eigenvector of G, in which case n(G) > 1, a contradiction since zi is a CV in H and n(G) = n(H — zi) = 0.
Hence, n(Z + e) = 0.	□
Lemma 3.4 is now applied to the particular case when Z + e is obtained from the superimposition of Hi and H2 with core vertices zi and z2, respectively.
Theorem 3.5. If zi and z2 are CV in Hi and in H2, respectively, then n(Z + e) = 0 and zi and z2 are both CFVupp in Z + e.
0
0
150
Ars Math. Contemp. 16 (2019) 141-155
Proof. By Corollary 3.3, z1 and z2 are duplicate vertices. The first part of the result follows by applying Lemma 3.4. Also, since n(Z + e) = 0, then z1 and z2 cannot be CV in Z + e. Noting that n(Z + e - z1) = n(H2) = 1 and n(Z + e - z2) = n(H1) = 1, we get that z1
Remark 3.6. Proposition 1.7, Proposition 3.2 and Theorem 3.5 imply that when z1 and z2 are CV in the key-graphs, each of the two positions y2 and y3 in the 3-type-code can be filled in only one way, namely C in the position y2 and U in the position y3. Therefore, there is only one possible class of the 3-type-code graphs having C in its first position y1, namely CCU. Moreover the two key graphs H1 and H2 are induced subgraphs in both Z and Z + e.
4 Three-type-code
Were it not for the restrictions of Lemmas 1.4, 2.2 and 3.1, the type of vertices would allow 81 classes of graphs for Z and another 81 for Z + e. These Lemmas allow only 27 potential classes and by eigenvector techniques, even these are further restricted to just nine with a specific 3-type-code. In Figure 4, three molecular graphs {Z + e} that are not chemical are presented for the each type of vertex z1 in H1.
Figure 4: Graphs Z + e, having type M, U and C respectively, for the vertex z1 in H1.
Except for the case UCC (that is, when {z1, z2} are CFVupp in H1 and in H2 and CV in Z and in Z + e), examples for all the remaining eight possible 3-type-codes graphs are known to exist (see Table 1). It is worth noting that among the eight graphs {Z + e} and the associated graphs {Z} drawn in Table 1, six are chemical graphs. The occurrence, or otherwise, of the UCC class remains open. Table 1 illustrates the different types of z1 and z2 in {H1, H2}, in Z and in Z + e, the associated code, the corresponding nullities of Z and of Z + e, and an example of a possible graph Z + e (when existence is known).
Observe that although the interlacing theorem allows three values for the nullity of Z, this value can never be zero.
At this stage, we can provide answers to the questions we posed at the end of Section 1.2 for the subclasses of graphs {Z} and {Z + e}.
(i) On deleting the vertex z1 or z2 from Z, the nullity remains unchanged only for MMM, MMC, UMM and UMC out of the nine possibilities for the 3-type-code with z1 and z2 CFVmid in Z. Similarly, on deleting the vertex z1 or z2 from Z + e, the nullity remains unchanged for MMM, MCM, UMM and UCM.
and z2 are both CFVupp in Z + e.
□
(ii) On deleting the edge e = z1z2 in Z + e, the type of the vertices z1 and z2 remains unchanged when the 3-type-code is one of MMM, MCC, UMM and, possibly, UCC.
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
151
Table 1: All possible cases of superimpositions {Z} and the derived class {Z+e} of graphs.
Type of z1 and of z2 in			Code	n(Z)	n(Z + e)	Example of Z + e				
Hi & H2	Z	Z + e								
CFVmid	CFVmid	CFVmid	MMM	1	1	1				
	CFVmid	CV	MMC	1	2					
	CV	CFVmid	MCM	2	1	1				
	CV	CV	MCC	2	2			Sk / ^2 Jz\		
CFVUpp	CFVmid	CFVmid	UMM	1	1			Zi		1
	CFVmid	CV	UMC	1	2			zi		1
	CV	CFVmid	UCM	2	1	0-				
	CV	CV	UCC	2	2	(not known)				
CV	CV	CFVUpp	CCU	2	0				r	
152
Ars Math. Contemp. 16 (2019) 141-155
We observe that no 3-type-code has U in both positions y2 and y3. This can be explained since if z1 and z2 are CFVupp in Z and n(H1) = n(H2) = 1, then n(Z) = 0, which never occurs by Lemma 2.1 and Proposition 3.2. Another point worth noting is that, in the case where zi and z2 are CFV in the key-graphs, the results do not depend on whether they are upper or middle. Thus, the type of the core-forbidden vertices z1 and z2 in H1 and H2 is not a factor that determines their type in Z and in Z + e. Could it be that distinguishing between the types U and M for z1 and z2 in H1 and H2 would determine the existence or otherwise of UCC?
5 Electrical conductivity
A model device consists of the molecule with a pair of semi-infinite wires attached to it, so that a voltage can be applied across the molecule. The molecule, the wires and the contact atoms are represented by an augmented molecular graph with vertices for atoms and with edges for the sigma bonds. Left and right wires are represented by two special source and sink vertices L and R outside the molecule, which are then in contact with the molecule through single (usually distinct) vertices (contact atoms) labelled L and R. Coulomb and resonance integrals are assigned to the wires and molecule-wire contacts. This model gives a Huckel/Tight-Binding model for ballistic currents which is the simplest version of the SSP (Source-and-Sink Potential) model for ballistic conduction through simple molecular electronic devices [8, 9, 12]. The approximations lead to a non-Hermitian set of linear equations of order n + 2, with an implicit dependence of the SSP matrix entries on the eigenvalue. Linear algebraic techniques are used to describe the solutions of the larger problem in terms of characteristic polynomials derived from the original n x n adjacency matrix.
Conduction or insulation of the unsaturated molecular device can then be predicted. The criteria for conduction at zero energy (the Fermi or non-bonding level) depend on the changes in nullity when the contact vertices L and R are deleted from the molecular graph on n vertices, separately and together [3, 5, 19].
5.1 Transmission
A molecular device G can be considered as a graph on n vertices with two prescribed vertices L and R connected by wires to two vertices L and R outside the molecule. The transmission at energy E, from the sink R, of ballistic electrons entering at the source L, can be expressed in terms of the characteristic polynomials s(E), u(E), t(E) and v(E) of G, G — L, G — R and G — L — R, respectively, as functions of E. To determine whether a device conducts or bars conduction at the Fermi level of energy (E = 0), it suffices to consider the possible nullity signatures as an ordered quadruple (gs = n(G),gu = n(G — L),gt = n(G — R), gv = n(G — L — R)). Cauchy's inequalities for the eigenvalues of real symmetric matrices and of their principal submatrices lead to the interlacing theorem for graphs. As a consequence, the change in the nullity on deleting a vertex can be at most one. Hence relative to gs, each of gu and gt can take 3 values whereas gv can take 5. Thus the quadruple signature can in principle take 45 values with respect to gs.
However interlacing, device symmetry, and the Jacobi-Sylvester theorem (that is u(E)t(E) — s(E)v(E) is a perfect square j^R, where Jir is the LR^ entry of the adjugate of EI — A) restrict the number from 45 to just 11 [5, 19]. Table 2 gives the signatures of all possible classes of n-conjugated devices and their conducting/insulating properties at the
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
153
Fermi level of energy.
Table 2: The conductivity of all devices (G, L, R), their variety [19] and case [5].
Signature(gs ,9t,9u,9v )	Nullity of G	Variety	Case	Transmission
Two CVs		1		
(9s, 9s - 1,gs - 1,gs - 2)	no > 2	1(i)	11	Insulator
(.9s, 9s - 1,gs - 1,gs)	no > 1	1(ii)	9	Conductor
(9s, 9s - 1,9s - 1,9s - 1)	no > 1	1(iii)	10	Conductor
CV and CFV		2		
(9s, 9s + 1,9s - 1,9s)	no > 1	2a	5	Insulator
(9s, 9s, 9s - 1,9s - 1)	no > 1	2b	8	Insulator
Two CFVs		3		
(9s, 9s + 1,9s + 1, 9v)		3a		
(9s, 9s + 1,9s + 1,9s)		3a(i)	2	Conductor
(9s, 9s + 1,9s + 1,9s +2)		3a(ii)	1	Insulator
(9s, 9s + 1, 9s, 9v)		3b		
(9s, 9s + 1,9s, 9s + 1)		3b(i)	3	Insulator
(9s, 9s + 1,9s, 9s)		3b(ii)	4	Conductor
(9s, 9s, 9s, 9v)		3c		
(9s, 9s, 9s, 9s + 1)		3c(i)	6	Conductor
(9s, 9s, 9s, 9s)		3c(ii)	7	
(9s, 9s, 9s, 9s) & ja (0) = 0		3c(iiA)	7i	Conductor
(9s, 9s, 9s, 9s) & ja (0) = 0		3c(iiB)	7ii	Insulator
5.2 A superimposition device
The superimposition Z and the derived graph Z + e have a structure that restricts the number of device classes to which they can belong. Their signature can be determined from Table 1.
All the 11 device classes are realizable by molecular graphs. Table 3 shows that, of these, the superimpositions Z may be of only 5 cases and the derived graphs Z + e may also be of 5 cases. Both Z and Z + e can be of case 7 which assumes conductivity or insulating properties according to the vanishing or otherwise of jZlZ2(0). From Table 2, the derived graph Z + e may be an insulator only for case 7 when both z1 and z2 are middle core-forbidden vertices in their respective key-graphs H1 and H2. Apart from case 7, a superimposition Z is an insulator only when both z1 and z2 are core vertices in their respective key-graphs.
Table 3: All possible cases of superimpositions {Z} and the derived class {Z} of graphs.
Type of zi and of in			Code	Signature(Z)		Signature(Z + e)	
Til &	z	Z + e		Variety	Case	Variety	Case
	CFVmid	CFVmid	MMM	(9s, 9s, 9s, 9s)	3c/7	(9s, 9s, 9s, 9s)	3c/7
CFVmid	CFVmid	CV	MMC	(9s, 9s, 9s, 9s)	3c/7	(9s,9s-i,9s-i,9s-i)	lm/10
	CV	CFVmid	MCM	(9s, 9s~ 1,9s -1,9s-I)	lm/10	(9s, 9s, 9s, 9s)	3c/7
	CV	CV	MCC	(9s,9s-i,9s-i,9s-i)	lm/10	(9s, 9s~ 1,9s -1,9s-I)	lm/10
	CFVmid	CFVmid	UMM	(9s, 9s, 9s, 9s + 1)	3«/6	(9s, 9s, 9s, 9s + 1)	3«/6
CFVupp	CFVmid	CV	UMC	(9s, 9s, 9s, 9s + 1)	3«/6	(9s, 9s - 1,9s ~ 1,9s)	lu/9
	CV	CFVmid	UCM	(9s, 9s - 1,9s ~ 1,9s)	lu/9	(9s, 9s, 9s, 9s + 1)	3«/6
	CV	CV	UCC	(9s, 9s - 1,9s ~ 1,9s)	lu/9	(9s, 9s - 1,9s ~ 1,9s)	lu/9
cv	CV	CFVupp	CCU	(9s, 9s~ 1,9s -1,9s	li/11	(9s,9s + 1,9s + 1,9s)	Zai/2
I. Sciriha et al.: The conductivity of superimposed key-graphs with a common ...
155
References
[1]	D. A. Ali, J. B. Gauci, I. Sciriha and K. R. Sharaf, Coalescing Fiedler and core vertices, Czechoslovak Math J. 66 (2016), 971-985, doi:10.1007/s10587-016-0304-8.
[2]	M. Andelic, C. M. da Fonseca and R. Mamede, On the number of P-vertices of some graphs, Linear Algebra Appl. 434 (2011), 514-525, doi:10.1016/j.laa.2010.09.017.
[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, doi:10.1063/1.4863559.
[4]	P. W. Fowler, B. T. Pickup, T. Z. Todorova, R. De Los Reyes and I. Sciriha, Omni-conducting fullerenes, Chem. Phys. Lett. 568-569 (2013), 33-35, doi:10.1016/j.cplett.2013.03.022.
[5]	P. W. Fowler, B. T. Pickup, T. Z. Todorova and W. Myrvold, A selection rule for molecular conduction, J. Chem. Phys. 131 (2009), 044104, doi:10.1063/1.3182849.
[6]	P. W. Fowler, I. Sciriha, M. Borg and B. T. Pickup, Molecular graphs and molecular conduction: the d-omniconductors, to appear.
[7]	P. W. Fowler, I. Sciriha, M. Borg, V. E. Seville and B. T. Pickup, Near omni-conductors and insulators: Alternant hydrocarbons in the SSP model of ballistic conduction, J. Chem. Phys. 147 (2017), 164115, doi:10.1063/1.4995544.
[8]	A. Goker, F. Goyer and M. Ernzerhof, Bond dissociation and correlation effects in molecular electronic devices, J. Chem. Phys. 129 (2008), 194901, doi:10.1063/1.3013815.
[9]	F. Goyer and M. Ernzerhof, Correlation effects in molecular conductors, J. Chem. Phys. 134 (2011), 174101, doi:10.1063/1.3581096.
[10]	I.-J. Kim and B. L. Shader, On Fiedler- and Parter-vertices of acyclic matrices, Linear Algebra Appl. 428 (2008), 2601-2613, doi:10.1016/j.laa.2007.12.022.
[11]	M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, 1964.
[12]	B. T. Pickup and P. W. Fowler, An analytical model for steady-state currents in conjugated systems, Chem. Phys. Lett. 459 (2008), 198-202, doi:10.1016/j.cplett.2008.05.062.
[13]	B. T. Pickup, P. W. Fowler, M. Borg and I. Sciriha, A new approach to the method of source-sink potentials for molecular conduction, J. Chem. Phys. 143 (2015), 194105, doi:10.1063/1. 4935716.
[14]	I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1998), 193-211, doi:10.1016/s0012-365x(97)00036-8.
[15]	I. Sciriha, On the rank of graphs, in: Y. Alavi, D. R. Lick and A. Schwenk (eds.), Combinatorics, Graph Theory, and Algorithms, Vol. II, New Issues Press, Kalamazoo, Michigan, 1999 pp. 769-778, proceedings of the 8th Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications, dedicated to the memory of Paul Erdos, held at Western Michigan University, Kalamazoo, Michigan, June 3-7, 1996.
[16]	I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007), 451462, doi:10.13001/1081-3810.1215.
[17]	I. Sciriha, Coalesced and embedded nut graphs in singular graphs, Ars Math. Contemp. 1 (2008), 20-31, doi:10.26493/1855-3974.20.7cc.
[18]	I. Sciriha, Maximal core size in singular graphs, Ars Math. Contemp. 2 (2009), 217-229, doi: 10.26493/1855-3974.115.891.
[19]	I. Sciriha, M. Debono, M. Borg, P. W. Fowler and B. T. Pickup, Interlacing-extremal graphs, Ars Math. Contemp. 6 (2013), 261-278, doi:10.26493/1855-3974.275.574.