% 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} \\
                         &not 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
