On Sum Graphs over Some Magmas

[cor]Corresponding author

aff]Rogério Reis

[aff]organization=CMUP & DM-DCC, Faculdade de Ciências
da Universidade do Porto, addressline = Rua do Campo Alegre,
postcode =4169-007, city=Porto, country=Portugal

We consider the notion of a sum graph and relaxed sum graph over a
magma, give several examples and results of sum graphs over some
natural magmas. We classify the cycles that are sum graphs for the
magma of the subsets of a set with the operation of union, determine
the abelian groups that provide a sum labelling of $C_4$, and show
that $C_{4\ell}$ is a sum graph over the abelian group
$\ZZ_f\times\ZZ_f$, where $f=f_{2\ell}$ is the corresponding
Fibonacci number. For integral sum graphs, we give a linear upper
bound for the radius of matchings, improving Harary's labelling for
this family of graphs, and give the exact radius for the family of
totally disconnected graphs.

Using the Z3 SMT-system, we found integer labellings for the
4D-cube, giving a negative answering to a question of Melnikov and
Pyatikin, having also obtained some results on mod sum graphs and
relaxed sum graphs. Finally, we show that the direct product
operation is closed for strong integral sum graphs.

Graph labellingsum graphintegral sum graph

§ INTRODUCTION

Harary introduced the notions of a sum graph and a
difference graph in [7]. In the first case, one
has a graph that can be labelled with elements of $\NN$, the set of
positive integers, in such a way that two vertices are adjacent if and
only if the sum of the labels of those vertices is a label of some
other vertex, while in the second case the absolute value of the
diference replaces the sum.  In Section $4$ of [7]
(p. 105), Harary remarks that the notion of a sum graph can be
naturally extended to other “number systems”, which in its wider
generality are magmas (cf. Definition 1, p. 1 in

In Section 2, we define the notion of a sum graph over a magma, as
well as the notion of a relaxed sum graph, giving some examples.

In Section 3, we deal with sum graphs over magmas with operations on
sets, showing that $C_n$, the cycle of length $n$, is a sum graph, for
$n\geq 4$, exactly when $n$ is even; characterising when the complete
graph, $K_m$, is a sum graph for the symmetric difference; and showing
that $C_4$ is not a sum graph for the magmas over sets with the
operation given by the complement of intersection, or of the union.

In Sections 4 to 8 we investigate when are cycle graphs sum graphs
over finite abelian groups. In particular, we show that $C_4$ is a sum
graph over an abelian group if and only if the order of the group is a
multiple of $5$; find a necessary condition for $C_n$ to be a
sum graph over an abelian group, and use this to give several
examples. Finally, we show that $C_{4\ell}$ is always a sum group over
an appropriate abelian group.

An integral sum graph, first defined in [8], is nothing
more that a sum graph over the additive group of the
integers. Melnikov and Pyatkin [12] introduced the
notion of the radius of an integral sum graph, and in Section 9 we
give a linear upper bound for the radius of matchings, improving
Harary's labelling for this family of graphs. We also give the exact
radius for the family of totally disconnected graphs.  Using the Z3
problem solver, we found the exact number of integral sum graphs, and
of relaxed integral sum graphs, for all graphs with size up to 8, as
well as the number of integral for the cubic graphs with 4 to 12
vertices, and also integer labellings for the 4D-cube, $Q_4$, giving a
negative answering to a question of Melnikov and Pyatikin. Moreover,
we give the radius of $Q_4$, and show that it has an infinite number
of primitive labellings.

In Section 10, using again Z3, we found out that $K_{3,3}$ is not a
mod sum graph, while $Q_3$ and the Petersen graph are mod sum graphs
for appropriate moduli. We give an explicit upper bound for the
minimal modulus for which a connected graph admits a sum labelling.

In Section 11, using Z3 one more time, we found out that $K_{3,3}$ is
a relaxed mod sum graph, while the triangular prism is not. We also
found the exact number of relaxed integral sum graphs for all cubic
graphs with 4 to 14 vertices.

Finally, in Section 12, we show that the direct product of two strong
integral sum graphs is also a strong integral sum graph.

§ SUM GRAPHS OVER MAGMAS

The relevance of the notion of a sum graph is that it constitutes a
concise description for the graphs that admit a suitable
labelling. For this purpose, a magma is the more general structure
that accomodates this representation. Recall that a magma is just a
set equipped with a binary operation.

Given a magma $(M,\oplus)$ and $V\subseteq M$, we will denote by
$\mathcal{G}_{(M,\oplus)}(V)$, or simply by $\mathcal{G}_{M}(V)$
when the operation on $M$ is clear from the context, the (simple)
graph $G=(V,E)$ whose edges are given by:

\begin{equation}
\label{sumgraph_c}
(v,w)\in E \iff v\oplus w\in V \;\;\vee\;\; w\oplus v\in V.
\end{equation}

A graph $G$ is a sum graph over $M$, or an $M-$graph,
when $G=\mathcal{G}_M(V)$ for some $V\subseteq M$. A graph is said
to be a strong $M-$graph when, for any $v\in V$, $v\oplus
v\not\in V$.

A labelling of a graph $G=(V,E)$ on a magma $M$ is a map
$\lambda:V\to W$ with $W\subseteq M$ such that the graphs $G$ and
$\mathcal{G}_{M}(W)$ are isomorphic. The labelling is called a
strong labelling if $\mathcal{G}_{M}(W)$ is a strong

* The following is an example of a $(\ZZ,+)-$graph with the
vertices identified with their labels, as we will always do
throughout this paper:

[node distance=15mm, scale=1, auto=left]
(n1) -3;
(n2) [right of=n1] 1;
(n3) [below of=n2] -2;
(n4) [left of=n3] -1;
(n5) [right of=n2] -4;
(n6) [right of=n3] 3;
/→in n1/n2, n2/n3, n3/n4,
n4/n1,n2/n5,n3/n6,n5/n6 () – (→);

* In [8], Harary points out that, letting
$(a_n)_{n\in\NN}$ be inductively defined by $a_0=1$, $a_1=2$,
$a_n = a_{n-2}-a_{n-1}$, for $n\geq 2$, the path graph, $P_n$, for
$n\geq 4$, is a $(\ZZ,+)-$graph with the labelling given by this
sequence. For instance:

[node distance=15mm, scale=1, auto=left]
(n0) $P_6$:;
(n1) [right of=n0] 1;
(n2) [right of=n1] 2;
(n3) [right of=n2] -1;
(n4) [right of=n3] 3;
(n5) [right of=n4] -4;
(n6) [right of=n5] 7;
/→in n1/n2, n2/n3, n3/n4, n4/n5,n5/n6 () – (→);

Harary does not provide a proof that this labelling does not generate
spurious edges. A proof was provided by Sharary for a family of close
related labellings (see Lemma 4 in [15]). Observe that the
maximum absolute of these labellings grows exponentially with the size
of the graph, but, as a consequence of the proof of Theorem 1 in
[12], it can be shown there exists a labelling that is
linear (see first paragraph in Section <ref> below).

* Every graph $G=(V,E)$ is an $M-$graph over some magma $M$. For
example, one can define $M=\{v,\bullet\}$, for some fixed $v\in V$
and the operation $\oplus$ on $M$ by: $a\oplus b=v$ if $(a,b)\in E$,
and $a\oplus b=\bullet$ if $(a,b)\not\in E$.

* Obviously, when $M$ is a commutative magma condition
(<ref>) simplifies to:

$$(a,b)\in E \iff a\oplus b\in V.$$

* A sum graph is simply a $(\NN,+)-$graph; an integral sum graph
is a $(\ZZ,+)-$graph. We will simply call them $\NN-$graphs and
$\ZZ-$graphs, respectively.

* A difference graph [7] is nothing else than an
$(\NN,\ominus)-$graph, where $x\ominus y = |x-y|$.

* A mod sum graph, a concept introduced and studied in
[2], is a $(\ZZ_m,+)-$graph, for some $m\in\NN$ with
$m\geq 2$ (the case $m=1$ is rather trivial). We will just call them

* In [1] it was shown that $(\NN_{\geq
2},\times)-$graphs are exactly the same as $(\NN,+)-$sum

* In [10] it was shown that a $(\RR^+,+)-$graph
is a $(\NN,+)-$graph.

* It is clear that any $\NN-$graph with more than one vertex
cannot be connected, since the vertex with the maximum value cannot
be adjacent to any other vertex. This leads to the notion of the
sum number of a given graph $G$, as the smallest number of
isolated nodes which when added to $G$ yields a sum graph.  In
[8], Harary states that the sum number of $C_n$ is $2$
for all $n\geq 3$, except for $n=4$, in which case it is $3$. A
proof of this statement was given in <cit.>. As an example, the graph $C_4 \cup 3 K_1$ can be
given as a $\NN-$graph in the following way, for instance:

[node distance=15mm, scale=1, auto=left]
(n1) 1;
(n2) [right of=n1] 3;
(n3) [below of=n2] 6;
(n4) [left of=n3] 8;
(n5) [right of=n2] 4;
(n6) [below of=n5,yshift=7.5mm] 9;
(n7) [right of=n3] 14;
/→in n1/n2, n2/n3, n3/n4, n4/n1 ()
– (→);

* According to Gallian [6], the notion of a strong
sum graph was introduced in [4]. It was used in
[5] to prove a conjecture of Harary, made in
[7], that the sum number of every tree with at least two
vertices is $1$.

The notion of a sum graph isomorphism is the natural one:

Given two sum graphs $\mathcal{G}_{(M,\oplus)}(V)$ and
$\mathcal{G}_{(N,\odot)}(W)$, a bijective map $f:V\to W$ is said to
be a sum graph isomorphism if

\begin{equation}\label{sumgraphiso_c}
f(v_1\oplus v_2) = f(v_1) \odot f(v_2), \text{ for all } v_1,
v_2\in V.
\end{equation}

If an isomorphim exists between the two sum graphs, we express that
by writing
$\mathcal{G}_{(M,\oplus)}(V)\simeq \mathcal{G}_{(N,\odot)}(W)$, and
say that the two sum graphs are isomorphic.

The notion of a sum graph can be generalised by allowing distinct
vertices to have the same labelling, a concept that is obviously still
quite useful to give a concise description of a graph that allows such
a representation.

A relaxed sum graph over the magma $M$, or
$M-_{\rm rx}$graph for short, is defined as in
Definition <ref> but by allowing $V$ to be a multiset with
domain $M$.

* It is clear that every complete graph $K_n$ is a
$\ZZ-_{\rm rx}$graph with the zero labelling, i.e. all vertices are
labelled with $0$. The fact that the complete graphs, a family
easily described, are not integral sum graphs for $n\geq 4$
([15]) shows by itself the usefulness of the notion of
relaxed sum graph.

* Here is an example of a graph, a cubic graph, that is not a
$\ZZ-$graph, but is a $\ZZ-_{\rm rx}$graph:

[node distance=15mm, scale=0.6, auto=left]
(n1) at (0,0) -3;
(n2) at (2,-2) -15;
(n3) at (2,2) -11;
(n4) at (2,0) -3;
(n5) at (4,2) 5;
(n6) at (4,0) -1;
(n7) at (4,-2) 4;
(n8) at (6,0) -14;
(n9) at (8,-1) 3;
(n10) at (8,1) 3;
(n11) at (10,2) -6;
(n12) at (10,-2) -18;
() – (→);

This example was found with the help of the Z3 Theorem Prover, as
explained below, in Section <ref>.

§ MAGMAS ON SETS

§.§ The Union and the Intersection

Let $U(S)=(\pp(S),\cup)$ be the magma of the subsets of a set $S$ with
the union operation, and $I(S)=(\pp(S),\cap)$. The map
$\Psi:U(S)\to I(S)$ given by $\Psi(A)=\bar{A}$ is a magma isomorphism,
and thus a graph is a sum graph over $U(S)$ if and only if it is a sum
graph for $I(S)$.

For $U(S)$, the complete graphs $K_n$ are sum graphs for all
$n\leq |S|+1$, as it is enough to consider a chain of $n$ sets.

An example of a $C_4$ sum graph over $U(S)$, when $S$ has at least $4$
elements, is the following, where $A,B,C,D\subseteq S$ are four
disjoint subsets of $S$:

[node distance=2cm, scale=1, auto=left]
(n1) $A$;
(n2) [right of=n1] $A\cup B\cup C$;
(n3) [below of=n2] $C$;
(n4) [left of=n3] $A\cup C\cup D$;
/→in n1/n2, n2/n3, n3/n4, n4/n1 ()
– (→);

Actually, one has:

When $n\geq 5$ is an odd integer, the graph $C_n$ is not a sum graph
over any magma of subsets of a set with the union operation. The
graph $C_{2k}$ is a sum graph over that magma for a set with $2k$

We start by noticing that, in such a sum graph that contains no
triangles, if $a$ and $b$ are two adjacent vertices, then $a\cup b$
cannot be distinct from both $a$ and $b$. Therefore, given two
adjacent vertices, one of them must contain the other.

Suppose now that $C_n$ is a sum graph, and let $v_1$ be a vertex that
is minimal for inclusion. Then $v_2$ contains $v_1$, and $v_3$ cannot
contain $v_2$ because that would create a triangle, so that $v_3$ must
be contained in $v_2$. The same reasoning applies to every consecutive
vertex, and therefore the Hasse diagram of the vertices must have the

[node distance=2cm, scale=1, auto=left]
(v1) $v_1$;
(v2) [above right of=v1,xshift=-4mm] $v_2$;
(v3) [right of=v1] $v_3$;
(v4) [right of=v2] $v_4$;
(v5) [right of=v3] $v_5$;
(v6) [right of=v4] ;
[-] (v1)edge(v2)
[dashed] (v5) – (v6);

There are two cases to consider: either $v_n$ is in the lower or in
the upper level of this diagram. In the first case, it cannot be
connected to $v_1$, as that would entail the edge $v_n v_2$, showing
that $C_{2n+1}$ is not a sum graph for $n\geq 2$. In the second case
one can give the following construction of $C_{2k}$: take pairwise
disjoint subsets $A_1, \ldots,A_k, B_1, \ldots, B_k$ (each can be a
singleton, for example) and set $v_{2i-1} = A_i$ and
$v_{2i}= A_i\cup A_{i+1}\cup B_i$, for $i=1,\ldots,k$, where we set
$A_{k+1} = A_1$.

§.§ The Symmetric Difference

Let $S$ be a finite set, and consider the group given by the symmetric
difference on the subsets of $S$. Note that the empty set is the
neutral element in this group, while every element is its own
inverse. A group in which every element, other than the identity, has
order 2 is called a Boolean group, and it is easy to see that
every finite Boolean group is isomorphic to the group formed by the
subsets of some finite set, with the symmetric difference.

It is clear that, for all $n\in\NN$, the complete graph $K_{2^n}$ is a
sum graph for any of these groups. By removing the vertex
corresponding to the neutral element, one sees that the graph
$K_{2^n-1}$ is also a sum graph. We now show that there are no other
complete graphs that are sum graphs for Boolean groups.

A graph $K_m$ is a sum graph over some magma of subsets of a set $S$
with the symmetric difference if and only if $m = 2^k-\varepsilon$
for $\varepsilon\in\{0,1\}$.

Suppose $K_m$ is a sum graph over the group $A$ of subsets of a
set $S$ with $n$ elements. Since in these groups each element is its
own inverse, and the operation restricted to the vertices of the graph
is closed, the subset formed by the vertices is either a subgroup of
$A$, if the empty set is one of the vertices, or, otherwise, becomes a
subgroup when adding the empty set. Thus, by Lagrange's theorem,
either $m$ or $m+1$ divides $2^n$.

§.§ The Complements of the Intersection and of the Union

Consider the magmas $\overline{U}(S) = (\pp(S),\overline{\cap})$ and
$\overline{I}(S) = (\pp(S),\overline{\cup})$ on the subsets of a set
$S$ with the operations given by
$A\,\overline{\cap}\, B = \overline{A\cap B}$ and
$A\,\overline{\cup}\, B = \overline{A\cup B}$, respectively, where the
overline denotes the complement.

The map $\Psi:\overline{U}(S)\to \overline{I}(S)$ given by
$\Psi(A)=\bar{A}$ is a magma isomorphism, and thus a graph is a sum
graph over $\overline{U}(S)$ if and only if it is so for

The graph $C_4$ is not a sum graph over a magma $\overline{U}(S)$.

Suppose there is such a magma $\overline{U}(S)$, and let $A$
and $B$ be two adjacent vertices. Their composition
$\bar{A}\cup \bar{B}$ must be a third vertex, since
$\bar{A}\cup \bar{B} = A$ (for example) implies $A=S$ and
$B=\emptyset$, and then all edges incident to $\emptyset$ would be
present in the graph. Without loss of generality, we may assume that
the labelling of $C_4$ is as follows:

[node distance=2cm, scale=1, auto=left]
(n1) $A$;
(n2) [right of=n1] $B$;
(n3) [below of=n2] $\bar{A}\cup\bar{B}$;
(n4) [left of=n3] $C$;
/→in n1/n2, n2/n3, n3/n4, n4/n1 ()
– (→);

Now, $B\,\overline{\cap}\,(\bar{A}\cup\bar{B}) = \bar{B}\cup A$ is
either $C$ or $A$, because, as we just saw one cannot have
$X\,\overline{\cap}\, Y = X$, for any vertices $X$ and $Y$.

In the first case, $C=\bar{B}\cup A$, the edge $BC$ would be
present. In the other case, one would have $\bar{B}\subseteq A$, and
therefore $\bar{A}\subseteq B$, which entails that the diagonal edge
opposed to $BC$ would be present.

§ THE $C_4$ PROBLEM ON ABELIAN GROUPS

As mentioned above, $C_4$ is not a sum graph, i.e. an $\NN$-graph. It
is not even a $\ZZ-$graph, as stated by Harary in [8] and
proved by Sharary in <cit.>. For a short and
elegant proof of this, see section 2 of [12].

Let us, then, consider the problem of determing the abelian groups $A$
such that $C_4$ is an $A-$graph.  Assume one has such a group $A$, and
let $V=\{a,b,c,d\}\subseteq A$. Since $0$, the neutral element of $A$,
cannot be in $V$, as it would be adjacent to every vertex, it is easy
to see that there are only two cases to consider:

[node distance=2cm, scale=1, auto=left, every
node/.style=circle, fill=black!10]
(n1) $a$;
(n2) [right of=n1] $b$;
(n3) [below of=n2] $c$;
(n4) [left of=n3] $d$;
/→in n1/n2, n2/n3, n3/n4, n4/n1
() – (→);

\begin{cases}
\end{cases}
\begin{cases}
\end{cases}
\end{array}

From these one deduces that one must have, in both cases, $5 a=0$
(with $a\neq 0$), and, respectively,

\begin{equation*}
\begin{array}{ccc}
\begin{cases}
\end{cases}
\begin{cases}
\end{cases}
\end{array}
\end{equation*}

Note that both give rise to the same set of vertices and, in both
cases, the sums of the diagonally opposed vertices are $0$, which
ensures that resulting graph is indeed a $C_4$. This proves the

If $A$ is an abelian group of order $n$, then $C_4$ is a $A-$graph
if and only if $5 \mid n$.

Example: Choosing $a=1$ in $\ZZ_5$ and $a=3$ in $\ZZ^*_{11}$,
one obtains the following isomorphic sum graphs over these groups:

[node distance=2cm, scale=1, auto=left]
(n1) 1;
(n2) [right of=n1] 3;
(n3) [below of=n2] 4;
(n4) [left of=n3] 2;
at (1,-1) $\ZZ_5$;
/→in n1/n2, n2/n3, n3/n4, n4/n1 ()
– (→);

[node distance=2cm, scale=1, auto=left]
(n1) 3;
(n2) [right of=n1] 5;
(n3) [below of=n2] 4;
(n4) [left of=n3] 9;
at (1,-1) $\ZZ^*_{11}$;
/→in n1/n2, n2/n3, n3/n4, n4/n1
() – (→);

§ THE $C_N$ PROBLEM

Given $n\in\NN$, let us consider the problem of finding an abelian
group $A$ for which $C_n$ is a $A-$graph. We will restrict our search
to Fibonacci labellings of cyclic graphs, i.e. labbelings in
which each label is the sum of the two previous labels, when going
through the vertices sequentially, clockwise or otherwise. Here is an
example of such a Fibonacci labelling of $C_7$ over the group
$\ZZ_{29}$, and a non-Fibonacci labelling of that same graph, but over
$\ZZ_{7}$, that was obtained with the help of SageMath [14]:

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular polygon
sides=7] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 7)$24$;
(n3) at (a.corner 6)$25$;
(n4) at (a.corner 5)$20$;
(n5) at (a.corner 4)$16$;
(n6) at (a.corner 3)$7$;
(n7) at (a.corner 2)$23$;
at (0,0) $\ZZ_{29}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6, n6/n7,
n7/n1 () – (→);

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular
polygon sides=7] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 2)$6$;
(n3) at (a.corner 3)$12$;
(n4) at (a.corner 4)$3$;
(n5) at (a.corner 5)$15$;
(n6) at (a.corner 6)$7$;
(n7) at (a.corner 7)$5$;
at (0,0) $\ZZ_{17}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6,
n6/n7, n7/n1 () – (→);

If one denotes the vertices of the $n$-gon by $(a_i)_{i\in\ZZ_n}$, and
decide that $a_{i+1} = a_i + a_{i-1}$, one gets:

\begin{eqnarray*}
a_2 &=& a_0 + a_1\\
a_3 &=& a_1 + a_2\\
a_{n-1} &=& a_{n-3} + a_{n-2}\\
a_0 &=& a_{n-2} + a_{n-1}\\
a_1&=& a_{n-1} + a_0.
\end{eqnarray*}

From these, it is easy to see that $a_i = f_{i-1} a_0 + f_i a_1$ for
$i = 2,\ldots, n-1$, $a_0 = f_{n-1} a_0 + f_n a_1$, and
$a_1 = f_n a_0 + f_{n+1} a_1$, where $f_n$ is the usual $n$-th
Fibonacci number. These last two equalities yield

\begin{equation}
\label{eq:1}
f_n a_1 =  (1-f_{n-1}) a_0 \quad \text{ and } \quad (f_{n+1}-1) a_1
= - f_n a_0,
\end{equation}

which are, hence, necessary conditions for a Fibonacci labelling of
$C_n$ to exist.

Let $d = (f_n, f_{n+1}-1)$ and $x, y\in\ZZ$ such that
$d = x f_n + y (f_{n+1}-1)$. Let $z = (1-f_{n-1}) x -f_n y$. From
equations (<ref>), one obtains

\begin{equation}
\label{eq:2}
d a_1 = z a_0.
\end{equation}

Note that, since $d$ divides $f_n$ and $f_{n+1}-1$, it also divides
their difference, $f_{n-1}-1$ , and thus $d$ divides $z$.

Letting $q\in\NN$ be such that $f_n = dq$, one has

\begin{equation}
\label{eq:3}
(zq+f_{n-1}-1) a_0= 1.
\end{equation}

If one now lets $q_1\in\NN$ be such that $f_{n+1}-1 = d q_1$, then,
using the right equation in (<ref>) together with (<ref>),
one gets

\begin{equation}
\label{eq:4}
(z q_1+f_n) a_0=1.
\end{equation}

Setting $e=z q+f_{n-1}-1$ and $z_1=z q_1+f_n$, the last two equations
can be replaced by

\begin{equation}
\label{eq:5}
(e,z_1) a_0=1.
\end{equation}

In this way, equations (<ref>) may be replaced by equations
(<ref>) and (<ref>). Observe that $d$ divides $(e,z_1)$.  We
can, then, summarize what was here shown, as follows.

For $n\in\NN$, let $d=(f_n,f_{n+1}-1)$. Find $x,y\in\ZZ$ such that
$d=x f_n + y(f_{n+1}-1)$, and set $z=(1-f_{n-1})x-f_n y$.  Let
$q\in\NN$ be such that $f_n=dq$, and let $q_1\in\NN$ be such that
$f_{n+1}-1 = dq_1$. Set $e=zq+f_{n-1}-1$, and $z_1=z q_1+f_n$.

Then, a necessary condition for $a_0, a_1\in A$ to generate a
Fibonacci labelling of $C_n$, over the abelian group $A$, is that
the order of $a_0$ divides $(e,z_1)$, and that
$a_1 = \frac{z}d\, a_0$.

One can find $(f_n, f_{n+1}-1)$ as follows. By induction it is easy to
see that

\begin{equation}
\label{eq:6}
(f_n, f_{n+1}-1) = (f_{n-k}+(-1)^k f_k, f_{n-k-1}-(-1)^k f_{k+1}).
\end{equation}

Let us first consider the case when $n$ is odd, $n=2j+1$. Choosing
$k=j$ in the previous equality, one gets

\begin{eqnarray}
\label{eq:7}
(f_n, f_{n+1}-1) &=& (f_{j+1}+(-1)^j f_j, f_j-(-1)^j f_{j+1})\nonumber\\
&=& (f_{j+1}+f_j,f_{j+1}-f_j)\nonumber\\
&=& (2f_j+f_{j-1},f_{j-1})\nonumber\\
&=& (2f_j,f_{j-1}) \nonumber\\
&=& \begin{cases}2, & \text{if } 2\mid f_n \\
1, & \text{if } 2\nmid f_n \end{cases} =
\begin{cases}2, & \text{if } 3\mid n \\
1, & \text{if } 3\nmid n.
\end{cases}
\end{eqnarray}

Now, if $n$ is even, one needs to consider whether or not $4\mid
n$. If $n=4j$, then choosing $k=2j$ in equation (<ref>), one has

\begin{eqnarray}
\label{eq:8}
(f_n, f_{n+1}-1) &=& (f_{2j}+ f_{2j}, f_{2j-1}-f_{2j+1})\nonumber\\
&=& (2f_{2j},f_{2j}) = f_{2j}.
\end{eqnarray}

If $n=4j+2$, then choosing $k=2j+1$ in equation (<ref>), one has

\begin{eqnarray}
\label{eq:9}
(f_n, f_{n+1}-1) &=& (f_{2j+1}-f_{2j+1}, f_{2j}+f_{2j+2})\nonumber\\
&=& f_{2j}+f_{2j+2} = 2f_{2j}+f_{2j+1}.
\end{eqnarray}

For all $n\in\NN$,

\begin{equation*}
(f_n, f_{n+1}-1) =
\begin{cases}2, & \text{if } n\equiv 3\pmod{6}, \\
1, & \text{if }  n\equiv 1,5 \pmod{6},\\
f_{\frac{n}2}, & \text{if } n \equiv 0 \pmod{4},\\
f_{\frac{n}2}+2f_{\frac{n}2-1}, & \text{if } n \equiv 2 \pmod{4}.
\end{cases}
\end{equation*}

Using this, and with the help of SageMath to verify that one does not
get undesired edges, we got the following two examples:

* For $n=15$, one is in the first case of equation (<ref>),
so that $d=2$. Also, $z=162$, $(e,z_1)=682$. Taking $A=\ZZ_{682}$,
$a_0=1$ e $a_1 = 81$, one obtains the following example of a
labelling for $C_{15}$:

$\mathcal{G}_{\ZZ_{682}}([1, 81, 82, 163, 245, 408, 653, 379, 350,
47, 397, 444, 159, 603, 80])$,

the vertices being displayed here in cyclic order.

* For $n=6$, one gets $d=4$, $z=-4$, $(e,z_1)=4$. Using the group
$\ZZ_4\times\ZZ_4$ with $a_0=(1,2)$ and $a_1=(0,1)$, the conditions
(<ref>) and (<ref>) are satisfied, and one indeed gets a
Fibonacci labelling for $C_6$ over this group:

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular polygon
sides=6] (a) ;

(n1) at (a.corner 1)$(0,1)$;
(n2) at (a.corner 2)$(1,0)$;
(n3) at (a.corner 3)$(3,1)$;
(n4) at (a.corner 4)$(2,3)$;
(n5) at (a.corner 5)$(1,2)$;
(n6) at (a.corner 6)$(1,1)$; at (0,0)
$\ZZ_4\times\ZZ_4$; /→in n1/n2, n2/n3,
n3/n4, n4/n5, n5/n6, n6/n1 () – (→);

§.§ A Serendipitious Conjecture

For $n\in\NN$, let $e(n)$ and $z_1(n)$ be defined and above, and set
$\delta(n) = (e(n),z_1(n))$. Numerical computations make us suspect

\begin{equation}
\label{eq:10}
\lim_{k\to\infty}\frac{\delta(n_{k+1})}{\delta(n_k)} =
\begin{cases}
2+\phi, & \text{ if } n_k = 4k+r, \text{ for } r\in\{0,2\}.\\[2mm]
\ds 13+\frac{8}{\phi}, &\text{ if } n_k = 6k+r, \text{ for }
\end{cases}
\end{equation}

where $\phi = \frac{1+\sqrt{5}}2$ is the golden ratio.

§ MORE EXAMPLES

In this section we gather some extra examples obtained with the help
of the results from the previous section, and also with SageMath.

* A Fibonacci labelling for $C_5$ over the group $\ZZ_{11}$:

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular polygon
sides=5] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 2)$3$;
(n3) at (a.corner 3)$9$;
(n4) at (a.corner 4)$5$;
(n5) at (a.corner 5)$4$;
at (0,0) $\ZZ_{11}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n1 () – (→);

* A Fibonacci labelling for $C_6$ over the group
$\ZZ_4\times \ZZ_4$, and a non-Fibonacci labelling for the same graph
over $\ZZ_{13}$:

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular polygon
sides=6] (a) ;

(n1) at (a.corner 1)$(0,1)$;
(n2) at (a.corner 2)$(1,0)$;
(n3) at (a.corner 3)$(3,1)$;
(n4) at (a.corner 4)$(2,3)$;
(n5) at (a.corner 5)$(1,2)$;
(n6) at (a.corner 6)$(1,1)$; at (0,0)
$\ZZ_4\times\ZZ_4$; /→in n1/n2, n2/n3,
n3/n4, n4/n5, n5/n6, n6/n1 () – (→);

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular
polygon sides=6] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 2)$5$;
(n3) at (a.corner 3)$9$;
(n4) at (a.corner 4)$6$;
(n5) at (a.corner 5)$3$;
(n6) at (a.corner 6)$2$; at (0,0) $\ZZ_{13}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6,
n6/n1 () – (→);

* A Fibonacci labelling for $C_8$ over the group
$\ZZ_3\times\ZZ_{15}$, and one non-Fibonacci labelling over

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=4cm,regular polygon,regular polygon
sides=8] (a) ;

(n1) at (a.corner 1)$(0,1)$;
(n2) at (a.corner 8)$(1,3)$;
(n3) at (a.corner 7)$(1,4)$;
(n4) at (a.corner 6)$(2,7)$;
(n5) at (a.corner 5)$(0,11)$;
(n6) at (a.corner 4)$(2,3)$;
(n7) at (a.corner 3)$(2,14)$;
(n8) at (a.corner 2)$(1,2)$;
at (0,0) $\ZZ_{3}\times\ZZ_{15}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6, n6/n7,
n7/n8, n8/n1 () – (→);

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=4cm,regular polygon,regular
polygon sides=8] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 2)$13$;
(n3) at (a.corner 3)$17$;
(n4) at (a.corner 4)$25$;
(n5) at (a.corner 5)$21$;
(n6) at (a.corner 6)$14$;
(n7) at (a.corner 7)$7$;
(n8) at (a.corner 8)$6$;
at (0,0) $\ZZ_{29}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6,
n6/n7, n7/n8, n8/n1 () – (→);

* Finally, a Fibonacci labelling for $C_{12}$ over the group

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=55mm,regular polygon,regular
polygon sides=12] (a) ;

(n1) at (a.corner 2)$(0,1)$;
(n2) at (a.corner 1)$(5,3)$;
(n3) at (a.corner 12)$(5,4)$;
(n4) at (a.corner 11)$(10,7)$;
(n5) at (a.corner 10)$(15,11)$;
(n6) at (a.corner 9)$(25,18)$;
(n7) at (a.corner 8)$(0,29)$;
(n8) at (a.corner 7)$(25,7)$;
(n9) at (a.corner 6)$(25,36)$;
(n10) at (a.corner 5)$(10,3)$;
(n11) at (a.corner 4)$(35,39)$;
(n12) at (a.corner 3)$(5,2)$;
at (0,0) $\ZZ_{40}\times\ZZ_{40}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6, n6/n7,
n7/n8, n8/n9, n9/n10, n10/n11, n11/n12, n12/n1 ()
– (→);

§ A $C_9$ EXAMPLE

The attempts we made to find a number $m\in\NN$ for which $C_9$ is a
$\ZZ_m-$graph, using the method described above were unsucceful. Then,
to find such a number $m$, we used the following strategy.

If $V=\{ x_i: i\in\ZZ_9\}$ are the vertices of $C_9$, then one may seek
for a field in which the following linear system has a non-trivial

\begin{equation}
\label{eq:11}
x_i + x_{i+1} = x_{g(i)} \text{ where } g(i)\not\in \{i,i+1\} \text{
and } g(i)\neq g(i+1),
\end{equation}

for all $i\in\ZZ_9$.

Using SageMath to randomly search for integral matrices $9\times 9$
corresponding to linear systems like this, computing their
determinants to find a finite field where these are zero, then
computing a non-trivial element of the respective kernel, and finally
checking that the sums of non-adjacent vertices are not in the chosen
solution, we were able to find the following example:

[roundnode/.style=circle, fill=black!10]

[draw=none,minimum size=3cm,regular polygon,regular polygon
sides=9] (a) ;

(n1) at (a.corner 1)$1$;
(n2) at (a.corner 2)$8$;
(n3) at (a.corner 3)$16$;
(n4) at (a.corner 4)$24$;
(n5) at (a.corner 5)$40$;
(n6) at (a.corner 6)$11$;
(n7) at (a.corner 7)$51$;
(n8) at (a.corner 8)$9$;
(n9) at (a.corner 9)$7$;
at (0,0) $\ZZ_{53}$;
/→in n1/n2, n2/n3, n3/n4, n4/n5, n5/n6, n6/n7,
n7/n8, n8/n9, n9/n1 () – (→);

as well as two others over the field $\ZZ_{47}$:

\begin{eqnarray*}
\mathcal{G}_{\ZZ_{47}}([1,12,36,23,13,30,43,26,22]),\\
\mathcal{G}_{\ZZ_{47}}([1,34,14,26,35,38,44,41,40]).
\end{eqnarray*}

§ $C_{4\ELL}$ AS A SUM GRAPH OVER AN ABELIAN GROUP

Set $n=4\ell$, $f=f_{2\ell}$ and $A=\ZZ_f\times\ZZ_f$. Consider the
graph $C$ whose vertices are $a_i = (f_i,f_{i-1})\in A$ with
$i=0,1,\ldots,n-1$, and the edges the ones induced by the sum graph
law. By (<ref>), and using the same notations as above, we get
$d= f_{2\ell} =f$. Since $d$ divides $z$, equations (<ref>) and
(<ref>) are trivially satisfied in $A$. Therefore, it only
remains to show that $C$ does not have any edge besides the

Suppose, by contradiction, that there is, in $C$, an edge $a_ia_j$
with $0<i+1<j<n$, i.e. that $a_i+a_j=a_k$ in $A$. This entails

\begin{equation*}
\left\{
\begin{array}{l}
f_i + f_j \equiv f_k \pmod{f}\\
f_{i-1} + f_{j-1} \equiv f_{k-1}\pmod{f}.
\end{array}
\right.
\end{equation*}

Subtracting the second from the first, mantaining the first, and
swapping them, one gets

\begin{equation*}
\left\{
\begin{array}{l}
f_{i-1} + f_{j-1} \equiv f_{k-1}\pmod{f}\\
f_{i-2} + f_{j-2} \equiv f_{k-2}\pmod{f}.
\end{array}
\right.
\end{equation*}

Repeating this, one eventually obtains $a_0 + a_{j-i} = a_{k-i}$,
which means that one can reduce to the case $i=0$.  Thus, one has

\begin{equation}
\label{eq:13}
\left\{
\begin{array}{l}
f_j \equiv f_k \pmod{f}\\
1 + f_{j-1} \equiv f_{k-1}\pmod{f}.
\end{array}
\right.
\end{equation}

Taking $j=j'+2\ell$ and $k=k'+2\ell$, with $1<j'<2\ell$ and
$-2\ell<k'<2\ell$, which can be done since
$f_i\equiv f_{i+4\ell} \pmod{f_{2\ell}}$ (this follows from
(<ref>) and $f_{4\ell+1}\equiv 1\pmod{f_{2\ell}}$), and using
the fact that ([16], (1.8), p. 9)

\begin{equation}
\label{eq:vorobiev}
f_{m+n} = f_{m-1} f_n + f_m f_{n+1},
\end{equation}

which holds for all $m,n\in\ZZ$, one obtains from the first
congruence in (<ref>) that

\begin{equation*}
f_{j'}f_{2\ell+1} \equiv f_{j'+2\ell} \equiv f_{k'+2\ell} \equiv
\end{equation*}

Since two consecutive Fibonacci numbers are coprime, one deduces that

\begin{equation}
\label{eq:14}
f_{j'} \equiv f_{k'}\pmod{f_{2\ell}}.
\end{equation}

If $0< k'<2\ell$, this entails $f_{j'}=f_{k'}$, and hence $j=k$, which
is absurd. Now, since $f_{-t}=(-1)^{t-1}f_t$, one has to deal only
with the case when $k'$ is even. In this case, one gets

\begin{equation}
\label{eq:15}
f_{j'} + f_{k'}\equiv 0 \pmod{f_{2\ell}},
\end{equation}

with $1<j'<2\ell$, and $0<k'<2\ell-1$. This congruence can only hold
for $j'=2\ell-1$ and $k'=2\ell-2$. But, then, the second congruence in
(<ref>) yields

\begin{equation*}
1 + f_{4\ell-2}\equiv f_{4\ell-3} \pmod{f_{2\ell}},
\end{equation*}

which is equivalent to

\begin{equation*}
f_{4\ell-4}\equiv -1 \pmod{f_{2\ell}}.
\end{equation*}

Using (<ref>), one gets:

$$-1\equiv f_{4\ell-4} \equiv f_{2\ell-1} f_{2\ell-4} \equiv f_{2\ell-2}
f_{-1}f_{2\ell-4}\equiv f_{2\ell-2} f_{2\ell-4}\pmod{f_{2\ell}}.$$

Applying again (<ref>),

$$-1\equiv f_{2\ell-2} f_{2\ell-4}\equiv f_{2\ell-1}f_{-2}f_{2\ell-4}
\equiv -f_{2\ell-1}f_{2\ell-4}\equiv 1  \pmod{f_{2\ell}},$$

which gives the desired contradiction.

We have thus shown the following result.

For every $\ell\in\NN$, the graph $C_{4\ell}$ is a sum graph over
the group $\ZZ_f\times\ZZ_f$, where $f=f_{2\ell}$ is the
corresponding Fibonacci number.

§ INTEGRAL SUM GRAPHS

§.§ The radius of a $\ZZ-$graph.

For $\ZZ-$graphs, Melnikov and Pyatkin [12] defined the
radius of a labelling as its maximum absolute value, i.e. the
radius of the smallest interval centered on the origin that contains
the labelling set, and defined the radius of a $\ZZ$-graph,
$G$, as the smallest of the radius of all its labellings, denoted by
$r(G)$.  In their paper it is shown (see <cit.>) that the radius of $C_n$ grows at most linearly with
$n$. It is easy to see that a labelling for $P_n$ can be obtained from
their labelling for $C_{n+1}$, by excluding the label of maximum
value, and that one has $r(P_n)\leq \frac{17}2 n$.

In [8], Harary showed that all matchings, $mP_2$, are
$\ZZ-$graphs. By relying on the ideas presented in [12],
one can improve Harary's result by showing the following.

For all $m\geq 4$, $r(mP_2)\leq 3m-4$.

The idea is to consider two intervals of integers,

with $a>b\in\NN$ appropriately chosen. To start with, choose $a$ and
$b$ such that $2a\geq a+(m-1)$, $2b\geq b+(m-1)$, so that there are
no edges between the vertices with labellings in the same
interval. One then adds a pair of vertices with labellings $a-b$ and
$b+(m-2)$, whose sum is the maximum label. The requirement that
there are no undesired edges leads to the conditions $b\geq m-1$ and
$a\geq 2m-2$. Choosing $b=m-1$ and $a=2m-2$ yields the following
labelling for $mP_2$:

[node distance=25mm, scale=1, auto=left]
(n1) $(2m-2)$;
(n2) [right of=n1] $(2m-1)$;
(n3) [below of=n2,yshift=10mm] $(-m)$;
(n4) [left of=n3] ($-m+1$);
(n5) [right of=n2,xshift=-10mm] $\cdots$;
(n6) [right of=n3,xshift=-10mm] $\cdots$;
(n7) [right of=n5,xshift=-10mm] $(3m-4)$;
(n9) [right of=n7] $(m-1)$;
(n8) [right of=n6,xshift=-10mm] $(-2m+3)$;
(n10) [right of=n8] $(2m-3)$,;
/→in n2/n3,n4/n1,n7/n8,n9/n10
() – (→);

which yields the claim.

Sharary has shown that, for $n>3$, $K_n$ is not a $\ZZ-$graph
<cit.>. We show here that their complements,
$\bar{K}_n$, are $\ZZ-$graphs, for all $n$, and determine their radii.

For all $n\in\NN$, $r(\bar{K}_n) = n-1$.

It is easy to show that, for any $n\in\NN$, the numbers

$$-(n-1), -(n-2), \ldots, -\left\lceil\frac{n}2\right\rceil,
\left\lfloor\frac{n}2\right\rfloor,\left\lfloor\frac{n}2\right\rfloor+1,
\ldots,(n-1)$$

provide a labelling for $\bar{K}_n$, showing that
$r(\bar{K}_n) \leq n-1$.

To show that it cannot be smaller, suppose that there is a labelling
of $\bar{K}_n$ with labels in $[-(n-2),(n-2)]$. By multiplying by
$-1$ if necessary, one may assume that there are at least
$\lceil\frac{n}2\rceil$ labels in $[1,(n-2)]$, since $0$ cannot be
one of the labels for $n>1$. We show by induction that the numbers
$1,2,\ldots,\lfloor\frac{n}2\rfloor-1$ cannot be labels, which
yields a contradiction, since
$\lceil\frac{n}2\rceil+\lfloor\frac{n}2\rfloor-1 = n-1 > n-2$.  The
proof is split into two cases: $n$ odd and $n$ even.

Odd case.  If $1$ is a label, then at least one element in
each of the following pairs is not a label:
$(2,3),(4,5),(6,7), \ldots (n-3,n-2)$, which would imply that there
would be at most $n-2-\frac{n-3}2 =\frac{n-1}2$ labels.

Assume, now, that one had already shown that any positive value
smaller than $k$ is not a label, for any $k\leq \frac{n-3}2$. If $k$
is a label, then at most one element of each of the following
disjoint pairs is a label:

$(k+1,2k+1), (k+2,2k+2),\ldots, (2k,3k)$,

$(3k+1,4k+1), (3k+2,4k+2),\ldots, (4k,5k)$,

$((2i-1) k+1,2ik+1),\ldots, ((2i-1)k+j,2ik+j)$,

with $i,j\in\NN$, where either

(a) $j\leq k$ and $2ik+j = n-2$, or

(b) $j=k$ and $(2i+1)k< n-2 < (2i+2)k+1$.

In case (a), the labelling would not include
$(k-1)+k(i-1)+j = (n-2)-ki-1$ numbers, leaving out only $ki+1$,
which is not greater than $\frac{n-1}2$, as $2ki+1\leq n-2$. In case
(b), one would only have at most $(n-2) -ki-(k-1) = (n-1)-k(i+1)$
possible labels, but this number is also less or equal to
$\frac{n-1}2$, since
$n-2<(2i+2)k+1\iff n-2\leq 2k(i+1) \iff n-1\leq 2k(i+1)$, since $n$
is odd.

Even case. In this instance, if $1$ is a label, then
at least one element in each of the following pairs is not a label:
$(2,3),(4,5),(6,7), \ldots (n-4,n-3)$, and thus one has at most
$\frac{n}2 -1$ labels up to $n-3$, consequentely $n-2$ must be a
label. One concludes that $n-4$ must also be a label, and then
$n-6$, and so on, up to $2$. For $n\geq 8$, this implis that the
existence of the edge $2$—$4$, and the cases $n=2,4,6$ are easy to

Assume, now, that one had already shown that any positive value
smaller than $k$ is not a label, for any $k\leq \frac{n}2-1$. Again,
if $k$ is a label, then one element of each of the following
disjoint pairs is not a label:

$(k+1,2k+1), (k+2,2k+2),\ldots, (2k,3k)$,

$(3k+1,4k+1), (3k+2,4k+2),\ldots, (4k,5k)$,

$((2i-1) k+1,2ik+1),\ldots, ((2i-1)k+j,2ik+j)$,

with $i,j\in\NN$, where either

(a) $j\leq k$ and $2ik+j = n-2$, or

(b) $j=k$ and $(2i+1)k< n-2 < (2i+2)k+1$.

In case (a), the labelling does not include
$(k-1)+k(i-1)+j = (n-2)-ki-1$ numbers, leaving out only $ki+1$,
which is not greater than $\frac{n}2-1$, as $2ki+1\leq n-2$ implies
$2ki+1\leq n-3$, as $n$ is even.

The case (b) is a bit more delicate.  Considering now the following
pairs, starting at $n-2$ and going downwards:

$(n-2,n-2-k),\ldots, (n-2-(k-1),n-2-(2k-1))$,

$(n-2-2k,n-2-3k),\ldots, (n-2-(3k-1),n-2-(4k-1))$,

$(n-2-2(i-1)k,n-2-(2i-1)k),\ldots, (n-2-((2i-1)k-1),n-2-(2ik-1))$,

one sees that the number of possible labels is, at most,
$\ell=(n-2) -ki-(k-1) = (n-1)-k(i+1)$. Since $n$ is even,
$n-2<(2i+2)k+1$ implies $n-2\leq (2i+2)k$, and thus
$\ell\leq \frac{n}2$. It follows that one must have
$\ell = \frac{n}2$ and $n-2 = (2i+2)k$; that every pair in the above
array must contain one (and only one) label; and that all numbers
from $k+1$ up to $2k = (n-2)-2ik$ must be labels.

But then, at least $k,k+1,2k$ are labels, since $k\geq 2$. It
follows that $2k+1, 3k, 3k+1$ are not labels. Repeating the argument
for the pairs starting at $(k+2,2k+2)$, in which case the last pair
involved would be $((2i+1)k,(2i+2)k)$, one sees that one of the
numbers in the pair $(2k+1,3k+1)$ must be a label. This yields the
desired contradiction, as long as $3k+1\leq n-2 = 2(i+1)k$, which is
equivalent to $\frac12+\frac{1}{2k}\leq i$, or $i\geq 1$. Finally,
just note that the case $i=0$ occurs if and only if one has
$\frac{n}2-1 = (i+1)k = k$, or $n-2=2k$, and then all numbers from
$k$ to $2k$ must be labels. But then none of the numbers
$-1,-2,\ldots,-k$ can be labels, and then there are not enough
labels. This completes the proof.

Remark: For $n$ even, one also has, for $\bar{K}_n$, the
labelling with radius $n-1$:

$$-(n-1), -(n-3), \ldots,-3, -1, 1, 3,\ldots,(n-3), (n-1).$$

§.§ The Z3 Theorem Prover and Presburger Arithmetic

The fact that the Presburger arithmetic is decidable implies that it
is decidable to find out if a given graph is or not a sum graph,
either over $\mathbb{Z}$ or $\mathbb{N}$. A problem of this kind can
be computationally solved by means of a SMT problem solver. A
Satisfiability Modulo Theories (SMT) problem is a decision problem for
logical formulas with respect to combinations of background theories,
in this case integer arithmetic. We used
Z3[<https://github.com/Z3Prover/z3/wiki>], a SMT solver
that, for small instancies, could directly obtain answers for problems
concerning the existence of $(\ZZ,+)$ or $(\NN,+)-$graphs.

For $(\ZZ_n,+)-$graphs, Z3 documentation states that it does not
support, at the moment, modular arithmetic. But because these
problems, by definition, only involve, positive and negative,
equalities between additive expressions, the transformation of these
formulas into boolean formulas using integer arithmetic was
straightforward, making possible to use Z3 for these problems too.

Using Z3 and the list of graphs in Brendan McKay webpage[
<http://users.cecs.anu.edu.au/ bdm/data/graphs.html>], we got
the following data, where $t$ is the total number graphs with $n$
vertices, and $isg$ is the respective number of integral sum graphs:

$n$   $t$   isg    risg      $isg/t$     $risg/t$
2   2   2   2   1   1

3   4   4   4   1   1

4   11   5   6   0.45   0.55

5   34   14   18   0.41   0.53

6   156   50   72   0.32   0.46

7   1044   226   361   0.22   0.35

8   12346   1460   3162   0.12   0.26

It is a direct consequence of the fact that a sum labelling
constitutes a compressing code for a graph that admits such a
labelling, that the percentage of graphs that are sum graphs must go
to zero as the size of the graph increases, by a basic Kolmogorov
complexity result [11].

§.§ The $n$-dimensional Cube

In [12], Melnikov and Pyatkin showed that the 3D-cube
graph, $Q_3$, is not an integral sum graph, and then asked (Question
3, p. 245) whether it is true that the $n$-dimensional cube graph,
$Q_n$, is not an integral sum graph for all $n\geq 2$. It turns out
that the answer to this question is negative. Using the Z3 Theorem
Prover we have obtained the integral sum labellings of the 4D-cube
that we are going to describe using the order of the vertices depicted
in the following figure:

[node distance=2cm, scale=1, auto=left]
(n0) at (-0.2,0.2) 0;
(n1) at (1.6,0.2) 1;
(n2) at (-0.8,-0.9) 2;
(n3) at (1,-0.9) 3;
(n4) at (-0.2,2) 4;
(n5) at (1.6,2) 5;
(n6) at (-0.8,1) 6;
(n7) at (1,1) 7;
(n8) at (-1.3,-0.5) 8;
(n9) at (2.7,-0.5) 9;
(n10) at (-2,-2) 10;
(n11) at (2,-2) 11;
(n12) at (-1.3,2.7) 12;
(n13) at (2.7,2.7) 13;
(n14) at (-2,1.7) 14;
(n15) at (2,1.7) 15;
n12/n14,n13/n15,n15/n14 () – (→);
n8/n9,n8/n10,n8/n12 [dotted] () – (→);
/→in n0/n1,n0/n2,n1/n3,n2/n3,n0/n4,n1/n5,n2/n6,
n3/n7,n4/n6,n5/n7,n4/n5,n6/n7 [densely dotted] () –
n0/n8,n1/n9,n2/n10,n3/n11,n4/n12,n5/n13,n6/n14, n7/n15
[dashed] () – (→);

Note that here the tags are not labels in the previous sense, i.e. sum
labellings, but are just meant to give a specific order to the
vertices — if you convert the tags to binary, you will see the
reason behind the choice we made. Using this order, the first three
labellings found by Z3 were, with the respective radius:

These $3$ solutions are all in the nullspace, $K$, of the matrix
$M\in\mm_{32\times 16} (\ZZ)$ of the system $x_i + x_j - x_k = 0$,
where $v_iv_j$ is an edge of $Q_4$, with $i,j\in\{0,1,\ldots,15\}$
corresponding to their location in binary, and $v_k$ is the vertex
such that $v_i+v_j=v_k$. It turns out that $\dim K = 3$, with a
$\QQ-$basis given by:

\arraycolsep=1pt
\begin{array}{ccccccccccccccccccccccccccccccccccc}
\end{array}

and the above solutions are, respectively:

\arraycolsep=1pt
\begin{array}{lcrcrcrr}
\text{sol}_1 &=& -6 u_1 &+&19 u_2 &-& 40 u_3 &\qquad (\text{radius} = 46),\\
\text{sol}_2 &=& 32 u_1 &-&5 u_2 &-& 14 u_3 & (\text{radius} = 37),\\
\text{sol}_3 &=& 6 u_1 &+&9 u_2 &-& 35 u_3 & (\text{radius} = 35).
\end{array}

We then used Z3 to probe for the radius of $Q_4$, which turns out to
be $24$, with the following labelling:

Given a $\ZZ-$graph $G$ with a labelling $\lambda$, the nullspace of
the matrix of the system given by the equations $x_i+x_j = x_k$ with
$\{i,j\}\in E(G)$ and $k\in V(G)$ such that
$\lambda(i)+\lambda(j)=\lambda(k)$, will be here called the
kernel of the labelling $\lambda$ of $G$, while a kernel of
a $\ZZ-$graph $G$ is the kernel of some of its labellings.

We now show that any $\ZZ-$graph with a kernel of dimension at least
$2$ has infinitely many primitive labellings, i.e. labellings
that are not obtainable by multiplying another labelling by some
integer of modulus bigger than one, using the fact that a vector space
over a infinite field (in the present case, $\QQ$) cannot be the union
of a finite number of its lower dimensional subspaces (see Theorem 1.2
in [13]).

If a $\ZZ-$graph with at least two vertices has a kernel with
dimension at least $2$, then it has infinitely many primitive

Let $G$ be a $\ZZ-$graph with a kernel $K$ with
dimension at least $2$. Each non-edge of $G$ yields an equation
$x_i+x_j = x_k $ that corresponds to an hyperplane that necessarily
intersects $K$ in a lower dimensional subspace, since $G$ has a
labelling, i.e. a solution of the system $S$ that does not belong to
neither of these hyperplanes. Since there are finitely many such
hyperplanes, and their union cannot contain the entire space $K$, it
follows that $K$ has infinitely many $\QQ-$lines outside all of
those hyperplanes, each of which has an integral primitive point.

As an immediate consequence of this result, and the labellings above
mentioned for the 4D-cube, we get:

The hypercube graph $Q_4$ has infinitely many primitive labellings.

We tried to use Z3 to determine whether $Q_5$ it is, or not, a
$\ZZ-$graph, for more than two months of CPU time, but without sucess.

§.§ Cubic Graphs

Using the Z3 Theorem Prover we obtained the following results:

* There are no cubic graphs with 4 or 6 vertices that are integral
sum graphs.

* Of the 5 non-isomorphic cubic graphs with 8 vertices, only one
is an integral sum graph, as stated in [12].

* Of the 19 non-isomorphic cubic graphs with 10 vertices, only 6
are integral sum graphs, the ones given in [12]. In
particular, the Petersen graph is not an integral sum graph.

* Of the 85 non-isomorphic cubic graphs with 12 vertices, only 9
are not integral sum graphs.

Question: Are all cubic graphs with sufficiently many
vertices integral sum graphs?

§ MOD SUM GRAPHS

A graph that is a $\ZZ_n-$graph for some $n\in\NN$ is known as a
mod sum graph. Using the Z3 Theorem Prover, we obtained the
following results:

* Neither $K_{3,3}$, nor the triangular prism:

[node distance=10mm, scale=0.6, auto=left, every
node/.style=circle,inner sep=0pt, minimum size=6pt,fill=black!100]]
(o1) at (2,3.5) ;
(o2) at (4,0) ;
(o3) at (0,0) ;
/→in o1/o2,o2/o3,o3/o1 () – (→);
(i1) at (2,2);
(i2) at (2.8,0.8);
(i3) at (1.2,0.8);
/→in i1/i2,i2/i3,i3/i1 () – (→);
/→in o1/i1,o2/i2,o3/i3 () – (→);

are mod sum graphs.

* The 3D-cube is a mod sum graph over $\ZZ_{15}$:

[node distance=17mm, scale=0.8, auto=left]
(f1) $9$;
(f2) [right of=f1] $12$;
(f3) [below of=f2] $4$;
(f4) [left of=f3] $8$;
/→in f1/f2, f2/f3, f3/f4, f4/f1 ()
– (→);
(b1) at (1,1)$3$;
(b2) [right of=b1] $6$;
(b3) [below of=b2] $2$;
(b4) [left of=b3] $1$;
/→in b1/b2, b2/b3, b3/b4, b4/b1 ()
– (→);
/→in f1/b1, f2/b2, f3/b3,f4/b4 () –

* The Petersen graph is a mod sum graph over $\ZZ_{28}$:

[node distance=15mm, scale=0.6, auto=left]
(o1) at (4,6) $1$;
(o2) at (1,4) $20$;
(o3) at (7,4) $19$;
(o4) at (2,0) $7$;
(o5) at (6,0) $5$;
/→in o1/o2,o2/o4,o4/o5,o5/o3,o3/o1 () – (→);
(i1) at (4,4.3)$23$;
(i2) at (2.6,3.3)$27$;
(i3) at (5.4,3.3)$21$;
(i4) at (3.3,1.5)$12$;
(i5) at (4.7,1.5)$24$;
/→in i1/i4,i4/i3,i3/i2,i2/i5,i5/i1 () –
/→in o1/i1,o2/i2,o3/i3,o4/i4,o5/i5 () –

It turns out that, given a connected graph $G$, there is a number
$N\in\NN$ such that, if $G$ is not a $\ZZ_m-$graph for all
$m\leq N$, then $G$ is not a mod sum graph at all. In order to show
this, we start by noticing the followng trivial fact.

Let $G$ be a $\ZZ_m-$graph with $n$ vertices and with labelling
$v$. Set $d=\gcd(v_1,\ldots,v_n)$. If $d \mid m$, then $G$ is also a

It immediately follows from the fact that
$v_i+v_j\equiv v_k\pmod{m}$ is equivalent to
$\frac{v_i}d + \frac{v_j}d \equiv \frac{v_k}d \pmod{\frac{m}d}$.

Let $G$ be a connected graph with $n\geq 3$ vertices, and set
$N=2\cdot 3^{n-1}$. Then, if $G$ is not a $\ZZ_m-$graph for all
$m\leq N$, then $G$ is not a mod sum graph at all.

Let $G$ be a connected graph with $n\geq 3$ vertices.
Since all trees with $3$ or more vertices are mod sum graphs
[2], we may restrict our attention to graphs that are
not trees, and hence have at least $n$ edges <cit.>.  Assume, then, that such a graph $G$ is a mod sum
graph, and let $m\in\NN$ be the smallest number such that $G$ is a
$\ZZ_m-$graph.  Let $M$ be the matrix of the homogeneous system
$x_i+x_j - x_k = 0$ with $\{i,j,k\}\in\{1,2,\ldots,n\}$ such that
$ij\in E_G$, where $v$ is the labelling function, and $k$ a vertex
such that $v_i+v_j \equiv v_k \pmod{m}$. Let $A$ be an $n\times n$
minor of $M$, and $\Delta\in\ZZ$ its determinant. By the usual proof
of Cramer's rule, one has $\Delta v_i \equiv 0 \pmod{m}$, for all
$i\in\{1,\ldots,n\}$. Let $d = \gcd(v_1,\ldots,v_n)$. If
$(d,m)\neq 1$, by the previous lemma $G$ would be a
$\ZZ_{\frac{m}{(d,m)}}-$graph, contradicting the minimality of
$m$. Therefore $(d,m)=1$, and one concludes that $m\mid \Delta$.

Finally, from the fact that the rows of $A$ consists of only three
non-zero entries, two ones and one minus one, it is easy to conclude
by induction, using the Laplace expansion to compute determinants,
that $|\Delta| \leq 2\cdot 3^{n-1}$.

§ RELAXED SUM GRAPHS

§.§ Relaxed Integral Sum Graphs

Again, using the Z3 Theorem Prover we have got:

* There are no cubic graphs with 4 or 6 vertices that are integral
relaxed sum graphs.

* Of the 5 non-isomorphic cubic graphs with 8 vertices, only one
is an integral relaxed sum graph.

* Of the 19 non-isomorphic cubic graphs with 10 vertices, only 6
are non integral relaxed sum graphs. In particular the Petersen
graph is (again) not an integral relaxed sum graph.

* Of the 85 non-isomorphic cubic graphs with 12 vertices, only 2
are not integral relaxed sum graphs.

* All the 509 non-isomorphic cubic graphs with 14 vertices are
integral relaxed sum graphs.

Question: Are all cubic graphs with more that 12
vertices integral relaxed sum graphs?

§.§ Relaxed Mod Sum Graphs

The graph $K_{3,3}$ is a $\ZZ_9-_{\rm rx}$graph:

[node distance=25mm, scale=1, auto=left]
(a1) $1$;
(a2) [right of=a1] $4$;
(a3) [right of=a2] $7$;
(b1) [below of=a1] $6$;
(b2) [below of=a2] $6$;
(b3) [below of=a3] $6$;
a1/b1,a1/b2,a1/b3,a2/b1,a2/b2,a2/b3,a3/b1,a3/b2,a3/b3 () – (→);

Using the Z3 Theorem Prover, we found out that the triangular prism is
not a relaxed mod sum graph.

§ THE DIRECT PRODUCT OF GRAPHS

The direct product $G\times H$ of two graphs $G$ and $H$, also known
as the tensor or Kronecker product, is the graph whose vertex set is
the cartesian product $G\times H$ and two vertices $(g_1,h_1)$ and
$(g_2,h_2)$ are adjacent if and only if $g_1$ is adjacent to $g_2$ in
$G$, and $h_1$ is adjacent to $h_2$ in $H$. We show here that if $G$
and $H$ are strong $\ZZ-$graphs, then so is $G\times H$.

We start with the following lemma, that is inspired in the proof of
the main result of [1].

If $G$ is a $\ZZ^k-$graph, then it is also a $\ZZ-$graph. The same
holds for strong sum graphs.

Let $M$ be bigger than twice the maximum of the absolute values of
all coordinates of the labels of the vertices of $G$. Then just use
the fact that the map $\ZZ^k\to\ZZ$ given by
$(x_1,\ldots, x_k) \mapsto \sum\limits_{i=1}^k x_i M^{i-1}$ is a
group homomorphism, and it is injective when restricted to the
labels of $G$, which follows from the fact that $x\equiv y\pmod{M}$
implies that $x=y$ whenever $|x| < \frac{M}2$ and $|y| < \frac{M}2$.

We can now show the claimed result.

If $(G_i)_{i=1,\ldots,k}$ is a finite family of strong $\ZZ-$graphs,
then so is their direct product $\prod\limits_{i=1}^k G_i$.

It is clear form the definition of the product of graphs that
$\prod\limits_{i=1}^k G_i$ is a strong $\ZZ^k-$graph when every
$G_i$ is a strong $\ZZ-$graph. The result then follows at once from
the previous lemma.

Observe that, if $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are $\ZZ-$graphs,
but $G_1$ is not a strong $\ZZ-$graph, then the argument in the
previous proof fails, because if $u\in V_1$ is such that $2u\in V_1$,
and $v,w\in V_2$ are distinct, then $(u,v)+(u,w)\in V_1\times V_2$,
but $(u,v)$ is not adjacent to $(u,w)$ in $G_1\times G_2$. We point
out that Weischel [17] has shown that $G\times H$ is
connected if and only if either $G$ or $H$ has an odd cycle, which
gives a way of constructing connected $\ZZ-$graphs.

§.§ Acknowledgements

We thank Henning Fernau for introducing us to the subject of sum
graphs with an interesting question that we could not solve but that
motivated the work here presented.

This research was partially supported by CMUP (Centro de Matemática
da Universidade do Porto), the Center for Mathematics of the
University of Porto, which is financed by national funds through FCT
under the project with reference UID/MAT/00144/2020.

[1]
Deborah Bergstrand, Ken Hodges, George Jennings, Lisa Kuklinski, Janet Wiener,
and Frank Harary.
Product graphs are sum graphs.
Mathematics Magazine, 65(4):262–264, 1992.

[2]
J. Boland, R. Laskar, C. Turner, and G. Domke.
On mod sum graphs.
Congressus Numerantium, 70:131–135, 1990.

[3]
N. Bourbaki.
Algebra I: Chapters 1-3.
Actualités scientifiques et industrielles. Springer, 1998.

[4]
G. J. Chang.
Strong sum graphs.
Bull. Inst. Combin. Appl., 7:47–52, 1993.

[5]
M. N. Ellingham.
Sum graphs from trees.
Ars Combinatoria, 35:335–349, 1993.

[6]
Joseph A. Gallian.
A dynamic survey of graph labeling.
The Electronic Journal of Combinatorics, #DS6, 25th edition,

[7]
Frank Harary.
Sum graphs and difference graphs.
Congressus Numerantium, 72:101–108, 1990.

[8]
Frank Harary.
Sum graphs over all the integers.
Discret. Math., 124(1-3):99–105, 1994.

[9]
Frank Harary.
Graph Theory.
CRC Press, 2018.

[10]
F. Harary, I.R. Hentzel, and D. Jacobs.
Digitizing sum graphs over the reals.
Caribbean J. Math. Comput. Sci., 1:1–4, 1991.

[11]
Ming Li and Paul Vitányi.
An Introduction to Kolmogorov Complexity and Its
Texts in Computer Science. Springer, 2008.

[12]
Leonid S. Melnikov and Artem V. Pyatkin.
Regular integral sum graphs.
Discret. Math., 252(1-3):237–245, 2002.

[13]
Steven Rotman.
Advanced Linear Algebra.
Springer, Third edition, 2008.

[14]
Sage Developers.
SageMath, the Sage Mathematics Software System
(Version 9.7), 2021.

[15]
Ahmad Sharary.
Integral sum graphs from complete graphs, cycles and wheels.
Arab Gulf Journal of Scientific Research, 14:1–14, 1996.

[16]
N.N. Vorobiev and M. Martin.
Fibonacci Numbers.
Birkhäuser Basel, 2002.

[17]
Paul M. Weichsel.
The Kronecker product of graphs.
Proceedings of the American Mathematical Society, 13(47–52),


[datatype=bibtex] [overwrite=true] [fieldset=url, null] [fieldset=doi, null]
[fieldset=eprint, null]

# Neuromorphic analog circuits for robust on-chip always-on learning in
spiking neural networks

Arianna Rubino1, Matteo Cartiglia1, Melika Payvand, Giacomo Indiveri 1 These
authors have contributed equally to this work. This work has received funding
from European Union’s Horizon 2020 research and innovation program under grant
agreement No 871737 (“BeferroSynaptic”), from the European Research Council
(ERC) under grant agreement No 724295 (“NeuroAgents”), the Swiss National
Science Foundation Sinergia project CRSII5-18O316, and the UZH Candoc
fellowship FK-22-084.  Institute of Neuroinformatics, University of Zurich and
ETH Zurich
Email<EMAIL_ADDRESS>
###### Abstract

Mixed-signal neuromorphic systems represent a promising solution for solving
extreme-edge computing tasks without relying on external computing resources.
Their spiking neural network circuits are optimized for processing sensory
data on-line in continuous-time. However, their low precision and high
variability can severely limit their performance. To address this issue and
improve their robustness to inhomogeneities and noise in both their internal
state variables and external input signals, we designed on-chip learning
circuits with short-term analog dynamics and long-term tristate discretization
mechanisms. An additional hysteretic stop-learning mechanism is included to
improve stability and automatically disable weight updates when necessary, to
enable continuous always-on learning. We designed a spiking neural network
with these learning circuits in a prototype chip using a 180 nm CMOS
technology. Simulation and silicon measurement results from the prototype chip
are presented. These circuits enable the construction of large-scale spiking
neural networks with online learning capabilities for real-world edge
computing tasks.

###### Index Terms:

always-on learning, edge-computing, on-chip learning online, SNN, hysteresis,
tristability.

##  I Introduction

The requirements of artificial intelligence (AI) systems operating at the edge
are similar to those that living organisms face to function in daily life.
They need to measure sensory signals in real-time, perform closed-loop
interactions with their surroundings, be energy-efficient, and continuously
adapt to changes in the environment and in their own internal state. These
requisites are well supported by neuromorphic systems and emerging memory
technologies that implement brain-inspired mixed-signal spiking neural network
(SNN) architectures [1, 2, 3, 4, 5]. These types of SNNs operate in a data-
driven manner, with an event-based representation that is typically sparse in
both space and time. Since they compute only when data is present, they are
very power efficient. Similar to the biological neural systems they model,
these SNNs are particularly well-suited to processing real-world signals. They
can be designed to operate at the same data-rate of the input streams in real-
time by matching the time constants of neural computation with those of the
incoming signal dynamics. However, similar to their biological counterparts,
these systems are affected by a high degree of variability and sensitivity to
noise.

Figure 1: Micrograph of the prototype chip comprising of the learning circuits
in a network of 4 neurons with 64 synapses each (see highlighted area). The
chip, comprising of additional test structures, measures $3\times 5\,$mm2.

One of the most effective strategies that biology uses to cope with noise and
variability is to utilize adaptation and plasticity. This strategy has also
been adopted by the neuromorphic community: several on-chip implementations of
spike-based learning circuits have been proposed in the past [6, 10, 11, 12,
13, 14, 15, 16, 17, 7, 8, 9]. However, few have addressed the problem of being
able to operate robustly and autonomously in continuous time, with the ability
to switch automatically and reliably between learning and inference modes.
Following the original neuromorphic engineering approach [18], we propose a
set of analog circuits that faithfully emulate synaptic plasticity mechanisms
observed in pyramidal cells of cortical circuits and implement complex spike-
based learning and state-dependent mechanisms that support this functionality.
In addition, we extend the concept of long-term bi-stability of synaptic
weights, proposed to increase robustness to noise and variability in the input
signals [19, 14], to a tristate stability and weight discretization circuit
that increases the resolution of the (stable and crystallized) synaptic
weights. The synaptic plasticity circuits update an internal state variable of
the synapse on every pre-synaptic input spike. The change in this state
variable is computed in continuous time by the soma block of the neuron. In
parallel, depending on its value, the internal variable is driven to one of
three possible stable states and converted to a discrete three-state synaptic
weight current value. The post-synaptic learning circuits comprise an
additional mechanism that gates the weight changes, to stop the learning
process when the neuron’s mean firing rate is outside a defined learning
window. The circuits were fabricated on a prototype SNN chip designed in a 180
nm 6M1P CMOS technology and tested within a network of 4 neurons with 64
synapses each (see Fig. 1). In the following sections we describe the main
building blocks used at both the synapse and neuron level, demonstrate their
expected behavior with circuit simulations, and provide experimental results
measured from the chip.

##  II Network architecture

Figure 2: Block diagram of a single neuron row. The plastic synapses (in red)
consist of input logic, a weight update, tristate stability, and a current ADC
block. Input spikes arriving at a synapse update the internal weight variable
$\textsf{V}_{\textsf{w}}$, and change it by an amount that is determined by
the post-synaptic learning circuits at the soma (in green). The weight voltage
is slowly driven to one of three possible stable states, and converted into a
synaptic current by thresholding circuits. A parallel pathway provides a
target current (in blue). Both input and target currents are integrated over
time by differential pair integrator (DPI) circuits. The soma (in green),
comprises of an Integrate & Fire (I&F) block which integrates the sum of
target and input currents, a Delta rule block that calculates the difference
of the two DPI currents to determine the amplitude of the weight change, and a
hysteretic Winner-Take-All (hWTA) block used to determine if and when to
“stop-learning”.

The block diagram of each neuron in the network is shown in Fig. 2. Input
digital events ($\textsf{x}_{\textsf{0-N}}$) arrive at the individual synapses
via asynchronous logic [2] and trigger local weight update circuits to induce
a change in the voltage stored on a local capacitor by an amount determined by
the post-synaptic learning circuits. In parallel, a tristate stability circuit
drives this internal voltage to one of three possible stable states. This
local internal voltage is then discretized and converted to a low,
intermediate or high current value. All currents produced by all synapses are
summed spatially and conveyed to a differential pair integrator (DPI), which
integrates the weighted sum over time [20]. A parallel and analogous pathway
receives input events representing a desired target signal
($\textsf{x}_{\textsf{t}}$), and produces a corresponding current from its
dedicated DPI circuit. The target and input currents are both summed to drive
the neuron’s post-synaptic Integrate & Fire (I&F) circuit [21], and subtracted
to drive the soma’s Delta rule circuit [22]. The Delta rule circuit produces
either positive or negative weight update signals proportional to the
difference between the target input and the weighted synaptic input. These
signals are broadcast to all the neuron’s input synapses in continuous time if
learning is enabled. Learning is enabled (or disabled) by means of two
hysteretic Winner-Take-All (hWTA) circuits [23] that compare the neuron’s mean
output firing rate to a low and a high threshold (see Section III-B for
details).

##  III Circuits

As the details of the Delta rule and I&F circuits have already been presented
[22, 21, 11], we describe the synapse learning circuits and the soma hWTA
circuit.

(a)

(b)

(c)

(d)

Figure 3: Synapse learning circuits. (3(a)) The weight update circuit
increases or decreases the internal analog weight variable
$\textsf{V}_{\textsf{w}}$ with every input spike $\textsf{V}_{\textsf{PRE}}$;
(3(b)) The tri-stability supply voltage circuit determines which of the two
amplifiers in (3(c)) to power depending on the value of
$\textsf{V}_{\textsf{w}}$ with respect to $\textsf{V}_{\textrm{dd}}/2$ by
activating either $\textsf{V}_{\textsf{bH}}$ or $\textsf{V}_{\textsf{bL}}$.
(3(c)) The tristability circuit drives the $\textsf{V}_{\textsf{w}}$ voltage
towards ground, $\textsf{V}_{\textrm{dd}}/2$ or $\textsf{V}_{\textrm{dd}}$
depending on its value relative to $\textsf{V}_{\textsf{THH}}$ and
$\textsf{V}_{\textsf{THL}}$. (3(d)) The current discretization circuit
converts $\textsf{V}_{\textsf{w}}$ into a low (the leakage current
$\textsf{I}_{\textsf{0}}$), intermediate, or high current.

###  III-A Plastic synapse circuit

Figure 4: hysteresis WTA circuit used to determine the “stop-learning”
signals. The digital output voltage $\textsf{V}_{\textsf{OUT}}$ switches from
low to high only if the left input current $\textsf{I}_{\textsf{L}}$ increases
above $\textsf{I}_{\textsf{R}}$ by an amount at least equal to
$\textsf{I}_{\textsf{bh}}$.

Figure 3 presents all of the learning circuits used at the synaptic level.
With every pre-synaptic spike, the weight update circuit (Fig. 3(a)) increases
or decreases the internal analog weight variable $\textsf{V}_{\textsf{w}}$ by
an amount determined by the voltages $\textsf{V}_{\textsf{UP}}$ and
$\textsf{V}_{\textsf{DN}}$, produced by the post-synaptic Delta rule circuits.
The tri-stability supply voltage circuit (Fig. 3(b)), produces the biases that
power either of the positive feedback amplifiers of Fig. 3(c), depending on
the state of $\textsf{V}_{\textsf{w}}$ with respect to
$\textsf{V}_{\textrm{dd}}/2$. The tri-stability circuit (Fig. 3(c)) consists
of two slew-rate limited positive feedback amplifiers which slowly drive
$\textsf{V}_{\textsf{w}}$ towards ground, $\textsf{V}_{\textrm{dd}}/2$, or
$\textsf{V}_{\textrm{dd}}$ depending on the value of $\textsf{V}_{\textsf{w}}$
relative to $\textsf{V}_{\textsf{THH}}$ and $\textsf{V}_{\textsf{THL}}$. The
weight discretization circuit (Fig. 3(d)) sets the value of the effective
synaptic current $\textsf{I}_{\textsf{w}}$ to $\textsf{I}_{\textsf{0}}$,
$\textsf{I}_{\textsf{wb}}$, or $2\textsf{I}_{\textsf{wb}}$ depending on the
state of $\textsf{V}_{\textsf{w}}$ with respect to $\textsf{V}_{\textsf{THL}}$
and $\textsf{V}_{\textsf{THH}}$.

###  III-B Hysteretic WTA for “stop-learning”

Figure 4 shows an instance of a hWTA circuit: it consists of two identical
cells, ($M_{2}$–$M_{6}$) and ($M_{7}$–$M_{11}$) that compete with each other.
As soon as one cell wins (e.g., the left one), the bias current
$\textsf{I}_{\textsf{bh}}$ is copied and added to the input current of the
winning branch (e.g., $\textsf{I}_{\textsf{L}}$). This creates a hysteresis
window, such that for the winning (left) cell to lose the competition, its
input current has to decrease below the input current of the opposite branch
by an additional factor equal to the bias current
($\textsf{I}_{\textsf{L}}<\textsf{I}_{\textsf{R}}-\textsf{I}_{\textsf{bh}}$).
The output voltage of this circuit $\textsf{V}_{\textsf{OUT}}$ switches to
“high” when the left cell wins, and to “low” when the right cell becomes the
winner.

To implement the “stop-learning” mechanism [14], we produce a current
$\textsf{I}_{\textsf{Ca}}$ (a surrogate of the neuron’s calcium concentration)
by integrating the post-synaptic neuron spikes with a DPI circuit [20]. We
then compare this current to two thresholds with the two hWTA circuits. The
digital output nodes of the two hWTA circuits were connected to logic gates to
produce an active high Learn signal when the $\textsf{I}_{\textsf{Ca}}$
current is within the set bounds (i.e., within the learning region) and a low
when it is outside this region. This Learn signal is then used as a “third
factor” to enable or disable the Delta rule weight circuit, and switch on or
off the weight updates. The hysteresis windows of the hWTA circuits are used
to distinguish between cases in which the target input is present (to enable
learning) or absent (to disable learning and automatically switch to an
“inference” mode). The effect of this window is described in Section IV-A.

##  IV Results

We validate the learning circuits with both circuit simulations and with
experimental results measured from the fabricated chip.

(a)

(b)

Figure 5: Row simulation results. In the top plots of both sub-figures, the
DPI synapse current (in red) follows the DPI target current (in blue) when the
target input is high. The neuron’s membrane activity (in grey) is scaled for
visibility. In the lower plots of both sub-figures the calcium current (in
black) enables the Learn signal when it lies between the learning region’s low
(green line) and high (red line) thresholds. (5(a)) Small hysteresis bias
($\textsf{I}_{\textsf{bh}}$ = 100 pA): after the target current is removed the
calcium current drops back into the learning region, the weights are
decreased, and the neuron forgets its tuning. (5(b)) Large hysteresis bias
($\textsf{I}_{\textsf{bh}}$ = 800 pA): the large hysteresis region around the
highest threshold (shaded pink) keeps the learning disabled, despite the fact
that the calcium current fell below the high threshold. The weights of the
plastic synapses do not change and the neuron maintains its proper tuning to
the trained pattern.

###  IV-A Circuit simulation results

Here, we show simulations of a single neuron and 40 plastic synapses during a
learning task and show how the hWTA enables automatic switching from learning
to inference.

After initializing all synaptic weights to zero, we started a training phase
by stimulating each plastic synapse with a 25 Hz input spike train, and by
sending a spike train with a 1 kHz frequency to the target synapse. As
expected, during this training phase, the weights of the synapses potentiated
and the total weighted synaptic input current increased (see the red trace of
Fig. 5). During the inference phase, we removed the target input spike train
while keeping on stimulating the input synapses. As expected, without this
extra input, the average mean firing rate of the neuron decreased, and the
calcium concentration current fell below the upper bound of the learning
region. Figure 5 shows this task performed with two values for
$\textsf{I}_{\textsf{bh}}$, which governs the width of the hysteresis window.
Without a proper hysteresis window (Fig. 5(a)), when the neuron falls back
into a learning region it “forgets” its training (i.e., the learning circuits
decrease the weights). On the other hand, by properly tuning the hysteresis
window (Fig. 5(b)), the network remains in a “stop-learning” mode, and the
neuron retains a high output firing rate response to the trained pattern, even
in absence of a target signal. In the larger hysteresis window case, the total
estimated power consumption is 1.07 uW, and a maximum (mean) energy of 740 pJ
(680 pJ) is required to update the weights.

###  IV-B Chip measurement results

(a)

(b)

Figure 6: Tristability chip measurements. (6(a)) Stability at
$\textsf{V}_{\textrm{dd}}$ and ground: When the target is presented, the
plastic synapse weight is increased by the post-synaptic learning circuits
($\overline{\textsf{V}_{\textrm{up}}}$ and $\textsf{V}_{\textrm{dn}}$ scaled
for visibility). As the tristability bias increases, the circuit opposes the
weight update more strongly. When the target is removed, the tristability
maintains the weight value around $\textsf{V}_{\textrm{dd}}$ for larger values
of $\textsf{I}_{\textsf{bs}}$ (in orange and purple). (5(b)) Stability at
$\textsf{V}_{\textrm{dd}}/2$: as $\textsf{I}_{\textsf{bs}}$ increases the
tristability opposes the learning with more strength.

####  IV-B1 Tristability

The results from the measurements of the plastic synapse circuits are shown in
Fig. 6. Initially, the neuron is presented with a high target activity,
triggering large positive weight updates and causing a rapid increase in the
synapse weight internal variable. Upon removal of the target, the weight is
decreased. By increasing the power to the tristate stability amplifiers (Fig.
3(c)), i.e., by increasing $\textsf{I}_{\textsf{bs}}$ of Fig. 3(b), the
circuit opposes the weight changes more strongly and drives
$\textsf{V}_{\textsf{w}}$ to one of the three stable states more quickly.
Stability at $\textsf{V}_{\textrm{dd}}$ and ground is shown in Fig. 6(a) and
at $\textsf{V}_{\textrm{dd}}/2$ in Fig. 6(b). Once the stimulation ends, the
tristability circuit crystalizes the weight to one of the three stable states
depending on the value of $\textsf{I}_{\textsf{bs}}$.

####  IV-B2 Hysteresis for “stop-learning”

Figure 7 shows the results of the characterization of the hysteretic calcium-
based stop-learning mechanism.

Figure 7: Hysteresis chip measurements. The hysteresis window is shown for
three different values of $\textsf{I}_{\textsf{bh}}$. Increases in
$\textsf{I}_{\textsf{bh}}$ produce larger hysteresis windows which are useful
for tuning the “stop-learning” properties of the network.

Similarly to the previous experiment, the neuron is initially stimulated with
a high target activity, bringing it to the learning region. The plastic
synapse weight rapidly increases, pushing the neuron into the “stop-learning”
region. Once the target activity is removed, the neuron returns to the
learning region, and, for small hysteresis window settings (top blue plot in
Fig. 7), the plastic synapse decreases its weight as it is stimulated. For
higher values of $\textsf{I}_{\textsf{bh}}$ the hysteresis window increases
(orange plot in Fig. 7) and when the target is removed, the neuron’s return to
the learning mode is delayed. As this delay increases, even though the plastic
synapse keeps on being stimulated, the neuron remains in the “stop-learning”
region and the weight remains unchanged (purple plot in Fig. 7).

TABLE I: Comparison to the state-of-the-art

|  [24] |  [25] |  [17] |  [11] |  [This work]
---|---|---|---|---|---
Technology |  28 nm |  14 nm |  180 nm |  180 nm |  180 nm
Design |  digital |  digital |  mixed-signal |  mixed-signal |  mixed-signal
Learning |  semi supervised |  programmable |  semi supervised |  error based |  semi supervised
Stop learning |  yes |  no |  yes |  no |  yes
Weight resolution |  3bit |  9bit |  bi-stable |  4bit |  tri-stable
Energy/SOP |  12.7 pJ |  120 pJ |  360 pJ |  720 pJ |  680 pJ
Power supply |  0.55 V |  0.75 V |  1.8 V |  1.8 V |  1.8 V

##  V Conclusions

We presented a set of analog circuits that enable learning in mixed-signal
neuromorphic SNNs, with tristate stability and weight discretization circuits.
By comparing the neuron’s calcium concentration to lower and upper bounds, and
by using hysteresis, we demonstrate effective always-on learning features,
that automatically switch from learning mode to inference mode, without having
to manually disable or enable learning. Comparisons to previous efforts are
provided in Table I.

## Acknowledgment

The authors thank Shyam Narayanan, Charlotte Frenkel, and Junren Chen for
fruitful discussions and contributions.

## References

  * [1] E. Chicca, F. Stefanini, C. Bartolozzi and G. Indiveri  “Neuromorphic electronic circuits for building autonomous cognitive systems”  In _Proceedings of the IEEE_ 102.9, 2014, pp. 1367–1388
  * [2] S. Moradi, N. Qiao, F. Stefanini and G. Indiveri  “A Scalable Multicore Architecture With Heterogeneous Memory Structures for Dynamic Neuromorphic Asynchronous Processors (DYNAPs)”  In _Biomedical Circuits and Systems, IEEE Transactions on_ 12.1, 2018, pp. 106–122
  * [3] Chetan Singh Thakur et al.  “Large-Scale Neuromorphic Spiking Array Processors: A Quest to Mimic the Brain”  In _Frontiers in Neuroscience_ 12, 2018, pp. 891
  * [4] Qiangfei Xia and J. Yang  “Memristive crossbar arrays for brain-inspired computing”  In _Nature materials_ 18.4 Nature Publishing Group, 2019, pp. 309
  * [5] Ben Varkey Benjamin et al.  “Neurogrid simulates cortical cell-types, active dendrites, and top-down attention”  In _Neuromorphic Computing and Engineering_ 1.1 IOP Publishing, 2021, pp. 013001
  * [6] P. Häfliger, M. Mahowald and L. Watts  “A spike based learning neuron in analog VLSI”  In _Advances in neuralinformation processing systems (NIPS)_ 9 MIT Press, 1997, pp. 692–698
  * [7] Pierre Lewden et al.  “Toward Hardware Spiking Neural Networks with Mixed-Signal Event-Based Learning Rules”  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , 2020, pp. 1–8
  * [8] Seiji Uenohara and Kazuyuki Aihara  “A 18.7 TOPS/W Mixed-Signal Spiking Neural Network Processor With 8-bit Synaptic Weight On-Chip Learning That Operates in the Continuous-Time Domain”  In _IEEE Access_ 10, 2022, pp. 48338–48348
  * [9] Melika Payvand et al.  “Self-organization of an inhomogeneous memristive hardware for sequence learning”  In _Nature communications_ 13.1 Nature Publishing Group, 2022, pp. 1–12
  * [10] A. Bofill-i-Petit and A.F. Murray  “Circuits for VLSI implementation of temporally asymmetric Hebbian learning”  In _Advances in Neural Information processing systems (NIPS)_ 14 Cambridge, MA, USA: MIT Press, 2002, pp. 1091–1098
  * [11] Matteo Cartiglia et al.  “Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems”  In _IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2022, pp. 1–5  IEEE
  * [12] G. Indiveri  “Neuromorphic Bistable VLSI Synapses with Spike-Timing-Dependent Plasticity”  In _Advances in Neural Information Processing Systems (NIPS)_ 15 Cambridge, MA, USA: MIT Press, 2003, pp. 1091–1098
  * [13] E. Chicca et al.  “A VLSI recurrent network of integrate–and–fire neurons connected by plastic synapses with long term memory”  In _IEEE Transactions on Neural Networks_ 14.5, 2003, pp. 1297–1307
  * [14] S. Mitra, S. Fusi and G. Indiveri  “Real-time classification of complex patterns using spike-based learning in neuromorphic VLSI”  In _Biomedical Circuits and Systems, IEEE Transactions on_ 3.1 IEEE, 2009, pp. 32–42
  * [15] C. Mayr and J. Partzsch  “Rate and Pulse Based Plasticity Governed by Local Synaptic State Variables”  In _Frontiers in Synaptic Neuroscience_ 2.33, 2010, pp. 28
  * [16] S. Bamford, A.F. Murray and D.J. Willshaw  “Spike-timing-dependent plasticity with weight dependence evoked from physical constraints”  In _Biomedical Circuits and Systems, IEEE Transactions on_ 6.4 IEEE, 2012, pp. 385–398
  * [17] Ning Qiao et al.  “A reconfigurable on-line learning spiking neuromorphic processor comprising 256 neurons and 128K synapses”  In _Frontiers in neuroscience_ 9 Frontiers, 2015, pp. 141
  * [18] Carver Mead  “How we created neuromorphic engineering”  In _Nature Electronics_ 3.7 Nature Publishing Group, 2020, pp. 434–435
  * [19] W. Senn and S. Fusi  “Learning Only When Necessary: Better Memories of Correlated Patterns in Networks with Bounded Synapses”  In _Neural Computation_ 17.10 MIT Press, 2005, pp. 2106–2138
  * [20] C. Bartolozzi and G. Indiveri  “Synaptic dynamics in analog VLSI”  In _Neural Computation_ 19.10, 2007, pp. 2581–2603
  * [21] Arianna Rubino et al.  “Ultra-Low-Power FDSOI Neural Circuits for Extreme-Edge Neuromorphic Intelligence”  In _IEEE Transactions on Circuits and Systems I: Regular Papers_ 68.1 IEEE, 2020, pp. 45–56
  * [22] M. Payvand and G. Indiveri  “Spike-Based Plasticity Circuits for Always-on On-Line Learning in Neuromorphic Systems”  In _IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2019, pp. 1–5  IEEE
  * [23] G. Indiveri  “Winner-take-all networks with lateral excitation”  In _Analog Integrated Circuits and Signal Processing_ 13.1/2 Kluwer Academic, 1997, pp. 185–193
  * [24] Charlotte Frenkel, Martin Lefebvre, Jean-Didier Legat and David Bol  “A 0.086-mm2 12.7-pJ/SOP 64k-Synapse 256-Neuron Online-Learning Digital Spiking Neuromorphic Processor in 28-nm CMOS”  In _IEEE Transactions on Biomedical Circuits and Systems_ 13.1 IEEE, 2019, pp. 145–158
  * [25] Mike Davies et al.  “Loihi: A neuromorphic manycore processor with on-chip learning”  In _IEEE Micro_ 38.1 IEEE, 2018, pp. 82–99