% Begin of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Encoding: ASCII
% Tex format: LaTeX
% Last modified: August 5, 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Magic-type Labelings}
\subsection{Magic Labelings}\label{magic_labeling}
Motivated by the notion of magic squares in number theory, magic labelings
were introduced by Sedl\'a\v{c}ek \cite{Se1} in 1963. Responding to a
problem raised by Sedl\'a\v{c}ek, Stewart (\cite{St1} and \cite{St2})
studied various ways to label the edges of a graph in the mid 60s. Stewart
calls a connected graph
{\em semi-magic}\subindex{graph}{semi-magic}
if there is a labeling of the
edges with integers such that for each vertex $v$ the sum of the labels of
all edges incident with $v$ is the same for all $v$. (Berge \cite{Ber} used the
term ``regularisable" for this notion.)
A semi-magic labeling where the edges are labeled with distinct positive
integers is called a {\em magic}\subindex{labeling}{magic} labeling.
Stewart calls a magic labeling
{\em supermagic}\subindex{labeling}{supermagic}\subindex{graph}{supermagic}
if the set of edge
labels consists of consecutive positive integers. The classic concept of
an $n \times n$ magic square\index{magic square} in number theory corresponds to a supermagic
labeling of $K_{n,n}$. Stewart \cite{St1} proved the following: $K_n$ is magic
for $n = 2$ and all $n \geq 5$; $K_{n,n}$ is magic for all $n \geq 3$;
fans\index{fan} $F_n$ are magic if and only if $n$ is odd and $n \geq 3$; wheels\index{wheel}
$W_n$ are magic for $n \geq 4; W_n$ with one spoke deleted is
magic for $n = 4$ and for $n \geq 6$. Stewart \cite{St1} also proved
that $K_{m,n}$ is semi-magic if and only if
$m = n$.
In \cite{St2} Stewart proved that $K_n$ is supermagic for $n \geq 5 $ if and
only if $n > 5$ and $n \not\equiv 0$ (mod 4). Sedl\'a\v{c}ek \cite{Se2} showed
that M\"{o}bius ladders\index{M\"{o}bius ladder}
$M_n$ (see \S \ref{product_related_graphs} for the definition) are
supermagic when $n \geq 3$ and $n$ is
odd and that $C_n \times P_2$ is magic, but not supermagic, when $n \geq 4$
and
$n$ is even.
Shiu, Lam and Lee \cite{SLL2} have proved: the composition of $C_m$
and ${\overline K_n}$ is supermagic when $m \geq 3$ and $n\geq 2$;
the complete $m$-partite graph $K_{n,n,\ldots,n}$ is supermagic when $n
\geq 3,~ m>5$ and $m \not\equiv 0$ (mod 4); and if $G$ is an $r$-regular
supermagic graph, then so is the composition of $G$ and ${\overline K_n}$ for
$n \geq 3$.
Ho and Lee \cite{HL} showed that the composition of $K_k$ and the null graph with $n$
vertices is supermagic for $k= 3$ or 5 and $n= 2$ or $n$ odd.
Ba\v{c}a, Holl\"ander and Lih \cite{BHL} have found
two families of 4-regular\index{regular graph} supermagic graphs.
Shiu, Lam and Cheng \cite{SLC2} prove that
for $n\geq 2, mK\sb {n,n}$ is
supermagic if and only if $n$ is even or both $m$ and $n$ are odd.
Ivan\u{c}o \cite{Iv} gives a characterization of all supermagic regular
complete multipartite graphs. He proves that $Q_n$ is supermagic if and only
if $n = 1$ or $n$ is even and greater than 2 and that $C_n \times C_n$ and
$C_{2m} \times C_{2n}$ are supermagic. He conjectures that $C_m \times C_n$ is
supermagic for all $m$ and $n$.
Trenkl\'er \cite{Tre2} has proved that a connected magic graph with $p$
vertices and $q$ edges other
than $P_2$ exits if and only if $5p/4 < q \leq p(p-1)/2.$
In \cite{SGL} Sun, Guan and Lee give an efficient algorithm for
finding a magic labeling of a graph.
Trenkl\'er \cite{Tre3} extended the definition of supermagic graphs to include
hypergraphs\index{hypergraph} and proved that the complete $k$-uniform $n$-partite
hypergraph is supermagic if $n \neq 2$ or 6 and $k \geq 2$ (see also
\cite{Tre4}).
Sedl\'a\v{c}ek \cite{Se2} also proves that graphs obtained from an odd cycle
$u_1,u_2, \ldots, u_m, u_{m + 1},$\\$ v_m, \ldots, v_1 ~(m \geq 2)$ by
joining each
$u_i$ to $v_i$ and $v_{i + 1}$ and $u_1$ to $v_{m +1}, u_m$ to $v_1$
and $v_1$ to $v_{m + 1}$ are magic.
Trenkl\'er and Vetch\'{y} \cite{TV} have shown that if $G$ has order
at least 5 then $G^i$ is magic for all $i \geq 3$ and $G^2$ is magic if
and only if $G$ is not
$P_5$ and $G$ does not have a 1-factor whose every edge
is incident with an end-vertex of $G$. Seoud and Abdel
Maqsoud \cite{SA1} proved that $K_{1,m,n}$ is magic for all $m$
and $n$ and that $P_n^2$ is magic for all $n$. Characterizations of
regular\index{regular graph} magic graphs were given by Dood \cite{Doo3} and necessary and
sufficient
conditions for a graph to be magic were given in \cite{Je}, \cite{JT} and \cite{DH}.
Some sufficient conditions for a graph to be magic are given in
\cite{Doo1}, \cite{Tre1} and \cite{Mu}.
The notion of magic graphs was generalized in \cite{Doo2} and \cite{ST}.
In 1976 Sedl\'a\v{c}ek \cite{Se2} defined a
connected graph with at least
two edges to be {\em pseudo-magic}\index{pseudo-magic graph}\subindex{graph}{pseudo-magic}
if there exists a real-valued function
on the edges with the property that distinct edges have distinct values
and the sum of the values assigned to all the edges incident to any
vertex is the same for all vertices. Sedl\'a\v{c}ek proved that when
$n \geq 4$ and $n$ is even, the M\"{o}bius ladder\index{M\"{o}bius ladder} $M_n$ is not
pseudo-magic
and when
$m\geq 3$ and $m$ is odd, $C_m \times P_2$ is not pseudo-magic.
Kong, Lee and Sun \cite{KLS} used the
``magic labeling"\subindex{labeling}{magic} for a labeling of the
edges with nonnegative integers such that for each vertex $v$ the sum of
the labels of all edges incident with $v$ is the same for all $v$.
In particular, the edge labels need not be distinct. They
let $M(G)$ denote the
set of all such labelings of $G$. For any
$L$ in $M(G)$, they let $s(L)=\max\{L(e)\colon e$ in $E\}$ and define
the {\em magic strength}\index{magic strength}\subindex{strength}{magic} of $G$ as
$m(G)=\min\{s(L)\colon L$ in $M(G)\}$. To distinguish these
notions from
ones with the same names and notation introduced in the next section for
labelings from the
set of vertices and edges we call the Kong, Lee and Sun version the
{\em edge magic strength}\index{edge magic strength}\subindex{strength}{edge magic}
and use $em(G)$ for
$\min\{s(L)\colon L$ in $M(G)\}$ instead of $m(G)$.
Kong, Lee and Sun \cite{KLS} use $DS(k)$ to denote the graph
obtained by taking two copies of $K_{1,k}$ and connecting the $k$ pairs of
corresponding leafs. They show: for $k >1,~ em(DS(k)) = k -1;
~ em(P_k + K_1)$ is 1 for $k = 1$ or 2, $k$ if $k$ is
even and greater than 2 and
0 if $k$ is odd and greater than 1; for $k \geq 3, ~ em(W(k)) = k/2$ if $k$ is
even and $em(W(k)) = (k - 1)/2$ if $k$ is odd;
$em(P_2 \times P_2) = 1,
em(P_2 \times P_n) = 2$ if $n >3,
~em(P_m \times P_n) = 3$ if $m$ or $n$ is even and greater than 2;
$em(C_{3}^{(n)}) = 1$ if $n = 1$
(Dutch windmill -- see \S \ref{complete_graphs})
\index{Dutch windmill} and
$em(C_{3}^{(n)}) = 2n -1$ if $n > 1$. They also prove that if $G$ and $H$ are
magic graphs then $G \times H$ is magic and $em(G \times H)$ = max$\{em(G),
em(H)\}$ and that
every connected graph is an induced
subgraph of a magic graph (see also \cite{ELNR} and \cite{FIM1}). They conjecture that
almost all connected graphs are not magic.
In \cite{LSS} Lee, Saba and Sun show that
the edge magic
strength
of $P\sp k\sb n$ is 0 when $k$ and $n$ are both odd. Sun and Lee \cite{SuL}
show that the Cartesian,
conjunctive,
normal, lexicographic, and disjunctive products of two magic graphs are
magic and the sum
of two magic graphs is magic. They also determine
the magic strengths of the products and sum in terms of the magic strengths of
the components graphs.
S. M. Lee and colleagues \cite{LeWo} and \cite{LLSW} call a graph
$G$ {\em $k$-magic}\subindex{graph}{$k$- magic} if there is a labeling from
the edges of $G$ to the set
$\{1,2, \ldots, k -1\}$ such that for each vertex $v$ of $G$ the sum of
all edges incident with $v$ is a constant independent of $v$. The set of all
$k$ for which $G$ is $k$-magic is denoted by IM($G$) and called the
{\em integer-magic spectrum}\index{integer-magic spectrum}
of $G$. In \cite{LeWo} Lee and Wong investigate the
integer-magic spectrum
of powers of paths. They prove:
IM($P_{4}^2)$ is $\{4,6,8,10, \ldots\}$;
for $n > 5,$ IM($P_n^2$) is the set of all positive integers except 2;
for all odd $d > 1,$ IM($P_{2d}^d$)
is the set of all positive integers except 1;
IM($P_4^3$) is the set of all positive integers;
for all odd $n \geq 5,$ IM($P_n^3$)
is the set of all positive integers except 1 and 2; and
for all even $n \geq 6,$ IM($P_n^3$)
is the set of all positive integers except 2.
They conjecture that for $k > 3,$ IM($P_n^k$) is
the set of all positive integers when $n = k + 1$;
the set of all positive integers except 1 and 2 when $n$ and $k$ are odd
and $n \geq k$;
the set of all positive integers except 1 and 2 when
$n$ and $k$ are even and $k \geq n/2$;
the set of all positive integers except 2 when $n$ is even and $k$ is
odd and $n \geq k$; and
the set of all positive integers except 2 when
$n$ and $k$ are even and $k \leq n/2$.
In \cite{LLSW} Lee et al. investigated the integer-magic spectrum of trees
obtained by joining the centers
of two disjoint stars $K_{1,m}$ and $K_{1,n}$ with an edge.
They denote these graphs by ST($m,n$). Among their results are:
IM(ST($m,n$)) is the empty set when $|m -n| = 1$;
IM(ST($2m,2m$)) is the set of all positive integers;
IM(ST($2m+1,2m+1$)) ~$(m \geq 1)$
is the set of all positive integers except 2;
IM($W_{2n + 1}$) is the set of all positive integers;
IM($W_{2n}$) ~$(n > 1)$ is the set of all positive integers except 2;
IM($C_{2n} \cdot K_1$)
is the set of all positive integers except 2;
IM($C_{2n+1} \cdot K_1$)
is the set of all even positive integers;
IM($P_m \times P_n$) ~$(m,n) \neq (2,2)$
is the set of all positive
integers except 2;
IM($P_2 \times P_2$) is the set of all positive integers
and IM($P_n + K_1) ~(n > 2)$ is the set of
all positive
integers except 2;
and IM($K_{1,k + 1}) ~(k > 2)$
is the set of all multiples of $k$.
Lee et al. use the notation $C_m @ C_n$
for the graph obtained by starting with $C_m$ and
attaching paths $P_n$ to $C_m$ by identifying the endpoints of the
paths with each successive pairs of verticies of $C_m$. They prove that
IM($C_m @ C_n$)
is the set of all positive integers if $m$ or $n$ is even and
IM($C_m @ C_n$)
is the set of all even positive integers if $m$ and $n$ are odd.
Specialized results about the integer-magic spectra of amalgamations of
stars and cycles are given by Lee and Salehi in \cite{LeSa}.
%\subsubsection*{Abbreviation}
The table following summarizes the state of knowledge about magic-type
labelings.
In the table {\bf SM} means semi-magic;
{\bf M} means magic; {\bf SPM} means supermagic.
A question mark following
an abbreviation indicates that the graph is conjectured to have the
corresponding property. The table was prepared by Petr Kovar and Tereza
Kovarova.
%\begin{description}
%\item [SM] semi-magic
%\item [M] magic
%\item [SPM] magic
%\end{description}
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of Magic Labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable: Summary of Magic Labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
% \hspace*{2.7in} & \hspace*{2.8in}\\
& & \\
$K_n$ & M & if $n=2$, $n\geq5$ \cite{St1} \\
& SPM & for $n\geq5$ iff $n>5$, $n\not\equiv0\ (\mod 4)$ \cite{St2} \\
& & \\
$K_{m,n}$ & SM & if $n\geq3$ \cite{St1} \\
& & \\
$K_{n,n}$ & M & if $n\geq3$ \cite{St1} \\
& & \\
Fans $F_n$ & M & iff $n$ is odd, $n\geq3$ \cite{St1} \\
& & \\
Wheels $W_n$ & M & if $n\geq4$ \cite{St1} \\
& & \\
Wheels with one & M & if $n=4$, $n\geq6$ \cite{St1} \\
spoke deleted & & \\
& & \\
M\"{o}bius ladders $M_n$ & SPM & if $n\geq3$, $n$ is odd \cite{Se2} \\
& & \\
$C_n\times P_2$ & M not SPM & for $n\geq4$, $n$ even \cite{Se2} \\
& & \\
Composition of $C_m$ and $\overline{K}_n$ & SPM & if $m\geq3$, $n\geq2$ \cite{SLL2} \\
& & \\
$K_{\underbrace{n,n,\ldots,n}_p} $ & SPM & $n\geq3$, $p>5$ and $p\not\equiv0\ (\mod4)$ \cite{SLL2} \\
& & \\
Composition of $r$-regular & SPM & if $n\geq3$ \cite{SLL2} \\
SPM graph and $\overline{K}_n$ & & \\
& & \\
Composition of $K_k$ and $\overline{K}_n$ & SPM & if $k=3$ or $5$, $n=2$ or $n$ odd \cite{HL} \\
% null graph with $n$ vertices & & \\
& & \\
$mK_{n,n}$ & SPM & for $n\geq2$ iff $n$ is even or \\
& & both $n$ and $m$ are odd \cite{SLC2} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Magic-type Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
$Q_n$ & SPM & iff $n=1$ or $n>2$ even \cite{Iv} \\
& & \\
% $C_n\times C_n$ & SPM & \cite{Iv} \\
$C_m\times C_n$ & SPM & $m=n$ or $m$, $n$ even \cite{Iv} \\
& & \\
% $C_{2m}\times C_{2n}$ & SPM & \cite{Iv} \\
% & & \\
$C_{m}\times C_{n}$ & SPM? & for all $m$ and $n$ \cite{Iv} \\
& & \\
connected $(p,q)$-graph & M & iff $5p/4 < q \leq p(p-1)/2$ \\
other than $P_2$ & & \cite{Tre2} \\
& & \\
$G^i$ & M & $|G|\geq5$, $i\geq3$ \cite{TV} \\
& & \\
$G^2$ & M & $G\neq P_5$ and $G$ does not have a 1-factor whose \\
& & every edge is incident with an end-vertex of $G$ \\
& & \\
$K_{1,m,n}$ & M & for all $m$, $n$ \cite{SA1} \\
& & \\
$P_{n}^2$ & M & for all $n$ \cite{SA1} \\
& & \\
$G\times H$ & M & iff $G$ and $H$ are magic \cite{KLS} \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
\newpage
\subsection{Edge-magic Total and Super Edge-magic Labelings}\label{edge_magic_total}
In 1970 Kotzig and Rosa \cite{KR1} defined a magic labeling of a graph $G(V,E)$
as a bijection $f$ from $V \cup E$ to $\{1,2,\ldots,{\mid}V \cup
E{\mid}\}$ such that for all edges $xy$, $f(x) + f(y) + f(xy)$ is
constant. To distinguish between this usage from that of Stewart we will
call this labeling an
{\em edge-magic total}\subindex{labeling}{edge-magic total} labeling.
Kotzig and Rosa proved:
$K_{m,n}$
has an edge-magic total labeling for all $m$ and $n$; $C_n$ has an
edge-magic total
labeling for all $n \geq 3$ (see also \cite{GoS}, \cite{RB}, \cite{BPR} and \cite{ELNR}); and
the disjoint union\index{union} of $n$
copies of $P_2$
has an edge-magic total labeling if and only if $n$ is odd. They further
state that $K_n$ has an edge-magic total labeling if and only if $n = 1,
2,3,5$ or
$6$ (see \cite{KR2}, \cite{CT} and \cite{ELNR}) and ask whether all trees\index{tree} have
edge-magic total
labelings. Wallis et al. \cite{WBMS} enumerate every edge-magic total labeling
of complete graphs. They also prove that the following graphs are
edge-magic total:
paths, crowns, complete bipartite graphs, and cycles with a single edge
attached to one vertex. Enomoto, Llado, Nakamigana and Ringel \cite{ELNR}
prove that all complete bipartite
graphs are edge-magic total. They also show that
wheels\index{wheel} $W_n$ are not edge-magic total when $n \equiv 3$
(mod 4) and
conjectured
that all other wheels are edge-magic total.
This conjecture was
proved when $n \equiv 0, 1 $ (mod 4) by
Phillips, Rees and Wallis \cite{PRW1} and when $n \equiv 6$ (mod 8) by Slamin,
Ba\v{c}a, Lin, Miller and Simanjuntak \cite{SBLMS}.
Fukuchi \cite{Fuk3} verified all cases of the conjecture independently of the
work of
others. Slamin et al. further show that all fans\index{fan} are edge-magic
total.
Ringel and Llado
\cite{RL} prove that a graph with $p$ vertices and $q$ edges is not
edge-magic total
if $q$ is even and $p+q\equiv 2$ (mod 4) and each
vertex has odd degree.
Ringel and Llado conjecture that trees\index{tree} are edge-magic total.
In \cite{BBR} Babujee, Baskar Rao
present algorithms for producing edge-magic total labelings
of trees with a minimum number of
pendent vertices and trees with a maximum number of pendent vertices.
Beardon \cite{Bea2} extends the notion of edge-magic total to countable
infinite graphs \subindex{graph}{countable infinite}
$G(V,E)$
(that is, $V \cup E$ is countable). His main result is that a
countably infinite
tree that processes an infinite simple
path has a bijective edge-magic total labeling using the integers as
labels.
He asks whether all countably infinite trees have an edge-magic total
labeling with the integers as labels and whether the graph with the
integers as vertices and an edge joining
every two distinct vertices has a bijective edge-magic total labeling
using the integers.
Balakrishnan and Kumar \cite{BK2} proved
that the join of $\overline{K_n}$ and two disjoint copies of $K_2$ is edge-magic
total if and only if $n =3$. Yegnanarayanan \cite{Ye2} has proved the following
graphs have edge-magic total labelings: $nP_3$ where $n$ is odd; $P_n + K_1; P_n
\times C_3 ~(n \geq 2)$; the crown $C_n \odot K_1$; and $P_m \times C_3$ with
$n$ pendant vertices attached to each vertex of the outermost $C_3$.
He conjectures that
for all $n, ~C_n \odot \overline{K_n},$ the $n$-cycle with $n$ pendant
vertices attached at each vertex of the cycle,
and $nP_3$ have edge-magic total labelings.
In fact, Figueroa-Centeno, R. Ichishima and F. A.
Muntaner-Batle \cite{FIM8} have proved the
stronger statement that
for all $n \geq 3$,
the corona\index{corona} of $C_n \odot \overline{K_m}$ admits an
edge-magic labeling
where the set of vertex labels is $\{1,2, \ldots,|V|\}$
Yegnanarayanan \cite{Ye2} also introduces
several variations of edge-magic labelings and provides some results
about them. Kotzig \cite{Wal3} provides some necessary conditions for
graphs with an even number of edges in which every vertex has odd degree
to have an edge-magic total
labeling.
Craft and Tesar \cite{CT} proved that an $r$-regular\index{regular graph} graph with
$r$ odd and $p \equiv 4$ (mod 8) vertices can not be edge-magic total.
Wallis \cite{Wal1} proved that if $G$ is an edge-magic total
$r$-regular graph with $p$ vertices and $q$ edges with $r=
2^ts + 1 ~(t > 0)$ and
$q$ even, then $2^{t + 2}$ divides $p$.
Figueroa-Centeno, Ichishima and Muntaner-Batle \cite{FIM2} and
Ichishima \cite{FIM2} have
proved the following graphs are edge-magic total: $P_4 \cup nK_2$ for
$n$ odd;
~$P_3 \cup nK_2; ~P_5 \cup nK_2; ~nP_i$
for $n$ odd and $i = 3,4,5;~2P_n; ~P_1 \cup P_2 \cup \cdots \cup P_n;
~mK_{1,n}; ~K_{1,n} \cup K_{1,n + 1}; ~C_m \odot nK_1; ~K_1 \odot nK_2$
for $n$ even; ~$W_{2n}; ~K_2 \times {\overline K_n}, ~nK_3$ for $n$ odd;
binary trees\subindex{tree}{binary}, generalized
Petersen graphs\subindex{Petersen graph}{generalized}
(see also \cite{NB}), ladders (see also \cite{WiBa}), books\index{book}, fans\index{fan},
and odd cycles with pendant edges attached to one vertex. Enomoto et al. \cite{ELNR}
conjecture that if $G$ is a graph of order $n + m$ that contains $K_n,$
then $G$ is not edge-magic total for $n \gg m$. Wijaya and Baskoro \cite{WiBa}
proved that
$P_m \times C_n$ is edge-magic total for odd $n$ at least 3.
Ngurah and Baskoro \cite{NB} state that
$P_2 \times C_n$ is not edge-magic total.
Hegde and Shetty \cite{HeSh1} have shown that every $T_p$-tree (see \S \ref{elegant_labelings} for
the definition) is edge-magic total.
Wallis \cite{Wal1} proves that a
cycle with one pendent edge is edge-magic
total. In \cite{Wal1} Wallis poses a large number of research problems about
edge-magic total graphs. Avadayappan, Jeyanthi and Vasuki \cite{AJV}
define the {\em magic strength}\subindex{strength}{magic} of a graph $G$ as
the minimum of all constants over all edge-magic total labelings of $G$.
We denote this by $emt(G)$.
They use the notation
$$ for the tree obtained from the
bistar\index{bistar} $B_{n,n}$ by subdividing the edge joining the
two stars. They
prove: $emt(P_{2n}) = 5n +
1;~ emt(P_{2n + 1}) = 5n + 3; ~emt() = 4n +9;~ emt(B_{n,n}) = 5n + 6;
emt((2n + 1)P_2) = 9n + 6;~ emt(C_{2n + 1}) = 5n + 4;~ emt(C_{2n}) = 5n +
2; ~emt(K_{1,n}) = 2n + 4; ~emt(P^2)
= 3n$; and $emt(K_{n,m}) \leq (m + 2)(n + 1)$ where $n \leq m$.
Hegde and Shetty \cite{HeSh4} define the
{\em maximum magic strength}\subindex{strength}{maximum magic} of a
graph $G$
as the maximum constant over all edge-magic total
labelings of $G$. We use $eMt(G)$ to denote the maximum
magic strength of $G$. Hegde and Shetty call a graph $G$ with $p$ vertices {\em
strong magic}\subindex{graph}{strong magic} if
$emt(G) = eMt(G)$; {\em ideal magic}\subindex{graph}{ideal magic}
if $1 \leq eMt(G) - emt(G) \leq p$; and
{\em weak magic}\subindex{graph}{weak magic} if $eMt(G) - emt(G) > p.$
They prove that for an edge-magic total graph $G$ with $p$ vertices and
$q$ edges, $~eMt(G) = 3(p + q +
1) - emt(G)$. Using this result they obtain: $P_n$ is ideal magic for $n > 2$;
$K_{1,1}$ is strong magic, $K_{1,2}$ and $K_{1,3}$ are ideal magic, and
$K_{1,n}$ is
weak magic for $n> 3$; $B_{n,n}$ is ideal magic; $(2n + 1)P_2$ is strong
magic;
cycles are ideal magic; and the generalized web\subindex{web}{generalized}
$W(t,3)$ (see \S \ref{cycle_related_graphs}) with the
central vertex deleted is weak magic.
Enomoto et al. \cite{ELNR} call an edge-magic total labeling {\em
super
edge-magic}\subindex{labeling}{super edge-magic} if the set of vertex
labels is $\{1,2, \ldots, |V|\}$
(Wallis \cite{Wal1} calls these labelings {\em strongly edge-magic}).
\subindex{labeling}{strongly edge-magic}
They prove the following:
$C_n$ is super edge-magic if and only if $n$ is
odd, caterpillars\index{caterpillar} are super
edge-magic; $K_{m,n}$ is super edge-magic if and only if $m
=1$ or $n=1$; and $K_n$ is super edge-magic if and only if $n = 1, 2$ or
3. They also prove that if a graph with $p$ vertices and $q$ edges is
super edge-magic then, $q \leq 2p-3$.
Enomoto et al. \cite{ELNR} conjecture that every tree is super edge-magic.
Lee and Shan \cite{LSha} have verified this conjectures for trees with up to 17
vertices with a computer.
Kotzig
and Rosa's (\cite{KR1} and \cite{KR2}) proof that $nK_2$ is edge-magic total when $n$ is
odd actually shows that it is super edge-magic. Kotzig and Rosa also prove that
every caterpillar is super-edge magic. Figueroa-Centeno, Ichishima and
Muntaner-Batle prove the following: if $G$ is a bipartite or tripartite
(super)
edge-magic graph,
then $nG$ is (super) edge-magic when $n$ is odd \cite{FIM5};
if $m$ is a multiple of $n+ 1,$ then $K_{1,m} \cup K_{1,n}$ is super
edge-magic
\cite{FIM5};
$K_{1,2} \cup K_{1,n}$ is super edge-magic if and only if $n$ is a multiple of
3; $K_{1,m} \cup K_{1,n}$ is edge-magic if and only if $mn$ is even \cite{FIM5};
$K_{1,3}
\cup K_{1,n}$ is super edge-magic if and only if $n$ is a multiple of 4 \cite{FIM5};
$P_m \cup K_{1,n}$ is super edge-magic when $m \geq 4$ \cite{FIM5}; $2P_n$ is
super edge-magic if and only if
$n$ is not 2 or 3; $2P_{4n}$ is super edge-magic for all $n$ \cite{FIM5};
$K_{1,m} \cup
2nK_2$ is super edge-magic for all $m$ and $n$ \cite{FIM5};
$C_3 \cup C_n$ is super edge-magic if and only if $n \geq 6$ and $n$ is
even \cite{FIM8};
$C_4 \cup C_n$ is super edge-magic if and only if $n \geq 5$ and $n$ is
odd \cite{FIM8};
$C_5 \cup C_n$ is super edge-magic if and only if $n \geq 5$ and $n$ is
even \cite{FIM8};
if $m$ is even and at least 6 and $n$ is odd and satisfies $n \geq m/2 + 2$,
then $C_m \cup C_n$ is super edge-magic \cite{FIM8};
$C_4 \cup P_n$ is super edge-magic if and only if $n \neq 3$ \cite{FIM8};
$C_5 \cup P_n$ is super edge-magic if $n \geq 4$ \cite{FIM8};
if $m$ is even and at least 6 and $n \geq m/2 + 2$, then $C_m \cup P_n$ is super
edge-magic \cite{FIM8}; and
$P_m \cup P_n$ is super edge-magic if and only if $(m,n) \neq (2,2)$ or (3,3)
\cite{FIM8}.
They conjecture \cite{FIM5} that
$K_{1,m} \cup K_{1,n}$ is super egde-magic only when
$m$ is a multiple of $n + 1$ and they prove that if $G$ is a super edge-magic
graph with $p$ vertices and $q$ edges with $p\geq 4$ and $q \geq 2p -4$,
then $G$ contains triangles.
In \cite{FIM8} Figueroa-Centeno et al. conjecture that
$C_m \cup C_n$ is super edge-magic if and only if $m + n \geq 9$ and $m + n$ is
odd.
Lee and Kong \cite{LK} use St($a_1,a_2, \ldots, a_n$) to denote the disjoint
union\index{union} of the $n$ stars St($a_1$), St($a_2$), $\ldots$ , St($a_n$). They
prove the
following graphs are super edge-magic: St($m,n$) where $n \equiv 0 $ mod($m +
1$); St($1,1,n$); St($1,2,n$); St($1,n,n$); St($2,2,n$) ;St($2,3,n$);
St($1,1,2,n$)~ ($n \geq 2$);
St($1,1,3,n$);
St($1,2,2,n$); and
St($2,2,2,n$). They conjecture that
St($a_1,a_2, \ldots, a_n$) is super edge-magic when $n > 1$ is odd.
Enomoto,
Masuda and Nakamigawa \cite{EMN} have proved that every graph can be embedded in
a connected super edge-magic graph as an induced subgraph. Slamin et al. \cite{SBLMS}
proved that the friendship graph\index{friendship graph}
consisting of $n$ triangles is super edge-magic
if and only if $n$ is 3, 4, 5 or 7. Fukuchi proved \cite{Fuk2} the generalizied
Petersen graph\subindex{Petersen graph}{generalized}
$P(n,2)$ (see \S \ref{miscellaneous_results} for the definition) is super
edge-magic if $n$ is odd and at least 3.
Baskoro and Ngurah \cite{BN} showed that $nP_3$ is super edge-magic for $n \geq 4$
and $n$ even.
Hegde and Shetty \cite{HeSh5} showed that a graph is super edge-magic if and
only
if it is strongly $k$-indexable\subindex{graph}{strongly $k$-indexable}
(see \S \ref{sequential_labelings}).
Figueroa-Centeno, Ichishima and Muntaner \cite{FIM1} proved that
a graph is super edge-magic if and only if it is
strongly 1-harmonious\subindex{graph}{strongly 1-harmonious}
and that a super edge-magic graph is cordial\subindex{graph}{cordial}. They
also proved that $P_n^2$ and $K_2 \times C_{2n + 1}$ are super edge-magic.
In \cite{FIM2} Figueroa-Centeno et al. show that the following graphs are
super edge-magic: $P_3 \cup kP_2$ for all $k; ~kP_n$
when $k$ is odd; and $k(P_2 \cup P_n)$ when $k$ is odd and $n = 3$ or $n
= 4$; fans\index{fan} $F_n$ if and only if $n \leq 6$.
They conjecture that $kP_2$ is not super edge-magic when
$k$ is even. This conjecture has been proved by Z. Chen
\cite{Che3} who showed that $kP_2$ is super edge-magic if and
only if $k$ is odd. Figueroa-Centeno et al. provide a strong necessary
condition
for a book\index{book} to have a super edge-magic labeling and conjecture that for
$n \geq 5$ the book $B_n$ is super edge-magic if and only if $n$ is
even or $n \equiv
5$ (mod 8). They prove that every tree with an $\alpha$-labeling is
super edge-magic. Yokomura (see \cite{ELNR}) has shown that $P_{2m + 1} \times
P_2$ and $C_{2m +
1} \times P_m$ are super edge-magic (see also \cite{FIM1}).
In \cite{FIM7}, Figueroa-Centeno et al. proved that if $G$ is a (super) edge-magic
2-regular graph, then $G \odot {\overline K_n}$ is (super) edge-magic and that
$C_m \odot {\overline K_n}$ is super edge-magic.
Fukuchi \cite{Fuk1} shows how to recursively create super edge-magic trees from
certains kinds of existing super edge-magically labelled trees\index{tree}.
Lee and Lee \cite{LeLe} investigate the existence of total edge-magic
lableings and
super edge-magic labelings of unicylic graphs. They obtain a variety of
positive and negative results and conjecture that all unicyclic are total
edge-magic.
Shiu and Lee \cite{ShLe} investigated edge labelings of multigraphs\index{multigraph}.
Given a multigraph $G$ with $p$ vertices and $q$ edges they call a
bijection
from the set of edges of $G$ to $\{1, 2,
\ldots , q \}$ with the property that for
each vertex $v$ the sum of all edge labels incident to $v$ is a constant
independent of $v$ a {\em supermagic}\subindex{labeling}{supermagic} labeling of $G$.
They use
$K_2[n]$ to denote the multigraph consisting of
$n$ edges joining 2 vertices and
$mK_2[n]$ to denote the disjoint union\index{union} of $m$ copies of $K_2[n]$.
They prove that for $m$ and $n$ at least 2, ~$mK_2[n]$ is supermagic if
and only if $n$ is even or if both $m$ and
$n$ are odd.
In 1970 Kotzig and Rosa \cite{KR1} defined the
{\em edge-magic deficiency}\subindex{deficiency}{edge-magic}, $\mu(G)$,
of a graph $G$ as the minimum $n$ such that $G \cup nK_1$ is edge-magic total.
If no such $n$ exists they define $\mu(G) = \infty$. In 1999 Figueroa-Centeno,
Ichishima and Muntaner-Batle \cite{FIM4} extended this notion to {\em super
edge-magic deficiency}\subindex{deficiency}{super edge-magic},
$\mu_s(G)$, is the analogous way. They prove the
following: $\mu_s(nK_2) = \mu(nK_2) = n -1$ (mod 2);
$\mu_s(C_n) = 0 $ if $n$ is odd; $\mu_s(C_n) = 1$ if $n \equiv 0$ (mod
4); $\mu_s(C_n) = \infty$ if $n \equiv 2$ (mod 4);
$\mu_s(K_n) = \infty$ if and only if $n \geq 5; \mu_s(K_{m,n}) \leq (m -1)(n-
1); \mu_s(K_{2,n}) = n-1$; and $\mu_s(F)$ is finite for all forests\index{forest} $F$.
They also prove that if a graph $G$ has $q$ edges with $q/2$ odd and every
vertex is
even, then $\mu_s(G) = \infty$.
In \cite{FIM9} Figueroa-Centeno et al. proved that
$\mu_s(P_m \cup K_{1,n}) = 1$ if $m =2$ and $n$ is odd or $m =3$ and
is not congruent to 0 mod 3 while in all other cases
$\mu_s(P_m \cup K_{1,n}) = 0$.
They also proved that $\mu_s(2K_{1,n} = 1$ when $n$
is odd and $\mu_s(2K_{1,n} \leq 1$ when $n$
is even. They conjecture that $\mu_s(2K_{1,n} = 1$ in all cases.
Other results in \cite{FIM9} are:
$\mu_s(P_m \cup P_n) = 1$ when $(m,n) = (2,2)$ or $(3,3)$ and
$\mu_s(P_m \cup P_n) = 0$ when $(m,n) \neq (2,2)$ or $(3,3)$;
$\mu_s(K_{1,m} \cup K_{1,n}) = 0$ when $mn$ is even and
$\mu_s(K_{1,m} \cup K_{1,n}) = 1$ when $mn$ is odd;
$\mu(P_m \cup K_{1,n}) = 1$ when $m = 2$ and $n$ is odd and
$\mu(P_m \cup K_{1,n}) = 0$ in all other cases;
$\mu(P_m \cup P_n) = 1$ when $(m,n) = (2,2)$ and
$\mu(P_m \cup P_,n) = 0$ in all other cases;
$\mu_s(2C_n) = 1$ when $n$ is even and $\infty$ when $n$ is odd;
$\mu_s(3C_n) = 0$ when $n$ is odd;
$\mu_s(3C_n) = 1$ when $n \equiv 0$ (mod 4);
$\mu_s(3C_n) = \infty$ when $n \equiv 2$ (mod 4);
and $\mu_s(4C_n) = 1$ when $n \equiv 0$ (mod 4). They conjecture the following:
$\mu_s(mC_n) = 0$ when $mn$ is odd;
$\mu_s(mC_n) = 1$ when $mn \equiv 0$ (mod 4);
$\mu_s(mC_n) = \infty$ when $mn \equiv 2$ (mod 4);
$\mu_s(2K_{1,n}) = 1$; if $F$ is a forest with two components, then $\mu(F) \leq
1$ and $\mu_s(F) \leq 1$.
Z. Chen \cite{Che3} has proven: the join of $K_1$ with any
subgraph of a star is super edge-magic; the join of two nontrivial graphs
is super edge-magic if and only if at least one of them has exactly
two vertices and their union has exactly one edge; and
if a $k$-regular graph is super edge-magic, then
$k\leq3$. Chen also obtained
the following conditions: there is
a connected super edge-magic graph with $p$ vertices and $q$ edges
if and only if $p-1 \leq q \leq 2p-3$; there
is a connected 3-regular super edge-magic graph with $p$ vertices if and
only if $p \equiv 2$ (mod 4); if $G$ is a $k$-regular edge-magic total
graph with $p$ vertices
and $q$ edges then $(p + q)(1 + p + q) \equiv 0$ (mod 2$d$) where $d$
= gcd($k -1,q)$. As a corollary of the last result, Chen observes
that $nK_2 + nK_2$ is not edge-magic total.
Another labeling that has been called ``edge-magic" was introduced by
Lee, Seah and Tan in 1992 \cite{LST}. They defined
a graph $G=(V,E)$ to be
{\em edge-magic}\subindex{graph}{edge-magic}\subindex{labeling}{edge-magic}
if there exists a
bijection $f\colon E\to\{1,2,\ldots,\vert E\vert \}$ such that the
induced mapping
$f\sp +\colon V\to{N}$ defined by $f\sp +(u)=\sum\sb {(u,v)\in
E}f(u,v)\pmod{\vert V\vert }$ is a constant map.
Lee conjectured that a cubic graph \index{cubic graph}
with $p$ vertices is edge-magic if and only if $p\equiv2$ (mod 4).
Lee, Pigg
and Cox \cite{LPC} verified this conjecture for several classes of cubic
graphs. Shiu and Lee \cite{ShLe} showed that the conjecture is not true for
multigraphs and disconnected graphs. Lee, Seah and Tan \cite{LST}
establish that a necessary condition for a
multigraph with $p$ vertices and $q$ edges to be edge-magic is
that $p$ divides $q(q+ 1)$ and exhibit several new classes of cubic
edge-magic graphs.
They also proved: $K_{n,n} ~(n \geq 3)$ is edge-magic, $K_n$
is
edge-magic for $n \equiv 1, 2$ (mod 4) and for $n \equiv 3$ (mod 4)
$(n \geq 7)$. Lee, Seah and Tan further proved that following graphs are
not
edge-magic:
all trees\index{tree} except $P_2$, all unicyclic graphs, and $K_n$ where $n \equiv 0$
(mod 4). Schaffer and Lee \cite{ScL} have proved that $C_m \times C_n$ is always
edge-magic. Lee, Tong and Seah \cite{LTS} have conjectured that the total graph of a
$(p,p)$-graph is edge-magic if and only if $p$ is odd. They prove this
conjecture for cycles.
For any graph $G$ and any positive integer $k$
the graph $G[k]$, called the {\em k-fold G}\index{k-fold G},
is the hypergraph\index{hypergraph} obtained from
$G$ by replacing each edge of $G$ with $k$ parallel edges. Lee, Seah and
Tan \cite{LST} proved that for any graph $G$ with $p$ vertices and $q$ edges,
$~G[2p]$ is
edge-magic and, if $p$ is odd, $G[p]$ is edge-magic. Shiu, Lam and
Lee
\cite{SLL3} show that if $G$ is an $(n+ 1,n)$-multigraph\index{multigraph},
then $G$ is edge-magic
if and only if $n$ is odd and $G$ is isomorphic to the disjoint union of
$K_2$ and $(n - 1)/2$ copies of $K_2[2]$. They also prove that if $G$ is a
$(2m + 1,
2m)$-multigraph and $k$ is at least 2, then $G[k]$ is edge-magic
if and only if $2m + 1$ divides $k(k -1)$. For a $(2m, 2m -1)$-multigraph
$G$
and $k$ at least 2, they show that $G[k]$ is edge-magic if $4m$
divides $(2m -1)k((2m-1)k
+ 1) $ or if $ 4m$ divides $(2m + k -1)k.$ In \cite{SLL1} Shiu, Lam and Lee
characterize the $(p,p)$-multigraphs that are edge-magic as $mK_2[2]$
or
the disjoint union of $mK_2[2]$ and two particular multigraphs
or the disjoint union of $K_2, mK_2[2]$ and 4 particular multigraphs.
They also show for every $(2m + 1, 2m + 1)$-multigraph $G,~ G[k]$ is
edge-magic for all $k$ at least 2. Lee, Seah and Tan \cite{LST} prove that the
multigraph $C_n[k]$ is edge-magic for $k \geq 2$.
%\subsubsection*{Abbreviation}
The table following summarizes what is known about edge-magic total labelings.
We use {\bf EMT} for edge-magic total and {\bf SEM} for super edge-magic labelings.
A question mark following
an abbreviation indicates that the graph is conjectured to have the
corresponding property. The table was prepared by Petr Kovar and Tereza
Kovarova.
%\begin{description}
%\item [EMT] edge-magic total labeling
%\item [SEM] super edge-magic labeling
%\end{description}
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of Edge-magic total Labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of Edge-magic total Labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
% \hspace*{2.7in} & \hspace*{2.8in}\\
& & \\
$K_{m,n}$ & EMT & for all $m$ and $n$ \cite{KR1} \\
& & \\
$C_n$ & EMT & for $n\geq3$ \cite{KR1} \cite{GoS} \cite{RB} \cite{BPR} \\
& & \\
$\bigcup\limits_n P_2$ & EMT & iff $n$ odd \cite{KR1} \\
& & \\
$K_n$ & EMT & iff $n=1,2,3,4,5$ or $6$ \cite{KR2} \cite{CT} \cite{ELNR} \\
& & enumerate all EMT of $K_n$ \cite{WBMS} \\
& & \\
Trees & EMT? & \cite{KR2} \cite{RL} \\
& & \\
$P_n$ & EMT & \cite{WBMS} \\
& & \\
Crowns $C_n \odot K_1$ & EMT & \cite{WBMS} \\
& & \\
$K_{m,n}$ & EMT & \cite{WBMS} \\
& & \\
$C_n$ with a single edge & EMT & \cite{WBMS} \\
attached to one vertex & & \\
& & \\
Wheels $W_n$ & not EMT & if $n\equiv3\ (\mod 4)$ \cite{ELNR} \\
& EMT & if $n\equiv0,1\ (\mod 4)$ \cite{PRW1} \\
& EMT & if $n\equiv6\ (\mod 8)$ \cite{SBLMS} \\
& EMT & if $n\equiv0,1,2\ (\mod 4)$ \cite{Fuk2} \\
& & \\
Fans & EMT & \cite{SBLMS} \\
& & \\
$(p,q)$-graph & not EMT & if $q$ even and $p+q\equiv2\ (\mod 4)$\ \cite{RL} \\
& & \\
% join of $\overline{K}_n$ and two & EMT & iff $n=3$ \cite{BK2} \\
% copies of $K_2$ & & \\
% & & \\
$nP_3$ & EMT & if $b$ is odd \cite{Ye2} \\
& & \\
$P_n + K_1$ & EMT & \cite{Ye2} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
$P_n + K_1$ & EMT & \cite{Ye2} \\
& & \\
$P_n\times C_3$ & EMT & $n\geq2$ \cite{Ye2} \\
& & \\
Crown $C_n\odot K_1$ & EMT & \cite{Ye2} \\
& & \\
% $P_m\times C_3$ with $n$ pendant & EMT & \cite{Ye2} \\
% vertices attached to each & & \\
% outermost $C_3$ & & \\
$nP_3$ & EMT? & \cite{Ye2} \\
& & \\
% Corona $C_n\odot \overline{K}_m$ & SEM & $n\geq3$ \cite{FIM8} \\
% & & \\ % is further in text
$r$-regular graph & not EMT & $r$ odd and $p\equiv4\ (\mod 8)$ \cite{CT} \\
& & \\
$G$ $r$-regular $(p,q)$-graph & & if $r=2^ts+1 (t>0)$ and $q$ even \\
& & then $2^t+2$ divides $p$ \cite{Wal1} \\
& & \\
$P_4\cup nK_2$ & EMT & $n$ odd \cite{FIM1} \cite{FIM2} \\
& & \\
$P_3\cup nK_2$ and $P_5\cup nK_2$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$nP_i$ & EMT & $n$ odd, $i = 3, 4, 5$ \cite{FIM1}\cite{FIM2} \\
& & \\
$2P_n$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$P_1 \cup P_2 \cup \cdots \cup P_n$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$mK_{1,n}$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$K_{1,n} \cup K_{1,n+1}$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$C_m \odot \overline{K}_n$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
$K_1 \odot nK_2$ & EMT & $n$ even \cite{FIM1} \cite{FIM2} \\
& & \\
$W_{2n}$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$K_2\times \overline{K}_n$ & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
$nK_3$ & EMT & $n$ odd \cite{FIM1} \cite{FIM2} \\
& & \\
binary trees & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
generalized Petersen graph & EMT & \cite{FIM1} \cite{FIM2} \cite{NB} \\
$P(m,n)$ & & \\
& & \\
ladders & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
books & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
fans & EMT & \cite{FIM1} \cite{FIM2} \\
& & \\
odd cycle with pendant edges & EMT & \cite{FIM1} \cite{FIM2} \\
attached to one vertex & & \\
& & \\
$P_m \times C_n$ & EMT & $n$ odd $n \geq 3$ \cite{WiBa} \\
& & \\
$P_m \times P_2$ & EMT & $m$ odd $m \geq 3$ \cite{WiBa} \\
& & \\
$P_2 \times C_n$ & not EMT & \cite{NB} \\
& & \\
$K_{1,m}\cup K_{1,n}$ & EMT & iff $mn$ is even \cite{FIM5} \\
& & \\
% $G$ of order $m+n$ & not EMT? & $n\gg m$ \cite{ELNR} \\
% contains $K_n$ & & \\
% & & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of Super Edge-magic Labelings}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of Super Edge-magic Labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
% \hspace*{2.7in} & \hspace*{2.8in}\\
& & \\
$C_n$ & SEM & iff $n$ is odd \cite{ELNR} \\
& & \\
Caterpillars & SEM & \cite{ELNR} \cite{KR1} \cite{KR2} \\
& & \\
$K_{m,n}$ & SEM & iff $m=1$ or $n=1$ \cite{ELNR} \\
& & \\
$K_n$ & SEM & iff $n=1,2$ or $3$ \cite{ELNR} \\
& & \\
% $(p,q)$-graph & & if $(p,q)$-graph is SEM then $q\leq2p-3$ \cite{ELNR} \\
% & & \\
Trees & SEM? & \cite{ELNR} \\
& & \\
$nK_2$ & SEM & if $n$ odd \cite{KR1} \cite{KR2} \\
& & \\
$nG$ & SEM & if $G$ is a bipartite or tripartite \\
& & SEM graph and $n$ odd \cite{FIM5} \\
& & \\
$K_{1,m}\cup K_{1,n}$ & SEM & if $m$ is a multiple of $n+1$ \cite{FIM5} \\
& & \\
$K_{1,m}\cup K_{1,n}$ & SEM? & iff $m$ is a multiple of $n+1$
\cite{FIM5} \\ % conjecture
& & \\
$K_{1,2}\cup K_{1,n}$ & SEM & iff $n$ is a multiple of $3$ \cite{FIM5} \\
& & \\
$K_{1,3}\cup K_{1,n}$ & SEM & iff $n$ is a multiple of $4$ \cite{FIM5} \\
& & \\
$P_m\cup K_{1,n}$ & SEM & if $m\geq4$ is even \cite{FIM5} \\
& & \\
$2P_n$ & SEM & iff $n$ is not $2$ or $3$ \cite{FIM5} \\
& & \\
$2P_{4n}$ & SEM & for all $n$ \cite{FIM5} \\
& & \\
$K_{1,m}\cup 2nK_{1,2}$ & SEM & for all $m$ and $n$ \cite{FIM5} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
$C_3\cup C_n$ & SEM & iff $n\geq6$ even \cite{FIM8} \\
& & \\
$C_4\cup C_n$ & SEM & iff $n\geq5$ odd \cite{FIM8} \\
& & \\
$C_5\cup C_n$ & SEM & iff $n\geq5$ even \cite{FIM8} \\
& & \\
$C_m\cup C_n$ & SEM & if $m\geq6$ even and $n$ odd $n\geq m/2+2$ \cite{FIM8} \\
& & \\
$C_m\cup C_n$ & SEM? & iff $m+n\geq9$ and $m+n$ odd \cite{FIM8} \\ %
conjecture
& & \\
$C_4\cup P_n$ & SEM & iff $n\neq 3$ \cite{FIM8} \\
& & \\
$C_5\cup P_n$ & SEM & if $n\neq 4$ \cite{FIM8} \\
& & \\
$C_m\cup P_n$ & SEM & if $m\geq6$ even and $n\geq m/2+2$ \cite{FIM8} \\
& & \\
$P_m\cup P_n$ & SEM & iff $(m,n)\neq(2,2)$ or $(3,3)$ \cite{FIM8} \\
& & \\
Corona $C_n\odot \overline{K}_m$ & SEM & $n\geq3$ \cite{FIM8} \\
& & \\
$St(a_1,\ldots,a_n)$ & & is a disjoint union of stars (see \S \ref{edge_magic_total}) \\
$St(m,n)$ & SEM & $n\equiv0\ (\mod m+1)$ \cite{LK} \\
$St(1,k,n)$ & SEM & $k=1,2$ or $n$ \cite{LK} \\
$St(2,k,n)$ & SEM & $k=2,3$ \cite{LK} \\
$St(1,1,k,n)$ & SEM & $k=2,3$ \cite{LK} \\
$St(k,2,2,n)$ & SEM & $k=1,2$ \cite{LK} \\
% $St(k,2,2,n)$ & SEM & $k=1,2$ \cite{LK} \\
& & \\
$St(a_1,\ldots,a_n)$ & SEM? & for $n>1$ odd \cite{LK} \\
& & \\
% $G$ & & can be embeded into a SEM \\
% & & as induced subgraph \cite{EMN} \\
% & & \\
Friendship graph & SEM & iff $n=3,4,5$ or $7$ \cite{SBLMS} \\
of $n$ triangles & & \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
Generalized Petersen & SEM & if $n\geq3$ odd \cite{Fuk1} \\
graph $P(n,2)$ (see \S \ref{miscellaneous_results}) & & \\
& & \\
$nP_3$ & SEM & if $n\geq4$ even \cite{BN} \\
& & \\
% $G$ & SEM & iff $G$ is strongly $1$-harmonious \\
% & & and that SEM $G$ is cordial \cite{FIM1} \\
% & & \\
$P_n^2$& SEM & \cite{FIM1} \\
& & \\
$K_2\times C_{2n+1}$& SEM & \cite{FIM1} \\
& & \\
% $P_3\cup kP_2$& SEM & \cite{FIM2} \\
% & & \\
$P_3\cup kP_2$& SEM & for all $k$ \cite{FIM2} \\
& & \\
$kP_n$ & SEM & if $k$ is odd \cite{FIM2} \\
& & \\
$k(P_2\cup P_n)$ & SEM & if $k$ is odd and $n=3,4$ \cite{FIM2} \\
& & \\
Fans $F_n$ & SEM & iff $n\leq6$ \cite{FIM2} \\
& & \\
$kP_2$ & SEM & iff $k$ is odd \cite{Che3} \\
& & \\
Book $B_n$ & SEM? & iff $n$ even or $n\equiv5 \ (\mod 8)$\cite{FIM2} \\
& & \\
Tree with $\alpha$ labeling & SEM & \cite{FIM2} \\
& & \\
$P_{2m+1}\times P_2$ & SEM & \cite{ELNR} \cite{FIM1} \\
$P_{2m+1}\times P_m$ & SEM & \cite{ELNR} \cite{FIM1} \\
& & \\
$G\odot\overline{K}_n$ & EMT/SEM & if $G$ is EMT/SEM $2$-regular graph \cite{FIM7} \\
& & \\
$C_m\odot\overline{K}_n$ & SEM & \cite{FIM7} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of Edge-magic total and Super Edge-magic Labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Types} & {\em Notes}\\
\hline
& & \\
join of $K_1$ with any subgraph & SEM & \cite{Che3} \\
of a star & & \\
& & \\
join of two nontrivial graphs & SEM & \cite{Che3} \\
one has two vertices and their & & \\
union has exactly one edge & & \\
& & \\
if $G$ is $k$-regular SEM graph & & then $k\leq3$ \cite{Che3} \\
& & \\
$G$ is connected $(p,q)$-graph & SEM & $G$ exists iff $p-1\leq q\leq 2p-3$ \cite{Che3} \\
& & \\
$G$ is connected $3$-regular & SEM & iff $p\equiv2\ (\mod 4)$ \cite{Che3} \\
graph on $p$ vertices & & \\
& & \\
% if $G$ is connected $k$-regular & SEM & then $(p+q)(1+p+q)\equiv0\ (\mod 2d)$ \\
% $(p,q)$-graph & & where $d={\rm gcd}(k-1,q)$ \cite{Che3}\\
% & & \\
$nK_2+nK_2$ & not SEM & \cite{Che3} \\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
\newpage
\subsection{Vertex-magic Total Labelings and Totally
Magic Labelings}\label{vertex_magic}\label{totally magic}
MacDougall, Miller, Slamin and Wallis \cite{MMSW} introduced the notion of a
vertex-magic total labeling in 1999. For a graph $G(V,E)$ an injective
mapping
$f$ from $V \cup E$ to the set $\{1,2, \ldots, |V| + |E|\}$ is a
{\em vertex-magic total labeling}\subindex{labeling}{vertex-magic total}
if there is a constant $k$ so that for
every vertex $v, ~f(v) + \sum f(vu) = k$ where the sum is over all
vertices $u$ adjacent to $v$. They prove that the following graphs have
vertex-magic total labelings: $C_n;~ P_n$ for $n>2; K_{m,m}$
for
$m> 1; K_{m,m} - e$ for $m > 2$; and $K_n$ for $n$ odd. They also prove
that
when $n > m + 1, K_{m,n}$ does not have a vertex-magic total labeling.
They conjecture that $K_{m,m + 1}$ has a vertex-magic total labeling for
all $m$ and that $K_n$ has vertex-magic
total labeling for all $n \geq 3$. Lin and Miller \cite{LM} have shown that
$K_{m,m}$ is vertex-magic total for all $m > 1$ and that $K_n$ is
vertex-magic total
for all $n \equiv 0$ (mod 4). Phillips, Rees and Wallis \cite{PRW2}
generalized the Lin and Miller result by proving that $K_{m,n}$ is
vertex-magic total if and only if $m$ and $n$ differ by at most 1.
Miller, Ba\v{c}a, and MacDougall \cite{MBM}
have proved that the generalized Petersen graphs\subindex{Petersen graph}{generalized}
$P(n,k)$ (see Section~\ref{miscellaneous_results}
for the definition) are vertex-magic total when $n$ is even and $k
\leq n/2
-1$. They conjecture that all $P(n,k)$ are vertex-magic total when $k\leq
(n-1)/2$ and all prisms\index{prism} $C_n \times P_2$ are vertex-magic total.
Ba\v{c}a, Miller and Slamin \cite{BMS} proved the first of these conjectures
(see also \cite{SlM} for partial results) while
Slamin
and Miller prove the second.
MacDougall et al. (\cite{MMSW} and \cite{MMW})
have shown: $W_n$ has a vertex-magic total labeling if and only if $n \leq
11$;
fans
$F_n$ have a vertex-magic total labelings if and only if $n \leq 10$;
freindship\index{friendship graph} graphs
have vertex-magic total labelings if and only if the number of triangles is at
most 3; $K_{m,n}~ (m > 1)$ has a vertex-magic total labeling if and only
if
$m$ and $n$ differ by
at most 1. Wallis \cite{Wal1} proved: if $G$ and $H$ have the same order and $G
\cup H$ is vertex-magic total then so is $G+ H$; if the disjoint union\index{union}
of stars\index{star}
is vertex-magic total then the average size of the stars is less than 3;
if a tree\index{tree} has $n$ internal vertices and more than $2n$ leaves then it
does not
have a vertex-magic total labeling.
Wallis \cite{Wal2} has shown that
if $G$ is a regular\index{regular graph} graph of even degree that has a
vertex-magic total labeling then the graph consisting of an odd
number of copies of $G$ is vertex-magic total.
He also proved that
if $G$ is a regular graph of odd degree (not $K_1$) that has a
vertex-magic total labeling then the graph consisting of any number
of copies of $G$ is vertex-magic total.
Fron\v{c}ek, Kov\'{a}\v{r} and Kov\'{a}\v{r}ov\'{a}~\cite{FKK1} proved that $C_n
\times C_{2m+1}$ and $K_5 \times C_{2n+1}$ are vertex-magic total.
Kov\'{a}\v{r} in~\cite{Kov1} furhermore proved some general results about
products of certain regular vertex-magic total graphs.
In particular if $G$ is a $2r+1$ vertex-magic total graph which can be factored
into an $(r+1)$-regular graph and an $r$-regular graph then $G \times K_5$ and
$G \times C_n$ for $n$ even are also vertex-magic total.
He also proved that taking $G$ an $r$-regular vertex-magic total graph and $H$ a
$2s$-regular supermagic graph which can be factored into two $s$-regular factors
then their Cartesian product $G \times H$ is vertex-magic total if either $r$ is
odd or $r$ is even and $|H|$ is odd.
Beardon \cite{Bea1} has shown that a necessary condition for a graph
with $p$ vertices and $q$ edges and a vertex of degree $d$ to
be vertex-magic total is $(d + 2)^2 \leq (14q^2 +16q + 4)/p$. When the
graph is connected we have the stronger condition
$(d + 2)^2 \leq (7q^2 +11q + 4)/p$. As a corollary it follows that
the following are not
vertex-magic total: wheels\index{wheel} $W_n$ when $n \geq 12$, fans\index{fan} $F_n$ when $n
\geq 11$, and friendship graphs\index{friendship graph} $C_3^{(n)}$
when $n \geq 4$.
Wood \cite{Wo} generalizes vertex-magic and edge-magic labelings by
requiring only that the labels be positive integers rather than
consecutive positive integers.
He gives upper bounds for
the minimum values of the magic constant and the largest label for
complete graphs, forests, and arbitrary graphs.
Exoo et al. \cite{ELMPW} call a function $\lambda$ a
{\em totally magic labeling}\subindex{labeling}{totally magic} of
a graph $G$ if $\lambda$ is both an edge-magic and a vertex-magic labeling
of
$G$.
A graph with such a labeling is called {\em totally magic}\subindex{graph}{totally magic}.
Among their results are: $P_3$ is the only connected totally magic graph that
has a vertex of degree 1; the only totally magic graphs with a component $K_1$
are $K_1$ and $K_1 \cup P_3$;
the only totally magic complete graphs are $K_1$
and $K_3$;
the only totally magic complete bipartite graph is $K_{1,2}$;
$nK_3$ is totally magic if and only if $n$ is odd;
$P_3 \cup nK_3$ is totally magic if and only if $n$ is even.
J. McSorley and W. Wallis \cite{MW}
examine the possible totally magic labelings of a union of an odd number
of triangles and determine the spectrum of possible values for
the sum of the label on a vertex and the
labels on its incident edges
and the sum of an edge label and the labels of the endpoints
of the edge for all known totally magic graphs.
%\subsubsection*{Abbreviation}
In the table we use following abbreviations
\begin{description}
\item [VMT] vertex-magic total labeling
\item [TM] totally magic labeling
\end{description}
A question mark following
an abbreviation indicates that the graph is conjectured to have the
corresponding property. The table was prepared by Petr Kovar and Tereza
Kovarova.
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of vertex-magic total labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of vertex-magic total labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
% \hspace*{2.7in} & \hspace*{2.8in}\\
$C_{n}$ & VMT & \cite{MMSW}\\
& & \\
$P_{n}$ & VMT & $n>2$ \cite{MMSW}\\
& & \\
$K_{m,m}$ & VMT & $m>1$ \cite{MMSW}\cite{LM}\\
& & \\
$K_{m,m}-e$ & VMT & $m>2$ \cite{MMSW}\\
& & \\
$K_{m,n}$ & VMT & iff $|m-n|\leq1$ \cite{PRW2}\cite{MMSW}\cite{MMW}\\
% not if $n>m+1$ \cite{MMSW}\\ & &
& & \\
$K_{n}$ & VMT & for $n$ odd \cite{MMSW}\\
& & for $n\equiv2\ (\mod4),\, n>2$ \cite{LM}\\
& & \\
%Petersen $P(n,k)$ & VMT & for all $n$ and $k$ \cite{BMS}\\
Petersen $P(n,k)$ & VMT & \cite{BMS}\\
& & \\
%prisms $C_{n}\times P_{2}$ & VMT & for all $n$ \cite{SlM}\\
prisms $C_{n}\times P_{2}$ & VMT & \cite{SlM}\\
& & \\
$W_{n}$ & VMT & iff $n\leq 11$ \cite{MMSW}\cite{MMW}\\
& & \\
$F_{n}$ & VMT & iff $n\leq 10$ \cite{MMSW}\cite{MMW}\\
& & \\
friendship graphs (see \S \ref{vertex_magic})& VMT & iff $\#$ of triangles $\leq 3$ \cite{MMSW}\cite{MMW}\\
& & \\
$G+H$ & VMT & $|V(G)|=|V(H)|$ \\
& & and $G\cup H$ is VMT \cite{Wal1}\\
& & \\
%unions of stars & VMT & (see \S \ref{vertex_magic}) \cite{Wal1}\\
unions of stars & VMT & \cite{Wal1}\\
& & \\
Tree with $n$ internal vertices & & \\
and more than $2n$ leaves & not VMT & \cite{Wal1}\\
& & \\
%odd $\#$ of copies of $G$ & VMT & if $G$ is regular of even\\
$nG$ & VMT & $n$ odd, $G$ regular of even\\
& & degree, VMT \cite{Wal2}\\
& & \\
%any $\#$ of copies of $G$ & VMT & if $G$ is regular of odd\\
$nG$ & VMT & $G$ is regular of odd\\
& & degree, VMT, but not $K_{1}$ \cite{Wal2}\\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of vertex-magic total labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$C_n \times C_{2m+1}$ & VMT & \cite{FKK1}\\
& & \\
$K_5 \times C_{2n+1}$ & VMT & \cite{FKK1}\\
& & \\
$G \times C_{2n}$ & VMT & $G$ $2r+1$-regular VMT (see \S \ref{vertex_magic}) \cite{Kov1}\\
& & \\
$G \times K_5$ & VMT & $G$ $2r+1$-regular VMT (see \S \ref{vertex_magic}) \cite{Kov1}\\
& & \\
$G \times H$ & VMT & $G$ $r$-regular VMT, $r$ odd or $r$ even and $|H|$ odd,\\
& & $H$ $2s$-regular supermagic \cite{Kov1}\\
& & \\
$P_{3}$ & TM & the only connected TM graph\\
& & with vertex of degree 1 \cite{ELMPW}\\
& & \\
%$K_{1}$,$K_{1}\cup P_{3}$ &TM & the only TM graphs with \\
% & & component $K_{1}$ \cite{ELMPW}\\
% & & \\
$K_{n}$ & TM & iff $n=1,3$ \cite{ELMPW}\\
& & \\
$K_{m,n}$ & TM & iff $K_{m,n}=K_{1,2}$ \cite{ELMPW} \\
& & \\
$nK_{3}$ & TM& iff $n$ is odd \cite{ELMPW}\\
& & \\
$P_{3}\cup nK_{3}$ & TM& iff $n$ is even \cite{ELMPW}\\
& & \\
\hline
\end{tabular}
\end{center}
\end{table}
\newpage
\subsection{1-vertex magic vertex labeling}\label{1-vertex-magic-vertex}
In 2001, Simanjuntak, Rodgers and Miller \cite{SRM} defined a {\em 1-vertex magic
vertex labeling}\subindex{labeling}{1-vertex magic vertex}
of $G(V,E)$ as a bijection from $V$ to $\{1,2, \ldots, |V|\}$
with the property that there is a constant $k$ such that at any vertex $v$ the
sum $\sum f(u)$ taken over all neighbors of $v$ is $k$. Among their results
are:
$H \times {\overline K_{2k}}$ has a 1-vertex-magic vertex labeling for any
regular graph\index{regular graph} $H$; the symmetric complete multipartite graph with $p$
parts,
each of which contains $n$ vertices,
has a 1-vertex-magic vertex labeling if and only
if whenever $n$ is odd, $p$ is also odd, and if $n = 1$, then $p =1; ~P_n$
has a 1-vertex-magic vertex labeling if and only if
$n = 1$ or 3; ~$C_n$
has a 1-vertex-magic vertex labeling if and only if
$n =4; ~K_n$
has a 1-vertex-magic vertex labeling if and only if
$ n =1; ~W_n$
has a 1-vertex-magic vertex labeling if and only if
$n = 4$; a tree
has a 1-vertex-magic vertex labeling if and only if
it is $P_1$ or $P_3;$ and $r$-regular graphs with $r$ odd do not have a
1-vertex-magic vertex labeling.
%\subsubsection*{Abbreviation}
In the table we use the abbreviation 1VM for 1-vertex magic vertex labeling.
%A question mark following an abbreviation indicates
% that the graph is conjectured to have the corresponding property.
The table was prepared by Petr Kovar and Tereza Kovarova.
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}[bht]
\caption{\bf Summary of 1-vertex magic vertex labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of 1-vertex magic vertex labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$H\times\overline{K}_{2k}$ & 1VM & $H$ is regular \cite{SRM}\\
& & \\
symmetric $K_{\underbrace{n,n,...\,,n}_{p}}$ & 1VM & iff whenever $n$ is odd also $p$ is odd
,\\[-5mm]
& & and for $n=1$ also $p=1$ \cite{SRM}\\
& & \\
$P_{n}$ & 1VM & iff $n=1$ or $n=3$ \cite{SRM}\\
& & \\
$C_{n}$ & 1VM & iff $n=4$ \cite{SRM}\\
& & \\
$K_{n}$ & 1VM & iff $n=1$ \cite{SRM}\\
& & \\
$W_{n}$ & 1VM & iff $n=4$ \cite{SRM}\\
& & \\
tree $T$ & 1VM & iff $T=P_{1}$ or $P_{3}$ \cite{SRM}\\
& & \\
$r$ -- regular graph & not 1VM & $r$ is odd \cite{SRM}\\
\hline
\end{tabular}
\end{center}
\end{table}
\newpage
\subsection{Magic Labelings of Type $(a,b,c)$}\label{magic-type-abc}
A magic-type method for labeling the vertices, edges and faces\index{face} of a
planar graph\index{planar graph} was
introduced by Lih \cite{Lih} in 1983. Lih defines a {\em magic labeling of
type} (1,1,0)\subsubindex{labeling}{magic}{of type (1,1,0)}
of a planar graph $G(V,E)$ as an injective function from
$\{1,2,
\ldots, |V| + |E|\}$ to $V\cup E$ with the property that for each interior
face the sum of the labels of the vertices and the edges surrounding that
face is some fixed value. Similarly, Lih
defines a
{\em magic labeling of type $(1,1,1)$}\subsubindex{labeling}{magic}{of type (1,1,1)}
of a planar graph
$G(V,E)$ with face set $F$ as an injective
function from $\{1,2,
\ldots, |V| + |E| + |F|\}$ to $V\cup E \cup F$ with the property that for
each interior
face the sum of the labels of the face and the vertices and the edges
surrounding that
face is some fixed value. Lih calls a labeling involving the faces of a
plane
graph {\em consecutive}\subsubindex{labeling}{magic}{consecutive}
if for every integer $s$ the weights of all
$s$-sided faces constitute a set of consecutive integers.
Lih gave consecutive magic
labelings of type $(1,1,0)$
for wheels\index{wheel}, friendship graphs\index{friendship graph}, prisms\index{prism}
and some members of the Platonic family\index{Platonic family}.
In \cite{Bac14} Ba\v{c}a shows that the cylinders\index{cylinders} $C_n \times P_m$
have magic labelings of type $(1,1,0)$ when $m \geq 2, n\geq3, n \neq
4$. Ba\v{c}a has given magic
labelings of type $(1,1,1)$ for fans\index{fan} \cite{Bac1}, ladders\index{ladder} \cite{Bac1},
planar bipyramids\index{planar bipyramid} (that is, 2-point suspensions of paths)
\cite{Bac1}, grids \cite{Bac4},
hexagonal lattices\index{hexagonal lattice} \cite{Bac3}, M\"{o}bius ladders\index{M\"{o}bius ladder}
\cite{Bac8} and $P_n \times P_3$ \cite{Bac12}. Ba\v{c}a
\cite{Bac2}, \cite{Bac10}, \cite{Bac11}, \cite{Bac12}, \cite{Bac13}
and
Ba\v{c}a and Holl\"ander \cite{BHo2}
give magic labelings
of type $(1,1,1)$ and type
$(1,1,0)$ for certain classes of convex polytopes\index{convex polytope}.
Ba\v{c}a \cite{Bac9} also
provides consecutive and magic labelings of type $(0,1,1)$
\subsubindex{labeling}{magic}{of type (0,1,1)}
(that is, an injective
function from $\{1,2,
\ldots, |E| + |F|\}$ to $E \cup F$ with the property that for
each interior
face the sum of the labels of the face and the edges
surrounding that
face is some fixed value)
and a consecutive labeling of type $(1,1,1)$
for a kind of planar graph with hexagonal
faces.
A {\em magic labeling of
type} (1,0,0)\subsubindex{labeling}{magic}{of type (1,0,0)} of a planar graph
$G$ with vertex set $V$ is an injective function from
$\{1,2,
\ldots, |V|\}$ to $V$ with the property that for each interior
face the sum of the labels of the vertices surrounding that
face is some fixed value.
Kathiresan, Muthuvel and Nagasubbu \cite{KaMN}
define a {\em lotus inside a circle}\index{lotus inside a circle}
as the graph obtained from the cycle with consecutive vertices
$a_1, a_2, \ldots, a_n$ and the star with central vertex $b_0$ and end vertices
$b_1, b_2, \ldots, b_n$ by joining each $b_i$ to $a_i$ and $a_{i + 1} ~(a_{n+ 1}
= a_1)$. They prove that these graphs ($n \geq 5$) and subdivisions\index{subdivision} of
ladders\index{ladder} have consecutive labelings of type $(1,0,0)$.
Devaraj \cite{Dev} proves that graphs
obtained by subdividing each edge of a ladder exactly the same number of
times has a magic labeling of type $(1,0,0)$.
%\subsubsection*{Abbreviation}
In the table we use following abbreviations
\begin{description}
\item [M(x,x,x)] magic labeling of type $(x,x,x)$
\item [CM(x,x,x)] consecutive magic labeling of type $(x,x,x)$
\end{description}
A question mark following
an abbreviation indicates that the graph is conjectured to have the
corresponding property. The table was prepared by Petr Kovar and Tereza
Kovarova.
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of magic labelings of type $(a,b,c)$}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of magic labelings of type $(a,b,c)$}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$W_{n}$ &CM(1,1,0) & \cite{Lih}\\
& & \\
friendship graphs &CM(1,1,0) & \cite{Lih}\\
& & \\
prisms & CM(1,1,0)& \cite{Lih}\\
& & \\
cylinders $C_{n}\times P_{m}$ &M(1,1,0) & $m\geq2$, $n\geq3$, $n\neq4$ \cite{Bac14}\\
& & \\
fans $F_{n}$ &M(1,1,1) & \cite{Bac1}\\
& & \\
ladders & M(1,1,1) & \cite{Bac1}\\
& & \\
planar bipyramids &M(1,1,1) & \cite{Bac1}\\
(see \S \ref{vertex_magic}) & & \\
& & \\
grids &M(1,1,1) & \cite{Bac4}\\
& & \\
hexagonal lattices &M(1,1,1) & \cite{Bac3}\\
& & \\
M\"{o}bius ladders &M(1,1,1) & \cite{Bac8}\\
& & \\
$P_{n}\times P_{3}$ &M(1,1,1) &\cite{Bac12} \\
& & \\
certain classes of & M(1,1,1) & \cite{Bac2}, \cite{Bac10}, \cite{Bac11}, \cite{Bac12}, \\
convex polytopes & M(1,1,0) & \cite{Bac13}, \cite{BHo2}\\
& & \\
kind of planar graph & M(0,1,1)& \cite{Bac9}\\
with hexagonal faces & CM(0,1,1)& \\
& CM(1,1,1)& \\
& & \\
lotus inside a circle (see \S \ref{vertex_magic}) &CM(1,0,0)& $n\geq 5$ \cite{KaMN}\\
& & \\
subdivisions of ladders &M(1,0,0)& \cite{Dev} \\
&CM(1,0,0)& \cite{KaMN}\\
\hline
\end{tabular}
\end{center}
\end{table}
\newpage
%\subsection{Set-magic Labelings}\label{set_magic_labeling}
%
%Singhi, Vijayakumar and Usha Devi \cite{SVU} define a {\em set-magic
%labeling}
%\subindex{labeling}{set-magic}
%of a graph $G$ without isolated vertices to be an assignment of distinct
%subsets of a set $X$ to the edges of $G$ such that for every vertex $v$
%of $G$, the union of the subsets assigned to the edges incident with $v$
%is $X$. They characterize infinite graphs $G$ having set-magic labelings
%$f$ such that $|f(e)|=2$ for all $e\in E(G)$.
\subsection{Antimagic Labelings}\label{antimagic_labeling}
Ba\v{c}a, et al. \cite{BBMMSS1} introduced the notion of a
$(a,d)$-vertex-antimagic total labeling in 2000. For a graph $G(V,E),$ an
injective mapping
$f$ from $V \cup E$ to the set $\{1,2, \ldots, |V| + |E|\}$ is a
{\em $(a,d)$-vertex-antimagic total labeling}\subindex{labeling}{$(a,d)$-vertex-antimagic total} if
the set $\{f(v) + \sum f(vu) \}$ where the sum is over all
vertices $u$ adjacent to $v$ for all $v$ in $G$ is $\{a,a + d, a + 2d,
\ldots, a + (|V|-1)d\}$. Among their results are: every super-magic
graph has an $(a,1)$-vertex-antimagic total labeling;
every $(a,d)$-antimagic
graph $G(V,E)$ is $(a + |E| + 1, d + 1)$-vertex-antimagic total;
and, for $d > 1$, every $(a,d)$-antimagic
graph $G(V,E)$ is $(a +|V| + |E|, d - 1)$-vertex-antimagic total. They also
show that paths and cycles have $(a,d)$-vertex-antimagic total
labelings for a wide variety of $a$ and $d$. In \cite{BBMMSS2} Ba\v{c}a et al.
use their results in \cite{BBMMSS1} to obtain numerous
$(a,d)$-vertex-antimagic total labelings for prisms\index{prism}, antiprisms\index{antiprism} and
generalized Petersen graphs\subindex{Petersen graph}{generalized}. Lin, Miller, Simanjuntak and Slamin
\cite{LMSS} have shown that for $n > 20,~ W_n$ has no $(a,d)$-vertex-antimagic
total labeling.
Simanjuntak, Bertault and Miller \cite{SBM} define an
{\em (a,d)-edge-antimagic vertex labeling}\subindex{labeling}{$(a,d)$-edge-antimagic vertex}
for a graph $G(V,E)$ as an injective
mapping
$f$ from $ V$ onto the set $\{1,2, \ldots, |V|\}$ such that
the set $\{ f(u) + f(v)| uv \in E \}$
is $\{a,a + d, a + 2d,
\ldots, a + (|E |-1)d\}$. (The equivalent notion of {\em
(a,d)-indexable}\subindex{labeling}{$(a,d)$-indexable} labeling was defined by Hegde in
1989 in his Ph. D. thesis--see \cite{Heg2}.)
Similarly, Simanjuntak et al. define an
{\em (a,d)-edge-antimagic total labeling}\subindex{labeling}{$(a,d)$-edge-antimagic total}
for a graph $G(V,E)$ as an
injective
mapping
$f$ from $ V \cup E$ onto the set $\{1,2, \ldots, |V| +|E|\}$ such that
the set $\{ f(v) + \sum f(vu)| uv \in E \}$ where $v$ ranges over all of $V$
is $\{a,a + d, a + 2d,
\ldots, a + (|V| -1)d\}$.
Among their results are: $C_{2n}$ has no $(a,d)$-edge-antimagic vertex
labeling; $C_{2n + 1}$ has a $(n +2, 1)$-edge-antimagic vertex labeling
and
a $(n +3, 1)$-edge-antimagic vertex labeling;
$P_{2n}$ has a $(n +
2,1)$-edge-antimagic vertex labeling;
$P_n$ has a $(3,2)$-edge-antimagic
vertex labeling;
$C_n$ has a $(2n + 2, 1)$- and a $(3n + 2, 1)$-edge-antimagic
total labeling;
$C_{2n}$ has a $(4n + 2,2)$- and a $(4n +
3,2)$-edge-antimagic total
labeling;
$C_{2n + 1}$ has a $(3n + 4,3)$- and a $(3n + 5,3)$-edge-antimagic
total labeling;
$P_{2n + 1}$ has a $(3n + 4,2)$-, a $(3n + 4, 3)$-, a $(2n +
4,4)$-, a $(5n + 4, 2)$-, a $(3n + 5, 2)$-,
and a $(2n + 6, 4)$-edge-antimagic total
labeling;
$P_{2n}$ has a $(6n,1)$- and a $(6n + 2,2)$-edge-antimagic
total labeling; and several parity conditions for $(a,d)$-edge-antimagic
total labelings. They conjecture: paths have no $(a,d)$-edge-antimagic vertex
labelings with $d>2; ~C_{2n}$ has a $(2n + 3,4)$- or a
$(2n + 4,4)$-edge-antimagic total labeling; $C_{2n + 1}$ has a $(n + 4,5)$- or a $(n +
5,5)$-edge-antimagic total labeling; and cycles have no $(a,d)$-antimagic
total
labelings with $d > 5$.
Ba\v{c}a, Lin, Miller and Simanjuntak \cite{BLMS} prove that a graph with $v$
vertices
and $e$ edges that
has an $(a,d)$-edge-antimagic vertex labeling
must satisfy $d(e-1)\leq 2v -1 -a \leq 2v -4.$ As a consequence,
they obtain:
for every path there is no $(a,d)$-edge-antimagic vertex labeling with $d >2$;
for every cycle there is no $(a,d)$-edge-antimagic vertex labeling with $d >1$;
for $K_n~ (n > 1)$ there is no $(a,d)$-edge-antimagic vertex
labeling (the cases for $n =2$ and $n = 3$ are handled individually);
$K_{n,n}~(n >3)$ has no $(a,d)$-edge-antimagic vertex labeling;
for every wheel\index{wheel} there is no $(a,d)$-edge-antimagic vertex labeling;
for every generalized Petersen graph\subindex{Petersen graph}{generalized} there
is no $(a,d)$-edge-antimagic vertex
labeling with $d >1$.
Ba\v{c}a et al. \cite{BLMS}
show that a graph with an $(a,d)$-edge-antimagic total labeling
must satisfy $d(e-1)\leq 2v-1-a \leq 2v-4$. As a consequence,
they obtain:
for every path there is no $(a,d)$-edge-antimagic total labeling with $d >2$;
for every cycle there is no $(a,d)$-edge-antimagic total labeling with $d >1$;
for every complete graph $K_n$ there is no $(a,d)$-edge-antimagic total
labeling with $n>3$;
$K_{n,n}$ has no $(a,d)$-edge-antimagic total labeling with $n >3$;
for every wheel there is no $(a,d)$-edge-antimagic total labeling;
for every generalized Petersen graph there is no $(a,d)$-edge-antimagic total
labeling with $d >1$.
%They also study the relationship between graphs with
%$(a,d)$-edge-antimagic labelings and magic and antimagic labelings. They
%conjecture that every tree has an $(a,1)$-edge-antimagic total labeling.
%definitions ???
An $a,d)$-edge-magic total labeling of $G(V,E)$ is called
a {\em super (a,d)-edge-magic}\subindex{labeling}{super edge-magic} if
the vertex labels are $ \{1, 2, \ldots, |V(G)|\}$ and
the edge labels are $\{|V(G)|+1, |V(G)|+2, \ldots, |V(G)|+|E(G)|\}$.
Ngurah and Baskoro \cite{NB} have shown that for $n$ odd and at least 3
the
generalized Petersen graphs $P(n,1)$
and $P(n,2)$ have $((5n + 5)/2, 2)$-edge-antimagic total labelings and $P(n,m),
n \geq 3, 1 \leq m < n/2$ has a super $(4n + 2, 1)$-edge-antimagic total
labeling.
Hartsfield and Ringel \cite{HR} introduced antimagic
graphs in 1990. A graph with $q$ edges is called
{\em antimagic}\subindex{graph}{antimagic}\subindex{labeling}{antimagic} if its
edges can be labeled with $1,2,
\ldots, q$ so that the sums of the labels of the edges incident to each
vertex are distinct. Among the antimagic graphs are
\cite{HR}: $P_n ~(n\geq 3)$, cycles, wheels\index{wheel}, and $K_n ~(n \geq 3)$.
Hartsfield and Ringel conjecture that every tree\index{tree} except $P_2$ is
antimagic and, moreover, every connected graph except $P_2$ is antimagic.
Alon, Kaplan, Lev, Roditty and Yuster \cite{AKLRY} use probabilistic
methods and analytic number theory to show that this
conjecture is true for all graphs with $n$ vertices and minmum degree
$\Omega(\mbox{log }n)$. They also prove that if $G$ is a graph with $n
\geq 4$
vertices and $\Delta(G) \geq n -2,$ then $G$ is antimagic and all
complete partite graphs except $K_2$ are antimagic.
The concept of an $(a,d)$-antimagic
labelings was introduced by Bodendiek and Wagner \cite{BW1} in 1993.
A connected graph $G=(V,E)$ is said to be
{\em $(a,d)$-antimagic}\subindex{graph}{$(a,d)$-antimagic} if there
exist positive integers $a$,
$d$ and a bijection $f\colon E\to \{1,2,\ldots,\vert E\vert \}$ such
that the induced mapping $g\sb
f\colon V\to N$, defined by $g\sb f(v)=\sum \{f(u,v)\colon (u,v)\in
E(G)\}$, is injective and $g\sb
f(V)=\{a,a+d,\ldots,a+(\vert V\vert -1)d\}$. (In \cite{LMSS} these are called
$(a,d)$-{\em vertex-antimagic edge labelings})\subindex{labeling}{$(a,d)$- vertex-antimagic edge}.
They prove (\cite{BW3} and \cite{BW4}) the Herschel graph\index{Herschel
graph}
is not
$(a,d)$-antimagic and obtain both positive and negative results about
$(a,d)$-antimagic labelings for various
cases of graphs called
{\it parachutes}\label{parachutes}\index{parachutes}
$P\sb {g,b}$.
($P\sb {g,b}$ is the graph obtained from the wheel
$W_{g+p}$ by deleting $p$ consecutive spokes.)
In \cite{BHo1} Ba\v{c}a and Holl\"ander prove that necessary
conditions for
$C_n \times P_2$ to be $(a,d)$-antimagic are $d = 1, a = (7n + 4)/2$ or $d
= 3, a = (3n + 6)/2$ when $n$ is even and $d = 2, a = (5n + 5)/2$ or $d =
4, a = (n + 7)/2$ when $n$ is odd. Bodendiek and Walther \cite{BW2}
conjectured that $C_n \times P_2 ~(n \geq 3)$ is $((7n + 4)/2,
1)$-antimagic when $n$
is even and is $((5n + 5)/2, 2)$-antimagic when $n$ is odd. These
conjectures were verified by Ba\v{c}a and Holl\"ander \cite{BHo1} who further
proved
that $C_n \times P_2~ (n \geq 3)$ is $((3n + 6)/2, 3)$-antimagic when $n$
is
even. Ba\v{c}a and Holl\"ander \cite{BHo1} conjecture that $C_n \times P_2$ is
$((n + 7)/2, 4)$-antimagic when $n$ is odd and at least 7. Bodendiek and
Walther \cite{BW2} also conjectured that
$C_n \times P_2~ (n\geq 7)$ is $((n+7)/2,4)$-antimagic.
Ba\v{c}a and Holl\"ander \cite{BHo3} prove that the
generalized Petersen graph\subindex{Petersen graph}{generalized} $P(n,2)$ is
$((3n+6)/2,3)$-antimagic for $n\equiv 0$ (mod 4), $n\geq 8$ (see \S
\ref{miscellaneous_results} for
the definition).
Bodendiek and Walther \cite{BW5} proved that the following graphs are not
$(a,d)$-antimagic: even cycles; paths of even order; stars; $C_3^{(k)};
C_4^{(k)}$; trees of odd order at least 5 that have a vertex that is
adjacent to three or more end vertices; $n$-ary trees with at least two
layers when $d = 1; K_{3,3}$; the Petersen graph; and
$K_4$. They also prove: $P_{2k+1}$ is
$(k,1)$-antimagic; $C_{2k + 1}$ is $(k + 2,1)$-antimagic; if a tree
of odd order $2k + 1 ~(k > 1)$ is
$(a,d)$-antimagic, then $d = 1$ and $a = k$;
if $K_{4k} ~(k\geq 2)$ is
$(a,d)$-antimagic, then $d$ is odd and $d \leq 2k(4k -3) + 1$;
if $K_{4k + 2}$ is
$(a,d)$-antimagic, then $d$ is even and $d \leq (2k + 1)(4k -1) + 1$; and
if $K_{2k+ 1} ~(k\geq 2)$ is
$(a,d)$-antimagic, then $d \leq (2k + 1)(k -1)$.
Lin, Miller, Simanjuntak and
Slamin \cite{LMSS} show that no wheel $W_n ~(n > 3)$ has an $(a,d)$-antimagic labeling.
Yegnanarayanan \cite{Ye2} introduces
several
variations of antimagic labelings and provides some results about
them.
The {\em antiprism}\label{antiprism}\index{antiprism} on $2n$ vertices has
vertex set $\{x_{1,1}, \ldots, x_{1,n}, x_{2,1},
\ldots, x_{2,n}\}$ and edge set $\{x_{j,i}, x_{j,i + 1}\} \cup \{x_{1,i},
x_{2,i} \} \cup \{x_{1,i}, x_{2,i-1}\}$ (subscripts are taken modulo $n$).
For $n \geq 3$ and $n \not\equiv 2$ (mod 4) Ba\v{c}a \cite{Bac5} gives $(6n +
3,2)$-antimagic
labelings and $(4n + 4, 4)$-antimagic
labelings for the antiprism\index{antiprism} on $2n$ vertices.
He conjectures that for $n \equiv 2$ (mod 4), $n \geq 6$, the
antiprism on $2n$ vertices has a $(6n + 3,2)$-antimagic labeling
and a $(4n + 4, 4)$-antimagic labeling.
Nicholas, Somasundaram and Vilfred \cite{NSV} prove the following: If $K_{m,n}$
where $m \leq n$ is $(a,d)$-antimagic then $d$ divides $((m-n)(2a + d(m + n
-1)))/4 + dmn/2$; if $m + n$ is prime, then $K_{m,n}$ where $n > m > 1$ is not
$(a,d)$-antimagic; if $K_{n ,n+ 2}$ is $(a,d)$-antimagic, then $d$ is even and
$n + 1 \leq d < (n + 1)^2/2$;
if $K_{n,n+2}$ is $(a,d)$-antimagic and $n$ is
odd, then $a$ is even and $d$ divides $a$;
if $K_{n,n+2}$ is $(a,d)$-antimagic and $n$ is
even, then $d$ divides $2a$; if $K_{n,n}$ is $(a,d)$-antimagic, then $n$ and $d$
are even and $0 < d < n^2/2$; if $G$ has order $n$ and is unicylic and
$(a,d)$-antimagic, then $(a,d) = (2,2)$ when $n$ is even and $(a,d) = (2,2)$ or
$(a,d) =
((n + 3)/2, 1)$; a cycle with $m$ pendant edges attached at each vertex is
$(a,d)$-antimagic if and only if $m = 1$;
the graph obtained by joining
an endpoint of $P_m$ with one vertex of the cycle $C_n$ is $(2,2)$-antimagic
if $m =n$ or $m = n-1$; if $m + n$ is even
the graph obtained by joining
an endpoint of $P_m$ with one vertex of the cycle $C_n$ is $(a,d)$-antimagic
if and only if $m =n$ or $m = n-1$. They conjecture that for $n$ odd
and at least $3,~K_{n,n + 2}$ is $((n + 1)(n^2 -1)/2,n + 1)$-antimagic
and they have obtained several results about
$(a,d)$-antimagic labelings of caterpillars.
Ba\v{c}a \cite{Bac6} defines
a connected plane graph\index{planar graph} $G$ with edge set $E$ and face set $F$
to be {\em $(a,d)$-face antimagic}\subindex{labeling}{$(a,d)$-face antimagic}\index{face}
if there exist positive integers $a$ and $d$ and
a bijection $g\colon E\to\{1,2,\ldots,\vert E\vert \}$ such that
the induced mapping $\psi\sb g\colon F\to
\{a,a+d,\ldots,a+(\vert F(G)\vert
-1)d\}$ is also a bijection where for a face $f,~ \psi\sb g(f)$ is the sum
of all $g(e)$
for all edges $e$
surrounding $f$.
Ba\v{c}a
\cite{Bac6} and Ba\v{c}a and Miller \cite{BaM1}
describe
$(a,d)$-face antimagic labelings for a certain classes of convex
polytopes\label{polytope}\index{convex polytope}.
In \cite{BaM2} Ba\v{c}a and Miller define the class $Q_n^m$ of convex
polytopes with vertex set $\{y_{j,i} : i = 1, 2, \ldots, n; j = 1,2, \ldots, m+1\}$
and edge set $\{ y_{j,i}y_{j, i+1} : i = 1,2, \ldots, n; j = 1,2, \ldots, m + 1\}
\cup \{y_{j,i}y_{j + 1, i}: i = 1,2, \ldots, n; j = 1,2, \ldots, m\} \cup
\{y_{j, i+1}y_{j + 1,i}: 1 + 1,2, \ldots, n; j = 1,2, \ldots, m, j \mbox{ odd}\}
\cup
\{y_{j,i}y_{j + 1,i + 1}: i = 1,2, \ldots, n; j = 1,2, \ldots, m, j \mbox{ even}\}$
where $y_{j, n+ 1} = y_{j,1}$. They prove that for $m$ odd, $m \geq 3, n \geq 3,
Q_n^m$ is $(7n(m + 1)/2 + 2, 1)$-face antimagic and when $m$ and $n$ are even, $m
\geq 4, n \geq 4,
Q_n^m$ is $(7n(m + 1)/2 + 2, 1)$-face antimagic.
They conjecture that when $n$ is odd, $n \geq 3$, and $m$ is even, then
$Q_n^m$ is $((5n(m + 1) + 5)/2, 2)-$face antimagic and $((n(m+1) + 7)/2, 4)$-face
antimagic. They further conjecture that when $n$ is even, $n> 4, m> 1$ or $n$ is
odd, $n > 3$ and $m$ is odd, $m> 1$ then $Q_n^m$ is $(3n(m + 1)/2 + 3,
3)$-face
antimagic.
In \cite{Bac7} Ba\v{c}a proves that for $n$ even and at least 4 the
prism\index{prism} $C_n \times P_2$ is $(6n + 3,2)$-face antimagic and $(4n +
4,4)$-face antimagic. He also conjectures that $C_n \times P_2$ is $(2n +
5,6)$-face antimagic. In \cite{BLM} Ba\v{c}a, Lin and Miller investigate $(a,d)$-face
antimagic labelings of the convex polytopes $P_{m+ 1} \times C_n$. They show
that if these graphs are $(a,d)$-face antimagic then either $d =2$ and $a =
3n(m+ 1) + 3$ or $d=4$ and $a = 2n(m + 1)+ 4$, or $d= 6$ and $a = n(m+ 1) + 5$. They
also prove that if $n$ is even, $n\geq 4$ and $m \equiv 1$ (mod 4), $m \geq
3,$
then
$P_{m+ 1} \times C_n$ has a $(3n(m+ 1) + 3, 2)$-face antimagic labeling and
if $n$ is even, $n\geq 4$ and $m $ is odd, $m \geq
3$,
or if $n \equiv 2$ (mod 4), $n \geq 6$ and $m$ is even, $m \geq 4$, then
$P_{m+ 1} \times C_n$ has a $(3n(m+ 1) + 3, 2)$-face antimagic labeling and
a $(2n(m + 1) + 4, 4)$-face antimagic labeling.
They conjecture that $P_{m + 1} \times C_n$ has $(3n(m + 1) + 3, 2)$
and $(2n(m + 1 ) + 4, 4)$-face antimagic labelings when $m \equiv 0$ (mod
4), $n \geq 4$ and for $m$ even and $m \geq 4$ and that $P_{m + 1} \times
C_n$ has a $(n(m + 1) +
5, 6)$-face antimagic labeling when $n$ is even and at least 4.
For a plane\index{planar graph} graph $G$, Ba\v{c}a and Miller \cite{BaM3}
call a bijection $h$ from
$V(G) \cup E(G) \cup F(G)$ to $\{1,2, \ldots, |V(G)| +|E(G)| \cup |F(G)|\}$ a
{\em $d$-antimagic labeling of type} $(1,1,1)$\subindex{labeling}{$d$-antimagic of type $(1,1,1)$}
if for every number $s$ the set of $s$-sided face
weights\index{weight} is $W_s =\{a_s, a_s + d, a_s + 2d, \ldots, a_s +(f_s -1)d\}$ for some
integers $a_s$ and $d$, where $f_s$ is the number of $s$-sided faces ($W_s$
varies with $s$). They show that the prisms $C_n \times P_2 ~~ (n \geq 3)$
have a 1-antimagic labeling of type $(1,1,1)$ and that for $n \equiv 3$ (mod 4)
$C_n \times P_2$ have a $d$-antimagic labeling of type $(1,1,1)$ for $d = 2,3,4
$ and 6. They conjecture for all $n \geq 3, ~ C_n \times P_2 $
has a $d$-antimagic labeling of type $(1,1,1)$
for $d = 2,3,4, 5$ and 6.
This conjecture has been proved for the case $d=3$ and $n \neq 4$ by
Ba\v{c}a, Miller and Ryan \cite{BMR} (the case $d = 3$ and $n =4$ is open). They
also prove that for $n \geq
4$ the antiprism\index{antiprism} on $2n$ vertices has a $d$-antimagic labeling of type $(1,1,1)$
for $d =
1,2$ and 4. They conjecture the result holds for $d = 3,5 $ and 6 as well.
Ba\v{c}a, Baskoro and Miller and \cite{BBM} have proved that hexagonal planar
honeycomb graphs\index{honeycomb graph} with an even number of columns have a $2$-antimagic and
$4$-antimagic labelings of type
$(1,1,1)$. They conjecture that these honeycombs also have
$d$-antimagic labelings of type $(1,1,1)$ for $d = 1, 3$ and 5. They pose
the odd number
of columns case for $1 \leq d \leq 5$ as an open problem.
Sonntag \cite{So} has extended the notion of antimagic
labelings
to hypergraphs\index{hypergraph}. He shows that certain classes of cacti, cycle and wheel
hypergraphs have antimagic labelings.
In \cite{BMMSW} Ba\v{c}a et al. survey results on antimagic, edge-magic total and
vertex-magic total labelings.
Figueroa-Centeno, Ichishima and Muntaner-Batle \cite{FIM3} have introduced
multiplicative analogs of magic and antimagic labelings.
They define a graph $G$
of size $q$ to be
{\em product magic}\subindex{labeling}{product magic}
if there is a labeling
$f$ from $E(G)$ onto $\{1,2, \ldots, q\}$ such that, at each vertex $v$, the
product of the labels on the edges incident with $v$ is the same. They call
a graph $G$ of size $q$
{\em product antimagic}\subindex{labeling}{product antimagic}
if there is a labeling
$f$ from $E(G)$ onto $\{1,2, \ldots, q\}$ such that the
products of the labels on the edges incident at each vertex $v$ are distinct.
They prove that a graph of size $q$ is product magic if and only if $ q \leq
1$ (that is, if and only if it is $K_2,
\overline{K_n}$ or $K_2 \cup \overline{K_n}$);
$~P_n~(n \geq 4)$ is product antimagic; every 2-regular graph is product
antimagic; and, if $G$ is product antimagic, then so are $G + K_1$ and $G\odot
{\overline K_n}$. They conjecture that a connected graph of size $q$ is product
antimagic if and only if $q \geq 3.$ They also define a graph $G$ with
$p$ vertrices and $q$ edges to be
{\em product edge-magic}\subindex{labeling}{product edge-magic}
if there is a labeling $f$ from $V(G) \cup E(G)$ onto
$\{1,2, \ldots, p + q\}$ such that $f(u)\cdot f(v)\cdot f(uv)$ is a constant
for all edges $uv$ and
{\em product edge-antimagic}\subindex{labeling}{product edge-antimagic}
if there is a labeling $f$ from $V(G) \cup E(G)$ onto
$\{1,2, \ldots, p + q\}$ such that for all edges $uv$ the products
$f(u)\cdot f(v)\cdot f(uv)$ are distinct.
They prove $K_2 \cup {\overline K_n}$ is product
edge-magic, a graph of size $q$ without isolated vertices is product edge-magic
if
and only if $q \leq 1$ and that every graph other than $K_2$ and $K_2 \cup
{\overline K_n}$ is product edge-antimagic.
%\subsection*{Abbreviation}
In the table following we use these abbreviations
\begin{description}
\item [A] antimagic labeling
\item [$(a,d)$-VAT] $(a,d)$-vertex-antimagic total labeling
\item [$(a,d)$-EAV] $(a,d)$-edge-antimagic vertex labeling
\item [$(a,d)$-EAT] $(a,d)$-edge-antimagic total labeling
\item [$(a,d)$-VAE] $(a,d)$-antimagic labeling
\item [$(a,d)$-FA] $(a,d)$-face antimagic labeling
\item [$d$-AT] $d$-antimagic labeling of type $(1,1,1)$
\end{description}
A question mark following
an abbreviation indicates that the graph is conjectured to have the
corresponding property. The table was prepared by Petr Kovar and Tereza
Kovarova.
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
\begin{table}
\caption{\bf Summary of antimagic labelings}
\addcontentsline{toc}{subsubsection}{Table \thetable:
Summary of antimagic labelings}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
% \hspace*{2.7in} & \hspace*{2.8in}\\
$P_{n}$ & $(a,d)$-VAT & wide variety of $a$ and $d$ \cite{BBMMSS1}\\
& & \\
$C_{n}$ & $(a,d)$-VAT & wide variety of $a$ and $d$ \cite{BBMMSS1}\\
& & \\
generalized Petersen & $(a,d)$-VAT & \cite{BBMMSS2}\\
graph $P(n,k)$ & & \\
& & \\
prisms $C_{n}\times P_{2}$ & $(a,d)$-VAT & \cite{BBMMSS2}\\
& & \\
antiprisms & $(a,d)$-VAT & \cite{BBMMSS2} \\
& & \\
$W_{n}$ & not $(a,d)$-VAT & for $n>20$ \cite{LMSS}\\
& & \\
$P_{n}$ & $(3,2)$-EAV& \cite{SBM}\\
& not $(a,d)$-EAV & with $d>2$ \cite{SBM}\\
& & \\
$P_{2n}$ & $(n+2,1)$-EAV& \cite{SBM}\\
& & \\
$C_{n}$ & not $(a,d)$-EAV& with $d>1$ \cite{BLMS}\\
& & \\
$C_{2n}$ & not $(a,d)$-EAV& \cite{SBM}\\
& & \\
$C_{2n+1}$ & $(n+2,1)$-EAV & \cite{SBM}\\
& $(n+3,1)$-EAV & \cite{SBM}\\
& & \\
$K_{n}$ & not $(a,d)$-EAV & for $n>1$ \cite{BLMS}\\
& & \\
$K_{n,n}$ & not $(a,d)$-EAV & for $n>3$ \cite{BLMS}\\
& & \\
$W_{n}$ & not $(a,d)$-EAV & \cite{BLMS}\\
& & \\
generalized Petersen & not $(a,d)$-EAV & with $d>1$ \cite{BLMS}\\
graph $P(n,k)$ & & \\
& & \\
$P_{n}$ & not $(a,d)$-EAT & with $d>2$ \cite{BLMS}\\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of antimagic labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$P_{2n}$ & $(6n,1)$-EAT & \cite{SBM}\\
& $(6n+2,2)$-EAT & \cite{SBM}\\
& & \\
$P_{2n+1}$ & $(3n+4,2)$-EAT & \cite{SBM}\\
& $(3n+4,3)$-EAT & \cite{SBM}\\
& $(2n+4,4)$-EAT & \cite{SBM}\\
& $(5n+4,2)$-EAT & \cite{SBM}\\
& $(3n+5,2)$-EAT & \cite{SBM}\\
& $(2n+6,4)$-EAT & \cite{SBM}\\
& & \\
$C_{n}$ & $(2n+2,1)$-EAT& \cite{SBM}\\
& $(3n+2,1)$-EAT & \cite{SBM}\\
& not $(a,d)$-EAT & with $d > 5$ \cite{BLMS}\\ %?
& & \\
$C_{2n}$ & $(4n+2,2)$-EAT & \cite{SBM}\\
& $(4n+3,2)$-EAT & \cite{SBM}\\
& $(2n+3,4)$-EAT? & \cite{SBM}\\
& $(2n+4,4)$-EAT? & \cite{SBM}\\
& & \\
$C_{2n+1}$ & $(3n+4,3)$-EAT & \cite{SBM}\\
& $(3n+5,3)$-EAT & \cite{SBM}\\
& $(n+4,5)$-EAT? & \cite{SBM}\\
& $(n+5,5)$-EAT? & \cite{SBM}\\
& & \\
$K_{n}$ & not $(a,d)$-EAT & with $d>5$ \cite{BLMS}\\ %?
& & \\
$K_{n,n}$ & not $(a,d)$-EAT & with $d>5$ \cite{BLMS}\\ %?
& & \\
$W_{n}$ & not $(a,d)$-EAT & with $d>4$ \cite{BLMS}\\ %?
& & \\
generalized Petersen & not $(a,d)$-EAT & with $d>4$ \cite{BLMS}\\ %?
graph $P(n,k)$ & $((5n+5)/2,2)$-EAT & for $n$ odd, $n\geq 3$ and
$k=1,2$\cite{NB}\\ %?
& super $(4n+2,1)$-EAT & for $n\geq3$, and $1\leq k
\leq n/2$ \cite{NB}\\
& & \\
Trees & $(a,1)$-EAT? & \cite{BLMS}\\ %?
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of antimagic labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$P_{n}$ & A & for $n\geq3$ \cite{HR}\\
& & \\
$C_{n}$ & A & \cite{HR}\\
& & \\
$W_{n}$ & A & \cite{HR}\\
& & \\
$K_{n}$ & A & for $n\geq3$ \cite{HR}\\
every connected graph & A & \cite{HR}\\
except $P_{2}$ & & \\
& & \\
Hershel graph & not $(a,d)$-VAE & \cite{BW1} \cite{BW3}\\
& & \\
parachutes $P_{g,b}$ & $(a,d)$-VAE & for certain classes \cite{BW1} \cite{BW3}\\
(see \S \ref{parachutes}) & & \\
& & \\
prisms $C_{n}\times P_{2}$ & $((7n+4)/2,1)$-VAE& $n\geq 3$, $n$ even \cite{BW2} \cite{BHo1}\\
& $((5n+5)/2,2)$-VAE& $n\geq 3$, $n$ odd \cite{BW2} \cite{BHo1}\\
& $((3n+6)/2,3)$-VAE& $n\geq 3$, $n$ even \cite{BHo1}\\
& $((n+7)/2,4)$-VAE?& $n\geq 7$, \cite{BW3}
\cite{BHo1}\\
& & \\
generalized Petersen & $((3n+6)/2,3)$-VAE & $n\geq8$, $n\equiv 0(\mod 4)$ \cite{BHo3}\\ %kongruent
graph $P(n,2)$ & & \\
& & \\
$C_{n}$ & not $(a,d)$-VAE & $n$ even \cite{BW5} \\
& & \\
$C_{2n+1}$ & not $(n+2,1)$-VAE & $n$ even \cite{BW5} \\
& & \\
$P_{2n}$ & not $(a,d)$-VAE & \cite{BW5} \\
& & \\
$P_{2n+1}$ & $(n,1)$-VAE & \cite{BW5} \\
& & \\
stars & not $(a,d)$-VAE & \cite{BW5} \\
& & \\
$C_{3}^{(k)},C_{4}^{(k)}$ & not $(a,d)$-VAE & \cite{BW5} \\[1mm]
& & \\
$K_{n,n+2}$ & $\left(\frac{(n+1)(n^{2}-1)}{2},n+1\right)$-VAE &$n\geq3$, $n$ odd \cite{BW5} \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of antimagic labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$K_{3,3}$ & not $(a,d)$-VAE & \cite{BW5} \\
& & \\
$K_{4}$ & not $(a,d)$-VAE & \cite{BW5} \\
& & \\
Petersen graph & not $(a,d)$-VAE & \cite{BW5} \\
& & \\
$W_{n}$ & not $(a,d)$-VAE & $n>3$ \cite{LMSS} \\
& & \\
antiprism on $2n$ & $(6n+3,2)$-VAE &$n\geq 3$, $n\not\equiv 2(\mod 4)$ \cite{Bac5} \\
vertices (see \S \ref{antiprism}) & $(4n+4,4)$-VAE &$n\geq 3$, $n\not\equiv 2(\mod 4)$ \cite{Bac5} \\ %put label on page 61
& $(2n+5,6)$-VAE? & $n\geq 4$ \cite{Bac5} \\
& $(6n+3,2)$-VAE? & $n\geq 6$, $n\not\equiv 2 (\mod
4)$ \cite{Bac5} \\
& $(4n+4,4)$-VAE? & $n\geq 6$, $n\not\equiv 2 (\mod
4)$
\cite{Bac5} \\ %asi chyba v textu
& & \\
$Q_{n}^{m}$ (see \S \ref{polytope}) & $(7n(m+1)/2+2,1)$-FA & $m\geq 3$, $n\geq 3$, $m$ odd \cite{BaM2} \\
& $(7n(m+1)/2+2,1)$-FA & $m\geq 4$, $n\geq 4$, $m,n$ even \cite{BaM2} \\
& $((5n(m+1)+5)/2,2)$-FA? & $m\geq 2$,
$n\geq 3$, $m$ even, $n$ odd \cite{BaM2} \\
& $((n(m+1)+7)/2,4)$-FA? & $m\geq 2$,
$n\geq 3$, $m$ even, $n$ odd \cite{BaM2} \\
& $(3n(m+1)/2+3,3)$-FA? & $m>1$, $n>4$,
$n$ even \cite{BaM2} \\
& $(3n(m+1)/2+3,3)$-FA? & $m>1$, $n>3$,
$m$ odd, $n$ odd \cite{BaM2} \\
& & \\
$C_{n}\times P_{2}$ & $(6n+3,2)$-FA & $n\geq 4$, $n$ even \cite{Bac7} \\
& $(4n+4,4)$-FA & $n\geq 4$, $n$ even \cite{Bac7} \\
& $(2n+5,6)$-FA? & \cite{Bac7} \\
& & \\
$P_{m+1}\times C_{n}$ & $(3n(m+1)+3,2)$-FA & $n\geq 4$, $n$ even and \cite{BLM} \\
& & $m\geq 3$, $m \equiv 1(\mod 4)$, \\
& $(3n(m+1)+3,2)$-FA and & $n\geq 4$, $n$ even and \cite{BLM} \\
& $(2n(m+1)+4,4)$-FA & $m\geq 3$, $m$ odd, \cite{BLM} \\
& & or $n\geq 6$, $n \equiv 2(\mod 4)$ and \\
& & $m\geq 4$, $m$ even \\
& $(3n(m+1)+3,2)$-FA? & $m\geq 4$, $n\geq 4$, $m\equiv 0(\mod 4)$ \cite{BLM} \\
& $(2n(m+1)+4,4)$-FA? & $m\geq 4$, $n\geq 4$, $m\equiv 0(\mod 4)$ \cite{BLM} \\
& $(n(m+1)+5,6)$-FA? & $n\geq 4$, $n$ even \cite{BLM} \\
\hline
\end{tabular}
\end{center}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
\begin{table}
%\caption{\bf Summary of antimagic labelings}
\caption{\bf continued}
%\vspace{0.25in}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\em Graph} & {\em Labeling} & {\em Notes}\\
\hline
$P_{n}\times P_{2}$ & $d$-AT & with $d = 1$ \cite{BaM3} \\
& $d$-AT & with $d = 2,3,4$ and $6$ \cite{BaM3} \\
& & for $n\equiv 3$ (mod 4)\\
& $d$-AT? & with $d = 2,3,4,5,6$ for $n\geq 3$
\cite{BaM3}\\
& $d$-AT & with $d = 3$ for $n\geq 4$ \cite{BMR}\\
& & \\
antiprism on $2n$ & $d$-AT & with $d = 1,2$ and $4$ for $n\geq 4$ \cite{BMR} \\
vertices & & \\
& $d$-AT? & with $d = 3,5$ and $6$ for $n\geq 4$
\cite{BMR} \\
& & \\
honeycomb graphs with & $d$-AT & with $d = 3,4$ \cite{BBM}\\
even number of columns & & \\
&$d$-AT? & with $d = 1,3$ and $5$ \cite{BBM}\\
\hline
\end{tabular}
\end{center}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of file