#  Some new results concerning the valences of (super) edge-magic graphs

Y. Takahashi  Department of Science and Engineering, Faculty of Electronics
and Informatics, Kokushikan University, 4-28-1 Setagaya, Setagaya-ku, Tokyo
154-8515, Japan<EMAIL_ADDRESS>,  F.A. Muntaner-Batle  Graph Theory
and Applications Research Group, School of Electrical Engineering and Computer
Science, Faculty of Engineering and Built Environment, The University of
Newcastle, NSW 2308 Australia<EMAIL_ADDRESS>and  R. Ichishima  Department
of Sport and Physical Education, Faculty of Physical Education, Kokushikan
University, 7-3-1 Nagayama, Tama-shi, Tokyo 206-8515, Japan
<EMAIL_ADDRESS>
(Date: June 28, 2023)

###### Abstract.

A graph $G$ is called edge-magic if there exists a bijective function
$f:V\left(G\right)\cup
E\left(G\right)\rightarrow\left\\{1,2,\ldots,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right\\}$
such that $f\left(u\right)+f\left(v\right)+f\left(uv\right)$ is a constant
(called the valence of $f$) for each $uv\in E\left(G\right)$. If
$f\left(V\left(G\right)\right)=\left\\{1,2,\ldots,\left|V\left(G\right)\right|\right\\}$,
then $G$ is called a super edge-magic graph. A stronger version of edge-magic
and super edge-magic graphs appeared when the concepts of perfect edge-magic
and perfect super edge-magic graphs were introduced. The super edge-magic
deficiency $\mu_{s}\left(G\right)$ of a graph $G$ is defined to be either the
smallest nonnegative integer $n$ with the property that $G\cup nK_{1}$ is
super edge-magic or $+\infty$ if there exists no such integer $n$. On the
other hand, the edge-magic deficiency $\mu\left(G\right)$ of a graph $G$ is
the smallest nonnegative integer $n$ for which $G\cup nK_{1}$ is edge-magic,
being $\mu\left(G\right)$ always finite. In this paper, the concepts of
(super) edge-magic deficiency are generalized using the concepts of perfect
(super) edge-magic graphs. This naturally leads to the study of the valences
of edge-magic and super edge-magic labelings. We present some general results
in this direction and study the perfect (super) edge-magic deficiency of the
star $K_{1,n}$.

###### Key words and phrases:

perfect (super) edge-magic labeling, perfect (super) edge-magic deficiency,
valence, graph labeling

###### 1991 Mathematics Subject Classification:

Primary 05C78

##  1\. Introduction

Unless stated otherwise, the graph-theoretical notation and terminology used
here will follow Chartrand and Lesniak [2]. In particular, the _vertex set_ of
a graph $G$ is denoted by $V\left(G\right)$, while the _edge set_ of $G$ is
denoted by $E\left(G\right)$.

For the sake of brevity, we will use the notation $\left[a,b\right]$ for the
interval of integers $x$ such that $a\leq x\leq b$. Kotzig and Rosa [14]
initiated the study of what they called magic valuations. This concept was
later named edge-magic labelings by Ringel and Lladó [22], and this has become
the popular term. A graph $G$ is called _edge-magic_ if there exists a
bijective function $f:V\left(G\right)\cup
E\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right]$
such that $f\left(u\right)+f\left(v\right)+f\left(uv\right)$ is a constant
(called the _valence_ $\text{val}\left(f\right)$ of $f$) for each $uv\in
E\left(G\right)$. Such a function is called an _edge-magic labeling_. More
recently, they have also been referred to as edge-magic total labelings by
Wallis [24].

Enomoto et al. [3] introduced a particular type of edge-magic labelings,
namely, super edge-magic labelings. They defined an edge-magic labeling of a
graph $G$ with the additional property that
$f\left(V\left(G\right)\right)=\left[1,\left|V\left(G\right)\right|\right]$ to
be a _super edge-magic labeling_. Thus, a _super edge-magic graph_ is a graph
that admits a super edge-magic labeling.

Lately, super edge-magic labelings and super edge-magic graphs were called by
Wallis [24] strong edge-magic total labelings and strongly edge-magic graphs,
respectively. According to the latest version of the survey on graph labelings
by Gallian [9] available to the authors, Hegde and Shetty [11] showed that the
concepts of super edge-magic graphs and strongly indexable graphs (see [1] for
the definition of a strongly indexable graph) are equivalent.

The following result found in [4] provides necessary and sufficient conditions
for a graph to be super edge-magic, which will prove later to be useful.

######  Lemma 1.1.

A graph $G$ is super edge-magic if and only if there exists a bijective
function
$f:V\left(G\right)\rightarrow\left[1,\right.\left|V\left(G\right)\right|]$
such that the set

$S=\left\\{f\left(u\right)+f\left(v\right):uv\in E\left(G\right)\right\\}$

consists of $\left|E\left(G\right)\right|$ consecutive integers. In such a
case, $f$ extends to a super edge-magic labeling of $G$ with valence
$k=\left|V\left(G\right)\right|+\left|E\left(G\right)\right|+s$, where
$s=\min\left(S\right)$ and

$S=\left[k-\left(\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right),k-\left(\left|V\left(G\right)\right|+1\right)\right]\text{.}$

The _low characteristic_ and _high characteristic_ of a super edge-magic graph
$G$ are defined by $\gamma\left(G\right)=\min\left(S\right)$ and
$\Gamma\left(G\right)=\max\left(S\right)$, respectively, where $S$ is the set
as in Lemma 1.1. These concepts will prove to be useful in this paper later.

For every graph $G$, Kotzig and Rosa [14] proved that there exists an edge-
magic graph $H$ such that $H=G\cup nK_{1}$ for some nonnegative integer $n$.
This motivated them to define the edge-magic deficiency of a graph. The _edge-
magic deficiency_ $\mu\left(G\right)$ of a graph $G$ is the smallest
nonnegative integer $n$ for which $G\cup nK_{1}$ is edge-magic. Inspired by
Kotzig and Rosa’s notion, the concept of _super edge-magic deficiency_
$\mu_{s}\left(G\right)$ of a graph $G$ was analogously defined in [6] as
either the smallest nonnegative integer $n$ with the property that $G\cup
nK_{1}$ is super edge-magic or $+\infty$ if there exists no such integer $n$.
Thus, the super edge-magic deficiency of a graph $G$ is a measure of how
“close” (“ far ”) $G$ is to (from) being super edge-magic.

An alternative term exists for the super edge-magic deficiency, namely, the
vertex dependent characteristic. This term was coined by Hedge and Shetty
[10]. In [10], they gave a construction of polygons having the same angles and
distinct sides using the result on the super edge-magic deficiency of cycles
provided in [7].

Noting that for a super edge-magic labeling $f$ of a graph $G$ with order $p$
and size $q$, the valence $k$ is given by the formula:

$k=\frac{\sum_{u\in
V\left(G\right)}\text{deg}(u)f(u)+\sum_{i=p+1}^{p+q}i}{q}\text{.}\\\ $

López et al. [16] defined the set

$S_{G}=\Biggl{\\{}\frac{\sum_{u\in
V\left(G\right)}\text{deg}(u)g(u)+\sum_{i=p+1}^{p+q}i}{q}\text{:}\\\ \text{
the function }g:V\left(G\right)\rightarrow\left[1,p\right]\text{ is
bijective}\Biggr{\\}}\text{.}$

If $\lceil\min S_{G}\rceil\leq\lfloor\max S_{G}\rfloor$, then the _super edge-
magic interval_ of $G$ is the set

$I_{G}=[\lceil\min S_{G}\rceil,\lfloor\max S_{G}\rfloor]\text{.}$

The _super edge-magic set_ of $G$ is

$\sigma_{G}=\left\\{k\in I_{G}\right.\text{: there exists a super edge-magic
labeling of }G\text{ with valence }k\left.\right\\}.$

López et al. called a graph $G$ _perfect super edge-magic_ if
$I_{G}=\sigma_{G}$. They showed that the family of paths $P_{n}$ is a family
of perfect super edge-magic graphs with $|I_{P_{n}}|=1$ if $n$ is even and
$|I_{P_{n}}|=2$ if $n$ is odd, and raise the question of whether there is an
infinite family of graphs $(F_{1},F_{2},\ldots)$ such that each member of the
family is perfect super edge-magic and
$\text{lim}_{i\rightarrow+\infty}|I_{F_{i}}|=+\infty$. They showed that graphs
$G\cong C_{p^{k}}\odot\overline{K_{n}}$, where $p>2$ is a prime number and
$\odot$ denotes the corona product, is such a family. For more detailed
information on this matter, see [16].

For an edge-magic labeling $f$ of a graph $G$, the valence $k$ is given by the
formula:

$k=\frac{\sum_{u\in V\left(G\right)}\text{deg}(u)f(u)+\sum_{e\in
E\left(G\right)}f\left(e\right)}{\left|E\left(G\right)\right|}\text{.}$

In [18] López et al. introduced, in a similar way of what we have seen so far
for the case of super edge-magic labelings, the concepts of edge-magic
interval, edge-magic set and perfect edge-magic graph.

For a graph $G$, define the set

$T_{G}=\Biggl{\\{}\frac{\sum_{u\in
V\left(G\right)}\text{deg}(u)g(u)+\sum_{e\in
E\left(G\right)}g\left(e\right)}{\left|E\left(G\right)\right|}\text{:}\\\
\text{ the function }g:V\left(G\right)\cup
E\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right]\text{
is bijective}\Biggr{\\}}\text{.}$

If $\lceil\min T_{G}\rceil\leq\lfloor\max T_{G}\rfloor$, then the _edge-magic
interval_ of $G$ is the set

$\lambda_{G}=\left[\lceil\min T_{G}\rceil,\lfloor\max
T_{G}\rfloor\right]\text{.}$

The _edge-magic set_ of $G$ is

$\tau_{G}=\left\\{k\in\lambda_{G}\right.\text{: there exists an edge-magic
labeling of }G\text{ with valence }k\left.\right\\}.$

López et al. called a graph $G$ _perfect edge-magic_ if
$\lambda_{G}=\tau_{G}$.

Motivated by the concepts of edge-magic and super edge-magic deficiencies
together with the concepts of perfect edge-magic and perfect super edge-magic
graphs, we introduce the concepts of perfect edge-magic deficiency and perfect
super edge-magic deficiency next.

The _perfect edge-magic deficiency_ $\mu_{p}\left(G\right)$ of a graph $G$ is
defined to be the smallest nonnegative integer $n$ with the property that
$G\cup nK_{1}$ is perfect edge-magic or $+\infty$ if there exists no such
integer $n$. On the other hand, the _perfect super edge-magic deficiency_
$\mu_{p}^{s}\left(G\right)$ of a graph $G$ is defined to be the smallest
nonnegative integer $n$ with the property that $G\cup nK_{1}$ is perfect super
edge-magic or $+\infty$ if there exists no such integer $n$.

In [18] López et al. defined the _irregular crown_
$C(n;j_{1},j_{2},\ldots,j_{n})=(V,E)$, where $n>2$ and $j_{i}\geq 0$ for all
$i\in[1,n]$ as follows: $V=\\{v_{i}:i\in[1,n]\\}\cup V_{1}\cup
V_{2}\cup\cdots\cup V_{n}$, where $V_{k}=\\{v_{k}^{i}:i\in[1,{j_{k}]}\\}$, if
$j_{k}\neq 0$ and $V_{k}=\emptyset$ if $j_{k}=0$ for each $k\in[1,n]$ and
$E=\\{v_{i}v_{i+1}:i\in[1,n-1]\\}\cup\\{v_{1}v_{n}\\}\cup(\cup^{n}_{k=1,j_{k}\neq
0}\\{v_{k}v_{k}^{l}:k\in[1,j_{k}]\\})$. In particular, they denoted the graph
$C_{m}^{n}\cong C(m;j_{1},j_{2},\ldots,j_{m})$, where $j_{2i-1}=n$ for each
$i\in[1,(m+1)/2]$, and $j_{2i}=0$ for each $i\in[1,(m-1)/2]$ using the
notation $C_{m}^{n}$. They proved that the graphs $C_{3}^{n}$ and $C_{5}^{n}$
are perfect edge-magic for all integers $n>1$. In the same paper, they also
proved that if $m=p^{k}$ when $p$ is a prime number and $k\in\mathbb{N}$, then
the graph $C_{m}\odot\overline{K_{n}}$ is perfect edge-magic for all positive
integers $n$.

López et al. [17] defined the concepts of $\mathfrak{F}^{k}$-family and
$\mathfrak{E}^{k}$-family of graphs as follows. The infinite family of graphs
$(F_{1},F_{2},\ldots)$ is an $\mathfrak{F}^{k}$-_family_ if each element
$F_{n}$ admits exactly $k$ different valences for super edge-magic labelings,
and $\text{lim}_{n\rightarrow+\infty}|I(F_{n})|=+\infty$. The infinite family
of graphs $(F_{1},F_{2},\ldots)$ is an $\mathfrak{E}^{k}$-_family_ if each
element $F_{n}$ admits exactly $k$ different valences for edge-magic
labelings, and $\text{lim}_{n\rightarrow+\infty}|J(F_{n})|=+\infty$.

An easy observation from the results found in [5] and independently in [24],
is that $(K_{1,2},K_{1,3},\ldots)$ is an $\mathfrak{F}^{2}$-family and
$\mathfrak{E}^{3}$-family. They posed the following two problems: for which
positive integers $k$ is it possible to find $\mathfrak{F}^{k}$-families and
$\mathfrak{E}^{k}$-families? Their main results in [17] are that an
$\mathfrak{F}^{k}$-family exits for each $k=$ 1, 2 and 3, and an
$\mathfrak{E}^{k}$-family exits for each $k=$ 3, 4 and 7.

The following inequality was found by Enomoto et al. [3].

######  Theorem 1.1.

If $G$ is a super edge-magic graph, then

$\left|E\left(G\right)\right|\leq 2\left|V\left(G\right)\right|-3\text{.}$

The following result found in [13] provides a sufficient condition for a super
edge-magic graph to contain a triangle.

######  Theorem 1.2.

If $G$ is a super edge-magic graph with

$\left|E\left(G\right)\right|=2\left|V\left(G\right)\right|-3\text{ or
}2\left|V\left(G\right)\right|-4\text{,}$

then $G$ contains a triangle.

##  2\. General results

In this section, we will establish some general results on super edge-magic
graphs. We begin with the following result, which relates the order, girth and
the cardinality of $\sigma_{G}$.

######  Theorem 2.1.

Let $G$ be a super edge-magic graph of size $2\left|V\left(G\right)\right|-3$
and girth $g\left(G\right)=3$. Then $\left|\sigma_{G}\right|=1$.

###### Proof.

Consider such a graph $G$. If $f$ is a super edge-magic labeling of $G$, then

$\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}=\left[3,2\left|V\left(G\right)\right|-1\right]$

and

$\text{val}\left(f\right)=\left|V\left(G\right)\right|+\left|E\left(G\right)\right|+\min\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}=3\left|V\left(G\right)\right|$

by Lemma 1.1. Therefore,
$\sigma_{G}=\left\\{3\left|V\left(G\right)\right|\right\\}$, completing the
proof. ∎

The next concept will prove to be useful throughout this paper. Let $f$ be a
super edge-magic labeling of a graph $G$. Then the _complementary labeling_
$\overline{f}$ of $f$ is defined as

$\overline{f}\left(x\right)=\left\\{\begin{tabular}[]{ll}$\left(\left|V\left(G\right)\right|+1\right)-f\left(x\right)$&if
$x\in V\left(G\right)$\\\
$\left(2\left|V\left(G\right)\right|+\left|E\left(G\right)\right|+1\right)-f\left(x\right)$&if
$x\in E\left(G\right)$.\end{tabular}\right.$

It is true that if $f$ is a super edge-magic labeling of a graph $G$, then
$\overline{f}$ is also a super edge-magic labeling of $G$.

Next, we show an example of a super edge-magic labeling of a graph $G$ with
$\left|E\left(G\right)\right|=2\left|V\left(G\right)\right|-4$ and labeled
with two different super edge-magic labelings $f$ and $\overline{f}$ (see
Figure 1 and Figure 2, respectively), producing two different valences. On the
orther hand, if $f$ is an edge-magic labeling of a graph $G$, then the
complementary labeling $\overline{f}$ of $f$ is the labeling
$\overline{f}:V\left(G\right)\cup
E\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right]$
defined by

$\overline{f}\left(x\right)=\left(\left|V\left(G\right)\right|+\left|E\left(G\right)\right|+1\right)-f\left(x\right)$

if $x\in V\left(G\right)\cup E\left(G\right)$. Observe that the complementary
labeling of an edge-magic labeling is also an edge-magic labeling.

Figure 1. A super edge-magic labeling $f$ with valence 11 Figure 2. A super
edge-magic labeling $\overline{f}$ with valence 12

######  Theorem 2.2.

Let $G$ be a super edge-magic graph of size $2\left|V\left(G\right)\right|-4$.
Then $\left|\sigma_{G}\right|=2$.

###### Proof.

Let $G$ be a super edge-magic graph with
$\left|E\left(G\right)\right|=2\left|V\left(G\right)\right|-4$ and $f$ be a
super edge-magic labeling of $G$. Then it is clear that

$\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}=\left[3,2\left|V\left(G\right)\right|-2\right]$

or

$\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}=\left[4,2\left|V\left(G\right)\right|-1\right]\text{.}$

Since each one of these two possibilities will provide a different valence, it
follows that $\left|\sigma_{G}\right|\leq 2$. However, we can guarantee that
$\left|\sigma_{G}\right|=2$. To see this, notice that the only way to get $3$
as an induced edge sum is by joining vertices, which have been labeled $1$ and
$2$ by a super edge-magic labeling $f$ of $G$. Now, if we consider the super
edge-magic labeling $\overline{f}$, the vertices to which $f$ assignes labels
$1$ and $2$ become labeled $\left|V\left(G\right)\right|$ and
$\left|V\left(G\right)\right|-1$ by $\overline{f}$, respectively. Moreover,
since they are adjacent, it follows that there is an edge with induced sum
$2\left|V\left(G\right)\right|-1$ when we consider $\overline{f}$. Thus, $f$
and $\overline{f}$ have valences

$\text{val}\left(f\right)=3+\left|V\left(G\right)\right|+2\left|V\left(G\right)\right|-4=3\left|V\left(G\right)\right|-1$

and

$\text{val}\left(\overline{f}\right)=\left(2\left|V\left(G\right)\right|-1\right)+\left|V\left(G\right)\right|+1=3\left|V\left(G\right)\right|\text{,}$

respectively. In a similar way, if $f$ is a labeling that has an induced edge
sum $2\left|V\left(G\right)\right|-1$, then vertices labeled
$\left|V\left(G\right)\right|$ and $\left|V\left(G\right)\right|-1$ must be
adjacent. Therefore, taking the complement of this labeling, we obtain the
desired result. ∎

The following result was shown in [13] (see also [15] for a different approach
to this problem using the product $\otimes_{h}$ defined on digraphs in [8]).

######  Theorem 2.3.

There exists an infinite family of super edge-magic graphs $G$ of size
$2\left|V\left(G\right)\right|-5$ and girth $g\left(G\right)=5$.

We next show the following result.

######  Theorem 2.4.

Let $G$ be a super edge-magic graph with
$\left|E\left(G\right)\right|=2\left|V\left(G\right)\right|-5$ and girth
$g\left(G\right)\geq 5$. Then $\left|\sigma_{G}\right|=1$.

###### Proof.

Let $G$ be a graph of girth $g\left(G\right)\geq 5$ and with a super edge-
magic labeling $f$. Consider the set
$S=\left\\{f\left(u\right)+f\left(v\right):uv\in E\left(G\right)\right\\}$.
Then there are three possibilities for $S$, namely,

$S=\left[3,2\left|V\left(G\right)\right|-3\right],S=\left[4,2\left|V\left(G\right)\right|-2\right]\text{
or }S=\left[5,2\left|V\left(G\right)\right|-1\right]\text{.}$

Assume, to the contrary, that
$S=\left[3,2\left|V\left(G\right)\right|-3\right]$. Now, the only way to get
the induced edge sum $3$ is by joining vertices labeled $1$ and $2$. The only
way to get the induced edge sum $4$ is by joining vertices labeled $1$ and
$3$. Hence, $G$ has edges joining those vertices. To get the induced edge sum
$5$, we cannot use vertices labeled $2$ and $3$, since this choice would force
a triangle and would have girth $3$. Thus, we need to include an edge joining
vertices labeled by $1$ and $4$. For a similar reason, to get the induced edge
sum $6$, we need to include an edge joining vertices labeled by $1$ and $5$.
Any other choice would produce a triangle. We proceed in this manner until we
get the induced edge sum $\left|V\left(G\right)\right|+1$. At this point, we
have a star of order $\left|V\left(G\right)\right|$ (see Figure 3). Thus, we
cannot add any new edge to get the induced edge sum
$\left|V\left(G\right)\right|+2$, since any new edge would produce a triangle.
In a similar way, we can see that the set
$S=\left[5,2\left|V\left(G\right)\right|-1\right]$ cannot take place.
Therefore, the only possibility left is
$S=\left[4,2\left|V\left(G\right)\right|-2\right]$, and the result follows. ∎

Figure 3. A star $G$ of order $\left|V\left(G\right)\right|=p$ with induced
edge sums

To conclude this section, we present the following result.

######  Theorem 2.5.

Let $G$ be a graph with
$\left|E\left(G\right)\right|\geq\left|V\left(G\right)\right|$. If $G$ is a
super edge-magic graph of girth $g\left(G\right)\geq 4$, then
$3+\left|E\left(G\right)\right|+\left|V\left(G\right)\right|$ is not a valence
for any super edge-magic labeling of $G$.

###### Proof.

Let $G$ be a super edge-magic graph with
$\left|E\left(G\right)\right|\geq\left|V\left(G\right)\right|$, girth
$g\left(G\right)\geq 4$ and with a super edge-magic labeling $f$. Assume, to
the contrary, that
$\text{val}\left(f\right)=3+\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.
Then

$3+\left|V\left(G\right)\right|+\left|E\left(G\right)\right|=\min\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}+\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\text{,}$

implying that

$\min\left\\{f\left(u\right)+f\left(v\right):uv\in
E\left(G\right)\right\\}=3\text{.}$

Now, the only way to obtain an edge with induced sum $3$ is by joining
vertices labeled $1$ and $2$. Also, the only way to obtain an edge with
induced sum $4$ is by joining vertices labeled $1$ and $3$. Hence, if we want
to avoid triangles, we need to induce the edge sums with labels
$\\{1,4\\},\\{1,5\\},\dots,\\{1,\left|V\left(G\right)\right|\\}$ to obtain the
induced edge sums $5,6,\dots,\left|V\left(G\right)\right|+1$, since any other
choice would produce a triangle. Moreover, notice that any choice for the edge
with induced sum $\left|V\left(G\right)\right|+2$ will produce a triangle,
which contradicts the fact that $g\left(G\right)\geq 4$. ∎

##  3\. New results involving stars

This section is devoted to study the valences for the edge-magic and super
edge-magic labelings of the unions of stars and isolated vertices. We begin by
presenting a result concerning with isomorphic labelings. To do this, we
introduce the concept of isomorphic (super) edge-magic labelings. For a graph
$G$, assume that $f$ and $g$ are two (super) edge-magic labelings of $G$. We
denote by $G_{f}$ and $G_{g}$ the graph $G$, where the vertices of $G$ take
the name of the labels assigned by the labelings $f$ and $g$, respectively.
Then we compute the adjacency matrices of $G_{f}$ and $G_{g}$, respectively,
and we denote them by $A\left(G_{f}\right)$ and $A\left(G_{g}\right)$, where
the rows and columns are placed in increasing order from left to right and top
to bottom, respectively. Notice that the rows and columns are not necessarily
labeled with consecutive integers, since the vertex labels of an edge-magic
labeling are not necessarily consecutive integers. Then labelings $f$ and $g$
are _isomorphic labelings_ , written $f\cong g$, if
$A\left(G_{f}\right)=A\left(G_{g}\right)$.

For example, consider the graph $G=C_{4}\cup K_{1}$ with two edge-magic
labelings $f$ and $g$ illustrated in Figure 4.

Figure 4. Two edge-magic labelings $f$ and $g$ of $G$

Then

$A\left(G_{f}\right)=A\left(G_{g}\right)=\bordermatrix{&1&2&3&5&8\cr
1&0&1&0&1&0\cr 2&1&0&1&0&0\cr 3&0&1&0&1&0\cr 5&1&0&1&0&0\cr 8&0&0&0&0&0}$

and hence $f\cong g$.

Next, consider the graph $G=C_{4}\cup K_{1}$ labeled by $\overline{f}$ as
illustrated in Figure 5.

Figure 5. An edge-magic labeling $\overline{f}$ of $G$

Then it is clear that $\overline{f}\not\cong f$ and $\overline{f}\not\cong g$,
since

$A\left(G_{\overline{f}}\right)=\bordermatrix{&2&5&7&8&9\cr 2&0&0&0&0&0\cr
5&0&0&1&0&1\cr 7&0&1&0&1&0\cr 8&0&0&1&0&1\cr 9&0&1&0&1&0}\text{,}$

$A\left(G_{\overline{f}}\right)\not=A\left(G_{f}\right)$ and
$A\left(G_{\overline{f}}\right)\not=A\left(G_{g}\right)$.

######  Theorem 3.1.

For every two positive integers $n$ and $l$, there exist exactly
$\left(l+1\right)\left(l+2\right)$ non-isomorphic super edge-magic labelings
of $K_{1,n}\cup lK_{1}$.

###### Proof.

Let $G=K_{1,n}\cup lK_{1}$, and define the graph $G$ with

$V\left(G\right)=\\{x\\}\cup\\{y_{i}:i\in\left[1,n\right]\\}\cup\\{z_{i}:i\in\left[1,l\right]\\}$

and $E\left(G\right)=\\{xy_{i}:i\in\left[1,n\right]\\}$. By Lemma 1.1, the set
$\\{f\left(xy_{i}\right):i\in\left[1,n\right]\\}$ is a set of $n$ consecutive
integers. Hence, if $S=\\{f\left(y_{i}\right):i\in\left[1,n\right]\\}$ is a
set of $n$ consecutive integers, then $S$ is
$\left[1,n\right]\text{or}\left[2,n+1\right]$ or $\dots\text{ or
}\left[l+2,n+l+1\right]$. This gives us $\left(l+2\right)$ possibilities for
the labels of $\\{y_{i}:i\in\left[1,n\right]\\}$ up to reordering. For each
one of these possibilities, there are exactly $\left(l+1\right)$ possible
labels that have not been used. This means that these labels must be assigned
to the vertices $\\{x\\}\cup\\{z_{i}:i\in\left[1,l\right]\\}$. However, since
$\deg z_{i}=0$ for each $i\in\left[1,l\right]$, we only need to concern about
the label assigned to $x$. Therefore, there are exactly $\left(l+1\right)$
possible choices for $f\left(x\right)$. This produces exactly
$\left(l+1\right)\left(l+2\right)$ non-isomorphic super edge-magic labelings
of $G$. ∎

######  Fact 1.

By the proof of the previous result, we know that if $f$ is a super edge-magic
labeling of $G$, then the set $\\{f\left(y_{i}\right):i\in\left[1,n\right]\\}$
is a set of $n$ consecutive integers.

Let $f$ be any super edge-magic labeling of $G$, and assume, without loss of
generality, that

$f\left(y_{1}\right)<f\left(y_{2}\right)<\cdots<f\left(y_{n}\right)$

and

$f\left(z_{1}\right)<f\left(z_{2}\right)<\cdots<f\left(z_{n}\right)\text{.}$

For the complementary labeling of $f$, we have

$\overline{f}\left(y_{1}\right)>\overline{f}\left(y_{2}\right)>\cdots>\overline{f}\left(y_{n}\right)$

and

$\overline{f}\left(z_{1}\right)>\overline{f}\left(z_{2}\right)>\cdots>\overline{f}\left(z_{n}\right)\text{.}$

Let $f$ be a super edge-magic labeling of $K_{1,n}\cup lK_{1}$. By Lemma 1.1,
we know that

$\displaystyle\text{val}\left(f\right)$ $\displaystyle=$ $\displaystyle
f\left(x\right)+f\left(y_{1}\right)+2n+l+1$ $\displaystyle=$ $\displaystyle
f\left(x\right)+f\left(y_{n}\right)+n+2\text{.}$

Thus, both sums $f\left(x\right)+f\left(y_{1}\right)$ and
$f\left(x\right)+f\left(y_{n}\right)$ perfectly determine the valence of the
labeling $f$.

From this, the following fact is clear.

######  Fact 2.

Let $f_{1}$ and $f_{2}$ be two super edge-magic labelings of $G$. Then

$\mathrm{val}\left(f_{1}\right)+1=\mathrm{val}\left(f_{2}\right)$

if and only if

$f_{1}\left(x\right)+f_{1}\left(y_{1}\right)+1=f_{2}\left(x\right)+f_{2}\left(y_{1}\right)$

if and only if

$f_{1}\left(x\right)+f_{1}\left(y_{n}\right)+1=f_{2}\left(x\right)+f_{2}\left(y_{n}\right)\text{.}$

Let $f$ be any super edge-magic labeling of $G$. Then
$\gamma\left(G\right)=f\left(x\right)+f\left(y_{1}\right)$ and
$\Gamma\left(G\right)=f\left(x\right)+f\left(y_{n}\right)$.

The fact that the set $\\{f\left(y_{i}\right):i\in\left[1,n\right]\\}$ is a
set of $n$ consecutive integers for any super edge-magic labeling of $G$
suggests the following definitions. Consider a super edge-magic labeling $f$
of $G$ and define the set
$S_{2}^{f}=\\{f\left(y_{i}\right):i\in\left[1,n\right]\\}$. Then

$S_{1}^{f}=\left[1,f\left(y_{1}\right)\right]\text{ and
}S_{3}^{f}=\left[1,n+l+1\right]\backslash\left(S_{1}^{f}\cup
S_{1}^{f}\right)\text{.}$

A super edge-magic labeling $f$ of $G$ is of type 1 and we write it as $f\in
T_{1}$ if $f\left(x\right)\in S_{1}^{f}$, and it is of type 2 and we write it
as $f\in T_{2}$ if $f\left(x\right)\in S_{3}^{f}$. From Fact 1, it is easy to
deduce the following fact.

######  Fact 3.

The set $T_{1}\cup T_{2}$ is a partition of the set

$F\left(G\right)=\left\\{\right.f\mathrm{\ :\ }f\text{ is a super edge-magic
labeling of }G\left.\right\\}\text{.}$

We are now ready to state and prove the following theorem.

######  Theorem 3.2.

There exists a bijective function between $T_{1}$ and $T_{2}$.

###### Proof.

Consider the function $\phi:T_{1}\rightarrow T_{2}$ defined by
$\phi\left(f\right)=\overline{f}$ for all $f\in T_{1}$. First, we show that if
$f\in T_{1}$, then $\overline{f}\in T_{2}$. If $f\in T_{1}$, then

$f\left(x\right)<f\left(y_{1}\right)<f\left(y_{2}\right)<\cdots<f\left(y_{n}\right)\text{,}$

implying that

$\begin{split}\left(n+l+2\right)-f\left(x\right)&>\left(n+l+2\right)-f\left(y_{1}\right)\\\
&>\left(n+l+2\right)-f\left(y_{2}\right)>\cdots>\left(n+l+2\right)-f\left(y_{n}\right)\text{.}\end{split}$

Thus,

$\overline{f}\left(x\right)>\overline{f}\left(y_{1}\right)>\overline{f}\left(y_{2}\right)>\cdots>\overline{f}\left(y_{n}\right)$

so that $\overline{f}\in T_{2}$.

Next, assume that $\left|\\{f_{a},f_{b}\\}\cap T_{1}\right|=2$, and we will
show that $\phi\left(f_{a}\right)\neq\phi\left(f_{b}\right)$. Assume that
$f_{a}\neq f_{b}$. Then we have two possibilities.

Case 1. If $f_{a}\neq f_{b}$, then
$\left(n+l+2\right)-\phi\left(f_{a}\right)\neq\left(n+l+2\right)-\phi\left(f_{b}\right)$.
Thus, $\overline{f_{a}}\neq\overline{f_{b}}$ so that
$\phi\left(f_{a}\right)\neq\phi\left(f_{b}\right)$.

Case 2. If
$\\{f_{a}\left(y_{i}\right):i\in\left[1,n\right]\\}\neq\\{f_{b}\left(y_{i}\right):i\in\left[1,n\right]\\}$,
then, without loss of generality, assume that

$f_{a}\left(y_{1}\right)<f_{b}\left(y_{1}\right)\text{ and
}f_{a}\left(y_{n}\right)<f_{b}\left(y_{n}\right)\text{.}$

Then

$\left(n+l+2\right)-f_{a}\left(y_{1}\right)>\left(n+l+2\right)-f_{b}\left(y_{1}\right)$

and

$\left(n+l+2\right)-f_{a}\left(y_{n}\right)>\left(n+l+2\right)-f_{b}\left(y_{n}\right)\text{.}$

This implies that
$\overline{f_{a}}\left(y_{1}\right)>\overline{f_{b}}\left(y_{1}\right)$, which
clearly implies that
$\overline{f_{a}}\left(y_{n}\right)>\overline{f_{b}}\left(y_{n}\right)$. Since

$\max\\{\overline{f_{a}}\left(y_{i}\right):i\in\left[1,n\right]\\}>\max\\{\overline{f_{b}}\left(y_{i}\right):i\in\left[1,n\right]\\}$

and

$\min\\{\overline{f_{a}}\left(y_{i}\right):i\in\left[1,n\right]\\}>\min\\{\overline{f_{b}}\left(y_{i}\right):i\in\left[1,n\right]\\}\text{,}$

it follows that $\phi\left(f_{a}\right)\neq\phi\left(f_{b}\right)$. Therefore,
$\phi$ is injective. It now remains to see that $\phi$ is surjective. Let
$\overline{f}\in T_{2}$ and, without loss of generality, assume that
$\overline{f}$ has the property that

$\overline{f}\left(x\right)>\overline{f}\left(y_{1}\right)>\cdots>\overline{f}\left(y_{n}\right)\text{,}$

that is,

$\left(n+l+2\right)-\overline{f}\left(x\right)<\left(n+l+2\right)-\overline{f}\left(y_{1}\right)<\cdots<\left(n+l+2\right)-\overline{f}\left(y_{n}\right)\text{.}$

This implies that

$\overline{\overline{f}}\left(x\right)<\overline{\overline{f}}\left(y_{1}\right)<\cdots<\overline{\overline{f}}\left(y_{n}\right)\text{.}$

Hence, $\overline{\overline{f}}\in T_{1}$. Clearly,
$\phi\left(\overline{\overline{f}}\right)=\overline{f}$, and $\phi$ is
surjective. Therefore, $\phi$ is bijective. ∎

######  Proposition 1.

Let $f_{1}$ and $f_{2}$ be two super edge-magic labelings of $K_{1,n}\cup
lK_{1}$ such that the valences of $f_{1}$ and $f_{2}$ are consecutive. Then
the valences of $\overline{f_{1}}$ and $\overline{f_{2}}$ are consecutive.

###### Proof.

Assume that $\text{val}\left(f_{1}\right)$ and $\text{val}\left(f_{2}\right)$
are consecutive, and let
$\text{val}\left(f_{1}\right)+1=\text{val}\left(f_{2}\right)$. Then we have
$f_{1}\left(a\right)+f_{1}\left(b\right)+f_{1}\left(ab\right)+1=f_{2}\left(a\right)+f_{2}\left(b\right)+f_{2}\left(ab\right)$,
where $ab\in E\left(K_{1,n}\cup lK_{1}\right)$. If we let $\omega=n+l+2$ and
$\rho=3n+2l+3$, then we have

$-2\omega-\rho+f_{1}\left(a\right)+f_{1}\left(b\right)+f_{1}\left(ab\right)+1=-2\omega-\rho+f_{2}\left(a\right)+f_{2}\left(b\right)+f_{2}\left(ab\right)\text{,}$

implying that

$\displaystyle\left(\omega-f_{1}\left(a\right)\right)+\left(\omega-
f_{1}\left(b\right)\right)+\left(\rho-f_{1}\left(ab\right)\right)-1$
$\displaystyle=$ $\displaystyle\left(\omega-
f_{2}\left(a\right)\right)+\left(\omega-f_{2}\left(b\right)\right)+\left(\rho-
f_{2}\left(ab\right)\right)\text{.}$

Hence,
$\overline{f_{1}}\left(a\right)+\overline{f_{1}}\left(b\right)+\overline{f_{1}}\left(ab\right)-1=\overline{f_{2}}\left(a\right)+\overline{f_{2}}\left(b\right)+\overline{f_{2}}\left(ab\right)$.
Thus,
$\text{val}\left(\overline{f_{1}}\right)-1=\text{val}\left(\overline{f_{2}}\right)$.
Consequently, the valences of $\overline{f_{1}}$ and $\overline{f_{2}}$ are
consecutive. ∎

Next, consider the graph $K_{1,n}\cup lK_{1}$ together with its associated set
$T_{1}$. Define the set $S\left(T_{1}\right)$ as
$S\left(T_{1}\right)=\left\\{\right.x\in\mathbb{N}:x=\text{val}\left(f\right)\text{
and }f\in T_{1}\left.\right\\}$. Also, consider the set $T_{2}$ associated to
$K_{1,n}\cup lK_{1}$ and, similarly, define the set $S\left(T_{2}\right)$ as
$S\left(T_{2}\right)=\left\\{\right.x\in\mathbb{N}:x=\text{val}\left(f\right)\text{
and }f\in T_{2}\left.\right\\}$. With these definitions in hand, we have the
following result.

######  Theorem 3.3.

The set $S\left(T_{1}\right)$ consists of consecutive integers.

###### Proof.

Let $f\in T_{1}$, and consider $\left(l+1\right)$ cases, depending on the
possibilities for $S_{1}^{f}$.

Case 1. Let $S_{1}^{f}=\\{1\\}$. In this case, $\min\left(S_{2}^{f}\right)=2$
and hence $3$ is the low characteristic of $f$.

Case 2. Let $S_{1}^{f}=\\{1,2\\}$. In this case,
$\min\left(S_{2}^{f}\right)=3$ and hence the low characteristic of $f$ is $4$
or $5$.

Case 3. Let $S_{1}^{f}=\\{1,2,3\\}$. In this case,
$\min\left(S_{2}^{f}\right)=4$ and hence the low characteristic of $f$ is $5$,
$6$ or $7$.

Case 4. Let $S_{1}^{f}=\\{1,2,3,4\\}$. In this case,
$\min\left(S_{2}^{f}\right)=5$ and hence the low characteristic of $f$ is $6$,
$7$, $8$ or $9$.

$\vdots$

Case $\left(l+1\right)$. Let $S_{1}^{f}=\\{1,2,\dots,l+1\\}$. In this case,
$\min\left(S_{2}^{f}\right)=l+2$ and hence the low characteristic of $f$ is
$l+3$, $l+4$, …, or $2l+3$.

This means that the labelings of $T_{1}$ have low characteristics $3$, $4$,…,
$2l+3$. Therefore, we conclude by Fact 2 that the set $S\left(T_{1}\right)$ is
a set of consecutive integers. ∎

The following result is an immediate consequence of the preceding theorem and
proposition.

######  Corollary 3.1.

The set $S\left(T_{2}\right)$ consists of consecutive integers.

Next, we will concentrate on the elements of $S\left(T_{2}\right)$. We know
that $S\left(T_{2}\right)$ contains the valences of the complementary
labelings of the super edge-magic labelings of $T_{1}$. We have seen above
that the low characteristics are $3,4,\dots,2l+3$. Thus, the high
characteristics of the elements of $T_{2}$ are
$\left(2n+2l+4\right)-3,\left(2n+2l+4\right)-4,\dots,\left(2n+2l+4\right)-\left(2l+3\right)$.
From these, we deduce that the minimum among all the low characteristics of
these labelings is

$\left(2n+2l+4\right)-\left(2l+3\right)=n+2\text{.}$

Therefore, the only requirement needed for $K_{1,n}\cup lK_{1}$ to be perfect
super edge-magic is $2l+3\geq n+2$.

######  Theorem 3.4.

For every positive integer $n$,

$\mu_{p}\left(K_{1,n}\right)<+\infty\text{.}$

###### Proof.

Let $G=K_{1,n}\cup lK_{1}$, and assume that $G$ is perfect super edge-magic.
Then it is trivial to observe that $K_{1,n}\cup l^{\prime}K_{1}$ is perfect
super edge-magic for any $l^{\prime}$ with $l^{\prime}\geq l$. Since $G$ is
perfect super edge-magic, it follows that the minimum valence of a super edge-
magic labeling (and also the smallest possible valence for an edge-magic
labeling of $G$) is computed as follows. First, observe that
$\left|V\left(G\right)\right|=n+l+1$ and $\left|E\left(G\right)\right|=n$.
Next, observe that the super edge-magic labeling with smallest valence has the
following properties.

  1. (1)

The vertex of $G$ of degree $n$ is labeled $1$.

  2. (2)

The labels of the vertices other than isolated vertices and edges are all the
numbers in the set $\left[2,2n\left(2n+1\right)\right]$.

With this knowledge in hand, we can compute the minimum possible valence
$\text{val}_{\min}\left(G\right)$ of $G$ as follows:

$\text{val}_{\min}\left(G\right)=\frac{n+\sum_{i=2}^{2n+1}i}{n}=2n+4\text{.}$

Thus, the minimum possible valence of any edge-magic labeling of $G$ is
$2n+4$. On the other hand, the maximum valence
$\text{val}_{\max}\left(G\right)$ of $G$ is given by

$\text{val}_{\max}\left(G\right)=\frac{\left(n-1\right)\left(n+l+1\right)+\sum_{i=l+1}^{2n+l+1}i}{n}=3n+3l+3\text{.}$

Hence, the maximum possible labeling of $G$ is $3n+3l+3$. Since $G$ is perfect
super edge-magic by assumption, it follows that for every
$\alpha\in\left[2n+4,3n+3l+3\right]$, there exists a super edge-magic labeling
of $G$ that has valence $\alpha$. At this point, define the graph $G$ with

$V\left(G\right)=\\{u_{i}:i\in\left[1,l\right]\\}\cup\\{v_{i}:i\in\left[n+l+1,2n+l+1\right]$

and $E\left(G\right)=\\{v_{2n+l+1}v_{i}:i\in\left[n+l+1,2n+l\right]\\}$, and
consider the following $l$ edge-magic labelings $f_{0},f_{1},\dots,f_{l-1}$.
For each $k\in\left[0,l-1\right]$, let $f_{k}\left(v_{i}\right)=i$, where
$i\in\left[1,2n+l+1\right]$. Also, let
$f_{0}\left(v_{2n+l+1}v_{n+l+i}\right)=n+l+1-i$ for each
$i\in\left[1,n\right]$, and the labels not used go on the set of vertices
$\\{u_{i}:i\in\left[1,l\right]\\}$. Now, the labels on the edges assigned by
each edge-magic labeling $f_{k}$ ($k\in\left[1,l\right]$) are defined as
$f_{k}\left(ab\right)=f_{0}\left(ab\right)-k$ for $ab\in E\left(G\right)$.
Once again, the labels assigned by $f_{k}$ to the vertices in the set
$\\{u_{i}:i\in\left[1,l\right]\\}$ are the labels not used for the rest of
vertices and edges. These edge-magic labelings $f_{0},f_{1},\dots,f_{l-1}$
produce the valences $4n+3l+2,4n+3l+1,\dots,4n+2l+2$ (see the following
example for labelings $f_{0},f_{1},f_{2}$ depicted in Figure 6).

Figure 6. Example for labelings $f_{0},f_{1},f_{2}$ with minimum induced edge
sums

Finally, recall that all valences from $2n+4$ to $3n+3l+3$ are attained by
super edge-magic labelings. Also, all valences from $4n+2l+2$ to $4n+3l+2$ are
attained by edge-magic labelings. Therefore, if we take $l$ large enough so
that $3n+3l+3\geq 4n+2l+2$. We conclude that $G$ is perfect edge-magic and
hence $\mu_{p}\left(K_{1,n}\right)<+\infty$. ∎

##  4\. Conclusions and new research trends

The main goal of this paper is to study the valences of the edge-magic and
super edge-magic labelings of graphs. This study started with the paper by
Godbold and Slater [12] in which they conjectured that the cycles other than
$C_{5}$ are perfect edge-magic. This conjecture remains open, but in [20], and
independently in [19] some substantial progress was made. For further
information on this problem, the interested reader may consult also [15] and
[21]. In this paper, we have introduced the concepts of perfect edge-magic
deficiency and perfect super edge-magic deficiency of graphs, and we have
studied these concepts in relation to the star $K_{1,n}$. In addition, we have
presented results on the cardinality of the super edge-magic set of graphs
with certain order, size and girth.

For future work, it is interesting to notice the following. Consider the cycle
$C_{3}$. It is clear that the super edge-magic interval for $C_{3}$ is
$\left[9,9\right]$.

Figure 7. Four non-isomorphic bijections of the form $f:V\left(C_{3}\cup
K_{1}\right)\rightarrow\left[1,4\right]$

Since $C_{3}$ is super edge-magic, it follows that $C_{3}$ is also perfect
super edge-magic. Thus, $\mu_{p}^{s}\left(G\right)=0$.

At this point, consider the graph $C_{3}\cup K_{1}$. Since $C_{3}=K_{3}$, it
follows that there exist four non-isomorphic bijections of the form
$f:V\left(C_{3}\cup K_{1}\right)\rightarrow\left[1,4\right]$ (see Figure 7).
From these four bijections, it is clear that only bijections $A$ and $B$ can
be extended to a super edge-magic labeling. In case of $A$, the labeling has
valence $10$ and in case of $B$ the labeling has valence $12$. Thus, there is
not any super edge-magic labeling of $C_{3}\cup K_{1}$ with valence $11$,
implying that $C_{3}\cup K_{1}$ is not perfect super edge-magic.

From this, we can see that, on the contrary of when we deal with super edge-
magic deficiency, that a graph $G$ has perfect super edge-magic deficiency $t$
so that $G\cup tK_{1}$ is perfect super edge-magic and $C_{3}\cup
t^{\prime}K_{1}$ is not perfect super edge-magic if $t^{\prime}<t$, it is not
necessarily true that $G\cup t^{\prime\prime}K_{1}$ is also perfect super
edge-magic for $t^{\prime\prime}>t$. This suggests the definition of strong
perfect super edge-magic deficiency. The _strong perfect super edge-magic
deficiency_ of a graph $G$ is the minimum nonnegative integer $t$ such that
$G\cup t^{\prime\prime}K_{1}$ is perfect super edge-magic for all
$t^{\prime\prime}\geq t$. If such $t$ does not exist, then the strong super
edge-magic deficiency of $G$ is defined to be $+\infty$.

We suspect that something similar comes about in the case of perfect edge-
magic deficiency and that similar concepts can be introduced in this case;
however, we do not have examples at this point to support this claim. Other
problems that we feel that would be interesting are problems of the following
type.

######  Problem 1.

For which real numbers $x$ $(0<x<1)$, there exists a sequence of graphs
$(G_{1}^{x},G_{2}^{x},\dots)$ such that
$\text{lim}_{n\rightarrow+\infty}\frac{|\tau_{G_{n}^{x}}|}{|\lambda_{G_{n}^{x}}|}=x$?

######  Problem 2.

For which real numbers $x$ $(0<x<1)$, there exists a sequence of graphs
$(H_{1}^{x},H_{2}^{x},\dots)$ such that
$\text{lim}_{n\rightarrow+\infty}\frac{|\sigma_{H_{n}^{x}}|}{|I_{H_{n}^{x}}|}=x$?

In summary, we consider that the continuation of the ideas established in this
paper constitute very interesting new trends for developing further research.

## Acknowledgement

The authors acknowledge Susana Clara López Masip for her careful reading of
this work and for her continuous support during the competition of this paper.

## References

  * [1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math., 93 (1991) 123–129.
  * [2] G. Chartrand and L. Lesniak, Graphs & Digraphs 3th ed. CRC Press (1996).
  * [3] H. Enomoto, A. Lladó, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math., 34 (1998) 105–109.
  * [4] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231 (2001) 153–168.
  * [5] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, On super edge-magic graphs, Ars Combin., 64 (2002) 81–95.
  * [6] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Electron. Notes Discrete Math., 11 (2002) 299–314.
  * [7] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin., 78 (2006) 33–45.
  * [8] R.M. Figueroa-Centeno, R. Ichishima, F.A. Muntaner-Batle, and M. Rius-Font, Labeling generating matrices,  J. Combin. Math. Combin. Comput., 67 (2008) 189–216.
  * [9] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., (2022) #DS6.
  * [10] S.M. Hegde and S. Shetty, Strongly indexable graphs and applications, Discrete Math., 309 (2009) 6160–6168.
  * [11] S. Hegde and S. Shetty, Strongly $k$-indexable and super edge magic labelings are equivalent, unpublished.
  * [12] R. Godbold and P.J. Slater, All cycles are edge-magic, Bull. Inst. Combin. Appl., 22 (1998) 93–97.
  * [13] R. Ichishima, F.A. Muntaner-Batle, and M. Rius-Font, Bounds on the size of super edge-magic graphs depending on the girth, Ars Combin., 119 (2015) 129–133.
  * [14] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970) 451–461.
  * [15] S.C. López and F.A. Muntaner-Batle, Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, SpringerBriefs in Mathematics, Springer, Cham, 2017.
  * [16] S.C. López, F.A. Muntaner-Batle, and M. Rius-Font, Perfect super edge-magic graphs, Bull. Math. Soc. Sci. Math. Roumanie, 55 (103)(2) (2012) 199–208.
  * [17] S.C. López, F.A. Muntaner-Batle, and M. Rius-Font, New problems related to the valences of (super) edge-magic labelings, AKCE Int. J. Graphs Combin., 10(2) (2013) 169–181.
  * [18] S.C. López, F.A. Muntaner-Batle, and M. Rius-Font, Perfect edge-magic graphs, Bull. Math. Soc. Sci. Math. Roumanie, 57 (105)(1) (2014) 81–91.
  * [19] S.C. López, F.A. Muntaner-Batle, and M. Rius-Font, A problem on edge-magic labelings of cycles, Can. Math. Bull., 57 (2014) 375–380.
  * [20] D. McQuillan, Edge-magic and vertex-magic total labelings of certain cycles, Ars Combin., 90 (2009) 257–266.
  * [21] P. Mohan, Product of digraphs, (super) edge-magic valences and related topics, Ph.D. Thesis, Universitat Politècnica de Catalunya, 2019.
  * [22] G. Ringel and A. Lladó, Another tree conjecture, Bull. Inst. Combin. Appl., 18 (1996) 83–85.
  * [23] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y and Dunod Paris (1967) 349–355.
  * [24] W.D. Wallis, Magic Graphs, Birkh$\ddot{a}$user, Boston (2001).


Simon Alford, Anshula Gandhi, Akshay Rangamani, Andrzej Banburski, Tony Wang,
Sylee Dandekar, John Chin, Tomaso Poggio, and Peter Chin 11institutetext:
Massachusetts Institute of Technology, Cambridge MA 02139, USA,
22institutetext: Raytheon BBN Technologies, Cambridge MA 02138
33institutetext: Boston University, Boston MA 02215

# Neural-guided, Bidirectional Program Search for Abstraction and Reasoning

Simon Alford 11 Anshula Gandhi 11 Akshay Rangamani 11 Andrzej Banburski 11
Tony Wang 11 Sylee Dandekar 22 John Chin 11 Tomaso Poggio 11 Peter Chin 33

###### Abstract

One of the challenges facing artificial intelligence research today is
designing systems capable of utilizing systematic reasoning to generalize to
new tasks. The Abstraction and Reasoning Corpus (ARC) measures such a
capability through a set of visual reasoning tasks. In this paper we report
incremental progress on ARC and lay the foundations for two approaches to
abstraction and reasoning not based in brute-force search. We first apply an
existing program synthesis system called DreamCoder to create symbolic
abstractions out of tasks solved so far, and show how it enables solving of
progressively more challenging ARC tasks. Second, we design a reasoning
algorithm motivated by the way humans approach ARC. Our algorithm constructs a
search graph and reasons over this graph structure to discover task solutions.
More specifically, we extend existing execution-guided program synthesis
approaches with deductive reasoning based on function inverse semantics to
enable a neural-guided bidirectional search algorithm. We demonstrate the
effectiveness of the algorithm on three domains: ARC, 24-Game tasks, and a
‘double-and-add’ arithmetic puzzle.

###### keywords:

abstraction, reasoning, program synthesis, neural networks

##  1 Introduction

00footnotetext: Published as a conference paper at Complex Networks 2021

The growth and tremendous success of deep learning has catapulted us past many
benchmarks of artificial intelligence. Reaching human and superhuman
performance in object recognition, language generation and translation, and
complex games such as Go and Starcraft has pushed the boundaries of what
humans can do and machines cannot [13, 12, 7, 16, 19, 22]. To continue to make
progress, we must identify and work towards reducing the gaps between human
and machine intelligence.

The Abstraction and Reasoning Corpus (ARC), introduced by François Chollet in
2019, captures an important aspect of human intelligence that our current
systems are unable to do: the ability to systematically and flexibly
generalize to new domains [6]. Chollet argues that intelligence must be
measured not as skill in a particular task, but as skill-acquisition
efficiency. General intelligent systems must also have developer-aware
generalization, i.e. be able to solve problems the developer of the system has
not encountered before or anticipated.

ARC consists of training, evaluation, and private test sets of 400, 400, and
200 tasks. Each task consists of 2–4 training examples and one or more test
examples. Each training example is an input/output pair of grids. To solve a
task, an agent must determine the relationship between input and output grids
in the training examples, and use this to produce the correct output grid for
each of the test examples, for which the agent is only given the input grid.
Each task is thus a few-shot learning problem, for which the solution is
symbolic and rule-based.

Figure 1: An example ARC task with three training examples and one test
example. The solution might be described as “find the most common object in
the input grid”.

The tasks are unique and constructed by hand so as to prevent the reverse
engineering of any synthetic generation process. They are designed to depend
on a set of human Core Knowledge inbuilt priors such as objectness, simple
arithmetic abilities, symmetry, and goal-directedness. The evaluation and
private test sets are designed such that a solution tailored to the training
set is unlikely to transfer to the evaluation or test sets. Chollet hosted a
Kaggle-competition for ARC and the winning solution, a hard-coded brute force
approach, achieved only $\sim 20\%$ performance on the private test set [2].

In this paper we report incremental progress on ARC and lay the foundation for
several approaches to abstraction and reasoning not based in brute-force
search. We approach ARC as a program synthesis benchmark, solving tasks by
writing programs that convert input grids to output grids. In Section 2 we
outline an approach to abstraction by applying DreamCoder [11]. We show this
approach enables learning new concepts that aid in generalization as well as
the solving of progressively more challenging tasks. In Section 3 we describe
a novel program synthesis approach motivated by the way humans approach ARC
that captures the reasoning required to search for ARC task solutions. Our
algorithm constructs a search graph and reasons over this graph structure to
discover task solutions. More specifically, we extend existing execution-
guided program synthesis approaches [10, 25] with deductive reasoning based on
function inverse semantics [18] to enable a neural-guided bidirectional search
algorithm. We evaluate our approach on three domains: ARC tasks, ‘24 Game’
problems, and a simple ‘double-and-add’ challenge. These experiments show the
benefits of bidirectional search over baselines and the potential for further
progress on ARC. In Section 4 we discuss related work, progress on ARC, and
future directions.

##  2 Abstraction using DreamCoder

We frame the problem as a search problem over the space of programs
expressible in some domain specific language (DSL). One way a learning agent
can achieve developer aware generalization (in the sense of [6]) is to
identify frequently occurring patterns of computation and form abstractions
from them. These abstractions enable searching for more complex programs more
quickly.

In this section we use DreamCoder [11], a recent tool for program synthesis,
to form abstractions. We first show how DreamCoder’s compression algorithm
enables learning generalizations of concepts seen in training. Second, we run
DreamCoder on ARC to show how forming new abstractions enables the agent to
solve progressively more challenging tasks.

###  2.1 Warmup: Forming Abstractions

To show how DreamCoder can form more abstract concepts from existing ones, we
supply our agent with six synthetic tasks (meant to be similar to ARC tasks):
drawing a line in three different directions, and moving an object in three
different directions. See Figure 2 for a visualization of these tasks.

We solve these tasks with four primitives: rotate clockwise and
counterclockwise, draw a line down, and move an object down. The programs
synthesized are the following:

(lambda (rotate_cw (draw_line_down (rotate_ccw $0))))  // draw line left
(lambda (rotate_cw (move_down (rotate_ccw $0))))  // move object left (lambda
(rotate_ccw (draw_line_down (rotate_cw $0))))  // draw line right (lambda
(rotate_ccw (move_down (rotate_cw $0))))  // move object right (lambda
(rotate_cw (rotate_cw (draw_line_down (rotate_cw (rotate_cw $0))))))  // draw
line up (lambda (rotate_cw (rotate_cw (move_down (rotate_cw (rotate_cw
$0))))))  // move object up

After running the compression algorithm, the agent creates the following new
abstractions:

(lambda (lambda (rotate_cw ($0 (rotate_ccw $1)))))  // apply action left
(lambda (lambda (rotate_ccw ($0 (rotate_cw $1)))))  // apply action right
(lambda (lambda (rotate_cw (rotate_cw ($0 (rotate_cw (rotate_cw $1)))))))  //
apply action up

Importantly, the abstractions formed are more general than the original
primitives given. This can help enable systematic generalization on further
tasks.

(a) An example “draw line left” task

(b) An example “move object left” task

Figure 2: Sample tasks involving applying an action left.

###  2.2 Enabling Generalization on ARC Symmetry Tasks

In a second experiment, we demonstrate how compression-based learning enables
developer-aware generalization on ARC. We provide DreamCoder with a set of
five grid-manipulation operations: flipping vertically with `vertical_flip`,
rotating clockwise with `rotate_cw`, overlaying two grids with `overlay`,
stacking two grids vertically with `vertical_stack`, and getting the left half
of a grid with `left_half`. We then train our agent on a subset of 36 ARC
tasks involving symmetry over five iterations of enumeration and compression.
During each iteration, our agent attempts to solve all 36 tasks by enumerating
possible programs for each task. It then runs compression to create new
abstractions. During the next iteration, the agent repeats its search equipped
with the new abstractions. In this experiment, our agent initially solves 16
tasks. After one iteration, it solves 17 in the same amount of time. After
another, it solves 19 tasks, and after the final iteration, it solves 22
tasks. Table 1 shows some of the new abstractions learned by DreamCoder’s
compression algorithm such as flipping horizontally, and stacking grids
horizontally. The program solutions for the final tasks solved, shown in
Figure 3, could not be feasibly discovered without the use of abstractions to
reduce the search time.

Action | Code
---|---
mirror across diagonal | `#(lambda (rotate_cw (vertical_flip $0)))`
rotate 180 degrees | `#(lambda (rotate_cw (rotate_cw $0)))`
flip horizontally | `#(lambda (rotate_cw (rotate_cw (vflip $0))))`
rotate counterclockwise | `#(lambda (rotate_cw (#(lambda (rotate_cw (rotate_cw $0))) $0)))`
stack grids horizontally | `#(lambda (lambda (#(lambda (rotate_cw (vertical_flip $0))) (stack_vertically`
| `(#(lambda (rotate_cw (#(lambda (vertical_flip $0)) $0))) $1)`
| `(#(lambda (rotate_cw (vertical_flip $0))) $0)))))`
Table 1: Useful actions learned in the process of solving symmetry tasks.
Pound signs represent abstractions. Abstractions may rely on others for
construction; e.g. to stack grids horizontally, we reflect each input
diagonally, stack vertically, and reflect the vertical stack diagonally.
Figure 3: One of the four-way mirroring tasks and the program discovered that
solves it written in terms of the original primitives. The program was
discovered only after four iterations of enumeration and compression.

###  2.3 Discussion

It is useful to compare the learning done in our approach to that done by
neural networks. Neural networks can also learn new concepts from training
examples, but their internal representation lacks structure which allows them
to apply learned concepts compositionally to other tasks. In contrast,
functions learned via compression, represented as programs, can naturally be
composed and extended to solve harder tasks, while reusing concepts between
tasks. This constitutes a learning paradigm which we view as essential to
human-like reasoning.

There is a caveat of the approach shown here. Abstraction as shown uses a
simple enumerative search. DreamCoder uses a form of neural-guided program
synthesis, predicting a distribution over functions to search over, but this
guidance is too weak to scale to the complexity of ARC tasks. In the next
section, we show the type of reasoning required for ARC and design an approach
to exhibit this reasoning.

##  3 Bidirectional, Neural-guided Program Search

In Subsection 3.1 we first motivate and describe our bidirectional, neural-
guided search algorithm. Then in Subsection 3.2 we present experiments and
results using this approach.

###  3.1 Algorithm Description

In this section we describe our reasoning approach for ARC. We first give a
motivating example of human reasoning on ARC, explain how to approximate it
with execution-guided synthesis, then incorporate inverse semantics to create
a bidirectional, neural-guided search algorithm.

#### Motivating Example

Solving ARC tasks fundamentally consists of a search for valid solutions. To
make this search tractable, our agent needs the ability to reason towards
solutions. ARC tasks feature rich visual queues that guide us towards
solutions. Without enabling our agent to take full advantage of these queues,
the search over possible programs becomes impossibly large. The process of
discovering the solution to an ARC task often consists of several discrete
steps of reasoning before discovering the solution. How can we design an
approach to search that searches for ARC solutions in the same manner as
humans?

As a motivating example, let us consider solving task 303 in Figure 4. The
reasoning steps to come to a solution might look something like this:

Figure 4: Task 303.

  1. 1.

Notice that the output grid consists of copies of the 3x3 input grid, arranged
in a certain arrangement among a 9x9 grid.

  2. 2.

New question: Where should we place the input grid copies?

  3. 3.

Notice that the placements match the arrangement of a different color’s pixels
for each grid. For example, in the first example, the diagonal of grids in the
output matches the green pixels in the input.

  4. 4.

New question: What color should we arrange our grid copies along?

  5. 5.

Solution: The color matched is the most common color in the grid.

Notice the way discovering a solution involves combining sequential insights
and problem reductions. Systematizing a form of reasoning for ARC that
emulates this reasoning will be based on a combination of execution-guided
program synthesis and inverse semantics.

#### Extending Execution-guided Synthesis

Execution-guided program synthesis [10, 5] is a form of program synthesis
where one executes partial programs to produce intermediate outputs, which are
used to guide the construction of the full program. Intermediate evaluations
provide the opportunity for step-by-step reasoning: instead of coming to the
answer at once, one can construct it piece by piece. Humans could be said to
make use of the same thing: for instance, it much easier to write out the
result of a multiplication digit by digit, instead of conducting the full
calculation in one’s head. The form of execution-guided synthesis we apply to
ARC is most similar to the ‘REPL’ approach of [10]. An example applying the
technique to ARC is shown in Figure 5.

Figure 5: Solving ARC task 138 from the evaluation set with execution-guided
synthesis. Conditioned on the input and output grids, the agent chooses to
flip the input horizontally in step one. This action is executed to produce
intermediate value i1. Next, the agent chooses to horizontally stack the
intermediate value with the input grid, producing another value i2. Last, the
agent horizontally stacks this value i2 with itself, correctly producing the
output grid for each example and solving the task.

Existing execution-based synthesis approaches are limited to bottom-up
enumeration: the leaves of the program are constructed (and evaluated) first.
In contrast, the steps for solving task 303 involve proposing a function that
is used to produce the output grid, and deducing the inputs required to
correctly produce the output as new intermediate targets before discovering
the complete program.

This form of deductive reasoning involves evaluating function in reverse. It
is best exemplified in the FlashMeta system [18], which leverages the inverse
semantics of operators to deduce one or more inputs of a function given the
output target and one or more inputs. We incorporate this type of reasoning
into an extension of execution-guided program synthesis.

#### Deductive reasoning via inverse semantics

For our purposes, we can consider two cases. The simplest case is when the
function is invertible. In this case, we can evaluate the inverse to produce
two new targets for the search, as shown in Figure 6. In the second case, the
function is conditionally invertible: given the output and one or more inputs
to a function, one can deduce the remaining inputs needed to produce the
output via this function. Many functions are conditionally invertible; perhaps
the most familiar family is arithmetic operators: if we know $1+x=5$, we can
deduce that $x=4$. An example relevant to ARC is shown in Figure 6. Using
conditional inverses, it is possible to formalize the reasoning described for
task 303.

Figure 6: Left: the function block is directly invertible: given the output,
we can deduce the inputs. Right: the function horizontal$\\_$stack (horizontal
stack) is conditionally invertible: given the output and one input, we can
deduce the other input.

#### Bidirectional, Neural-guided Program Search

To extend execution-guided synthesis to a bidirectional algorithm with inverse
and conditional inverse functions, we extend the environment of [10],
approaching the synthesis task via reinforcement learning.

The setup takes place in a Markov Decision Process. The current state is a
graph of nodes. Each node represents either an input value, the output value,
or an intermediate value resulting from the execution of an operation in the
forwards or backwards direction. A node is grounded if there is a valid
program to create that node from the operations applied so far. In general,
grounded nodes correspond to those from the forwards, i.e. bottom-up program
enumeration, direction of search, while ungrounded nodes correspond to those
from the backwards direction, i.e. top-down program enumeration.

An operation is a function from the grammar along with a designation of being
applied in forwards, inverse, or as a conditional inverse (and if as a
conditional inverse, conditioned on which input arguments). There are three
types of operations: forward operations, inverse operations, and conditional
inverse operations. A forward operation applies the function to a set of
grounded inputs to produce a new grounded node. An invertible operation takes
an ungrounded output and produces a new ungrounded target node such that
grounding the target node will cause the output node to be grounded as well. A
conditionally invertible operation takes an ungrounded output and one or more
grounded input nodes, and produces a new ungrounded target node such that
grounding the target node will cause the output node to be grounded as well.
All invertible and conditionally invertible operations have a corresponding
forward operation.

Solving a given task thus consists of an episode in the MDP. Actions in the
MDP correspond to a choice of operation and the choice of arguments for that
operation. Each action applies a function in either the forward or backward
direction. Intuitively, this executes a bidirectional search to try to connect
the grounded nodes on one side with the ungrounded output node on the other.
We give reward $R$ for solving the task and a penalty of $-1$ for choosing an
action corresponding to an invalid operation.

Like [10, 25, 5], we train with a combination of supervised training on
randomly generated programs fine-tuning with reinforcement learning algorithm
Reinforce. To generate random bidirectional programs for supervised training,
we first create a random program, and construct an execution trace for it by
probabilistically converting inverting function applications from the root.
Network architecture is held the same from [10], with task-dependent embedding
network nodes of the bidirectional graph, a DeepSet network [24] to encode the
graph into a single embedding and choose a function to apply, and a pointer
network [23] for choosing function arguments.

###  3.2 Experiments

We evaluate our bidirectional algorithm in three settings: solving ARC
symmetry tasks, solving arithmetic puzzles from the ‘24 Game’ family, and
solving ‘double-and-add’ puzzles. As a baseline, we compare bidirectional
synthesis with a forward-only baseline which only allows application of
operations in the forwards direction like existing approaches.

#### ARC symmetry tasks

As a proof of concept, we evaluate the bidirectional algorithm on a set of 18
ARC symmetry tasks—a subset of those used in Section 2. We use a DSL of six
operations: stacking two grids horizontally or vertically, rotating clockwise
or counterclockwise, and flipping a grid horizontally or vertically. The
rotation and flip functions are directly invertible, while the stacking
operations are conditionally invertible. We use a convolutional neural network
to embed grid example sets. We train on a set of randomly generated programs
evaluated on random input grids from the ARC training set, and fine-tune with
Reinforce before sampling rollouts for thirty minutes on all tasks at once.
The agent is able to solve 14 of 18 tasks, including one of the “four-way
mirror” tasks. In this experiment, bidirectional performed equally to the
forward-only baseline.

#### 24 Game

Next, we compare the performance of bidirectional search with the forward-only
baseline by tasking our agent with solving “24 Game” problems. A 24 Game
consists of four input numbers, one through nine. To solve the task, one must
use each number once in an expression that creates twenty four using
$+,-,\times,\div$. For example, given 8, 1, 3, and 2, a solution is
$24=(2-1)\times 3\times 8$. To solve these tasks bidirectionally, we can use
the conditional inverse of each arithmetic operator in addition to forward
arithmetic operations.111We relax the rule that each input is used exactly
once.

First we conduct supervised pretraining on all depths at once. These programs
may create any number as a target, not just 24, with the maximum allowed
integer 100, and no negative or nonintegral numbers. We then fine-tune on
different depths with Reinforce for 10,000 epochs of batch size 1000. We
measure performance by percent of episodes solved in the last 1,000 epochs of
training.

Results are shown in Table 2. Bidirectional synthesis outperforms the forward-
only baseline across all depths. This supports our thesis, but is suspicious:
as we should expect to see identical accuracy for depth one tasks, when only a
single action is needed. Accuracy remains fairly high as depth increases,
because depth does not necessarily imply program length: as many as 40% of
depth four tasks remain solvable in fewer than four actions.

Depth | 1 | 2 | 3 | 4
---|---|---|---|---
Forward-only | 87.22 $\pm 0.64$ | 84.29 $\pm 1.6$ | 75.88 $\pm 3.6$ | 67.04 $\pm 1.0$
Bidirectional | 95.2 $\pm 0.66$ | 92.9 $\pm 2.1$ | 87.7 $\pm 1.1$ | 85.3 $\pm 1.9$
Table 2: Percent of tasks solved for 24 Game, measured by percent of episodes
solved in the last 1000 epochs of RL fine-tuning. Forward-only denotes only
using forward operations. Bidirectional includes conditional-inverse
operations. Average over three runs with stdev shown.

#### Double-and-add

Last, we include results on a ‘double-and-add’ task to better show the
advantage of bidirectional search. Given a target number, one must reach it
starting from the number two by repeatedly adding one or doubling the number.
For example, $7=1+2*(1+2)$. This task, akin to the method for exponentiation
by repeated squaring, is much easier solved in a top-down fashion: the choice
of adding one or doubling boils down to whether the target is even or odd.
Here we have two forward operations, each of which are directly invertible. On
a training set of five thousand numbers sampled between one and five million,
and a held out set of five hundred numbers, our bidirectional model achieves
100% evaluation accuracy after a single epoch of supervised training. In
contrast, the forward-only model fails to solve the held-out tasks, due to the
difficulty “seeing” the solution from the source, see Figure 7.

Figure 7: Percent of tasks solved for bidirectional and forward-only agents
trained on the double-and-add task. The bidirectional agent achieves 100%
accuracy after a single epoch of training. After fifty epochs of training,
forward-only converges without solving the held-out tasks.

##  4 Discussion

#### Related work

Our work builds off and is inspired by a long line of progress in neural
program synthesis [3, 8, 4, 17, 21], execution-guided synthesis [10, 5, 26],
and deep reinforcement learning for search [19, 15].

Bidirectional, neural-guided program search is made possible primarily due to
the inverse semantics of FlashMeta [18]. The concept of bidirectional
programming, inverse semantics, and program inversion has been present
throughout the history of program synthesis [9, 20, 14], but the way in which
inverse evaluation is used here is most similar to FlashMeta.

#### ARC

To date, there are no prominent learning-based approaches to ARC that have
proven more successful than the Kaggle-winning brute-force approach [2]. Other
Kaggle approaches include genetic programming and cellular automata, but all
essentially rely on brute force search over a DSL of operations combined with
ARC-specific tricks, without any substantial learning [1]. The few-shot nature
and large search space for ARC make it a very challenging benchmark, and
progress scaling program synthesis algorithms is likely needed to enable
further progress. We hope our progress reported here inspires and enables
further progress on ARC.

#### Future work

The next step of our work is to combine the two approaches to create a unified
approach. This can be done by using the bidirectional search algorithm to
solve tasks, then create new operations out of abstractions base on tasks
solved. To fill out the learning approach, we can consider including the
ability to synthesize inverse and conditional inverse operations for newly
learned abstractions, perhaps as its own synthesis problem. Our approach
remains to be scaled up to a full DSL capable of solving ARC. Incorporating
more sophisticated inverse semantics and type-directed search are important
components of the full bidirectional approach.

## References

  * [1] Abstraction and reasoning challenge | kaggle. https://www.kaggle.com/c/abstraction-and-reasoning-challenge/leaderboard (2020)
  * [2] top-quarks/arc-solution. https://github.com/top-quarks/ARC-solution (2020), accessed: 2020-10-05
  * [3] Balog, M., Gaunt, A.L., Brockschmidt, M., Nowozin, S., Tarlow, D.: Deepcoder: Learning to write programs (2016)
  * [4] Cai, J., Shin, R., Song, D.: Making neural programming architectures generalize via recursion (2017)
  * [5] Chen, X., Liu, C., Song, D.: Execution-guided neural program synthesis. In: International Conference on Learning Representations (2018)
  * [6] Chollet, F.: On the measure of intelligence (2019)
  * [7] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding (2019)
  * [8] Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., rahman Mohamed, A., Kohli, P.: Robustfill: Neural program learning under noisy i/o (2017)
  * [9] Dijkstra, E.W.: Program Inversion, pp. 351–354. Springer New York, New York, NY (1982), https://doi.org/10.1007/978-1-4612-5695-3_63
  * [10] Ellis, K., Nye, M., Pu, Y., Sosa, F., Tenenbaum, J., Solar-Lezama, A.: Write, execute, assess: Program synthesis with a repl (2019)
  * [11] Ellis, K., Wong, C., Nye, M., Sable-Meyer, M., Cary, L., Morales, L., Hewitt, L., Solar-Lezama, A., Tenenbaum, J.B.: Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning (2020)
  * [12] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition (2015)
  * [13] Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems. pp. 1097–1105 (2012)
  * [14] Lubin, J., Collins, N., Omar, C., Chugh, R.: Program sketching with live bidirectional evaluation. Proceedings of the ACM on Programming Languages 4(ICFP), 1–29 (Aug 2020), http://dx.doi.org/10.1145/3408991
  * [15] McAleer, S., Agostinelli, F., Shmakov, A., Baldi, P.: Solving the rubik’s cube with approximate policy iteration. In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net (2019), https://openreview.net/forum?id=Hyfn2jCcKm
  * [16] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. nature 518(7540), 529–533 (2015)
  * [17] Nye, M., Hewitt, L., Tenenbaum, J., Solar-Lezama, A.: Learning to infer program sketches (2019)
  * [18] Polozov, O., Gulwani, S.: Flashmeta: a framework for inductive program synthesis. In: Aldrich, J., Eugster, P. (eds.) OOPSLA. pp. 107–126. ACM (2015), http://dblp.uni-trier.de/db/conf/oopsla/oopsla2015.html#PolozovG15
  * [19] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.: Mastering the game of go without human knowledge. nature 550(7676), 354–359 (2017)
  * [20] Srivastava, S., Gulwani, S., Chaudhuri, S., Foster, J.S.: Path-based inductive synthesis for program inversion. SIGPLAN Not. 46(6), 492–503 (Jun 2011), https://doi.org/10.1145/1993316.1993557
  * [21] Valkov, L., Chaudhari, D., Srivastava, A., Sutton, C., Chaudhuri, S.: Houdini: Lifelong learning as program synthesis (2018)
  * [22] Vinyals, O., Babuschkin, I., Czarnecki, W.M., Mathieu, M., Dudzik, A., Chung, J., Choi, D.H., Powell, R., Ewalds, T., Georgiev, P., et al.: Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature 575(7782), 350–354 (2019)
  * [23] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks (2017)
  * [24] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., Smola, A.: Deep sets (2018)
  * [25] Zhou, C., Li, C.L., Poczos, B.: Unsupervised program synthesis for images using tree-structured lstm (2020)
  * [26] Zohar, A., Wolf, L.: Automatic program synthesis of long programs with a learned garbage collector (2019)