% Begin of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Encoding: ASCII
% Tex format: LaTeX
% Last modified: August 23, 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Graceful and Harmonious Labelings}
\subsection{Trees}\label{trees}
The Ringel-Kotzig conjecture that all trees\index{tree} are graceful has been the
focus of many papers. Kotzig \cite{HKR} has called the effort to prove it a
``disease." Among the trees known to be graceful are:
caterpillars \cite{Ro1} (a {\em caterpillar}\index{caterpillar} is a tree with the property that
the removal of its endpoints leaves a path); trees with at most 4
end-vertices \cite{HKR}, \cite{Zha} and \cite{JMW}; trees with diameter at most 5
\cite{Zha} and \cite{HrHa}; trees with at
most 27 vertices \cite{AlM};
symmetrical trees\subindex{tree}{symmetrical} (i.e., a rooted
tree in which every level contains vertices of the same degree) \cite{BeS}, \cite{PoS};
rooted trees where the roots have odd degree and the lengths of the paths
from the root to the leaves differ by at most one and all the internal vertices
have the same parity \cite{C9};
% the graph obtained by identifying the endpoints any
%number of paths of a fixed length;
% \cite{Sar}\marginpar{!!};
%
% but what is Sar? reference is missing!!
%
regular bamboo trees\index{bamboo tree} \cite{Sek}
(a rooted tree consisting of branches of equal length
the endpoints of which are identified
with end points of stars of equal size;
and olive trees\index{olive tree} \cite{PR} and \cite{AB2}
(a rooted tree consisting of $k$ branches,
where the $i$th branch is a path of length $i$). Aldred,
\v{S}ir\'{a}\v{n}
and \v{S}ir\'{a}\v{n}
\cite{ASS} have proved that the number of graceful labelings of $P_n$ grows at
least
as fast as $(5/3)^n$. They mention that this fact has an application to
topological graph theory.
Stanton and Zarnke \cite{StZa} and Koh, Rogers and Tan \cite{KRT3} gave methods for
combining graceful trees to yield larger graceful trees.
Burzio and Ferrarese \cite{BurF} have shown that the graph obtained from any
graceful tree by subdividing\index{subdivision} every edge is also graceful. Morgan \cite{Mor2} has used
Skolem sequences\index{Skolem sequence} to construct classes of graceful trees.
In 1979 Bermond \cite{Be} conjectured that lobsters are graceful
(a {\em lobster}\index{lobster} is a tree with the property that
the removal of the endpoints leaves a caterpillar).
Special cases of this conjecture have been done by Ng \cite{N1},
by Wang, Jin, Lu and Zhang \cite{WJLZ} and by Abhyanker \cite{Abh}. Morgan \cite{Mor1}
has shown that all
lobsters with perfect matchings are graceful. Morgan and Rees \cite{MR} have used
Skolem
and Hooked-Skolem sequences to generate classes of graceful lobsters.
Whether or not lobsters are harmonious seems to have
attracted no
attention thus far.
Chen, L\"{u} and Yeh \cite{CLY}
define a {\em firecracker}\index{firecracker} as a graph
obtained from the concatenation of stars by linking one leaf from each.
They also define a {\em banana tree}\index{banana tree} as a graph
obtained by connecting a vertex $v$ to one leaf
of each of any number of stars ($v$ is not in any of the stars).
They proved that firecrackers are graceful and
conjecture that banana trees are graceful. Various kinds of bananas trees
have been
shown to be graceful by Bhat-Nayak and Deshmukh \cite{BD2}, by Murugan and
Arumugam \cite{MA2}, \cite{MA4} and by Vilfred \cite{Vil1}.
Despite the efforts of many, the graceful tree conjecture remains open
even for trees with maximum degree 3.
Aldred and McKay
\cite{AlM} used a
computer to show that all trees with at most 26 vertices are harmonious.
That caterpillars are harmonious has been shown by
Graham and Sloane \cite{GS}. Cahit extended the notion of
gracefulness to directed graphs in \cite{C10}.
More specialized results about trees are contained in \cite{Be}, \cite{Bl}, \cite{KRT2},
\cite{LLi}, \cite{C4} and \cite{JLLLLZ}.
\subsection{Cycle-Related Graphs}\label{cycle_related_graphs}
Cycle-related graphs have been the major focus of attention.
Rosa \cite{Ro1} showed that the $n$-cycle $C_n$ is graceful if and only if
$n \equiv 0$ or 3 (mod 4) and Graham and Sloane \cite{GS} proved that $C_n$ is harmonious if
and only if $n \equiv 1$ or 3 (mod 4).
Wheels\index{wheel} $W_n = C_n + K_1$ are both graceful and harmonious -- \cite{F1}, \cite{HK} and
\cite{GS}. Notice that
a subgraph of a graceful (harmonious) graph need not be graceful (harmonious).
The $n$-cone\index{$n$-cone} (also called the
$n$-{\em point suspension}\index{$n$-point suspension} of $C_m$) $C_m +
\overline{K_n}$ has been shown to be graceful when $m
\equiv 0$ or
3 (mod 12) by Bhat-Nayak and Selvam \cite{BNS}. When $n$ is even and $m$ is
2, 6 or 10 (mod 12) $C_m + \overline{K_n}$ violates the parity condition
for a
graceful graph. Bhat-Nayak and Selvam \cite{BNS} also prove that the following
cones are graceful:
$C_4 + \overline{K_n}, C_5+ \overline{K_2}, C_7 + \overline{K_n}, C_9 +
\overline{K_2}, C_{11} + \overline{K_n}$ and
$C_{19} + \overline{K_n}$.
The {\em helm}\index{helm} $H_n$ is the graph obtained
from a wheel by attaching a pendant edge at each vertex of the $n$-cycle.
Helms
have been shown to be graceful \cite{AF} and harmonious \cite{Gn}, \cite{LiuY3},
\cite{LiuY4}
(see also \cite{LZ2}, \cite{SY1}, \cite{LiuB2}, \cite{DL3} and \cite{RP1}). Koh, et al. \cite{KRTY}
define a
{\em web}\index{web} graph as one obtained by joining the pendant points of a helm
to form
a cycle and then adding a single pendant edge to each vertex of this outer
cycle.
They asked whether such graphs are graceful.
This was proved by Kang, Liang, Gao and Yang
\cite{KLGY}. Yang has extended the notion of a web by iterating the process of adding pendant
points and joining them to form a
cycle and then adding pendant points to the new cycle. In his notation, $W(2,n)$ is the web graph whereas
$W(t,n)$ is the generalized web with $t ~n$-cycles.
Yang has shown that $W(3,n)$ and $W(4,n)$ are graceful (see
\cite{KLGY}), Abhyanker and Bhat-Nayak \cite{AB1} have done $W(5,n)$ and
Abhyanker
\cite{Abh} has done $W(t,5)$ for $5\leq t \leq 13$.
Gnanajothi
\cite{Gn} has shown that webs with odd cycles are harmonious.
Seoud and Youssef \cite{SY1} define a {\em closed helm}\index{closed helm} as the graph obtained
from a helm by joining each pendant vertex to form a cycle and a
{\em flower}\index{flower} as the graph obtained from a helm by joining each pendant vertex
to the central vertex of the helm. They prove that closed helms and
flowers are harmonious when the cycles are odd.
A {\em gear graph}\index{gear graph} is obtained from the wheel by adding a vertex
between every
pair of adjacent vertices of the cycle. Ma and Feng \cite{MF2} have proved
all gears are graceful.
Liu \cite{LiuY3} has shown that if two or more vertices are inserted between
every pair of vertices of the $n$-cycle of the wheel $W_n$, the resulting
graph is
graceful. Liu \cite{LiuY1} has also proved that the graph obtain from a gear
graph by attaching one or more pendant points to each vertex
between the cycle vertices is graceful.
Abhyanker \cite{Abh} has investigated various unicyclic
graphs\subindex{graph}{unicyclic}. He proved that
the unicyclic graphs obtained by identifying one vertex of $C_4$ with
the root of the olive tree with $2n$ branches and identifying an adjacent
vertex on $C_4$ with the end point of the path $P_{2n-2}$ are graceful.
He showed that if one attaches any number of pendent edges to
these unicyclic graphs at the vertex of $C_4$ that is adjacent to the root
of the olive tree but not adjacent to the end vertex of the attached path
the resulting graphs are graceful.
Likewise, he proved that the graph obtained by deleting the branch of
length 1
from an olive tree with $2n$ branches and identifying the root of the edge
deleted tree with a vertex of a cycle of the form $C_{2n + 3}$ is
graceful. He also has a number of results similar to these.
Delorme, et al. \cite{DMTKT} and Ma and Feng \cite{MF1} showed that any cycle with
a chord\index{chord} is graceful. This was first conjectured by Bodendiek, Schumacher and
Wegner \cite{BSW2}, who proved various special cases.
Koh and Yap \cite{KY} generalized this by defining a {\em cycle with a}
$P_k$-{\em chord}\index{cycle with a $P_k$-chord} to be a cycle with the path $P_{k}$ joining two
nonconsecutive vertices of the cycle.
They proved that these graphs are graceful when $k=3$ and conjectured that all
cycles with a $P_{k}$-chord are graceful.
This was proved for $k \geq 4$ by Punnim and Pabhapote in 1987 \cite{PP}. Chen
\cite{CheZ} obtained the same result except for three cases
which were then handled by Gao \cite{Gu2}.
Xu \cite{XuS1} proved that all cycles with a chord are harmonious except for
$C_6$ in the case where the distance in $C_6$ between the endpoints of the
chord is 2.
The gracefulness of cycles with consecutive chords have also been investigated.
For $3\leq p \leq n-r$, let $C_n(p,r)$ denote the $n$-cycle with consecutive vertices
$v_1,v_2,\ldots,v_n$ to which the $r$ chords $v_1v_p, v_1v_{p+1},\ldots,v_1v_{p+r-1}$ have been added.
Koh and others, \cite{KRTY} and \cite{KP}, have handled the cases $r=2,3$ and $n-3$
where $n$ is the length of the cycle.
Goh and Lim \cite{GoL} then proved that all remaining cases are graceful.
Moreover,
Ma \cite{Ma} has shown that $C_n(p,n-p)$ is graceful when $p \equiv 0,3$ (mod 4) and
Ma, Liu and Liu \cite{MLL} have proved other special cases of these graphs are
graceful.
Ma also proved that if one adds to the graph $C_n(3,n-3)$ any number $k_i$
of paths of length 2 from
the vertex $v_1$ to the vertex $v_i$ for $i = 2,\ldots,n$, the resulting graph is graceful.
Chen \cite{CheZ} has shown that apart from four exceptional cases, a graph
consisting of three independent paths\index{path} joining two vertices of a
cycle is graceful.
This generalizes the result that a cycle plus a chord is graceful.
Liu \cite{LiuR} has shown that the $n$-cycle with consecutive vertices
$v_1, v_2, \ldots, v_n$ to which the chords $v_1 v_k$ and
$v_1 v_{k+2}~~ (2 \leq k \leq n-3)$ are adjoined is graceful.
In \cite{DL2} Deb and Limaye use the notation $C(n,k)$ to denote the cycle
$C_n$ with $k$ cords sharing a common endpoint.
For certain choices of $n$ and $k$ there is a unique $C(n,k)$ graph and
for other choices there is more than one graph possible. They call these
{\em shell-type} graphs\subindex{graph}{shell-type} and they call the
unique graph $C(n, n-3)$ a {\em shell}\index{shell}.
Notice that the shell $C(n, n-3)$ is the same as the fan $F_{n-1}$. Deb
and Limaye define a {\em multiple shell}\index{multiple shell}\subindex{shell}{multiple}
to be a collection of edge
disjoint shells that have their apex in common. They show that a variety of
multiple shells are harmonious and they conjecture that all multiple
shells are harmonious.
Sethuraman and Dhavamani \cite{SD1} use $H(n,t)$ to denote the graph obtained
from the cycle $C_n$ by adding $t$ consecutive chords incident with a
common vertex. If the common vertex is $u$ and $v$ is adjacent to $u$,
then for $k \geq 1,~ n \geq 4$ and $1 \leq t \leq n - 3$, Sethuraman and
Dhavamani denote by $G(n,t,k)$ the graph obtained by taking the union of
$k$ copies of $H(n,k)$ with the edge $uv$ identified. They conjecture that
every graph $G(n,t,k)$ is graceful. They prove the conjecture for the case
that $t = n-3$.
For $i = 1,2,
\ldots, n$ let $v_{i,1},v_{i,2}, \ldots, v_{i,2m}$ be the successive vertices of
$n$ copies of $C_{2m}$. Sekar \cite{Sek} defines a chain of cycles $C_{2m,n}$ as
the graph obtained by identifying $v_{i,m}$ and $v_{i + 1,m}$ for $i = 1,2,
\ldots, n-1$. He proves that $C_{6,2k}$ and $C_{8,n}$ are graceful for all $k$
and all $n$.
Truszczy\'{n}ski \cite{T} studied unicyclic graphs\index{unicyclic graph}
(i.e., graphs with a unique cycle) and
proved several classes of such graphs are graceful.
Among these are what he calls dragons.
A {\em dragon}\index{dragon} is formed by joining the end point of a path to a cycle
(Koh, et al. \cite{KRTY} call these {\em tadpoles}\index{tadpoles}).
This work led Truszczy\'{n}ski to conjecture that all unicyclic graphs except
$C_{n}$, where $n \equiv$ 1 or 2 (mod 4), are graceful. Guo \cite{Gu1} has shown
that dragons are graceful when the length of the cycle is congruent to 1 or 2
(mod 4). In his Master's thesis,
Doma \cite{Dom} investigates the gracefulness of various unicyclic graphs where
the cycle has up to 9 vertices.
Because of the immense diversity of unicyclic graphs, a proof of
Truszczy\'{n}ski's conjecture seems out of reach in the near future.
Cycles that share a common edge or a vertex have received some attention.
Murugan and Arumugan \cite{MA1} have shown that books\index{book} with $n$ pentagonal pages
(i.e., $nC_5$ with an edge in common) are graceful when $n$ is even and
not graceful when $n$ is odd.
Let $C_{n}^{(t)}$ denote the one-point union\index{one-point union} of $t$ cycles of length $n$.
Bermond and others (\cite{BBG} and \cite{BKT}) proved that $C_{3}^{(t)}$ (that is, the
friendship graph\index{friendship graph} or Dutch $t$-windmill)\index{Dutch $t$-windmill}
is graceful if and only if $t \equiv$ 0 or 1 (mod 4) while
Graham and Sloane \cite{GS} proved $C_{3}^{(t)}$ is harmonious if and only if
$t \not\equiv 2$ (mod 4).
Koh et al. \cite{KRLT} conjecture that $C_{n}^{(t)}$ is graceful if and only if
$ nt \equiv 0$ or $3$ (mod 4). Qian \cite{Q} verifies this conjecture for the
case that $t = 2$ and $n$ is even.
Figueroa-Centeno, Ichishima and
Muntaner-Batle \cite{FIM6} have shown
that if $m \equiv 0$ (mod 4) then the one-point union of 2, 3 or 4
copies of $C_m$ admits a special kind of graceful labeling called an
$\alpha$-valuation\index{$\alpha$-valuation} (see Section~\ref{alpha_labelings}) and if
$m \equiv 2$ (mod 4) then the one-point union of 2 or 4
copies of $C_m$ admits an $\alpha$-valuation.
Bodendiek, Schumacher and Wegner \cite{BSW1} proved that the one-point union of
any two cycles is graceful when the number of edges is congruent to 0 or 3
modulo 4.
(The other cases violate the necessary parity condition.)
Shee \cite{S2} has proved that $C_4^{(t)}$ is graceful for all $t$.
Seoud and Youssef \cite{SY8} have shown that the one-point union of
a triangle and $C_n$ is harmonious if and only if $n \equiv 1$ (mod 4) and that
if the one-point union of two cycles is
harmonious then the number of edges is divisible by 4. The question of whether
this latter condition is sufficent is open.
Figueroa-Centeno, Ichishima and Muntaner-Batle \cite{FIM6} have shown that if $G$ is
harmonious then the one-point union of an odd number of copies of
$G$ using the vertex labeled 0 as the shared point is harmonious.
Sethuraman and Selvaraju \cite{SS6} have shown that for a variety of choices of
points the one point union of any number of non-isomorphic complete bipartite
graphs\subindex{complete}{bipartite graph} is graceful. They raise the question of whether this is true for all
choices of the common point.
Another class of cycle-related graphs is that of triangular
cacti. A {\em triangular cactus}\subindex{cactus}{triangular}
is a connected graph all of whose blocks are triangles.
A {\em triangular snake}\index{snake}
is a triangular cactus whose block-cutpoint-graph is a
path (a triangular snake is obtained from a path $v_1,v_2,\ldots,v_n$ by
joining $v_i$ and $v_{i + 1}$ to a new vertex $w_i$ for $i = 1, 2,
\ldots, n -1$).
Rosa \cite{Ro2} conjectured that all triangular cacti with $t \equiv$ 0 or 1
(mod 4)
blocks are graceful (the cases where $t \equiv$ 2 or 3 (mod 4) fail to be
graceful because of the parity condition.)
Moulton \cite{Mo} proved the conjecture for all triangular snakes.
A proof of the general case (i.e., all triangular cacti) seems hopelessly
difficult. Liu and Zhang \cite{LZ2} gave an incorrect proof that
triangular snakes with an odd number of triangles are harmonious
while triangular snakes with $n \equiv 2$ (mod 4) triangles are
not harmonious. Xu \cite{XuS2} subsequently proved that triangular snakes are
harmonious if and only if the number of triangles is not congruent to 2
(mod 4).
Defining an $n$-polygonal snake\subindex{snake}{$n$-polygonal} analogous to triangular snakes, Sekar \cite{Sek} has
shown that such graphs are graceful when $n \equiv 0$ (mod 4), $(n \geq 8)$ and
when $n \equiv 2$ (mod 4) and the number of polygons is even. Gnanajothi \cite[pp. 31--34]{Gn},
had earlier shown that quadrilateral snakes are graceful.
Grace \cite{Gr3} has proved that $K_{4}$-snakes
these are harmonious.
Rosa \cite{Ro2} has also considered analogously defined quadrilateral
and pentagonal cacti and examined small cases.
Several people have studied cycles with pendant edges attached.
Frucht \cite{F1} proved that any cycle with a pendant edge attached at each
vertex (i.e., a ``crown"\index{crown}) is graceful.
Bu, Zhang and He \cite{BZH} and Barrientos \cite{Bar4} have
shown that any cycle with a fixed number of pendant edges adjoined to each
vertex is graceful. Barrientos \cite{Bar4} proved that the graph obtained from a
wheel by attaching one pendant edge to each vertex is graceful.
Grace \cite{Gr2} showed that an odd cycle with one or more pendant edges at
each vertex
is harmonious and conjectured that an even cycle with one pendant edge
attached
at each vertex is harmonious. This conjecture has been proved by Liu and
Zhang \cite{LZ1}, Liu \cite{LiuY3} and \cite{LiuY4}, Huang \cite{Hua} and Bu \cite{Bu2}.
Sekar \cite{Sek} has
shown that the graph obtained by attaching a path of fixed length to each vertex
of a cycle is graceful. For any $n \geq 3$ and any $t$ with $1 \leq t \leq n$,
let $C_{n}^{+t}$ denote
the class of graphs formed by adding a single pendant edge to $t$ vertices of
a cycle of length $n$. Ropp \cite{Rop} proved that for every $n$ and $t$ the
class $C_{n}^{+t}$ contains a graceful graph.
Gallian and Ropp \cite{Ga2} conjectured that for all $n$ and $t$, all
members of $C_{n}^{+t}$ are graceful. This was proved by Qian \cite{Q} and by
Kang, Liang, Gao and Yang \cite{KLGY}. Of course, this is just a special
case of the aforementioned
conjecture of Truszczy\'{n}ski that all unicyclic graphs except $C_n$ for
$ n \equiv 1$ or 2 (mod 4) are
graceful. Sekar \cite{Sek} proved that the graph obtained by identifying an endpoint
of a star with a vertex of a cycle is graceful.
\subsection{Product Related Graphs}\label{product_related_graphs}
Graphs that are cartesian products\index{Cartesian product}
and related graphs have been the subject of many papers.
That planar grids, $P_{m} \times P_{n}$, are graceful was proved by Acharya
and Gill \cite{AG} in 1978
although the much simpler labeling scheme given by Maheo \cite{Mah} in 1980
for $P_m \times P_2$ readily extends to all grids\index{grid}.
In 1980 Graham and Sloane \cite{GS} proved ladders\index{ladder},
$P_{m} \times P_{2},$ are
harmonious when $m > 2$ and in 1992 Jungreis and Reid \cite{JR} showed that
the grids $P_{m} \times P_{n}$ are harmonious when $(m,n) \neq (2,2)$.
A few people have looked at graphs obtained from planar grids in various ways.
Kathiresan \cite{Kat1} has shown that graphs obtained from ladders by
subdividing\index{subdivision}
each step exactly once are graceful and that graphs obtained by appending
an edge to each vertex of a ladder are graceful \cite{Kat2}.
Acharya \cite{A3} has shown that certain subgraphs of grid graphs are graceful.
Lee \cite{L1} defines a {\em Mongolian tent}\index{Mongolian tent}
as a graph obtained from $P_{m} \times P_{n}$,
$n$ odd, by adding one extra vertex above the grid and joining every other vertex
of the top row of $P_{m} \times P_{n}$ to the new vertex.
A {\em Mongolian village}\index{Mongolian village} is a graph formed by
successively amalgamating copies of Mongolian
tents with the same number of rows so that adjacent tents share a column. Lee
proves that Mongolian tents and villages are graceful. A
{\em Young tableau}\index{Young tableau} is a subgraph of $P_{m} \times P_{n}$ obtained by
retaining the first two rows of $P_{m} \times P_{n}$ and deleting vertices from
the right hand end of other rows in such a way that the lengths of the
successive rows form a nonincreasing sequence. Lee and K. C. Ng \cite{LNK}
have proved that
all Young tableaus are graceful. Lee \cite{L1} has also defined a
variation of
Mongolian tents by adding an extra vertex above the top row of a Young tableau
and joining every other vertex of that row to the extra vertex. He proves
these graphs are graceful.
{\em Prisms}\index{prism} are graphs of the form $C_{m} \times P_{n}$.
These can be viewed as grids on cylinders.
In 1977 Bodendiek, Schumacher and Wegner \cite{BSW2} proved that $C_{m} \times
P_{2}$
is graceful when $m \equiv 0 \pmod{4}.$ According to the survey by
Bermond \cite{Be}, T. Gangopadhyay and S. P. Rao Hebbare did the case that $m$
is even
about the same time. In a 1979 paper, Frucht \cite{F1} stated without proof that
he had done all $m$. A complete proof of all cases and some related results
were given by Frucht and Gallian \cite{FG} in 1988.
In 1992 Jungreis and Reid \cite{JR} proved that all $C_{m} \times P_{n}$ are
graceful when $m$ and $n$ are even or when $m \equiv 0$ (mod 4).
Yang and Wang have shown that the prisms $C_{4n + 2} \times P_{4m +
3}$ \cite{YW3}, $C_n \times P_2$ \cite{YW1} and $C_6 \times P_m (m \geq 2)$ (see \cite{YW3})
are graceful. Singh \cite{Sin1} proved that $C_3 \times P_n$ is graceful
for all $n$.
In their 1980 paper Graham and Sloane \cite{GS} proved that $C_{m} \times P_{n}$ is
harmonious when $n$ is odd and they used a computer to show $C_{4} \times P_{2}$,
the cube\index{cube}, is not harmonious.
In 1992 Gallian, Prout and Winters \cite{GPW} proved that $C_{m} \times P_{2}$ is
harmonious when $m \neq 4$.
In 1992, Jungreis and Reid \cite{JR} showed that $C_{4} \times P_{n}$ is
harmonious when $n \geq 3$.
Huang and Skiena \cite{HuS} have shown that $C_{m} \times P_n$ is graceful for
all $n$ when $m$ is even and for all $n$ with $3 \leq n\leq 12$ when $m$
is odd. Abhyanker \cite{Abh} proved that the graphs obtained from $C_{2m + 1}
\times P_5$ by adding a pendent edge to each vextex of the outercycle
is graceful.
Torus grids\index{torus grid} are graphs of the form $C_{m} \times C_{n}$\ $(m > 2, n > 2)$.
Very little success has been achieved with these graphs.
The graceful parity condition is violated for $C_m \times
C_n$ when $m$
and $n$ are odd and the harmonious parity condition \cite[Theorem 11]{GS} is
violated for $C_m \times C_n$ when $m \equiv 1,2,3$ (mod 4) and $n$ is odd.
In 1992 Jungreis and Reid \cite{JR}
showed that $C_{m} \times C_{n}$ is graceful when $m \equiv 0$ (mod 4) and $n$
is even.
A complete solution to both the graceful and harmonious torus grid problems will most
likely involve a large number of cases.
There has been some work done on prism-related graphs.
Gallian, Prout and Winters \cite{GPW} proved that all
prisms\index{prism} $C_{m} \times P_{2}$ with a single vertex deleted or single edge deleted
are graceful and harmonious.
The {\em M\"{o}bius ladder}\index{M\"{o}bius ladder} $M_{n}$ is the graph obtained from the ladder
$P_{n} \times P_{2}$ by joining the opposite end points of the two copies of
$P_{n}$.
In 1989 Gallian \cite{Ga1} showed that all M\"{o}bius ladders are graceful and
all but $M_{3}$ are harmonious.
Ropp \cite{Rop} has examined two classes of prisms with pendant edges attached.
He proved that all $C_{m} \times P_{2}$ with a single pendant edge at each
vertex are graceful and all $C_{m} \times P_{2}$ with a single pendant
edge at each vertex of one of the cycles are graceful.
Another class of cartesian products that has been studied is that of books and
``stacked" books.
The {\em book}\index{book} $B_{m}$ is the graph $S_{m} \times P_{2}$ where $S_{m}$ is the
star with $m + 1$ vertices.
In 1980 Maheo \cite{Mah} proved that the books of the form $B_{2m}$ are
graceful and conjectured that the books $B_{4m+1}$ were also graceful.
(The books $B_{4m + 3}$ do not satisfy the graceful parity condition.)
This conjecture was verified by Delorme \cite{D} in 1980.
Maheo \cite{Mah} also proved that $L_{n} \times P_{2}$ and $B_{2m} \times
P_{2}$ are graceful.
Both Grace \cite{Gr1} and Reid (see \cite{GJ}) have given harmonious labelings for $B_{2m}$.
The books $B_{4m+3}$ do not satisfy the harmonious parity condition
\cite[Theorem 11]{GS}.
Gallian and Jungreis \cite{GJ} conjectured that the books $B_{4m+1}$ are
harmonious.
Gnanajothi \cite{Gn} has verified this conjecture by showing $B_{4m + 1}$ has
an even stronger form of labeling -- see Section~\ref{sequential_labelings}.
Liang \cite{Li1} also proved the conjecture.
In their
1988 paper Gallian and Jungreis \cite{GJ}
defined a {\em stacked book}\subindex{book}{stacked} as a graph of the form $S_{m} \times P_{n}$.
They proved that the stacked books of the form $S_{2m} \times P_{n}$ are
graceful and posed the case $S_{2m + 1} \times P_{n}$ as an open question.
The {\em n-cube}\index{$n$-cube} $K_{2} \times K_{2} \times \cdots \times K_{2}$ ($n$
copies) was shown to be graceful by Kotzig \cite{K3}---see also \cite{Mah}.
In 1986 Reid \cite{Re} found a harmonious labeling for
$K_{4} \times P_{n}$. Petrie and Smith \cite{PS} have investigated graceful
labelings of graphs
as an exercise in constraint satisfaction. They have
shown that $K_m \times P_n$ is
graceful for $(m,n) = (4,2), (4,3), (4,4), (4,5)$ and (5,2) but not
is graceful for $(3,3)$ and $(6,2).$
The labeling for $K_5 \times P_2$ is the unique graceful
labeling. They also considered the graph obtained by identifying the hubs
of two copies of $W_n$. The resulting graph is not graceful when $n =3$
but is graceful when $n$ is 4 and 5.
The composition\index{composition}\subindex{graph}{composition}
$G_1[G_2]$ is the graph having vertex set $V(G_1) \times V(G_2)$
and edge set $\{(x_1,y_1),(x_2,y_2)|~x_1x_2 \in E(G_1) \mbox{ or } x_1= x_2
\mbox{ and } y_1y_2 \in E(G_2)\}$.
The symmetric product $G_1 \oplus G_2$ of graphs
$G_1$ and $G_2$ is the graph with vertex set
$V(G_1) \times V(G_2)$
and edge set $\{(x_1,y_1),(x_2,y_2)|~x_1x_2 \in E(G_1) \mbox{ or } y_1y_2
\in E(G_2) \mbox{ but not both}\}$.
Seoud and Youssef \cite{SY4} have proved that $P_n \oplus \overline{K_2}$ is
graceful when $n > 1$ and $P_n[P_2]$ is harmonious for all $n$.
They also observe that the graphs $C_m \oplus C_n$ and $C_m[C_n]$
violates parity conditions for graceful and harmonious graphs when $m$ and
$n$ are odd.
\subsection{Complete Graphs}\label{complete_graphs}
The questions of the gracefulness and
harmoniousness of the complete graphs\subindex{graph}{complete}\subindex{complete}{graph}
$K_{n}$ have been answered.
In each case the answer is positive if and only if $n \leq 4$ (\cite{Go}, \cite{Si},
\cite{GS}, \cite{BH}).
Both Rosa \cite{Ro1} and Golomb \cite{Go} proved that the complete bipartite
graphs\subindex{complete}{bipartite graph}
$K_{m,n}$ are graceful while Graham and Sloane \cite{GS} showed they are harmonious
if and only if $m$ or $n = 1$.
Aravamudhan and Murugan \cite{AM} have shown that the complete tripartite
graph\subindex{complete}{tripartite graph}
$K_{1,m,n}$ is both graceful and harmonious while Gnanajothi \cite[pp. 25--31]{Gn}
has shown that $K_{1,1,m,n}$ is both
graceful and harmonious and $K_{2,m,n}$ is graceful. Some of the same
results have been obtained by Seoud and Youssef \cite{SY3} who also observed
that when $m, n$ and $p$ are congruent to 2 (mod 4), $K_{m,n,p}$ violates
the parity conditions for harmonious graphs.
Beutner and Harborth \cite{BH} show that $K_n -e$ ($K_n$ with an edge deleted)
is graceful only if $n \leq 5$,
any $K_n - 2e~ (K_n$ with two edges deleted) is graceful only if $n
\leq 6$ and any $K_n - 3e$ is
graceful only if $n
\leq 6$. They also determine all graceful graphs $K_n -G$ where $G$ is
$K_{1,a}$ with $a \leq n -2$ and where $G$ is a matching $M_a$ with $2a \leq n$.
They give graceful labelings for $K_{1,m,n}, K_{2,m,n}, K_{1,1,m,n}$ and
conjecture that these and $K_{m,n}$ are the only complete multipartite
graphs
that are graceful. They have verified this conjecture for graphs with up to 23
vertices via computer.
Define the {\em windmill}\index{windmill} graphs $K_{n}^{(m)} (n > 3)$ to be the family
of graphs consisting of $m$ copies of $K_{n}$ with a vertex in common.
A necessary condition for $K_{n}^{(m)}$ to be graceful is that $n \leq 5$
-- see \cite{KRTY}.
Bermond \cite{Be} has conjectured that $K_{4}^{(m)}$ is graceful for all $m \geq 4$.
This is known to be true for $m \leq 22$ \cite{HuS}.
Bermond, Kotzig and Turgeon \cite{BKT} proved that $K_{n}^{(m)}$ is not graceful
when $n=4$ and $m=2$
or 3 and when $m=2$ and $n=5$.
In 1982 Hsu \cite{Hs} proved that $K_{4}^{(m)}$ is harmonious for all $m$.
Graham and Sloane \cite{GS} conjectured that $K_{n}^{(2)}$ is harmonious if and only
if $n=4$.
They verified this conjecture for the cases that $n$ is odd or $n=6$.
Liu \cite{LiuB2} has shown that $K_{n}^{(2)}$ is not harmonious if $n =
2^ap_1^{a_1}\cdots p_s^{a_s}$ where $a, a_1, \ldots, a_s$ are positive
integers and $p_1, \ldots, p_s$ are distinct odd primes and there is a $j$
for which $p_j \equiv 3$ (mod 4) and $a_j$ is odd. He also shows
that $K_n^{(3)}$ is not harmonious when $n \equiv 0$ (mod 4) and
$3n = 4^e(8k + 7)$ or $n \equiv 5$ (mod 8). Koh et al. \cite{KRLT} and
Rajasingh and Pushpam \cite{RP2} have shown that $K_{m,n}^{(t)},$
the one-point union\index{one-point union} of $t$ copies of $K_{m,n}$, is graceful.
Sethuraman and Selvaraju \cite{SS2} have proved that the one-point union of
graphs of the form $K_{2,m_i}$ for $i = 1,2, \ldots, n$ where the union
is taken at a vertex from the partite set with 2 vertices is graceful if
at most two of the $m_i$ are equal. They conjecture that the restriction
that at most two of the $m_i$ are equal is not necessary.
Koh et al. \cite{KRTY} introduced the notation $B(n,r,m)$ for the graph consisting
of $m$ copies of $K_{n}$ with a $K_{r}$ in common ($n \geq r$). (We
note that Guo \cite{Gu2} has used
the notation $B(n,r,m)$ to denote three independent paths of lengths $n,
r$ and $m$ joining two vertices.) Bermond \cite{Be} raised the
question: ``For which $m, n$ and $r$ is $B(n,r,m)$ graceful?" Of course, the
case $r = 1$ is the same as $K_{n}^{(m)}$. For $r > 1, B(n,r,m)$ is graceful
in the following cases: $n = 3, ~r = 2, m \geq 1$ \cite{KRL}; $n = 4, ~r = 2, m
\geq 1$
\cite{D}; $n = 4, ~r = 3, m \geq 1$ (see \cite{Be}), \cite{KRL}. Seoud and Youssef \cite{SY3}
have proved $B(3,2,m)$ and $B(4,3,m)$ are harmonious.
Liu \cite{LiuB1} has shown that if there is a prime $p$ such that $p \equiv 3$
(mod 4) and $p$ divides both $n$ and $n-2$ and the highest power of $p$
that divides $n$ and $n-2$ is odd, then $B(n,2,2)$ is not graceful.
More generally, Bermond and Farhi \cite{BF} have considered the class of graphs
consisting of $m$ copies of $K_{n}$ having exactly $k$ copies of $K_{r}$
in common. They proved such graphs are not graceful for $n$ sufficiently large
compared to $r$.
Sethuraman and Elumalai \cite{SE1} have shown that $K_{1,m,n}$ with a
pendent edge
attached to each vertex is graceful and $K_{m,n}$ with a pendent edge attached
at each vertex is graceful when $m$ is even and $m \leq n \leq 2m + 4$ and
when $m$ is odd and $m \leq n \leq 2m -1$. In
\cite{SK} Sethuraman and Kishore determine the graceful graphs that are the
union\index{union}
of $n$ copies of $K_4$ with $i$ edges deleted for $1 \leq i \leq 5$ with
one edge in common. The only cases that are not graceful are
those graphs where the members of the union are $C_4$ for
$n \equiv 3$ mod 4
and where the members of the union are $P_2$. They conjecture that these
two cases are the only instances of edge induced subgraphs of the union of
$n$ copies of $K_4$ with one edge in common that are not graceful.
Sethuraman and Selvaraju \cite{SS8} have shown that union of any number of
copies of $K_4$ with an edge deleted and one edge in common is harmonious.
\subsection{Disconnected Graphs}\label{disconnected_graphs}
\index{disconnected graph}\subindex{graph}{disconnected}
There have been many papers dealing with graphs that are not connected.
In 1975 Kotzig \cite{K2} considered graphs that are the disjoint union of $r$
cycles of length $s$, denoted by $rC_s$.
When $rs \equiv 1$ or 2 (mod 4), these graphs violate the parity
condition and so are not graceful.
Kotzig proved that when $r = 3$ and $s = 4k > 4$, then $rC_s$ has a stronger
form of graceful labeling called $\alpha$-labeling\index{$\alpha$-labeling}
(see \S \ref{alpha_labelings}) whereas
when $r \geq 2$ and $s = 3$ or 5, $rC_s$ is not graceful.
In 1984 Kotzig \cite{K4} once again investigated the gracefulness of $rC_s$ as
well as graphs that are the disjoint union\index{disjoint union} of odd
cycles.
For graphs of the latter kind he gives several necessary conditions.
His paper concludes with an elaborate table that summarizes what was then
known about
the gracefulness of $rC_s$. He \cite{He} has shown that graphs of the form
$2C_{2m}$ and graphs obtained by connecting two copies of $C_{2m}$ with
an edge are graceful.
Cahit
\cite{C7} has shown that $rC_s$ is harmonious when $r$ and $s$ are odd and
Seoud, Abdel Maqsoud and Sheehan \cite{SAS1}
noted that when $r$ or $s$ is even, $rC_s$ is not harmonious.
Seoud, Abdel Maqsoud and Sheehan \cite{SAS1} proved that
$C_n \cup C_{n + 1}$ is
harmonious if and only if $n \geq 4$.
They conjecture that $C_3 \cup C_{2n}$ is harmonious when $n \geq 3$.
This conjecture was proved when Yang, Lu, and Zeng \cite{YLZ} showed that
all
graphs of the form $C_{2j + 1} \cup C_{2n}$ are harmonious except for
$(n,j) = (2,1)$.
In 1978 Kotzig and Turgeon \cite{KT} proved that $mK_n$ (i.e., the union of $m$
disjoint copies of $K_n$) is graceful if and only if $m = 1$ and $n \leq 4$.
Liu and Zhang \cite{LZ2} have shown that
$mK_n$ is not harmonious for $n$ odd and $m \equiv 2$ (mod 4) and
is harmonious for $n = 3$ and $m$ odd.
They conjecture that $mK_3$ is not harmonious when $m \equiv 0$ (mod 4).
Bu and Cao \cite{BuC1} give some sufficient conditions for the gracefulness of
graphs of the form $K_{m,n} \cup G$ and they prove that $K_{m,n} \cup
P_t$ and
the disjoint union of complete bipartite graphs are graceful under some
conditions.
A {\em Skolem sequence}\index{Skolem sequence} of order $n$ is a sequence $s\sb 1,s\sb 2,\ldots,
s\sb {2n}$
of $2n$
terms such that, for each $k\in \{1,2,\ldots,n\}$, there exist exactly two
subscripts $i(k)$ and
$j(k)$ with $s\sb {i(k)}=s\sb {j(k)}=k$ and $\vert i(k)-j(k)\vert =k$. A
Skolem
sequence of
order $n$ exists if and only if $n\equiv 0$ or 1 (mod 4).
Abrham \cite{Ab2} has proved that any graceful $2$-regular graph of order
$n\equiv 0$ (mod 4) in which
all the
component cycles are even or of order $n\equiv 3$ (mod 4), with exactly
one component an odd cycle, can be used
to construct a Skolem sequence of order $n+1$. Also,
he showed that certain special
Skolem sequences of order $n$ can be used to generate graceful labelings
on certain $2$-regular graphs.
In 1985 Frucht and Salinas \cite{FS} conjectured that $C_s
\cup P_n$ is
graceful if and only if $s + n \geq 7$ and they proved the conjecture for
the case that $s = 4$.
Frucht \cite{F3} did the case the $s = 3$ and the case that $s = 2n+1$.
Bhat-Nayak and Deshmukh \cite{BD5} also did the case $s = 3$ and they
have done the cases of the\index{union}
form $C_{2x + 1} \cup P_{x -2\theta}$ where $1 \leq \theta \leq \lfloor
(x-2)/2\rfloor$ \cite{BD1}.
Choudum and Kishore \cite{CK2} have done the cases where $s \geq 5$ and $n
\geq (s + 5)/2$ and
Kishore \cite{Kis} did the case $ s= 5$. Gao and Liang \cite{GaL} have done the
following cases: $s > 4, n = 2$ (see also \cite{Gao}); $s = 4k, n = k+2, n = k
+3, n = 2k + 2;
s= 4k + 1, n = 2k, n = 3k -1, n = 4k -1; s = 4k + 2, n = 3k, n =3k + 1, n
= 4k + 1; s= 4k + 3, n = 2k + 1,n = 3k, n = 4k.$
Seoud, Abdel Maqsoud and Sheehan \cite{SAS2} did the case that $s = 2k$ ~($k
\geq 3$) and $n \geq k + 1$ as well as the cases where $s = 6, 8, 10, 12$ and
$n \geq 2$. Shimazu \cite{Shi} has handled the cases that $s \geq 5$ and $n = 2, s
\geq 4$ and $n = 3$ and $s = 2n + 2$ and $n \geq 2$. Liang \cite{Li2} has done
the following cases: $s = 4k, n = k +2, k +3, 2k + 1, 2k + 2, 2k + 3, 2k +
4, 2k + 5; s = 4k -1, n = 2k, 3k -1, 4k -1; s = 4k + 2, n = 3k, 3k + 1, 4k
+ 1; s = 4k + 3, n = 2k + 1, 3k, 4k$.
Youssef \cite{Yo1} proved that
$C_5 \cup S_n$ is graceful if and only if $ n = 1$ or 2 and that $C_6
\cup
S_n$ is graceful if and only if $n$ is odd or $n = 2$ or 4.
Seoud and Youssef \cite{SY2} have shown that $K_5
\cup K_{m,n},
K_{m,n} \cup K_{p,q} ~(m,n,p,q \geq 2), K_{m,n} \cup K_{p,q}\cup
K_{r,s}~~(m,n,p,q,r,s \geq 2, ~~ (p,q) \neq (2,2))$, and
$pK_{m,n} ~~(m,n \geq 2,(m,n) \neq (2,2))$ are graceful. They also prove
that $C_4 \cup K_{1,n}\;(n \neq 2)$
is not graceful whereas Choudum and Kishore \cite{CK4}, \cite{Kis} have proved that
$C_s \cup K_{1,n}$ is graceful for every $s \geq 7$ and $n \geq 1$.
Lee, Quach and Wang \cite{LQW} established the gracefulness of $P_s \cup K_{1,n}.$
Seoud and Wilson \cite{SeWi} have shown that $C_3 \cup K_4, C_3 \cup C_3 \cup
K_4$ and certain graphs of the form $C_3 \cup P_n$ and $C_3 \cup C_3
\cup P_n$ are not graceful.
Abrham and Kotzig \cite{AK4} proved that $C_p \cup C_q$ is graceful if and
only if $p + q \equiv 0$ or 3 (mod 4). Zhou
\cite{Zho} proved that $K_m \cup K_n ~(n > 1, m>1)$ is graceful if and only if
$\{m,n\} =
\{4,2\}$ or $\{5,2\}$. (C. Barrientos has called to my attention that $K_1 \cup
K_n$ is graceful if and only if $n = 3$ or 4.)
Shee \cite{S1} has shown that
graphs of the form $P_2 \cup C_{2k+1}\;
(k > 1), \;P_3 \cup C_{2k + 1},\; P_n \cup C_3$ and $S_n \cup C_{2k+1}$ all
satisfy a condition that is a bit weaker than harmonious.
Bhat-Nayak and Deshmukh \cite{BD3} have shown that $C_{4t} \cup K_{1,4t -1}$
and $C_{4t + 3} \cup K_{1,4t + 2}$ are graceful.
In considering graceful labelings of the disjoint unions of two or three
stars\index{star} with $e$ edges Yang and
Wang \cite{YW2}
permitted the vertex labels to range from 0 to $e + 1$ and 0 to $e + 2$,
respectively.
With these definitions of graceful, they proved that $S_m \cup S_n$ is
graceful if and only
if $m$ or $n$ is even and that $S_m \cup S_n \cup S_k$ is graceful if and
only if at least one of $m,n$ or $k$ is even ($m>1, n> 1,k>1 $).
Seoud and Youssef \cite{SY5} investigated the gracefulness of
specific families of the
form $G
\cup K_{m,n}$. They obtained the following results:
$C_3 \cup K_{m,n}$ is graceful if and only if $m \geq 2$ and $n \geq2$;
$C_4 \cup K_{m,n}$ is graceful if and only if $m \geq 2$ and $n \geq2$ or
$\{m,n\} =\{1,2\}$;
$C_7 \cup K_{m,n}$ and $C_8 \cup K_{m,n}$ are graceful for all $m$ and
$n$;
$mK_3 \cup nK_{1,r}$ is not graceful for all $m, n$ and $r$;
$K_i \cup K_{m,n}$ is graceful for $i \leq 4$ and $m\geq 2, n\geq2$ except
for $i = 2$ and $(m,n) = (2,2)$;
$K_5 \cup K_{1,n}$ is graceful for all $n$;
$K_6 \cup K_{1,n}$ is graceful if and only if $n$ is different
than 1 and 3.
Barrientos \cite{Bar6} has shown the following graphs are graceful: $C_6
\cup K_{1,2n + 1}; C_m \cup K_{s,t}$
for $m \equiv 0 \mbox{ or } 3$ (mod 4), $m \geq 11$ and $s \geq
1, t \geq 1;
\bigcup_{i = 1}^{t} K_{m_i, n_i}$ for $2 \leq m_i < n_i$; and $C_m \cup
\bigcup_{i = 1}^{t} K_{m_i, n_i}$ for $2 \leq m_i < n_i,
m \equiv 0 \mbox{ or } 3$ (mod 4), $m \geq 11$.
Youssef \cite{Yo2} has shown that if $G$ is harmonious then $mG$ and $G^m$ are
harmonious for
all odd $m$. He asks the question of whether $G$ is harmonious implies $G^m$ is
harmonious when $m \equiv 0$ (mod 4).
\subsection{Joins of Graphs}
A few classes of graphs that
are the join\subindex{graph}{joins} of graphs have been shown to be graceful and harmonious.
Among these are fans $P_{n} + K_{1}$ \cite{GS} and double fans $P_{n} +
\overline{K_{2}}$ \cite{GS}.
More generally, Reid \cite{Re} proved that $P_{n}
+ \overline{K_{t}}$ is harmonious and
Grace showed \cite{Gr2} that if $T$ is any graceful tree\index{tree}, then $T + \overline{K_{t}}$ is also
graceful. Fu and Wu \cite{FW} proved that if $T$ is a graceful tree, then $T +
S_k$ is graceful. Sethuraman and Selvaraju \cite{SS7} have shown that
$P_n + K_2$ is harmonious. They ask whether $S_n + P_n$ or $P_m + P_n$ is
harmonious.
Of course, wheels are of the form $C_{n} + K_{1}$ and are graceful and
harmonious. Hebbare \cite{H} showed that $S_{m} + K_{1}$ is graceful for all $m$.
Shee \cite{S1} has proved $K_{m,n} + K_1$ is harmonious and observed that various
cases of $K_{m,n} + K_t$ violate the harmonious parity condition in \cite{GS}.
Liu and Zhang
\cite{LZ2} have proved that $K_2 + K_2 + \cdots + K_2$ is
harmonious. Yuan and Zhu \cite{YZ} proved that $K_{m,n}
+ K _2$ is graceful and harmonious. Gnanajothi \cite[pp. 80--127]{Gn} obtained
the following:
$C_n + {\overline{K_2}}$ is harmonious when $n$ is odd and not harmonious when $n \equiv 2,4,6$ (mod 8);
$S_n + \overline{K_t}$ is harmonious; and
$P_n + \overline{K_t}$ is harmonious.
Balakrishnan and Kumar \cite{BK2} have proved that the join of $\overline{K}_n$
and two disjoint copies of $K_2$ is harmonious if and only if $n$ is even.
Bu \cite{Bu2} obtained partial results for the gracefulness of $K_n +
{\overline K_m}$.
Ram\'{i}rez-Alfons\'{i}n \cite{Ra} has proved that if $G$ is graceful and
$|V(G)| = |E(G)|= e$ and either 1 or $e$ is not a vertex label then $G +
\overline{K_t}$ is graceful for all $t$.
Seoud and Youssef \cite{SY4} have proved: the join of any two stars\index{star} is
graceful and harmonious; the join of any path and any star is
graceful; and $C_n + \overline {K_t}$ is harmonious for every
$t$ when $n$ is odd.
They also prove that if any edge is added to $K_{m,n}$ the resulting
graph is harmonious if $m$ or $n$ is at least 2.
Deng \cite{De} has shown certain cases of $C_n + \overline{K_t}$ are
harmonious.
Seoud and Youssef \cite{SY7} proved: the graph obtained by appending any
number of edges from the two vertices of degree $n \geq 2$ in $K_{2,n}$ is
not harmonious; dragons $D_{m,n}$ (i.e., $P_m$ is appended to
$C_n$) are not harmonious when $m + n$
is odd; and the disjoint union of any dragon and any number of cycles is
not harmonious when the resulting graph has odd order.
Youssef \cite{Yo1} has shown that if $G$ is a graceful graph with
$p$ vertices and $q$ edges with $p = q +
1$, then $G + S_n$ is graceful.
Sethuraman and Elumalai \cite{SE3} have proved that for every graph $G$
with $p$ vertices and $q$ edges
the graph $G + K_1 + \overline{K_m}$ is graceful when $m \geq 2^p - p -1 - q$.
As a corollary
they deduce that every graph is a vertex induced subgraph of a graceful graph.
Balakrishnan and Sampathkumar \cite{BS} ask for which $m \geq 3$ is the
graph $\overline{K_n} + mK_2$
graceful for all $n$. Bhat-Nayak and Gokhale \cite{BG} have proved that
$\overline{K_n} + 2K_2$ is not graceful. Youssef \cite{Yo1}
has shown that $\overline{K_n} + mK_2$ is graceful if $m \equiv 0$ or 1 (mod 4)
and that $\overline{K_n} + mK_2$ is not graceful if $n$ is odd and $m \equiv 2$
or 3 (mod 4).
Wu \cite{Wu4} calls a graceful graph with $n$ edges ($n \geq 1$) and $n + 1$ vertices
{\em vertex-saturated}\index{vertex-saturated}. He proves that for every
vertex-saturated graph $G$ the join of $G$ and $\overline {K_m}$ and the join of
$G$ and any star are graceful.
\subsection{Miscellaneous Results}\label{miscellaneous_results}
It is easy to see that $P_{n}^{2}$ is harmonious \cite{Gr2} while a proof that
$P_n^{2}$ is graceful has been given by Kang, Liang, Gao and Yang \cite{KLGY}.
($P_n^k$, the $k$th power of $P_n$,
is the graph
obtained from $P_n$ by adding edges that join all vertices $u$ and $v$ with
$d(u,v) = k$.)
This latter result
proved a conjecture of Grace \cite{Gr2}.
Seoud, Abdel Maqsoud and Sheeham \cite{SAS1} proved that $P_n^3$ is
harmonious and conjecture that $P_n^k$ is not harmonious when $k>3$.
However, Youssef \cite{Yo6} has observed that $P_8^4$ is harmonious.
Gnanajothi \cite[p. 50]{Gn} has shown that the graph that consists of
$n$ copies of $C_6$ that have exactly $P_4$ in common
is graceful if and only if $n$ is even.
For a fixed $n$, let $v_{i1}, v_{i2}, v_{i3}$ and
$v_{i4} \ (1 \leq i \leq n)$ be consecutive vertices of $n~$ 4-cycles.
Gnanajothi \cite[p. 35]{Gn} also proves that the graph
obtained by joining each $v_{i1}$ to $v_{i+1,3}$ is graceful for all
$n$ and
the generalized Petersen graph\subindex{Petersen graph}{generalized}
$P(n,k)$ is harmonious in all cases (see also \cite{LSchS}).
($P(n,k)$, where $n \geq 5$ and $ 1 \leq k \leq n$, has vertex set $\{a_0,a_1,\ldots, a_{n-1}, b_0,
b_1, \ldots, b_{n-1} \}$ and edge set $\{a_i a_{i+1} \mid i = 0, 1,
\ldots, n-1 \} \cup \{a_ib_i \mid i
= 0, 1, \ldots, n-1 \} \cup \{b_ib_
{i+k} \mid i = 0, 1, \ldots, n-1 \}$ where all subscripts are taken modulo
$n$ \cite{Wat}. The standard Petersen graph is $P(5,2)$.) The gracefulness of
the generalized Petersen graphs appears to be
an open problem.
Yuan and Zhu \cite{YZ} proved that $P_n^{2k}$ is harmonious when $1 \leq k
\leq (n-1)/2$
and that $P_n^{2k}$ has a stronger form of harmonious labeling (see
Section~\ref{sequential_labelings})
when $2k-1 \leq n \leq 4k-1$.
Cahit \cite{C7} defines a {\em $p$-star}\index{$p$-star} as the graph obtained by joining
$p$ disjoint paths of a fixed length $k$ to single vertex. He proves all
such graphs
are harmonious when $p$ is odd and when $k = 2$ and $p$ is even.
Sethuraman and Selvaraju \cite{SS1} define a graph $H$ to be a
{\em supersubdivision}\index{supersubdivision}
of a graph $G$, if every edge $uv$ of $G$ is replaced by $K_{2,m}~ ( m$
may vary for each edge) by identifying $u$ and $v$ with the two vertices
in $K_{2,m}$ that form one of the two partite sets. Sethuraman and
Selvaraju prove that every supersubdivision of a path is graceful and every
cycle has some supersubdivision that is graceful. They
conjecture that every supersubdivision of a star is graceful and that
paths and stars are the only graphs for which every supersubdivison is
graceful. In \cite{SS3} Sethuraman and Selvaraju prove that every connected
graph has some
supersubdivision that is graceful. They pose the question as to whether
this result is valid for disconnected graphs. They also ask
if there is any graph other than $K_{2,m}$ that can be used to
replace an edge of a connected graph to obtain a
supersubdivision that is graceful.
In \cite{SS4} Sethuraman and Selvaraju present an
algorithm that permits one to start with any non-trivial connected graph and
successively form supersubdivisions that have a strong form of graceful labeling
called an $\alpha$-labeling\index{$\alpha$-labeling} (see \S \ref{alpha_labelings}).
Kathiresan \cite{Kat4} uses the notation $P_{a,b}$ to denote the graph
obtained by identifying the end points of $b$ internally disjoint paths
each of length $a$. He conjectures that $P_{a,b}$ is graceful except when
$a$ is odd and $b \equiv 2 $ (mod 4). He proves the conjecture for the
case
that $a$ is even and $b$ is odd. Sekar \cite{Sek} has shown that $P_{a,b}$
is graceful when $a \neq 4r + 1, r > 1;
b = 4m, m> r$. Kathiresan also shows that the
graph obtained by identifying a vertex of $K_n$ with any noncenter vertex of the
star with $2^{n-1} - n(n-1)/2$ edges is graceful.
The graph $T_n$ has $3n$ vertices and $6n-3$ edges defined as follows. Start with a
triangle $T_1$ with vertices $v_{1,1}, v_{1,2}$ and $v_{1,3}$. Then $T_{i + 1}$
consists of $T_i$ together with three new vertices
$v_{i + 1,1},
v_{i + 1,2},
v_{i + 1,3}$ and edges
$v_{i +1,1}v_{i,2}$, $v_{i +1,1}v_{i,3}$, $v_{i +1,2}v_{i,1}$,
$v_{i +1,2}v_{i,3}$, $v_{i +1,3}v_{i,1}$, $v_{i +1,3}v_{i,2}$.
Gnanajothi \cite{Gn} proved
that $T_n$ is graceful if and only
if $n$ is odd. Sekar \cite{Sek} proved $T_n$ is graceful when $n$ is odd and
$T_n$ with a pendant edge attached to the starting triangle
is graceful when $n$ is even.
For a graph $G$, the {\em splitting graph\index{splitting graph}
\subindex{graph}{splitting} of}\/ $G, S^1(G)$, is obtanied from $G$
by adding for each vertex $v$ of $G$ a new vertex $v^1$ so that $v^1$ is
adjacent to every vertex that is adjacent to $v$.
Sekar \cite{Sek} has shown that $S^1(P_n)$
is graceful for all $n$ and $S^1(C_n)$ is graceful for $n \equiv 0,1$ mod 4.
The total graph\index{total graph}\subindex{graph}{total} $T(P_n)$ has vertex
set $V(P_n) \cup E(P_n)$ with two vertices adjacent whenever they are
neighbors in $P_n$. Balakrishnan, Selvam and Yegnanarayanan \cite{BSY1} have
proved that $T(P_n)$ is harmonious.
For any graph $G$ with vertices $v_1, \ldots,v_n$ and a vector
${\bf m}=(m_1,\ldots,m_n)$ of positive integers the corresponding
{\em replicated graph}\index{replicated graph}\subindex{graph}{replicated},
$R_{\bf m}(G)$, of $G$ is defined as follows. For each
$v_i$ form a stable set $S_i$ consisting of $m_i$ new vertices $ i= 1,
2, \ldots,n$ (recall a {\em stable} set\index{stable set} $S$ consists of a set of vertices
such
that there is not an edge $v_iv_j$ for all pairs $v_i,v_j$ in $S$); two
stable sets $S_i, S_j, i \neq j,$ form a complete bipartite graph if each
$v_iv_j$ is an edge in $G$ and otherwise there are no edges between $S_i$
and $S_j$.
Ram\'{i}rez-Alfons\'{i}n \cite{Ra} has proved that
$R_{\bf m}(P_n)$ is
graceful for all ${\bf m}$
and all $n> 1$
(see \S \ref{k_graceful_labelings} for a stronger result)
and that
$R_{(m,1,\ldots, 1)}(C_{4n}),
R_{(2,1,\ldots, 1)}(C_{n}) ~(n \geq 8)$ and,
$ R_{(2,2,1, \ldots, 1)}(C_{4n}) ~(n \geq 12)$ are graceful.
For any permutation $f$ on $1,\ldots, n$, the
{\em $f$-permutation}\index{$f$-permutation graph}\subindex{graph}{$f$-permutation}
graph on
a graph $G, P(G,f)$, consists of two disjoint copies of $G, G_1$ and
$G_2$, each of which has vertices labeled $v_1, v_2,
\ldots, v_n$ with $n$
edges obtained by joining each $v_i$ in $G_1$ to $v_{f(i)}$ in $G_2$.
In 1983
Lee (see \cite{LWK}) conjectured that for all $n > 1$ and all permutations on
$1,2, \ldots, n$, the permutation graph $P(P_n,f)$ is graceful. Lee, Wang
and Kiang \cite{LWK} proved that $P(P_{2k},f)$ is graceful when $f =
(12)(34)\cdots(k,k+1)\cdots(2k-1,2k)$. They conjectured
that if $G$ is a graceful nonbipartite graph with $n$ vertices then for
any permutation $f$ on $1,2, \ldots, n,$ the permutation graph $P(G,f)$ is
graceful.
Some families of graceful permutation graphs are given in \cite{LLWK}.
Gnanajothi \cite[p. 51]{Gn} calls a graph $G$ {\em bigraceful}
\index{bigraceful graph}\subindex{graph}{bigraceful} if both $G$ and its
line graph are graceful.
She shows the following are bigraceful:
$P_m$; $P_m \times P_n$;
$C_n$ if and only if $n \equiv 0,3$ (mod 4);
$S_n$; $K_n$ if and only if $n \leq 3$; and
$B_n$ if and only if $n \equiv 3$ (mod 4).
She also shows that $K_{m,n}$ is not bigraceful when $n \equiv 3$ (mod 4).
(Gangopadhyay and Hebbare \cite{GH} used the term ``bigraceful" to mean
a bipartite graceful graph.)
Murugan and Arumugan \cite{MA3} have shown that graphs obtained from $C_4$ by
attaching two disjoint paths of equal length to two adjacent vertices are
bigraceful.
Several well-known isolated graphs have been examined.
Graceful labelings of the Petersen graph\index{Petersen graph},
the cube\index{cube}, the icosahedron\index{icosahedron} and the
dodecahedron\index{dodecahedron} can be found in \cite{Go} and \cite{Gar}.
On the other hand, Graham and Sloane \cite{GS} showed that all of these except the
cube are harmonious.
Winters \cite{Wi} verified that the Gr\H{o}tzsch graph (see \cite[p. 118]{BoM}),
the Heawood graph\index{Heawood graph} (see \cite[p. 236]{BoM}) and the
Herschel graph\index{Herschel graph} (see \cite[p. 53]{BoM}) are graceful.
Graham and Sloane \cite{GS} determined all harmonious graphs with at most five
vertices. Seoud and Youssef \cite{SY8} did the same for graphs with six vertices.
\subsection{Summary}
The results and conjectures
discussed above are summarized in the tables following.
The letter G after a class of graphs indicates that the graphs in that class
are known to be graceful; a question mark indicates that the gracefulness of
the graphs in the class is an open problem; we put a ``G" next to a
question mark if the graphs have been conjectured to be graceful.
The analogous notation with the letter H is used to indicate the status of the
graphs with regard to being harmonious.
The tables impart at a glimpse what has been done and what needs to be
done to close out a particular class of graphs.
Of course, there is an unlimited number of graphs one could consider.
One wishes for some general results that would handle several broad classes
at once but the experience of many people suggests that this is unlikely to
occur soon.
The Graceful Tree Conjecture alone has withstood the efforts of
scores of people over the past three decades.
Analogous sweeping conjectures are probably true but appear hopelessly
difficult to prove.
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
% \setcounter{table}{0}
\begin{table}
\caption{\bf Summary of Graceful Results}
\addcontentsline{toc}{subsubsection}{Table \thetable: Summary of Graceful Results}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph & \em Graceful
\\ \hline
\hspace*{2.7in} & \hspace*{2.8in}\\
Trees & G if $\leq 27$ vertices \cite{AlM}\\
& G if symmetrical \cite{BeS}\\
& G if at most 4 end-vertices \cite{HKR}\\
& ?G Ringel-Kotzig\\
& \\
Cycles $C_{n}$ & G iff $n \equiv 0,3$ (mod 4) \cite{Ro1}\\
& \\
Wheels $W_{n}$ & G \cite{F1}, \cite{HK}\\
& \\
Helms (see \S \ref{cycle_related_graphs}) & G \cite{AF}\\
& \\
Webs (see \S \ref{cycle_related_graphs}) & G \cite{KLGY}\\
&\\
Gears (see \S \ref{cycle_related_graphs}) & G \cite{MF2} \\
& \\
Cycles with $P_{k}$-chord (see \S \ref{cycle_related_graphs}) & G \cite{DMTKT},
\cite{MF1}, \cite{KY}, \cite{PP}\\
& \\
$C_{n}$ with $k$ consecutive chords (see \S \ref{cycle_related_graphs}) & G if $k = 2, 3, n-3$
\cite{KP}, \cite{KRTY}\\
& \\
Unicyclic graphs & ?G iff G $\not = C_{n}, n \equiv
1, 2$ (mod 4) \ \cite{T} \\
& \\
$C_{n}^{(t)}$ (see \S \ref{cycle_related_graphs}) & $ n = 3$ G iff $t \equiv 0, 1$ (mod 4)\\
& \cite{BBG}, \cite{BKT}\\
& ?G if $nt \equiv 0, 3 \pmod{4}$ \cite{KRLT}\\
& G if $n = 6, t$ even \cite{KRLT}\\
& G if $ n = 4, t > 1$ \cite{S2}\\
& G if $ t = 2$, $ n \not\equiv 1$ (mod 4)
\cite{Q}, \cite{BSW1}\\
& \\
& \\ \hline
\end{tabular}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
% \setcounter{table}{0}
\begin{table}
\caption{\bf continued}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph & \em Graceful
\\ \hline
\hspace*{2.4in} & \hspace*{3.0in} \\
Triangular snakes (see \S \ref{cycle_related_graphs}) & G iff number of blocks $\equiv 0,1$ (mod 4)
\cite{Mo}\\
& \\
$K_4$-snakes (see \S \ref{cycle_related_graphs}) & ?\\
& \\
Quadilateral snakes (see \S \ref{cycle_related_graphs}) & G \cite{Gn}, \cite{Q}\\
& \\
Crowns $C_{n} \odot K_{1}$ & G \cite{F1}\\
& \\
Grids $P_{m} \times P_{n}$ & G \cite{AG}\\
& \\
Prisms $C_{m} \times P_{n}$ & G if $n = 2$ \cite{FG}, \cite{YW1}\\
& G if $m$ even \cite{HuS}\\
& G if $m$ odd and
~$3 \leq n \leq 12$ \cite{HuS}\\
& G if $m =3 $ \cite{Sin1}\\
& G if $m =6 $ see \cite{YW3}\\
& G if $m \equiv 2$ (mod 4) and $n \equiv
3$
(mod 4) \cite{YW3}\\
& \\
Torus grids $C_{m} \times C_{n}$ & G if $m \equiv 0$ (mod 4),
$n$ even \cite{JR} \\
& not G if $m,n$ odd (parity condition)\\
& \\
Vertex-deleted $C_{m} \times P_{n}$ & G if $n = 2$ \cite{GPW}\\
& \\
Edge-deleted $C_{m} \times P_{n}$ & G if $n = 2$ \cite{GPW}\\
& \\
M\"{o}bius ladders $M_{n}$ (see \S \ref{product_related_graphs}) & G \cite{Ga1}\\
& \\
Stacked books $S_{m} \times P_{n}$ (see \S \ref{product_related_graphs})
& $n = 2,$ G iff $m \not \equiv 3 $ (mod 4)
\cite{Mah},
\cite{D}, \cite{GJ} \\
& G if $m$ even \cite{GJ}\\
$n$-cube $K_{2} \times K_{2} \times \cdots \times K_{2}$
& G \cite{K3} \\
& \\
& \\
& \\ \hline
\end{tabular}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
% \setcounter{table}{0}
\begin{table}
\caption{\bf continued}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph & \em Graceful
\\ \hline
\hspace*{2.7in} & \hspace*{2.7in}\\
$K_{4} \times P_{n}$ & G if $n = 2,3,4,5$ \cite{PS}\\
& \\
$K_{n}$ & G iff $n \leq 4$ \cite{Go}, \cite{Si}\\
& \\
$K_{m,n}$ & G \cite{Ro1}, \cite{Go}\\
& \\
$K_{1,m,n}$ & G \cite{AM}\\
&\\
$K_{1,1,m,n}$ & G \cite{Gn}\\
\hspace*{2.5in} & \hspace*{3.1in} \\
Windmills $K_{n}^{(m)} (n > 3)$ (see \S \ref{complete_graphs}) & G if $n = 4, m \leq 22$
\cite{HuS} \\
&?G if $n = 4, m \geq 4$ \cite{Be}\\
& G if $n = 4, 4\leq m \leq 22$
\cite{HuS}\\
& not G if $n = 4, m = 2,3$ \cite{Be}\\
& not G if $(m,n) = (2,5)$ \cite{BKT}\\
& not G if $n > 5$ \cite{KRTY} \\
\hspace*{2.5in} & \hspace*{3.1in} \\
$B(n,r,m)\ r > 1$ (see \S \ref{complete_graphs}) & G if $(n,r) = (3,2), (4,3)$ \cite{KRL},
(4,2) \cite{D}\\
& \\
$mK_{n}$ (see \S \ref{disconnected_graphs}) & G iff $m = 1, n \leq 4 $ \cite{KT} \\
& \\
$C_s \cup P_n$ & ? G iff $s + n \geq 7$ \cite{FS}\\
& G if $s = 3$ \cite{F3}, $s = 4$ \cite{FS}, $s = 5$
\cite{Kis}\\
& G if $s>4, n = 2$ \cite{GaL}\\
& G if $s = 2n + 1$ \cite{F3}\\
& G if $s = 2k, n \geq k + 1$ \cite{SAS2}\\
& \\
$C_p \cup C_q$ & ? G iff $p + q \equiv 0, 3$ (mod 4) \cite{FS}\\
& G if $s = 2n + 1$ \cite{F3}, $s\geq 5$ \\
& and $n \geq (s + 5)/2$ \cite{CK2}\\
& \\
& \\ \hline
\end{tabular}
\end{table}
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
% \setcounter{table}{0}
\begin{table}
\caption{\bf continued}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph & \em Graceful
\\ \hline
\hspace*{2.4in} & \hspace*{2.6in}\\
Fans $F_{n} = P_n + K_1$ & G \cite{GS}\\
& \\
Double fans $P_{n} + \overline{K_{2}}$ & G \cite{GS} \\
& \\
$t$-point suspension $P_n + \overline{K_{t}}$ of $P_{n}$ & G \cite{Gr2}\\
& \\
$S_{m} + K_{1}$ & G \cite{H} \\
& \\
$t$-point suspension of $C_n + \overline{K_{t}}$ & G if $n \equiv 0$ or
3
(mod 12) \cite{BNS}\\
& not G if $t$ is even and $n \equiv 2, 6, 10~ $(mod 12)\\
& G if $n = 4, 7, 11$ or 19 \cite{BNS}\\
& G if $n = 5$ or 9 and $t = 2$ \cite{BNS}\\
&\\
$P_{n}^{2}$ (see \S \ref{miscellaneous_results})
& G \cite{LK}\\
& \\
Petersen $P(n,k)$ (see \S \ref{miscellaneous_results})& ?\\
&\\
Caterpillars & G \cite{Ro1} \\
& \\
Lobsters & ?G \cite{Be} \\
& \\ \hline
\end{tabular}
\end{table}
%\pagebreak
%\newpage
% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
% \setcounter{table}{1}
\begin{table}
\caption{\bf Summary of Harmonious Results}
\addcontentsline{toc}{subsubsection}{Table \thetable: Summary of Harmonious Results}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph
& \em Harmonious\\ \hline
\hspace*{2.3in} & \mbox{\hspace*{2.2in}}\\
Trees
& H if $\leq 26$ vertices \cite{AlM}\\
& ?H \cite{GS}\\
& \\
Cycles $C_{n}$
& H iff $n \equiv 1,3\;$ (mod 4) \cite{GS} \\
& \\
Wheels $W_{n}$
& H \cite{GS}\\
& \\
Helms (see \S \ref{cycle_related_graphs}) & H \cite{Gn}, \cite{LiuY4}\\
& \\
Webs (see \S \ref{cycle_related_graphs}) & H if cycle is odd\\
&\\
Gears (see \S \ref{cycle_related_graphs}) & ?\\
& \\
Cycles with $P_{k}$-chord
(see \S \ref{cycle_related_graphs}) & ?\\
& \\
$C_{n}$ with $k$ consecutive chords
(see \S \ref{cycle_related_graphs}) & ?\\
&\\
Unicyclic graphs
& ?\\
& \\
$C_{n}^{(t)}$ (see \S \ref{cycle_related_graphs})
& $n$ = 3 H iff $t \not\equiv 2\; $(mod 4) \cite{GS}\\
& H if $n=4,\; t>1$ \cite{S2} \\
& \\
Triangular snakes (see \S \ref{cycle_related_graphs}) & H if number of blocks is odd \cite{XuS2}\\
& not H if number of blocks $\equiv 2$ \\
& (mod 4) \cite{XuS2} \\
&\\
$K_4$-snakes (see \S \ref{cycle_related_graphs}) & H \cite{Gr3}\\
&\\
Quadrilateral snakes (see \S \ref{cycle_related_graphs}) & ?\\
& \\
Crowns $C_{n} \odot K_{1}$
& H \cite{Gr2}, \cite{LZ1}\\
& \\
Grids $P_{m} \times P_{n}$
& H iff $(m,n) \neq (2,2)$ \cite{JR}\\
&\\
& \\ \hline
\end{tabular}
\end{table}
%\pagebreak
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
% \setcounter{table}{1}
\begin{table}
\caption{\bf continued}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph
& \em Harmonious\\ \hline
\hspace*{2.4in} & \hspace*{2.7in} \\
Prisms $C_{m} \times P_{n}$
& H if $n = 2, m \not = 4$ \cite{GPW}\\
& H if $n$ odd \cite{GS}\\
& H if $m =4$ and $n \geq 3$ \cite{JR}\\
&\\
Torus grids $C_{m} \times C_{n}$,
& H if $m=4$, $n>1$ \cite{JR}\\
& not H if $m \not\equiv 0$ (mod 4)
and $n$ odd \cite{JR} \\
&\\
Vertex-deleted $C_{m} \times P_{n}$
& H if $n = 2$ \cite{GPW}\\
& \\
Edge-deleted $C_{m} \times P_{n}$
& H if $n =2$ \cite{GPW}\\
& \\
M\"{o}bius ladders $M_{n}$ (see \S \ref{product_related_graphs})
& H iff $n \not = 3$ \cite{Ga1}\\
&\\
Stacked books $S_{m} \times P_{n}$ (see \S \ref{product_related_graphs})
& $n = 2,$ H if $m$ even \cite{Gr1}, \cite{Re}\\
& not H $m \equiv 3$ (mod 4),
$n = 2$, \\
&(parity condition) \\
& H if $m \equiv 1$ (mod 4), $n = 2$ \cite{Gn}\\
& \\
$n$-cube $K_{2} \times K_{2} \times \cdots \times K_{2}$& not H if $n =2,
3$ \cite{GS}\\
& \\
$K_{4} \times P_{n}$
& H \cite{Re}\\
& \\
$K_{n}$ & H iff $n \leq 4$ \cite{GS}\\
&\\
$K_{m,n}$ & H iff $m$ or $n = 1$ \cite{GS}\\
& \\
$K_{1,m,n}$ & H \cite{AM}\\
&\\
$K_{1,1,m,n}$ & H \cite{Gn}\\
&\\
Windmills $K_{n}^{(m)}\;(n > 3)$ (see \S \ref{complete_graphs})
& H if $n = 4$ \cite{Hs}\\
& $m = 2,\mbox{ ?H iff }n = 4$ \cite{GS}\\
& not H if $m = 2, n$ odd or 6 \cite{GS} \\
& not H for some cases $m = 3$ \cite{LiuB2} \\
&\\
& \\ \hline
\end{tabular}
\end{table}
%\pagebreak
%\clearpage
% Set table counter to the value as on previous table
\setcounter{table}{\value{thistable}}
% \setcounter{table}{1}
\begin{table}
\caption{\bf continued}
\vspace{0.25in}
\begin{tabular}{|l|l|} \hline
\em Graph
& \em Harmonious\\ \hline
\hspace*{2.4in} & \hspace*{3.0in} \\
$B(n,r,m)\ r > 1$ (see \S \ref{complete_graphs})
& $(n,r) = (3,2), (4,3)$ \cite{SY3}\\
& \\
$mK_{n}$ (see \S \ref{disconnected_graphs}) & H $n = 3,\; m$ odd \cite{LZ2} \\
¬ H for $n$ odd,
$m \equiv 2$ (mod 4) \cite{LZ2}\\
&\\
$C_s \cup P_n$ & ?\\
&\\
Fans $F_{n} = P_n + K_1$
& H \cite{GS}\\
Double fans $P_{n} + \overline{K_{2}}$
& H \cite{GS}\\
&\\
$t$-point suspension $P_{n} + \overline{K_{t}}$ of $P_{n}$
& H \cite{Re}\\
& \\
$S_{m} + K_{1}$ & H \cite{Gn}, \cite{CHR}\\
& \\
$t$-point suspension $C_{n} + \overline{K_{t}}$ of $C_n$
& H if $n$ odd and $t = 2$ \cite{Re}, \cite{Gn}\\
& not H if $n \equiv 2,4,6$ ~(mod 8)
and $t= 2$ \cite{Gn}
\\
& \\
$P_{n}^{2}$ (see \S \ref{miscellaneous_results})& H \cite{Gr2}, \cite{LZ1}\\
&\\
Petersen $P(n,k)$ (see \S \ref{miscellaneous_results})
& H \cite{Gn}, \cite{LSchS} \\
& \\
Caterpillars
& H \cite{GS}\\
& \\
Lobsters
& ?\\
& \\ \hline
\end{tabular}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of file