% Begin of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Encoding: ASCII
% Tex format: LaTeX
% Last modified: August 5, 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Variations of Graceful Labelings}
\subsection{$\alpha$-labelings}\label{alpha_labelings}
In \cite{Ro1} Rosa defined an {\em $\alpha$-labeling}\index{$\alpha$-labeling}
to be a graceful
labeling with the additional property that there exists an integer $k$ so that for each
edge $xy$ either $f(x) \leq k < f(y)$ or $f(y) \leq k < f(x)$.
(Other names for such labelings are {\em balanced}\subindex{labeling}{balanced}
and {\em interlaced}\subindex{labeling}{interlaced}.)
It follows that such a $k$ must be the
smaller of the two vertex labels that yield the edge labeled 1.
Also, a graph with an $\alpha$-labeling is necessarily bipartite and
therefore can not contain a cycle of odd length.
Wu \cite{Wu1} has shown that a necessary condition for a bipartite
graph with $n$ edges and degree sequence $d_1,d_2, \ldots, d_p$ to have an
$\alpha$-labeling is that the gcd$(d_1,d_2, \ldots, d_p, n)$ divides
$n(n-1)/2$.
A common theme in graph labeling papers is to build up graphs that have desired
labelings from pieces with particular properties. In these situations, starting
with a graph that possesses an $\alpha$-labeling is a typical approach.
(See \cite{CHR}, \cite{Gr2}, \cite{CLY} and \cite{JR}.)
Moreover, Jungreis and Reid \cite{JR} showed how sequential labelings of graphs
(see Section~\ref{sequential_labelings}) can often be obtained by modifying $\alpha$-labelings
of the graphs.
Graphs with $\alpha$-labelings have proved to be useful in the development
of the theory of graph decompositions\index{decomposition}.
Rosa \cite{Ro1}, for instance, has shown that if $G$ is a graph
with $q$ edges and has an $\alpha$-labeling, then for every
natural number $p$,
the complete graph $K_{2qp+1}$ can be decomposed into copies of $G$ in
such a way
that the automorphism group of the decomposition itself contains
the cyclic group of order $p$.
In the same vein El-Zanati and Vanden Eynden \cite{EV1} proved that if $G$
has $q$ edges and admits an $\alpha$-labeling then $K_{qm,qn}$ can be
partitioned into subgraphs isomorphic to $G$ for all positive integers $m$
and $n$. Although
a proof of Ringel's conjecture that every tree has a graceful labeling has
withstood many attempts, examples of trees that do not have $\alpha$-labelings
are easy to construct (see \cite{Ro1}).
As to which graphs have $\alpha$-labelings, Rosa \cite{Ro1} observed that the
$n$-cycle has an $\alpha$-labeling if and only if $n \equiv 0$
(mod 4) while $P_n$ always has an
$\alpha$-labeling. Other familiar graphs that have $\alpha$-labelings
include caterpillars\index{caterpillar} \cite{Ro1},
the $n$-cube\index{$n$-cube} \cite{K1}, $B_{4n+1}$ (i.e., books with
$4n+1$ pages) \cite{GJ}, $C_{2m} \cup C_{2m}$, and $C_{4m} \cup C_{4m}
\cup C_{4m}$ for all $m>1$ \cite{K2},
$P_n \times Q_n$ \cite{Mah}, $K_{1,2k} \times Q_n$ \cite{Mah},
$C_{4m} \cup C_{4m} \cup
C_{4m} \cup C_{4m}$ \cite{LV}, $C_{4m} \cup C_{4n+2} \cup C_{4r+2},
C_{4m} \cup C_{4n} \cup C_{4r}$ when $m +n \leq r$ \cite{AK4}, $
C_{4m} \cup
C_{4n} \cup C_{4r}\cup C_{4s}$ when $m \geq n+r+s$ \cite{ACE}, $C_{4m} \cup
C_{4n} \cup C_{4r+2} \cup C_{4s+2}$ when $m\geq n+r+s +1$ \cite{ACE},
$((m + 1)^2 +1)C_4$ for all $m$ \cite{Zhi}, $k^2C_4$ for all $k$ \cite{Zhi},
and $(k^2 + k)C_4$ for all $k$ \cite{Zhi}. Abrham and Kotzig \cite{AK2} have shown
that $kC_4$ has an $\alpha$-labeling for $ 1 \leq k \leq 10$ and
that
if $kC_4$ has an $\alpha$-labeling then so does $(4k+1)C_4, (5k+1)C_4$ and
$(9k+1)C_4$. Eshghi \cite{Es2} proved that $5C_{4k}$ has an $\alpha$-labeling
for all $k$.
Figueroa-Centeno, Ichishima and
Muntaner-Batle \cite{FIM6} have shown
that if $m \equiv 0$ (mod 4) then the one-point union\index{one-point union}
of 2, 3 or 4 copies of $C_m$ admits an
$\alpha$-valuation and if
$m \equiv 2$ (mod 4) then the one-point union of 2 or 4
copies of $C_m$ admits an $\alpha$-valuation.
They conjecture that the one-point union of $n$ copies of $C_m$ admits an
$\alpha$-valuation
if and only if $mn \equiv 0$ (mod 4).
Zhile \cite{Zhi} uses $C_m(n)$ to denote the connected graph all of whose
blocks
are $C_m$ and whose block-cutpoint-graph is a path. He proves that for all
positive integers $m$ and $n$, ~$C_{4m}(n)$ has an $\alpha$-labeling but
$C_m(n)$ does not have an $\alpha$-labeling when $m$ is odd.
Abrham and Kotzig \cite{AK4} have proved that $C_m \cup C_n$ has an
$\alpha$-labeling if and only if both $m$ and $n$ are even and $m +n
\equiv 0$ (mod 4).
Kotzig \cite{K2} has also shown that
$C_4 \cup C_4 \cup C_4$ does not have an $\alpha$-labeling.
He asked if $n = 3$ is the only integer such that the disjoint union of
$n$ copies of $C_4$ does not have an $\alpha$-labeling. This was confirmed
by Abrham and Kotzig in \cite{AK3}. Eshghi \cite{Es1} proved that every 2-regular
bipartite
graph with 3 components has an $\alpha$-labeling if and only if the number of
edges is a multiple of four except for $C_4 \cup C_4 \cup
C_4$.
Jungreis and Reid \cite{JR} investigated the
existence of $\alpha$-labelings for graphs of the form $P_m \times P_n,
C_m \times P_n,$ and $C_m \times C_n$ (see also \cite{Ga4}). Of course, the
cases involving $C_m$ with $m$ odd are not bipartite, so there is no
$\alpha$-labeling. The only unresolved cases among these three families
are $C_{4m+2} \times P_{2n+1}$ and $C_{4m+2} \times C_{4n+2}$. All other
cases result in $\alpha$-labelings.
Balakrishman \cite{Ba} uses the notation $Q_n(G)$ to denote the graph
$P_2 \times P_2 \times \cdots \times P_2 \times G$ where $P_2$ occurs
$n -1$ times. Snevily \cite{Sn1} has shown that the graphs
$Q_n(C_{4m}$) and the cycles $C_{4m}$ with the path $P_n$
adjoined at each vertex have $\alpha$-labelings. He also has shown \cite{Sn2}
that compositions of
the form $G[\overline{K_{n}}]$ have an $\alpha$-labeling whenever $G$
does (see \S \ref{product_related_graphs} for the definition of composition). Balakrishman and Kumar
\cite{BK1} have shown that all graphs of the form $Q_n(G)$ where $G$ is
$K_{3,3}, K_{4,4}$, or $P_m$ have an $\alpha$-labeling. Balakrishman \cite{Ba}
poses the following two problems. For which graphs $G$ does $Q_n(G)$ have an
$\alpha$-labeling? For which graphs $G$ does $Q_n(G)$ have a graceful
labeling? Rosa \cite{Ro1} has shown that $K_{m,n}$ has an $\alpha$-labeling (see
also \cite{Bar3}). Barrientos \cite{Bar3} has shown that for $n$ even the graph obtained
from the wheel $W_n$ by attaching a pendant edge at each vertex has an
$\alpha$-labeling.
Qian \cite{Q} has proved that quadrilateral snakes\subindex{snake}{quadrilateral}
have $\alpha$-labelings.
Fu and Wu \cite{FW} showed that if $T$ is a tree that has an $\alpha$-labeling
with partite sets $V_1$ and $V_2$ then the graph obtained from $T$ by
joining new vertices $w_1, w_2, \ldots, w_k$ to every vertex of $V_1$ has
an $\alpha$-labeling. Similarly, they prove that the graph
obtained from $T$ by joining new vertices $w_1,w_2, \ldots, w_k$ to the
vertices of $V_1$ and new vertices $u_1,u_2, \ldots, u_t$ to
every vertex of $V_2$ has an $\alpha$-labeling. They also prove
that if one of the new vertices of either of these two graphs is
replaced by
a star and every vertex of the star is joined to the vertices of $V_1$ or
the vertices of both $V_1$ and $V_2$, the resulting graphs have
$\alpha$-labelings. Fu and Wu \cite{FW} further show that if $T$ is a tree with
an $\alpha$-labeling and the sizes of the two partite sets of $T$ differ at
by at most 1, then $T \times P_m$ has an $\alpha$-labeling.
Barrientos \cite{Bar4} defines a {\em chain graph}\index{chain graph} as one
with blocks $B_1,
B_2,
\ldots, B_m$ such that for every $i,~ B_i$ and $B_{i + 1}$ have
a common vertex in such a way that the block-cutpoint\index{block-cutpoint}
graph is a path. He shows
that if $B_1, B_2, \ldots, B_m$ are blocks that have $\alpha$-labelings then
there exists a chain graph $G$ with blocks $B_1, B_2, \ldots, B_m$ that has an
$\alpha$-labeling. He also shows that if $B_1, B_2, \ldots, B_m$ are complete
bipartite graphs, then any chain graph $G$ obtained by concatenation of these
blocks has an $\alpha$-labeling.
Wu (\cite{Wu2} and \cite{Wu3}) has given a number of methods for constructing
larger
graceful graphs from graceful graphs.
Let $G_1, G_2, \ldots,
G_p$ be
disjoint connected graphs.
Let $w_i$ be in $G_i$ for $1\leq i \leq
p$. Let $w$ be a new vertex not in any $G_i$. Form a new graph
$\oplus_w(G_1,G_2, \ldots, G_p)$
by adjoining to the graph $G_1\cup G_2
\cup \cdots \cup G_p$ the
edges $ww_1, ww_2, \ldots, ww_p$.
In the case where each of
$G_1, G_2, \ldots,
G_p$ is
isomorphic to a graph $G$ which has an $\alpha$-labeling and
each $w_i$ is the isomorphic image of the same vertex in $G_i$,
Wu shows that the resulting graph is graceful.
If $f$ is an $\alpha$-labeling of a graph,
the integer $k$ with
the property that for any edge $uv$ either $f(u) \leq k < f(v)$ or $f(v)
\leq k < f(u)$ is called the {\em boundary value}\index{boundary value}
or {\em critical number}\index{critical number} of $f$. Wu \cite{Wu2} has
also shown that if $G_1, G_2, \ldots, G_p$ are graphs of the same
order and have $\alpha$-labelings where the labelings for each pair of
graphs $G_i$ and
$G_{p-i+1}$ have the same boundary value for $1 \leq i \leq n/2$, then
$\oplus_w(G_1,G_2, \ldots, G_p)$ is graceful.
In \cite{Wu4} Wu proves that if $G$ has $n$ edges and $n + 1$ vertices and $G$ has an
$\alpha$-labeling with boundary value
$\lambda,$ where $|n -2\lambda -1 | \leq 1$, then $G \times P_m$ is graceful for
all $m$.
Snevily \cite{Sn2} says that a graph
$G$ {\em eventually has an $\alpha$-labeling}\subindex{$\alpha$-labeling}{eventually} provided that there
is a graph $H$, called a {\em host}\index{host graph} of $G$, which has
an $\alpha$-labeling and
that the edge set of $H$
can be partitioned into subgraphs isomorphic to $G$. He defines the
$\alpha$-{\em labeling number of}\index{labeling number} $G$ to be $G_{\alpha} = {\mbox
{min}}\{t :
{\mbox {there
is a host }} H$ of $G$ with $|E(H)| = t|G|\}$. Snevily proved that even
cycles have $\alpha$-labeling number at most 2 and he conjectured that
every bipartite graph has an $\alpha$-labeling number. This conjecture was
proved by El-Zanati, Fu and Shiue \cite{EFS}. There are no known examples of a
graph $G$ with $G_{\alpha} > 2$.
Given two bipartite graphs $G_1$ and $G_2$ with partite sets $H_1$ and
$L_1$
and $H_2$ and $L_2$, respectively, Snevily \cite{Sn1} defines their
{\em weak tensor product}\index{weak tensor product}
$G_1 \overline{\bigotimes} G_2$ as the bipartite graph with vertex set
$(H_1 \times H_2, L_1 \times L_2)$ and with edge $(h_1,h_2)(l_1,l_2)$ if
$h_1l_1 \in E(G_1)$ and $h_2l_2 \in E(G_2)$.
He proves that if $G_1$ and $G_2$ have $\alpha$-labelings then so does $G_1 \overline{\bigotimes} G_2$.
This result considerably enlarges the class of graphs known to have $\alpha$-labelings.
The sequential join\index{sequential join}
of graphs $G_1,G_2,\ldots,G_n$ is formed from $G_1 \cup G_2 \cup \cdots \cup G_n$
by adding edges joining each vertex of $G_i$ with each vertex of $G_{i+1}$ for $1 \leq i \leq n-1$.
Lee and Wang \cite{LWa} have shown that for all $n \geq 2$ and any positive
integers $a_1, a_2, \ldots, a_n$ the sequential join of the graphs
$\overline{K}_{a_1},
\overline{K}_{a_2}, \ldots, \overline{K}_{a_n}$ has an $\alpha$-labeling.
In \cite{Ga2} Gallian and Ropp conjectured that every graph obtained by
adding a single pendant edge\index{pendant edge} to one or more vertices of a cycle is
graceful. Qian \cite{Q} has proved this conjecture and in the case that the
cycle is even he showns the graphs have an $\alpha$-labeling. He further
proves that for $n$ even any graph obtained from an $n$-cycle
by adding one or more pendant edges at some vertices
has an $\alpha$-labeling as long as at least one vertex has
degree 3 and one vertex has degree 2.
For any tree $T(V,E)$ whose vertices are properly 2-colored Rosa and
\v{S}ir\'{a}\v{n}
\cite{RS} define a
{\em bipartite labeling}\index{bipartite labeling}\subindex{labeling}{bipartite}
of $T$ as a
bijection $f: V \rightarrow \{0, 1, 2, \ldots, |E|\}$ for which there is
a $k$ such that whenever $f(u) \leq k \leq f(v)$, then $u$ and $v$ have
different colors. They define the {\em $\alpha$-size}\index{$\alpha$-size}
of a tree $T$ as the
maximum number of distinct values of the induced edge labels $|f(u) -
f(v)|, uv \in E$, taken over all bipartite labelings $f$ of $T$. They
prove that the $\alpha$-size of any tree with $n$ edges is at least $5(n +
1)/7$ and that there exist trees whose $\alpha$-size is at most $(5n + 9)/6$.
They conjectured that minimum of the $\alpha$-sizes over all trees with $n$
edges is asymptotically $5n/6$. This conjecture has been proved for trees
of maximum degree 3 by Bonnington and \v{S}ir\'{a}\v{n} \cite{BoS}. Heinrich and Hell
\cite{HeH} defined the {\em gracesize}\index{gracesize}
of a graph $G$ with $n$ vertices as the maximum, over all
bijections
$f\colon
V(G) \rightarrow \{1, 2, \ldots, n\}$, of the number of distinct values
$\vert
f(u)-f(v)\vert $
over all edges $uv$ of $G$. So, from Rosa and
\v{S}ir\'{a}\v{n}'s result, the gracesize of any tree with $n$
edges is at least $5(n + 1)/7$.
In \cite{GPW} Gallian weakened the condition for an $\alpha$-labeling somewhat
by defining a {\em weakly $\alpha$-labeling}\index{weakly $\alpha$-labeling}
\subindex{$\alpha$-labeling}{weakly}
as a graceful labeling for which there is an integer $k$ so that for each edge $xy$
either $f(x) \leq k \leq f(y)$ or $f(y) \leq k \leq f(x)$. Unlike
$\alpha$-labelings, this condition
allows the graph to have an odd cycle, but still places a severe
restriction on the structure of the graph; namely, that the vertex with
the label $k$ must be on every odd cycle.
Gallian, Prout and Winters \cite{GPW} showed that the prisms $C_n \times P_2$
with a vertex deleted have $\alpha$-labelings.
The same paper reveals that $C_n \times P_2$ with an edge deleted from a cycle
has an $\alpha$-labeling when $n$ is even and a weakly $\alpha$-labeling when $n > 3$.
A special case of $\alpha$-labeling called strongly graceful was
introduced by Maheo \cite{Mah} in 1980. A graceful labeling $f$ of a graph $G$ is
called
{\em strongly graceful}\index{strongly graceful labeling}\subindex{labeling}{strongly graceful}
if $G$ is bipartite with two partite sets
$A$ and $B$ of the same order $s$, the number of edges is $2t + s,$
there is an integer $k$ with $t-s \leq k \leq t + s -1$ such that if $a \in
A, f(a) \leq k$, and if $b \in B, f(b) > k,$ and there is an involution
$\pi$ which is an automorphism of $G$ such that: $\pi$ exchanges $A$ and
$B$ and the $s$ edges $a\pi(a)$ where $a \in A$ have as labels the
integers between $t + 1$ and $t + s$.
Maheo's main
result is that if $G$ is strongly graceful then so is $G \times Q_n$.
In particular, she proved that $(P_n \times Q_n) \times
K_2$, $B_{2n}$ and $B_{2n} \times Q_n$ have strongly graceful labelings.
El-Zanati and Vanden Eynden \cite{EV2} call a strongly graceful labeling
a {\em strong $\alpha$-labeling}.
\subindex{strong}{$\alpha$-labeling}\subindex{$\alpha$-labeling}{strong}
They show that if $G$ has a
strong $\alpha$-labeling, then $G \times P_{n}$ has an
$\alpha$-labeling. They show that $K_{m,2}\times K_{2}$ has a strong
$\alpha$-labeling and that $K_{m,2}\times P_{n}$ has an
$\alpha$-labeling. They also show that if $G$ is a bipartite graph
with one more vertex than the number of edges, and if $G$ has an
$\alpha$-labeling
such that the cardinalities of the sets of the corresponding
bipartition of the vertices differ by at most 1, then $G \times
K_{2}$ has a strong $\alpha$-labeling and $G \times P_{n}$ has an
$\alpha$-labeling. El-Zanati and Vanden Eynden \cite{EV2} also note that
$K_{3,3}\times K_{2}$, $K_{3,4}\times K_{2}$, $K_{4,4}\times K_{2}$,
and $C_{4k}\times K_{2}$ all have strong $\alpha$-labelings.
El-Zanati and Vanden Eynden proved that $K_{m,2} \times Q_n$ has a strong $
\alpha$-valuation and that $K_{m,2} \times P_n$ has an $\alpha$-labeling
for all $n$. They also prove that if $G$ is a connected bipartite graph
with partite sets of odd order such that in each partite set each
vertex has the same degree, then $G \times K_2$ does not have a strong
$\alpha$-valuation.
As a corollary they have that $K_{m,n} \times K_2$ does not have a strong
$\alpha$-valuation when $m$ and
$n$ are odd.
An $\alpha$-labeling $f$ of a graph $G$ is called
{\em free}\index{free $\alpha$-labeling}\subindex{$\alpha$-labeling}{free}
by El-Zanati and Vanden Eynden in \cite{EV3}
if the critical number $k$ (in the definition of $\alpha$-labeling)
is greater than 2 and if neither 1 nor $k-1$ is used in the
labeling. Their main result is that the union\index{union} of graphs with free
$\alpha$-labelings has an $\alpha$-labeling. In particular, they show
that $K_{m,n}$, $m>1$, $n>2,$ has a free $\alpha$-labeling. They also
show that $Q_{n}$, $n\geq 3$, and $K_{m,2} \times Q_{n}$, $m >1$, $n
\geq 1$, have free $\alpha$-labelings. El-Zanati
[personal communication] has shown that the Heawood graph\index{Heawood graph} has a free
$\alpha$-labeling.
For connected bipartite graphs Grannell, Griggs and Holroyd \cite{GGH} introduced
a labeling that lies between
$\alpha$-labelings and graceful labelings. They call a vertex labeling $f$
of a bipartite graph $G$ with $q$ edges and partitite sets $D$ and $U$
{\em gracious}\index{gracious labeling}\subindex{labeling}{gracious}
if $f$ is a bijection from the vertex set of $G$ to $\{0,1, \ldots,
q\}$ such that the set of edge labels induced by $f(u) - f(v)$ for every edge
$uv$
with $u \in U$ and $v \in D$ is $\{1,2, \ldots,q\}$. Thus a gracious labeling
of $G$ with partite sets $D$ and $U$ is
a graceful labeling in which every vertex in $D$ has a label lower than every
adjacent vertex. They verified by computer that every tree of size up to 20 has
a gracious labeling. This led them to conjecture that every tree has a gracious
labeling. For any $k > 1$ and any tree $T$ Grannell et al. say that $T$
has a {\em gracious $k$-labeling}\index{gracious $k$-labeling} if the verticies of $T$ can be
partitioned into sets $D$ and $U$ in such a way that there is a
function
$f$ from the verticies of $G$ to the
integers modulo $k$ such that the edge labels induced by $f(u) - f(v)$ where
$u \in U$ and $v \in D$ has the
following properties: the number of edges labeled with 0 is one less than the
number of verticies labeled with 0 and for each nonzero integer $x$ the
number of edges labeled with $x$ is the same as the number of verticies labeled
with $x$. They prove that every nontrivial tree has a $k$-gracious labeling for
$k = 2,3,4,5$ and that caterpillars\index{caterpillar} are $k$-gracious for all $k \geq 2$.
The same labeling that is called gracious by Grannell, Griggs and
Holroyd is called a
{\em near $\alpha$-labeling}\index{near $\alpha$-labeling}\subindex{$\alpha$-labeling}{near}
by El-Zanati,
Kenig and Vanden Eynden \cite{EKV}.
They prove
that if $G$ is a graph with $n$ edges that has a near $\alpha$-labeling then
there exists a cyclic
$G$-decomposition\index{cyclic $G$-decomposition}\index{decomposition}
of $K_{2nx + 1}$ for all positive
integers $x$ and a cyclic $G$-decomposition of $K_{n,n}$. They further prove
that if $G$ and $H$ have near $\alpha$-labelings, then so does their weak tensor
product\index{weak tensor product} with respect to the corresponding vertex
partitions. They conjecture
that every tree has a near $\alpha$-labeling\index{near $\alpha$-labeling}.
Another kind of labelings for trees was introduced by
Ringel, Llado and Serra \cite{RLS} in an approach to proving their
conjecture $K_{n,n}$ is edge-decomposable\index{edge-decomposition} into $n$ copies of any given
tree with $n$ edges. If $T$ is a tree with $n$ edges and partite sets
$A$ and $B$, they define a labeling $f$ from the set of
vertices to $\{1, 2, \ldots, n\}$ to be a
{\em bigraceful}\subindex{labeling}{bigraceful} labeling of
$T$ if $f$ restricted to $A$ is injective, $f$ restricted to $B$ is
injective, and the edge labels given by $f(y) - f(x)$ where $yx$ is an
edge with $y$ in $B$ and $x$ in $A$ is the set $\{0, 1, 2, \ldots, n-1\}$.
(Notice that this terminology conflicts with that given in Section~\ref{miscellaneous_results}
In particular, the Ringel, Llado and Serra bigraceful does not imply the
usual graceful.) Among the graphs
that they show are bigraceful are: lobsters, trees of diameter at most 5,
stars $S_{k,m}$ with $k$ spokes of paths of length $m$, and complete
$d$-ary
trees for $d$ odd. They also prove that if $T$ is a tree then there is a
vertex $v$ and a nonnegative integer $m$ such that the addition of $m$
leaves to $v$ results in a bigraceful tree. They conjecture that all
trees are bigraceful.
\subsection{$k$-graceful Labelings}\label{k_graceful_labelings}
A natural generalization of graceful graphs is the notion of $k$-graceful
graphs introduced independently by Slater \cite{Sl2} in 1982 and by Maheo and
Thuillier \cite{MT} in 1982.
A graph $G$ with $q$ edges is {\em $k$-graceful}\index{$k$-graceful}
if there is labeling $f$ from the vertices of $G$ to
$\{0,1,2,\ldots,q+k-1\}$ such that
the set of edge labels induced by the absolute value of the difference of
the labels of adjacent vertices
is $\{k, k+1,\ldots,q+k-1\}$.
Obviously, 1-graceful is graceful and it is readily shown that any graph that has an $\alpha$-labeling is $k$-graceful for all $k$.
Graphs that are $k$-graceful for all $k$ are sometimes called {\em arbitrarily graceful}\subindex{graph}{arbitrarily graceful}.
Ng \cite{N2} has shown that there are graphs that are $k$-graceful for all $k$
but do not have an $\alpha$-labeling.
Results of Maheo and Thuillier \cite{MT} together with those of Slater \cite{Sl2}
show that: $C_n$ is $k$-graceful if and only if either
$n \equiv 0$ or $1$ (mod 4) with $k$ even and $k \leq (n-1)/2$, or
$n \equiv 3$ (mod 4) with $k$ odd and $k \leq (n^2-1)/2$.
Maheo and Thuillier \cite{MT} also proved that the wheel $W_{2k+1}$
is $k$-graceful and conjectured that $W_{2k}$ is $k$-graceful when
$k \neq 3$ or $k \neq 4$. This conjecture was proved by Liang, Sun and
Xu \cite{LSX}.
Kang \cite{Ka} proved that $P_m \times C_{4n}$ is $k$-graceful for all $k$.
Lee and Wang \cite{LW} showed that all pyramids, lotuses and diamonds are
$k$-graceful and Liang and Liu \cite{LL} have shown that
$K_{m,n}$ is $k$-graceful.
Bu, Gao and Zhang \cite{BGZ} have proved that $P_n \times P_2$ and $(P_n
\times P_2) \cup (P_n \times P_2)$ are $k$-graceful for all $k$.
Acharya (see
\cite{A3}) has shown that a $k$-graceful Eulerian graph with $q$
edges must satisfy one of the following conditions: $q \equiv 0$ (mod 4),
$q \equiv 1$ (mod 4) if $k$ is even, or
$q \equiv 3$ (mod 4) if $k$ is odd. Bu, Zhang and He \cite{BZH} have shown
that an even cycle with a fixed number of pendant edges adjoined to each
vertex is $k$-graceful.
Several authors have investigated the $k$-gracefulness of various classes
of subgraphs of grid graphs\index{grid}.
Acharya \cite{A1} proved that all 2-dimensional polyminoes\index{polyminoes}
that are convex and Eulerian are $k$-graceful for all $k$;
Lee \cite{L1} showed that Mongolian tents\index{Mongolian tent}
and Mongolian villages\index{Mongolian village} are
$k$-graceful for all $k$ (see Section~\ref{product_related_graphs} for definitions);
Lee and K. C. Ng \cite{LNK} proved that all Young tableaus\index{Young tableau}
(see \S \ref{product_related_graphs} for the defintions) are $k$-graceful for
all $k$. (A special case of this is $P_n \times P_2$.)
Lee and H. K. Ng
\cite{LNH} subsequently generalized these results on Young
tableaus to a wider class of planar graphs.
Let $c, m, p_1,p_2, \ldots, p_m$ be positive integers. For $i =
1,2,\ldots,m$, let $S_i$ be a set of $p_i + 1$ integers and let $D_i$ be
the set of positive differences of the pairs of elements of $S_i$. If
all these differences are distinct then the system $D_1, D_2, \ldots,
D_m$ is called a {\em perfect system of difference sets\index{perfect system of difference sets}
starting at $c$}
if the union of all the sets $D_i$ is \(c, c+ 1, \ldots, c -1 + \sum_{i =
1}^{m}\left(\begin{array}{c} p_i + 1 \\ 2 \end{array} \right)\).
There is a relationship between
$k$-graceful graphs and perfect systems
of difference sets. A perfect system of difference sets starting with $c$
describes a $c$-graceful
labeling of a graph that is decomposable into complete subgraphs\index{subgraph}.
A survey of perfect systems of difference sets is given in \cite{Ab}.
Acharya and
Hegde \cite{AH3} generalized $k$-graceful to
{\em $(k,d)$-graceful labelings}\index{$(k,d)$-graceful labeling}\subindex{labeling}{$(k,d)$-graceful}
by permitting the vertex labels to belong to $\{0,1,2,\ldots,k+(q-1)d\}$
and requiring the set
of edge labels induced by the absolute value of the difference of labels of adjacent vertices to be
$\{k, k+d, k+2d, \ldots, k+(q-1)d\}$.
They also introduce an analog of $\alpha$-labelings in the obvious way.
Notice that a (1,1)-graceful labeling is a graceful labeling and a
$(k,1)$-graceful labeling is a $k$-graceful labeling. Bu and Zhang
\cite{BZ} have shown that $K_{m,n}$ is $(k,d)$-graceful for all $k$
and $d$; for $n > 2, K_n$ is $(k,d)$-graceful if and only if $k
=d $
and $n \leq 4$; if $m_i,n_i \geq 2$ and max$\{m_i,n_i\} \geq 3$, then
$K_{m_1,n_1} \cup K_{m_2,n_2} \cup \cdots \cup K_{m_r,n_r}$ is
$(k,d)$-graceful for all $k, d,$ and $r$; if $G$ has an
$\alpha$-labeling, then $G$ is $(k,d)$-graceful for all $k$ and $d$; a
$k$-graceful graph is a $(kd,d)$-graceful graph; a $(kd,d)$-graceful
connected graph is $k$-graceful; and a $(k,d)$-graceful graph with $q$
edges that is not bipartite must have $k \leq (q-2)d$.
Let $T$ be a tree
with adjacent vertices $u_0$ and $v_0$ and pendant vertices $u$ and $v$ such
that the length of the path $u_0-u$ is the same as the length of the path
$v_0-v$. Hegde and Shetty \cite{HeSh4}
call the graph obtained from $T$ by deleting $u_0v_0$ and joining $u$ and
$v$ is called an
{\em elementary parallel transformation}\index{elem. parallel transformation}
of $T$. They say that a tree $T$
is a {\em $T_p$-tree}\index{$T_p$-tree} if it can be transformed into a path by a sequence
of elementary parallel transformations. They prove that every $T_p$-tree is
$(k,d)$-graceful for all $k$ and $d$ and every graph obtained from a $T_p$-tree
by subdividing each edge of the tree is
$(k,d)$-graceful for all $k$ and $d$.
Hegde \cite{Heg6} has proved the following: if a graph is $(k,d)$-graceful for
odd $k$ and even $d$, then the graph is bipartite; if a graph is
$(k,d)$-graceful and contains $C_{2j + 1}$ as a subgraph, then $k
\leq jd(q-j-1); ~K_n$ is $(k,d)$-graceful if and only if $n \leq 4;
~C_{4t}$ is $(k,d)$-graceful for all $k$ and $d;
~C_{4t +1}$ is $(2t,1)$-graceful;
$C_{4t +2}$ is $(2t-1,2)$-graceful; and
$C_{4t +3}$ is $(2t+ 1,1)$-graceful.
Hegde \cite{Heg4} calls a $(k,d)$-graceful graph
{\em $(k,d)$-balanced}\subindex{graph}{$(k,d)$-balanced}
if it has a $(k,d)$-graceful labeling $f$ with the property that there is
some integer $m$ so that for every edge $uv$ either $f(u) \leq m$ and $f(v)
>m$ or $f(u) > m$ and $f(v) \leq m$. He proves that if a graph is
$(1,1)$-balanced then it is $(k,d)$-graceful for all
$k$ and $d$ and that every $(1,1)$-balanced graph is $(k,k)$-balanced
for all $k$. He conjectures that all trees are $(k,d)$-balanced for some
values of $k$ and $d$.
Duan and Qi \cite{DQ} use
$G_t(m_1,n_1;m_2,n_2;\ldots;m_s,n_s)$ to denote the graph
composed of the $s$ complete bipartite graphs
$K_{m_1,n_1},K_{m_2,n_2},\ldots,K_{m_s,n_s}$ that have only $t~(1\leq
t\leq\min\{m_1,m_2,\dots,m_s\})$ common vertices but no common edge and
$G(m_1,n_1;m_2,n_2)$ to denote the graph composed of the complete
bipartite graphs
$K_{m_1,n_1},K_{m_2,n_2}$ with exactly one common edge. They prove that
these graphs are $k$-graceful graphs for all $k$.
Slater \cite{Sl5} has extended the definition of $k$-graceful graphs to
countable infinite graphs in a natural way.
He proved that all countably infinite trees, the complete graph
with countably many vertices and the countably infinite Dutch
windmill is $k$-graceful for all $k$.
More specialized results on
$k$-graceful labelings can be found in \cite{L1}, \cite{LNK}, \cite{LNH}, \cite{Sl2}, \cite{BuF},
\cite{BuH}, \cite{BGZ} and \cite{ChJ}.
\subsection{Skolem-Graceful Labelings}
A number of authors have invented analogues of graceful graphs by
modifying the permissible vertex labels. For instance, Lee (see \cite{LShe})
calls a graph $G$ with $p$ vertices and $q$ edges
{\em Skolem-graceful}\index{Skolem-graceful labelings}\subindex{labeling}{Skolem-graceful}
if there is an injection from the set of vertices of $G$ to
$\{1,2,\ldots,p\}$ such that the edge labels induced by ${\mid}f(x) -
{f(y)}{\mid}$ for each
edge $xy$ are $1,2,\ldots,q$. A necessary condition for a graph to be
Skolem-graceful is that $p \geq q+1$. Lee and Wui \cite{LWu} have shown that a
connected graph is Skolem-graceful if and only if it is a graceful tree.
Although the disjoint union of trees can not be graceful, they can be
Skolem-graceful. Lee and Wui \cite{LWu}
prove that the disjoint union of 2 or 3 stars\index{star} is Skolem-graceful
if and only if at least one star has even size.
In \cite{CK3} Choudum and
Kishore show that the disjoint union of $k$ copies of the star $K_{1, 2p}$
is Skolem graceful if $k \leq 4p + 1$ and the disjoint union of any number
of copies of $K_{1,2}$ is Skolem graceful.
For $k\geq 2$, let $St(n_1,n_2,\ldots,n_k)$ denote the disjoint union of
$k$ stars with $n_1, n_2, \ldots, n_k$ edges.
Lee, Wang and
Wui \cite{LWW}
showed that
the 4-star $St(n_1,n_2,n_3,n_4)$ is
Skolem-graceful for some special cases and conjectured that all 4-stars
are Skolem-graceful. Denham, Leu and Liu \cite{DLL}
proved this conjecture.
Kishore \cite{Kis} has shown that a necessary condition for
$St(n_1, n_2, \ldots, n_k)$
to be
Skolem graceful is that some $n_i$ is even or \(k \equiv 0\) or 1 (mod
4). He conjectures that each one of these conditions is sufficient.
Choudum and Kishore \cite{CK1} proved that all 5-stars are Skolem graceful.
Lee,
Quach and Wang \cite{LQW} showed that the disjoint union of the path $P_n$
and the star of size $m$ is Skolem-graceful if and only if $n=2$ and $m$
is even or $n \geq 3$ and $m \geq 1$. It follows from the work of Skolem
\cite{Sk} that $nP_2$, the disjoint union of $n$ copies of $P_2$, is
Skolem-graceful if and only if $n \equiv 0$ or 1 (mod 4). Harary and Hsu
\cite{HaHs} studied Skolem-graceful graphs under the name
{\em node-graceful}\subindex{graph}{node-graceful}.
Frucht \cite{F3} has shown that $P_m \cup P_n$ is Skolem-graceful when $m+n
\geq 5$.
Bhat-Nayak and Deshmukh \cite{BD4} have shown that $P_{n_1} \cup P_{n_2} \cup
P_{n_3}$ is Skolem-graceful when $n_1 < n_2 \leq n_3,~ n_2 = t(n_1 + 2) +
1$ and $n_1$ is even and when $n_1 3$ and $k > 3$ there is more
than one $kC_n$-snake.) If a $kC_n$-snake where
the path of minimum length
that contains all the cut-vertices of the graph has the property that the
distance between
any two consecutive cut-vertices is $\lfloor n/2\rfloor$ it is called
{\em linear}\subindex{$kC_n$-snake}{linear}.
Barrientos proves that $kC_4$-snakes are graceful and that the linear
$kC_6$-snakes are graceful when $k$ is even. When $k$ is odd he proves
that the linear $kC_6$-snake is nearly graceful. Barrientos further proves
that $kC_8$-snakes and $kC_{12}$-snakes are graceful in the cases where
the distances between consecutive vertices of the path of minimum length
that contains all the cut-vertices of the graph are all even and that
certain cases of $kC_{4n}$-snakes and $kC_{5n}$-snakes are graceful
(depending
on the distances between consecutive vertices of the path of minimum length
that contains all the cut-vertices of the graph).
Barrientos \cite{Bar6} also has shown that $C_m \cup K_{1,n}$ is nearly
graceful
when $m = 3,4,5,6.$
Yet another kind of labeling introduced by Rosa in his 1967 paper \cite{Ro1}
is a $\rho$-valuation.
A {\em $\rho$-valuation}\index{$\rho$-valuation} of a graph is
an injection from the vertices of the
graph with $q$ edges to the set $\{0,1,\ldots,2q\}$,
where if the edge labels induced by the absolute value of the
difference of the vertex labels are
$a_1, a_2, \ldots, a_q$, then $a_i = i$ or $a_i = 2q + 1 - i$.
Rosa \cite{Ro1} proved that a cyclic decomposition
of the edge set of the complete graph $K_{2q + 1}$ into subgraphs
isomorphic to a given graph $G$ with $q$ edges exists if and only if
$G$ has a $\rho$-valuation. (A decomposition of $K_n$ into copies of $G$ is
called {\em cyclic}\index{cyclic decomposition} if the
automorphism group of the decomposition itself contains the cyclic
group of order $n$.) It is known that every graph with at most
11 edges has a $\rho$-labeling and that all lobsters\index{lobster} have a
$\rho$-labeling (see \cite{CRS}). Donovan, El-Zanati, Vanden Eyden and
Sutinuntopas \cite{DEES} prove that $rC_m$ has a $\rho$-labeling (or a
more
restrictive labeling) when $r \leq 4$. They conjecture that every
2-regular graph has a $\rho$-labeling. Caro, Roditty and Sch\H{o}nheim
\cite{CRS}
provide a construction for the adjacency matrix\index{adjacency matrix}
for every graph that has
a $\rho$-labeling. They ask the following question: If $H$ is a connected
graph having a $\rho$-labeling and $q$ edges and $G$ is a new graph with
$q$ edges constructed by breaking $H$ up into disconnected parts does $G$
also have a $\rho$-labeling?
In their investigation of cyclic decompositions of complete graphs
El-Zanati, Vanden Eynden and Punnim \cite{EVP} introduced two kinds of
labelings. They say a bipartite graph $G$ with $n$ edges and partite sets
$A$ and $B$ has a {\em $\theta$-labeling}\index{$\theta$-labeling}
$h$ if $h$ is a one-to-one function from
$V(G)$ to $\{0,1, \ldots, 2n\}$ such that $\{h(b) - h(a)|~ ab \in E(G), a
\in A, b \in B\} = \{1,2, \ldots,n \}$. They call $h$ a
{\em $\rho^+$-labeling}\index{$\rho^+$-labeling} of $G$
if $h$ is a one-to-one function from
$V(G)$ to $\{0,1, \ldots, 2n\}$ and the integers $h(x) - h(y)$ are
distinct modulo $2n + 1$ over all ordered pairs $(x,y)$ where $xy$ is an
edge in $G$, and $h(b) > h(a)$ whenever
$a \in A, b \in B$ and $ab$ is an edge in $G$.
Note that $\theta$-labelings are $\rho^+$-labelings and $\rho^+$-labelings
are $\rho$-labelings. They prove that if $G$ is a bipartite graph
with $n$
edges and a $\rho^+$-labeling, then for every positive integer $x$ there
is
a cyclic $G$-decomposition of $K_{2nx + 1}$. They prove the following
graphs have $\rho^+$-labelings: trees of diameter at most 5, $C_{2n}$,
lobsters, and comets (that is, graphs obtained from stars by replacing
each edge by a path of some fixed length).
They also prove that the
disjoint union of graphs with $\alpha$-labelings have a $\theta$-labeling
and conjecture that all forests have $\rho$-labelings.
Blinco, El-Zanati and Vanden Eynden \cite{BEV} call a non-bipartite
graph {\em almost-bipartite}\index{almost-bipartite graph}\subindex{graph}{almost-bipartite}
if the removal of some edge
results in a bipartite graph. For these kinds of graphs $G$ they call a
labeling $h$ a {\em $\gamma$-labeling}\index{$\gamma$-labeling}
of $G$ if the following conditions are met:
$h$ is a $\rho$-labeling; $G$ is tripartite with vertex tripartition $A,
B, C$ with $C=\{c\}$ and $\overline{b}
\in B $ such that $\{\overline{b},c\}$ is the unique edge joining an
element of $B$ to $c$; if $\{a,v\}$ is an edge of $G$ with $a \in A$,
then
$h(a) 1$.
In \cite{BEV} Blinco, El-Zanati and Vanden Eynden consider a slightly restricted
$\rho^+$-labeling for a bipartite graph with partite sets $A$ and $B$ by
requiring that there exists a number $\lambda$ with the property that
$\rho^+(a) \leq \lambda$ for all $a \in A$ and $\rho^+(b) > \lambda$ for
all
$b \in B$. They denote such a labeling by $\rho^{++}$.
They use this knid of labeling to show that if $G$ is a 2-regular graph of
order $n$ in which each component has even order then there is a cyclic
$G$-decomposition of $K_{2nx + 1}$ for all $x$.
They also conjecture that every bipartite graph has a $\rho$-labeling and
every 2-regular graph has a $\rho$-labeling.
Dufour
\cite{Duf} and Eldergill \cite{E} have some results on the decomposition of the
complete graph using labeling methods. Balakrishnan and Sampathkumar \cite{BS}
showed that for each positive integer $n$ the graph $\overline{K_n} + 2K_2$
admits a $\rho$-valuation.
Balakrishnan \cite{Ba} asks if it is true that
$\overline{K_n} + mK_2$ admits a $\rho$-valuation for all $n$ and $m$.
Fron\v{c}ek \cite{Fr1}, \cite{Fr2} and Fron\v{c}ek and Kubesa \cite{FK} have introduced
several kinds of labelings for the purpose of proving the existence of
special kinds of decompositions\index{decomposition} of complete graphs
into spanning trees\index{spanning tree}.
For graphs with the property $p=q+1$, Frucht \cite{F3} has
introduced a stronger version of almost graceful graphs by permitting as
vertex labels $\{0,1, \ldots, q-1, q+1 \}$
and as edge labels $\{ 1,2,\ldots,q\}$.
He calls such a labeling
{\em pseudograceful}\index{pseudograceful labeling}\subindex{labeling}{pseudograceful}.
Frucht proved that $P_n \; (n \geq 3)$, combs, sparklers
(i.e., graphs obtained by joining an end vertex of a path to the center of a star),
$C_3 \cup P_n \; (n \not= 3)$, and $C_4 \cup P_n \;(n \not= 1)$ are
pseudograceful while $K_{1,n}\; (n \geq 3)$ is not.
Kishore \cite{Kis} proved that $C_s \cup P_n$ is pseudograceful when $s \geq
5$ and $n \geq (s + 7)/2$ and that $C_s \cup S_n$ is pseudograceful when
$s = 3, s= 4$, and $s \geq 7$.
Seoud and Youssef \cite{SY2} and \cite{SY5} extended the definition of
pseudograceful to all
graphs with $p \leq q + 1$. They proved that $K_m$ is
pseudograceful if and only if $m = 1, 3$ or 4 \cite{SY5}; $K_{m,n}$ is
pseudograceful when $n\geq 2$ and
$P_m +
\overline{K_n} \; (m\geq 2)$ \cite{SY2} is pseudograceful. They also proved
that
if $G$ is
pseudograceful, then $G\cup K_{m,n}$ is graceful for $m \geq 2$ and
$n\geq 2$ and $G\cup K_{m,n}$ is
pseudograceful for $m \geq 2, n \geq 2$ and $(m,n) \neq (2,2)$ \cite{SY5}.
They ask if $G\cup K_{2,2}$ is pseudograceful whenever $G$ is.
Youssef \cite{Yo1} has shown that if $H$ is pseudograceful and $G$ has an
$\alpha$-labeling with $k$ being the
smaller vertex label of the edge labeled with 1 and if either $k + 2$ or
$k -1$
is not a vertex label of $G$, then $G \cup H$ is graceful.
McTavish \cite{Mc} has investigated labelings where the vertex and edge labels are from $\{0,\ldots,q,q+1\}$.
She calls these {\em $\tilde{\rho}$-labelings}\index{$\tilde{\rho}$-labelings}.
Graphs that have {\em $\tilde{\rho}$}-labelings include cycles and the
disjoint union of $P_n$ or $S_n$ with any graceful graph.
Frucht \cite{F3} has made an observation about graceful labelings
that yields nearly graceful analogs of $\alpha$-labelings\index{$\alpha$-labeling}
and weakly $\alpha$-labelings\subindex{$\alpha$-labeling}{weakly} in a natural way.
Suppose $G(V,E)$ is a graceful graph with the vertex labeling $f$.
For each edge $xy$ in $E$, let $[f(x),f(y)]$ (where $f(x) \leq f(y)$) denote the interval of real numbers $r$ with $f(x) \leq r \leq f(y)$.
Then the intersection $\cap [f(x),f(y)]$ over all edges $xy \in E$ is a unit interval, a single point, or empty.
Indeed, if $f$ is an $\alpha$-labeling of $G$ then the intersection is a unit interval; if $f$ is a weakly $\alpha$-labeling,
but not an $\alpha$-labeling, then the intersection is a point; and, if $f$ is graceful but not a weakly $\alpha$-labeling, then the intersection is empty.
For nearly graceful labelings, the intersection also gives three distinct classes.
Singh and Devaraj \cite{SD} call a graph $G$ with $p$ vertices and
$q$ edges
{\em triangular graceful}\index{triangular graceful labeling}\subindex{labeling}{triangular graceful}
if there is an injection $f$ from $V(G)$ to $\{0,1,2, \ldots, T_q\}$ where
$T_q$ is the
$q$th triangular number and the labels induced on each edge $uv$ by $|f(u)
-f(v)|$
are the first $q$ triangular numbers. They prove the following graphs are
trianglar graceful: paths, level 2 rooted trees, olive trees (see Section~\ref{trees}
for the definition), complete $n$-ary trees, double stars, caterpillars,
$C_{4n}, C_{4n}$ with pendent edges, the one-point union of $C_3$ and
$P_n$, and
unicyclic graphs\index{unicyclic graph}\subindex{graph}{unicyclic} that have
$C_3$ as the unique cycle. They prove that wheels,
helms, flowers (see \S \ref{cycle_related_graphs} for the definition) and $K_n$ with $n \geq 3$
are not triangular graceful. They
conjecture that all trees are triangular graceful.
Van Bussel \cite{Van} considered two kinds of relaxations of graceful labelings as
applied to trees. He called a labeling
{\em range-relaxed graceful}\index{range-relaxed graceful labeling}\subindex{labeling}{range-relaxed graceful}
it is meets the same
conditions as a graceful labeling except the range of possible vertex labels
and edge labels are
not restricted to the number of edges of the graph (the edges are distinctly
labeled
but not necessarily labeled 1 to the number of edges). Similarly, he calls a
labeling {\em vertex-relaxed graceful}\index{vertex-relaxed graceful labeling}\subindex{labeling}{vertex-relaxed graceful}
if it satisfies the conditions of a graceful labeling
while permitting repeated vertex labels. He proves that
every tree $T$ with $q$ edges has a range-relaxed graceful labeling with the
vertex labels in
the range $0, 1, \ldots, 2q - diameter(T)$ and that every tree on $n$ vertices
has a vertex-relaxed graceful labeling such that the number of distinct vertex
labels is strictly greater than $n/2$.
Sekar \cite{Sek} calls an injective function $\phi$ from the vertices of a graph with
$q$ edges to $\{0,1,3,4, \ldots, 3q-2\}$
{\em one modulo three graceful}\index{one modulo three graceful labeling}%
\subindex{labeling}{one modulo three graceful}
if the edge labels induced by labeling each edge $uv$ with $|\phi(u) - \phi(v)|$ is
$\{1,4,7,
\ldots, 3q -2\}$. He proves that the following graphs are one modulo three
graceful:
$P_m;~ C_n$ if and only if $n \equiv 0$ mod 4; $K_{m,n}; C_{2n}^{(2)}$
(the
one-point
union of two copies of $C_{2n});
C_{n}^{(t)}$ for $n = 4$
or 8 and $t > 2;
C_6^{(t)}$ and $t \geq 4$;
caterpillars\index{caterpillar}, stars\index{star}, lobsters\index{lobster};
banana trees\index{banana tree}, rooted trees of height 2; ladders\index{ladder};
the graphs obtained by identifying the endpoints of any number
of copies of $P_n$;
the graph obtained by attaching pendent edges to each
endpoint of two identical stars and then identifying one endpoint from each of
these graphs;
the graph obtained by identifying a vertex of $C_{4k + 2}$ with an endpoint of
a star; $n$-polygonal snakes\subindex{snake}{$n$-polygonal}
(see \S \ref{cycle_related_graphs}) for $n \equiv 0$ (mod 4);
$n$-polygonal snakes for $n \equiv 0$ (mod 4);
$n$-polygonal snakes for $n \equiv 2$ (mod 4) where the number of polygons is
even; crowns $C_n \otimes K_1$ for $n$ even; $C_{2n} \otimes P_m (C_{2n}$ with
$P_m$ attached at each vertex of the cycle) for $m \geq 3$; chains
of cycles (see \S \ref{cycle_related_graphs}) of the form $C_{4,m}, C_{6,2m}$ and $C_{8,m}$.
He conjectueres that every one modulo three graceful graph is graceful.
\subsection{Cordial Labelings}
Cahit \cite{C2} has introduced a variation of both graceful and harmonious
labelings.
Let $f$ be a function from the vertices of $G$ to $\{0,1\}$ and for each edge $xy$ assign the label ${\mid}f(x) - {f(y)}{\mid}$.
Call $f$ a
{\em cordial labeling}\index{cordial labeling}\subindex{labeling}{cordial}
of $G$ if the number of vertices labeled 0 and the number of vertices labeled
1 differ by at most 1, and the number of edges labeled 0 and the number of edges labeled 1 differ at most by 1.
Cahit \cite{C3} proved the following: every tree is cordial; $K_n$ is cordial
if and only if $ n \leq 3$; $K_{m,n}$ is cordial for all $m$ and $n$;
the friendship graph\index{friendship graph} $ C_3^{(t)}$
(i.e., the one-point union\index{one-point union} of $t~$
3-cycles) is cordial if and only if $t
\not\equiv 2$
(mod 4); all fans\index{fan} are cordial; the wheel\index{wheel} $W_n$ is cordial if and only if
$ n \not\equiv 3$ (mod 4) (see also \cite{Du}); maximal outerplanar graphs are
cordial; and an Eulerian graph is not cordial if its size is congruent to 2
(mod 4).
Kuo, Chang and Kwong \cite{KCK} determine all $m$ and $n$ for which $
mK_n$ is
cordial.
A {\em $k$-angular cactus}\subindex{cactus}{$k$-angular} is a connected graph all
of whose blocks are cycles with $k$ vertices.
In \cite{C3} Cahit proved that a $k$-angular cactus with $t$ cycles is cordial
if and only if $kt \not\equiv 2$ (mod 4).
This was improved by Kirchherr \cite{Ki1} who showed any cactus whose blocks
are cycles is cordial if and only if the size of the graph is not congruent to 2 (mod 4).
Kirchherr \cite{Ki2} also gave a characterization of cordial graphs
in terms of their adjacency matrices.
Ho, Lee and Shee \cite{HLS2} proved:
$P_n \times C_{4m}$ is cordial for all $m$ and all odd $n$;
the composition $G$ \cite{H} and $H$ is cordial if $G$ is cordial and $H$
is
cordial and has odd order and even size (see \S \ref{product_related_graphs} for definition of
composition\index{composition}); for $n \geq 4$ the composition
$C_n[K_2]$ is cordial if and only if $ n \not\equiv 2$ (mod 4);
the Cartesian product\index{Cartesian product} of two cordial graphs
of even size is cordial.
The same authors \cite{HLS1} showed that a unicyclic graph is cordial
unless it is $C_{4k+2}$ and that the generalized Petersen graph\subindex{Petersen graph}{generalized}
(see \S \ref{miscellaneous_results} for definition)
$P(n,k)$ is cordial if and only if $n \not\equiv 2$ (mod 4).
Du \cite{Du} determines the maximal number of edges in a cordial graph of order
$n$ and gives a necessary condition for a
$k$-regular graph to be cordial.
Seoud and Abdel Maqusoud \cite{SA2} proved that if $G$ is a graph with $n$
vertices and $m$ edges and every vertex has odd degree then $G$ is not
cordial when $m + n \equiv 2$ (mod 4). They also prove the following:
for $m
\geq 2,~ C_n \times P_m$ is cordial except for the case $C_{4k + 2}
\times
P_2; P_n^2$ is cordial for all $n; P_n^3$ is cordial if and only if
$n\neq 4$; and $P_n^4$ is cordial if and only if $n \neq 4, 5$ or 6.
Seoud, Diab and Elsakhawi \cite{SDE} have proved the following graphs are
cordial: $P_n + P_m$ for all
$m$ and $n$ except $(m,n) = (2,2)$;
$C_m + C_n$ if $m \not\equiv 0$ (mod 4) and $n \neq 2$ (mod
4);
$P_n + K_{1,m}$ for all $n$ and odd $m$;
$C_n + K_{1,m}$ for $n \not\equiv 3$ (mod 4) and odd $m$ except $(n,m) =
(3,1); C_n + \overline{K_m}$ when $n$ is odd and when $n$ is even and $m$
is odd; $K_{1,m,n}; K_{2,2,m}$; the $n$-cube; books $B_n$ if and only if
$ n \not\equiv 3$ (mod
4); $B(3,2,m)$ for all $m; B(4,3,m)$ if and only if $m$ is even; and
$B(5,3,m)$ if and
only if $m \not\equiv 1$ (mod 4)~(see \S \ref{complete_graphs} for the notation $B(n,r,m)$).
Youssef \cite{Yo4} has proved the following:
If $G$ and $H$ are cordial\index{cordial graph} and one has
even size, then $G\cup H$ is cordial;
if $G$ and $H$ are cordial and both have even size, then $G + H$ is
cordial;
if $G$ and $H$ are cordial and one has even size and one of either has even
order, then $G + H$ is cordial; $C_m \cup C_n$ is cordial if and only if
$m +n
\not\equiv 2$ (mod 4); $mC_n$ is cordial if and only if $mn \not\equiv 2
$(mod
4); $C_m + C_n$ is cordial if and only if $(m,n) \neq (3,3)$ and
$\{m \mbox{ (mod 4)},n \mbox{ (mod 4)}\}
\not\equiv \{0,2\}$; if $P_n^k$ is cordial, then $n \geq k + 1 +
\sqrt{k
-2}$.
He conjectures that this latter condition is also sufficient. He confirms the
conjecture for $k = 5,6,7,8$ and 9.
Lee and Liu \cite{LeL} have shown that the
complete $n$-partite graph\subindex{complete}{$n$-partite graph}
if and only if at most three of its partite sets have odd
cardinality (see also \cite{Du}).
Lee, Lee and Chang \cite{LLC} prove the following graphs are cordial:
the Cartesian product of an arbitrary number of
paths;
the Cartesian product\index{Cartesian product} of two cycles if and only if at least one of them is
even; and the Cartesian product of an arbitrary number of cycles if at
least one of them has length a multiple of 4 or at least two of them are
even.
Shee and Ho \cite{SH1} have investigated the cordiality of the one-point union\index{one-point union}
of $n$ copies of various graphs. For $C_m^{(n)}$, the one-point
union of
$n$ copies of $C_m$, they proved:\\
\indent(i) If $m \equiv 0$ (mod 4), then $C_m^{(n)}$ is cordial for all
$n$;\\
\indent(ii) If $m \equiv 1$ or 3 (mod 4), then $C_m^{(n)}$ is cordial if and
only if $n \not\equiv 2$ (mod 4);\\
\indent(iii) If $m \equiv 2$ (mod 4), then $C_m^{(n)}$ is cordial if and
only if $n$ is even.\\
For $K_m^{(n)}$, the one-point union of $n$ copies of $K_m$, Shee and Ho
\cite{SH1} prove:\\
\indent(i) If $m \equiv 0 $ (mod 8), then $K_m^{(n)}$ is not cordial for $n
\equiv 3 $ (mod 4);\\
\indent(ii) If $m \equiv 4 $ (mod 8), then $K_m^{(n)}$ is not cordial for $n
\equiv 1 $ (mod 4);\\
\indent(iii) If $m \equiv 5 $ (mod 8), then $K_m^{(n)}$ is not cordial for
all odd $n$;\\
\indent(iv) $K_4^{(n)}$ is cordial if and only if $n\not\equiv
1 $ (mod 4);\\
\indent(v) $K_5^{(n)}$ is cordial if and only if $n$ is even;\\
\indent(vi) $K_6^{(n)}$ is cordial if and only if $n > 2$;\\
\indent(vii) $K_7^{(n)}$ is cordial if and only if $n\not\equiv
2 $ (mod 4);\\
\indent(viii) $K_n^{(2)}$ is cordial if and only if $n$ has the form
$p^2$ or $p^2 + 1$.\\
Benson and Lee \cite{BL} have investigated the regular windmill\index{windmill} graphs
$K_m^{(n)}$ and determined precisely which ones are cordial for $m < 14$.
For $W_m^{(n)}$, the one-point union of $n$ copies of the wheel\index{wheel} $W_m$ with
the common vertex being the center, Shee and Ho \cite{SH1} show:\\
\indent (i) If $m \equiv 0$ or 2 (mod 4), then $W_m^{(n)}$ is cordial for
all $n$;\\
\indent (ii) If $m \equiv 3$ (mod 4), then $W_m^{(n)}$ is
cordial if $n\not\equiv 1$ (mod 4);\\
\indent(iii) If $m \equiv 1$ (mod 4), then $W_m^{(n)}$ is cordial if
$n\not\equiv 3$ (mod 4).
\\
For all $n$ and all $m > 1$ Shee and Ho \cite{SH1} prove $F_m^{(n)}$, the
one-point union of $n$ copies of the fan
$F_m = P_m + K_1$ with the common point of the fans being the center, is
cordial. The {\em flag}\index{flag} $Fl_m$ is obtained by
joining one vertex of $C_m$ to an extra vertex called the {\em root}\index{root}.
Shee and Ho \cite{SH1} show all $Fl_m^{(n)}$, the one-point union of $n$
copies of $Fl_m$ with the common point being the root, are cordial.
Andar, Boxwala and Limaye \cite{ABL1} and \cite{ABL2} have proved the following
graphs are
cordial: helms\index{helm}; closed helms\subindex{helm}{closed};
generalized helms\subindex{helm}{generalized} obtained by taking a web and
attaching pendent vertices to all the vertices of the outermost cycle
in the case that the number cycles is even;
flowers (see \S \ref{cycle_related_graphs}), which are obtained by
joining the vertices of degree
one of a helm to the central vertex;
sunflower\index{sunflower} graphs, which are obtained by taking a wheel with the
central vertex $v_0$ and the $n$-cycle $v_1, v_2,\ldots,v_n$ and
additional vertices $w_1, w_2,\ldots,w_n$ where $w_i$ is joined by edges
to $v_i, v_{i+1},$ where $i+1$ is taken modulo $n,$ and multiple shells\index{shell}
(see \S \ref{cycle_related_graphs}).
For a graph $G$ and a positive integer $t$, Andar, Boxwala and Limaye \cite{ABL3}
define the $t$-uniform homeomorph\subindex{graph}{$t$-uniform homeomorph}
$P_t(G)$ of $G$ as the graph obtained from $G$ by
replacing every edge of $G$ by vertex disjoint paths of length $t$. They prove
that if $G$ is cordial and $t$ is odd, then $P_t(G)$ is cordial; if $t
\equiv
2$ (mod 4) a cordial labeling of $G$ can be extended to a cordial labeling of
$P_t(G)$ if and only if the number of edges labeled $0$ in $G$ is even; and
when $t \equiv 0$ (mod 4) a cordial labeling of $G$ can be extended to a
cordial
labeling of $P_t(G)$ if and only if the number of edges labeled $1$ in $G$ is
even. In \cite{ABL4} Ander et al. prove that $P_t(K_{2n})$ is cordial for all $t \geq
2$ and that $P_t(K_{2n + 1})$ is cordial if and only if $t \equiv 0$ (mod 4)
or $t$ is odd and $n \not\equiv 2$ (mod 4) or $t \equiv 2$ (mod 4) and $n$ is
even. In \cite{ABL5} Andar et al. define a $t$-ply graph $P_t(u,v)$ as a graph
consisting of $t$ internally disjoint paths joining vertices $u$ and $v$. They
prove that $P_t(u,v)$ is cordial except when it Eulerian and the number of
edges is congruent to 2 (mod 4).
For a binary labeling $g$ of a graph $G$ let $v_g(j)$ denote the number of
vertices labeled with $j$ and $e_g(j)$ denote the number edges labeled with
$j$. Then $i(G) = \mbox{min}\{|e_g(0) - e_g(1)|\}$ taken over all binary
labelings $g$ of $G$ with $|v_g(0) - v_g(1)| \leq 1$. In \cite{ABL6} Andar et al.
show that a cordial labeling
of $G$ can be extended to a cordial labeling of the graph obtained from $G$
by attaching $2m$ pendant edges
at each vertex of $G$. They also prove that a cordial labeling $g$ of a graph
$G$
with $p$ vertices can be extended to a cordial labeling
of the graph obtained from $G$ by attaching $2m + 1$ pendant edges at each
vertex of $G$ if and only if $G$ does not satisfy either of the conditions:
(1) $G$ has an even number of edges and $p \equiv 2$ (mod 4); (2)
$G$ has an odd number of edges and either $p \equiv 1 $ (mod 4) with $e_g(1) =
e_g(0) + i(G)$ or $n \equiv 3$ (mod 4) and $e_g(0) = e_g(1) + i(G).$
For graphs $G_1, G_2, \ldots, G_n ~(n \geq 2)$ that are all copies of a
fixed
graph $G$, Shee and Ho \cite{SH2} call a graph obtained by adding an edge from $G_i$
to $G_{i + 1}$ for $i = 1, \ldots, n-1$ a {\em path-union}\index{path-union}
of $G$ (the resulting
graph may depend on how the edges are chosen). Among their results they show the
following graphs are cordial: path-unions of cycles; path-unions of $n$ copies
of $K_m$ when $m = 4, 6$ or 7; path-unions of three or more copies of $K_5$;
and path-unions of two copies of $K_m$ if and only if $m-2, m$ or $m+2$ is a
perfect square. They also show that there exist cordial path-unions of wheels,
fans, unicyclic graphs, Petersen graphs, trees and various compositions.
Lee and Liu \cite{LeL} give the following general construction for the forming
of cordial graphs from
smaller cordial graphs. Let $H$ be a graph with an
even number of edges and a cordial labeling such that the vertices of $H$
can be divided into $t$ parts $H_1, H_2, \ldots, H_t$ each consisting of
an equal number of vertices labeled 0 and vertices labeled 1. Let $G$ be
any graph and $G_1, G_2, \ldots, G_t$ be any $t$ subsets of the vertices
of $G$. Let $(G,H)$ be the graph that is the disjoint union of $G$ and
$H$ augmented by edges joining every vertex in $G_i$ to every vertex in
$H_i$ for all $i$. Then $G$ is cordial if and only if $(G,H)$ is. From
this it follows that: all generalized fans\subindex{generalized}{fan}
$F_{m,n} = \overline{K_m} + P_n$
are cordial;
the generalized bundle\subindex{generalized}{bundle} $B_{m,n}$ is cordial if and only if $m$ is even
or $n \not\equiv 2$ (mod 4) \ ($B_{m,n}$ consists of $2n$
vertices $v_1, v_2, \ldots, v_n, u_1, u_2, \ldots, u_n$ with an edge from
$v_i$ to $u_i$ and $2m$ vertices $x_1, x_2, \ldots x_m, y_1, y_2, \ldots,
y_m$ with $x_i$ joined to $v_i$ and $y_i$ joined to $u_i$);
if $m$ is odd
a generalized wheel\subindex{generalized}{wheel}
$W_{m,n} = \overline{K_m} + C_n$ is cordial if and only if $n \not\equiv 3$
(mod 4). If $m$ is
even, $W_{m,n}$ is cordial if and only if $n \not\equiv 2$ (mod 4); a
complete $k$-partite graph is cordial
if and only if the number of parts with an odd number of vertices is at
most 3.
Sethuraman and Selvaraju \cite{SS8} have shown that certain cases of
the union of any number of
copies of $K_4$ with one or more edges deleted and one edge in common are
cordial. Youssef \cite{Yo6} has shown that the $k$th power of $C_n$ is cordial for
all
$n$ when $k\equiv 2$ (mod 4) and for all even $n$ when $k \equiv 0$ (mod
4).
Cahit \cite{C8} calls
a graph {\em $H$-cordial}\index{$H$-cordial}\subindex{graph}{$H$-cordial} if it is possible
to label the edges
with the numbers from the set $\{1,-1\}$ in such a way that, for some
$k$, at each vertex $v$ the
algebraic sum of the labels on the edges incident with $v$ is either $k$
or $-k$
and the
inequalities $\vert v(k)-v(-k)\vert \leq 1$ and $\vert e(1)-e(-1)\vert
\leq 1$ are also satisfied, where $v(i)$ and $e(j)$ are,
respectively, the
number of
vertices labeled with $i$ and the number of edges labeled with $j$.
He calls
a graph {\em $H_n$-cordial}\index{$H_n$-cordial}\subindex{graph}{$H_n$-cordial} if it is possible
to label the edges
with the numbers from the set $\{\pm 1,\pm 2, \ldots, \pm n\}$ in such a way
that,
at each vertex $v$ the algebraic
sum of the labels on the edges incident with $v$ is in the set $\{\pm 1,\pm 2,
\ldots, \pm n\}$
and the
inequalities $\vert v(i)-v(-i)\vert \leq 1$ and $\vert e(i)-e(-i)\vert
\leq 1$ are also satistied for each $i$ with $1 \leq i \leq n$.
Among Cahit's results are:
$K_{n,n}$ is $H$-cordial if and only if $n> 2$ and $n $ is even and
$K_{m,n}, m \neq n$, is $H$-cordial if and only if $n \equiv 0$ (mod 4),
$m$ is even and $m>2, n> 2$.
Unfortunately, Ghebleh and Khoeilar \cite{GK} have shown that other statements in
Cahit's paper are incorrect.
In particular, Cahit states that
$K_n$ is $H$-cordial if and only if $n\equiv 0$ (mod
4); $W_n$ is $H$-cordial if and only if
$n \equiv 1$ (mod 4); and $K_n$ is $H_2$-cordial if and only if $n\equiv 0$ (mod
4) while Ghebleh and Khoeilar instead prove that
$K_n$ is $H$-cordial if and only if $n\equiv 0$ or 3 (mod
4) and $n \neq 3; W_n$ is $H$-cordial if and only if
$n$ is odd; and $K_n$ is $H_2$-cordial if $n\equiv 0$ or 3 (mod
4) and $K_n$ is not $H_2$-cordial if $n \equiv 1$ (mod 4). Ghebleh and Khoeilar
also prove every wheel has an
$H_2$-cordial labeling.
By allowing 0 as the
possible induced vertex label of an $H$-cordial labeling Cahit \cite{C8} studies
semi-$H$-cordiality of
trees. He also generalizes $H$-cordial labelings.
Cahit and Yilmaz \cite{CY} call
a graph {\em $E_k$-cordial}\index{$E_k$-cordial}\subindex{graph}{$E_k$-cordial}
if it is possible to label the edges
with the numbers from the set $\{0, 1, 2, \ldots, k -1\}$ in such a way
that,
at each vertex $v$, the
sum modulo $k$ of the labels on the edges incident with $v$
satisfies the inequalities $\vert v(i)-v(j)\vert \leq 1$ and
$\vert e(i)-e(j)\vert
\leq 1$, where $v(s)$ and $e(t)$ are,
respectively, the number of
vertices labeled with $s$ and the number of edges labeled with $t$.
Obviously, $E_2$-cordial is the same as cordial. Cahit and Yilmaz prove
the following graphs are $E_3$-cordial:
$P_n ~(n \geq 3)$; stars $S_n $ if and only if $n \not \equiv 1$ (mod 3);
$K_n
~(n \geq 3); ~C_n ~(n \geq 3)$; friendship graphs; and fans $F_n ~(n \geq
3)$. They also prove that $S_n ~(n \geq 2)$ is $E_k$-cordial if and only
if $n \not\equiv 1$ (mod $k$) when $k$ is odd or $n \not\equiv 1 $ mod
$2k$ when $k$ is even and $k \neq 2$.
Hovey \cite{Ho} has introduced a simultaneous generalization of harmonious and cordial labelings.
For any Abelian group $A$ (under addition) and graph $G(V,E)$ he defines $G$
to be {\em A-cordial}\index{A-cordial graph}\subindex{graph}{A-cordial}
if there is a labeling of $V$ with elements of $A$ so that for all
$a$ and $b$ in $A$ when the edge $ab$ is labeled with $f(a) + f(b)$, the number of vertices labeled with $a$ and the number of vertices labeled $b$
differ by at most one and the number of edges labeled
with $a$ and the number labeled with $b$ differ by at most one.
In the case where $A$ is the cyclic group of order $k$, the labeling is
called {\em $k$-cordial}\index{$k$-cordial labeling}\subindex{labeling}{$k$-cordial}.
With this definition we have:
$G(V,E)$ is harmonious if and only if $G$ is ${\mid}E{\mid}$-cordial;
$G$ is cordial if and only if $G$ is 2-cordial.
Hovey has obtained the following:
caterpillars are $k$-cordial for all $k$;
all trees are $k$-cordial for $k = 3, 4$ and $5$;
odd cycles with pendant edges attached are $k$-cordial for all $k$;
cycles are $k$-cordial for all odd $k$;
for $k$ even, $C_{2mk+j}$ is $k$-cordial when $0 \leq j \leq \frac{k}{2} + 2$ and when $k < j < 2k$; $C_{(2m+1)k}$ is not $k$-cordial;
$K_m$ is 3-cordial;
and, for $k$ even, $K_{mk}$ is $k$-cordial if and only if $m = 1$.
Hovey advances the following conjectures:
all trees are $k$-cordial for all $k$;
all connected graphs are 3-cordial; and $C_{2mk+j}$ is $k$-cordial if and
only if $j \neq k$, where $k$ and $j$ are even and $0 \leq j < 2k$.
The last conjecture was verified by Tao \cite{Ta}. This
result combined with those of Hovey show that for all positive integers
$k$ the $n$-cycle is $k$-cordial with the exception that $k$ is even and
$n =2mk +k. $
Tao also proved that the crown with $2mk + j$ vertices is
$k$-cordial unless $j = k$ is even and for
$4 \leq n \leq k$ and the
wheel
$W_n$ is $k$-cordial unless $k \equiv 5$ (mod 8) and $n = (k +1)/2$.
In \cite{SS4} Sethuraman and Selvaraju present an
algorithm that permits one to start with any non-trivial connected graph $G$ and
successively form supersubdivisions (see \S \ref{miscellaneous_results} for the definition) that
are cordial in that case that every edge in
$G$ is replaced by $K_{2,m}$ where $m$ is even.
Sethuraman and Selvaraju \cite{SS5} also prove that the one edge union of $k$ copies
of shell graphs\index{shell graph} $C(n, n-3)$ (see \S \ref{cycle_related_graphs})
is cordial for all $n \geq 4$ and all $k$ and that the
one vertex union of any number of copies of $K_{m,n}$ is cordial.
Cairnie and Edwards \cite{CE} have determined the computational complexity of
cordial and $k$-cordial labelings. They prove a conjecture of Kirchherr
\cite{Ki2} that deciding whether a graph admits a cordial labeling is
NP-complete. As a corollary, this result implies that the same problem
for $k$-cordial labelings is NP-complete. They remark
that even the restricted problem of deciding whether connected graphs
of diameter 2
have a cordial labeling is also NP-complete.
In \cite{CLZ} Chartrand, Lee and Zhang introduced the notion of ramdomly
cordial\subindex{labeling}{ramdomly cordial} as follows.
Let $f$ be a labeling from $V(G)$ to $\{0,1\}$ and
for each edge $xy$ define $f^*(xy) = |f(x) - f(y)|$. For $i = 0$ and 1
let
$n_i(f)$ denote the number of vertices $v$ with $f(v)= i$ and
$m_i(f)$ denote the number of edges $e$ with $f^*(e) = i$. They call a
such a labeling $f$ {\em friendly}\subindex{labeling}{friendly}
if $|n_0(f) - n_1(f)| \leq 1$.
A graph $G$ for which every friendly labeling is cordial is called
{\em randomly cordial}\subindex{labeling}{randomly cordial}.
They prove that a connected graph of order $n \geq 2$
is randomly cordial if and only if $n =3$ and $G = K_3$, or $n$ is even
and $G = K_{1,n-1}$.
\subsection{$k$-equitable Labelings}
In 1990 Cahit \cite{C4}
proposed the idea of distributing the vertex and edge
labels among $\{0,1,\ldots,k-1\}$ as evenly as possible to obtain a generalization of graceful
labelings as follows.
For any graph $G(V,E)$ and any positive integer $k$,
assign vertex labels from $\{0,1,\ldots,k-1\}$ so
that when the edge labels induced by the absolute value of the
difference of the vertex labels,
the number of vertices
labeled with $i$ and the number of vertices labeled with $j$ differ by at
most
one and the number of edges
labeled with $i$ and the number of edges labeled with $j$ differ by at
most one.
Cahit has called a graph with such an assignment of labels
{\em $k$-equitable}\subindex{labeling}{$k$-equitable}.
Note that $G(V,E)$ is graceful if and only if it is
${\mid}E{\mid}+1$-equitable and $G(V,E)$ is cordial if and only if it is 2-equitable.
Cahit \cite{C3} has shown the following: $C_n$ is 3-equitable
if and only if $n \not \equiv 3$ (mod 6); a triangular snake with $n$
blocks is 3-equitable if and only if
$n$ is even; the friendship graph $C_3^{(n)}$ is 3-equitable if and only if
$n$ is even;
an Eulerian graph\index{Eulerian graph} with $q \equiv 3$ (mod 6) edges is not 3-equitable;
and all caterpillars are 3-equitable \cite{C3}.
Cahit \cite{C3} further gives a proof that $W_n$ is 3-equitable if and only if $n
\not\equiv 3$ (mod 6) but Youssef \cite{Yo3} proved that $W_n$ is 3-equitable for all
$n \geq 4$. Youssef \cite{Yo1} also proved that if $G$ is a $k$-equitable Eulerian
graph with $q$ edges and
$k\equiv 2 $ or 3 (mod 4) then $q \not\equiv k$ (mod $2k$).
Cahit conjectures \cite{C3} that a triangular cactus with $n$ blocks is
3-equitable if and only if $n$ is even.
In \cite{C4} Cahit proves that every tree with fewer than five
end vertices has a 3-equitable labeling. He conjectures that all
trees are $k$-equitable \cite{C5}. In 1999 Speyer and Szaniszl\'{o} \cite{SpS}
proved
Cahit's conjecture for $k = 3$.
In \cite{SA1} Seoud and Abdel Maqsoud prove: a graph with $n$
vertices and
$q$ edges in which every vertex has odd degree is not 3-equitable if $n
\equiv 0$ (mod 3) and $q \equiv 3$ (mod 6); all fans except $P_2 +
\overline{K_1}$ are 3-equitable; all double fans except $P_4 +
\overline{K_2}$ are 3-equitable; $P_n^2$ is 3-equitable for all $n$ except
3; $K_{1,1,n}$ is 3-equitable if and only if $n \equiv 0$ or 2
(mod
3); $K_{1,2,n}, n\geq 2$, is 3-equitable if and only if $n \equiv 2$
(mod 3); $K_{m,n}, ~3 \leq m\leq n$, is 3-equitable if and only if $(m,n)
=
(4,4); K_{1,m,n},~ 3 \leq m \leq n,$ is 3-equitable if and only if $(m,n)
= (3,4)$.
Szaniszl\'{o} \cite{Sz} has proved the
following: $P_n$ is $k$-equitable for all $k$; $K_n$ is 2-equitable if
and only if $n =1 ,2$ or 3; $K_n$ is not $k$-equitable for $3 \leq k <
n$; $S_n$ is $k$-equitable for all $k$; $K_{2,n}$ is $k$-equitable if and
only if $n \equiv k-1$ (mod
$k$), or $n \equiv 0, 1, 2,\ldots, \lfloor k/2 \rfloor -1$ (mod
$k$), or $n = \lfloor k/2 \rfloor$ and $k$ is odd.
She also proves that $C_n$ is $k$-equitable if
and only if $k$ meets all of the following conditions: $n \neq k$; if $k
\equiv 2, 3 $ (mod 4), then $n \neq k -1$; if $k \equiv 2, 3$ (mod 4) then
$n \not\equiv k$ (mod $2k$).
Vickrey \cite{Vi} has determined the $k$-equitablity of complete multipartite
graphs. He
shows that for $m \geq 3$ and $k\geq 3, ~K_{m,n}$ is
$k$-equitable if and only if $K_{m,n}$ is one of the following graphs:
$K_{4,4}$ for $k = 3$; $K_{3,k-1}$ for all $k$; or $K_{m,n}$ for $k> mn$.
He also shows that when $k$ is less than or equal to the number of
edges in the graph and at least 3, the only complete multipartite graphs
that are $k$-equitable are $K_{kn + k -1,2,1}$ and $K_{kn +k -1,1,1}.$
Partial results on the $k$-equitability of $K_{m,n}$ were obtained by Krussel
\cite{Kr}.
As a corollary of the result of Cairnie and Edwards \cite{CE} on the
computational complexity of
cordially labeling graphs, it follows that
the problem of finding $k$-equitable labelings of graphs is
NP-complete as well.
Seoud and Abdel Maqsoud \cite{SA2} call a graph
{\em $k$-balanced}\subindex{graph}{$k$-balanced} if the
vertex labels can be selected from $\{0,1, \ldots, k-1\}$ so that the
number of edges labeled $i$ and the number of edges labeled $j$
induced by the absolute value of the differences of the vertex
labels differ by at most 1.
They prove that $P_n^2$ is 3-balanced if and only if $n = 2,3, 4$ or 6;
for $k \geq 4, ~P_n^2 $ is not $k$-balanced if $k \leq n -2$ or $n + 1
\leq k \leq 2n - 3$; for $k \geq 4,~P_n^2$ is $k$-balanced if $k \geq 2n -
2$; for $k,m,n \geq 3,~ K_{m,n}$ is $k$-balanced if and only if $k \geq
mn$; for $m \leq n,~ K_{1,m,n}$ is $k$-balanced if and only if
($i$) $m =1, n=
1$ or 2, and $k= 3$;
($ii$) $m = 1$ and $k = n+ 1$ or $n + 2$; or
($iii$) $k \geq (m + 1)(n + 1)$.
Bloom has used the term $k$-equitable to
describe another kind
of labeling (see \cite{W1} and \cite{W2}).
He calls a graph {\em $k$-equitable}\subindex{labeling}{$k$-equitable}
if the edge labels induced by
the absolute value of the difference of the vertex labels have the
property that every edge label induced occurs exactly $k$ times.
A graph of order $n$ is called {\em minimally k-equitable}\subindex{graph}{minimally k-equitable}
if the vertex
labels are 1, 2,$ \ldots$, $n$ and it is $k$-equitable.
Both Bloom and Wojciechowski \cite{W1}, \cite{W2} proved that $C_n$ is minimally
$k$-equitable if and only if $k$ is a proper divisor of $n$.
Barrientos and Hevia \cite{BaH} proved that if $G$ is $k$-equitable of size $q =kw$
(in the sense of Bloom) then $\delta(G) \leq w$ and $\Delta(G) \leq 2w$.
Barrientos, Dejter and Hevia \cite{BDH} have shown that forests of even size
are 2-equitable.
They also prove that for $k =3$ or $k = 4$ a forest of size $kw$ is
$k$-equitable if and only if its maximum degree is at most $2w$ and that
if 3 divides $mn + 1$, then the double star $S_{m,n}$ is 3-equitable if
and only if $q/3\leq m \leq
\lfloor(q-1)/2\rfloor.~ (S_{m,n}$ is $K_2$ with $m$ pendant edges
attached at one
end and $n$ pendant edges attached at the other end.) They discuss the
$k$-equitability of forests for $k \geq 5$ and characterize
all caterpillars of diameter 2 that are $k$-equitable for all possible
values of $k$. Acharya and Bhat-Nayak \cite{AcBh} have shown that coronas of
the form $C_{2n} \odot K_1$ are minimally $4$-equitable.
In \cite{Bar1} Barrientos proves that the one-point union of
a cycle and a path (dragons) and the disjoint union of a cycle and a path
are $k$-equitable for all $k$ that divide the size of the graph.
Barrientos and Havia \cite{BaH} have shown the following: $C_n \times K_2$ is
$2$-equitable
when $n$ is even; books $B_n~(n \geq 3$) are $2$-equitable when $n$ is odd;
the vertex union of
$k$-equitable graphs is $k$-equitable; wheels $W_n$ are
$2$-equitable when $n\not\equiv 3$ (mod 4).
They conjecture that $W_n$ is
$2$-equitable when $n \equiv 3$ (mod 4) except when $n = 3$.
Their $2$-equitable labelings of $C_n \times K_2$ and the $n$-cube utilized
graceful labelings of those graphs.
Bhat-Nayak and M. Acharya \cite{BA} have proved the following:
the crowns\index{crown} $C_{2n}\odot K_1$ are minimally 2-equitable, minimally
$2n$-equitable, minimally 4-equitable, and minimally $n$-equitable;
the crowns $C_{3n}\odot K_1$ are minimally 3-equitable, minimally
$3n$-equitable, minimally $n$-equitable, and minimally 6-equitable;
the crowns $C_{5n}\odot K_1$ are minimally 5-equitable, minimally
$5n$-equitable, minimally $n$-equitable, and minimally 10-equitable;
the crowns $C_{2n+1}\odot K_1$ are minimally $(2n+1)$-equitable; and that
the
graphs $P_{kn+1}$ are $k$-equitable.
In \cite{Bar3} Barrientos calls a $k$-equitable labeling
{\em optimal}\subindex{labeling}{optimal $k$-equitable} if the
vertex labels are consecutive integers and
{\em complete}\subindex{labeling}{complete $k$-equitable} if the induced
edge labels are $1,2, \ldots, w$ where $w$ is the number of distinct edge
labels. Note that a graceful labeling is a complete $1$-equitable
labeling. Barrientos proves that $C_m \odot nK_1$ (that is, an $m$-cycle with
$n$ pendant edges attached at each vertex) is optimal 2-equitable when $m$ is
even, $C_3 \odot nK_1$ is complete 2-equitable when $n$ is odd and that
$C_3\odot nK_1$ is complete 3-equitable for all $n$. He also shows that
$C_n \odot K_1$ is $k$-equitable for every proper divisor $k$ of the size
$2n$. Barrientos and Havia \cite{BaH} have shown that the $n$-cube ($n \geq 2$) has a
complete
$2$-equitable labeling and that $K_{m,n}$ has a complete $2$-equitable labeling
when $m$ or $n$ is even. They conjecture that every tree of even size has an
optimal $2$-equitable labeling.
\subsection{Hamming-graceful Labelings}
Mollard, Payan and Shixin \cite{MPS} introduced a generalization of
graceful graphs called Hamming-graceful. A graph $G =(V, E)$ is called
{\em Hamming-graceful}\subindex{graph}{Hamming-graceful}\index{Hamming-graceful graph}
if there exists an injective labeling $g$ from
$V$ to the set of binary $|E|$-tuples such that
$\{d(g(v),g(u))| uv \in E\} = \{1, 2, \ldots,|E|\}$ where $d$ is the
Hamming distance.
Shixin and Yu \cite{ShY} have shown that all graceful graphs are
Hamming-graceful; all trees are Hamming-graceful; $C_n$ is
Hamming-graceful if
and only if $n\equiv 0$ or 3 (mod 4); if $K_n$ is Hamming-graceful, then
$n$ has the form $k^2$ or $ k^2 + 2; K_n$ is Hamming-graceful for $n =
2, 3, 4, 6, 9, 11, 16, $ and 18. They conjecture that $K_n$ is
Hamming-graceful for $n$ of the form $k^2$ and $k^2 +2$ for $k \geq 5$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of file