% Begin of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Encoding: ASCII
% Tex format: LaTeX
% Last modified: August 5, 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Variations of Harmonious Labelings}

\subsection{Sequential and Strongly $c$-harmonious Labelings}\label{sequential_labelings}

Chang, Hsu and Rogers \cite{CHR} and Grace \cite{Gr1}, \cite{Gr2} have investigated 
subclasses of harmonious graphs.
Chang et al. define an injective labeling $f$ of a graph $G$ with $q$
 vertices to be {\em strongly $c$-harmonious}\subindex{labeling}{strongly $c$-harmonious} 
if the vertex labels are 
from $\{0,1,\ldots,q-1\}$ and the edge labels induced by $f(x) + f(y)$ 
for each edge $xy$ are $c,\ldots,c+q-1$.
Grace called such a labeling {\em sequential}\subindex{labeling}{sequential}.
In the case of a tree, Chang et al. modify the definition to permit exactly one vertex label to be assigned to two vertices
while Grace allows the vertex labels to range from $0$ to $q$ with no vertex label used twice.
By taking the edge labels of a sequentially labeled graph with $q$ 
edges modulo $q$, we obviously obtain a harmoniously labeled graph.
It is not known if there is a graph that can be harmoniously labeled but not sequentially labeled.
Grace \cite{Gr2} proved that caterpillars\index{caterpillar}, caterpillars with a pendant edge, 
odd cycles  with zero or more pendant edges, trees with
 $\alpha$-labelings, wheels\index{wheel}
$W_{2n+1}$, and $P_n^2$  are sequential.
Liu and Zhang \cite{LZ1} finished off the crowns $C_{2n} \odot K_1$. (The case 
$C_{2n+1} \odot K_1$ was a special case of Grace's results. Liu \cite{LiuY3} 
proved crowns are harmonious.)  Bu 
\cite{Bu2} also proved that crowns\index{crown} are sequential as are all even cycles 
with $m$ pendant edges attached at each vertex. 
Figueroa-Centeno, Ichishima and Muntaner-Batle \cite{FIM7} proved that all cycles 
with $m$ pendant edges attached at each vertex are  sequential. 

Singh has  proved the following:  $C_n \odot K_2$ is sequential for all 
odd $n > 1 $ \cite{Sin2}; $C_n \odot P_3$ is sequential for all odd $n$ \cite{Sin4}; 
$K_2 
\odot C_n$ (each vertex of the cycle is joined by edges to the end points 
of a copy of $K_2$)
is sequential for all odd $n$ \cite{Sin4}; helms $H_n$ are sequential 
when $n$ is even \cite{Sin4}; and  $K_{1,n} + 
K_2, K_{1,n} + {\overline K_2}$, and ladders\index{ladder} are sequential \cite{Sin5}.  
Both Grace \cite{Gr1} and Reid (see \cite{GJ}) have found sequential labelings for 
the books $B_{2n}$.  
Jungreis and Reid \cite{JR} have shown the following graphs are sequential:
$P_m \times P_n \rule[-.1in]{.1in}{0in}  (m,n) \not= (2,2)$;
$C_{4m} \times P_n \rule[-.1in]{.1in}{0in}  (m,n) \not= (1,2)$;
$C_{4m+2} \times P_{2n}$;
$C_{2m+1} \times P_n$; and,
$C_4 \times C_{2n} \rule[-.1in]{.1in}{0in} (n > 1)$.
The graphs $C_{4m+2} \times C_{2n+1}$ and $C_{2m+1} \times C_{2n+1}$ fail 
to satisfy a necessary parity condition given by Graham and Sloane \cite{GS}.  
The remaining cases of $C_m \times P_n$ and $C_m \times C_n$ are open.  
Gallian, Prout and Winters \cite{GPW} proved that all graphs $C_n \times P_2$ 
with a vertex or edge deleted are sequential.

Gnanajothi \cite[pp. 68--78]{Gn} has shown the following graphs are sequential:
$K_{1,m,n}$; $mC_n$, the disjoint union of $m$ copies of $C_n$, if and only if $m$ and $n$ are odd;
books with triangular pages or pentagonal pages;
and books of the form $B_{4n+1}$, thereby answering a question and 
proving a conjecture of Gallian and Jungreis \cite{GJ}.
Sun \cite{Su} has also proved that $B_n$ is sequential if and only if $n 
\not\equiv 3$ (mod 4).

Yuan and Zhu \cite{YZ} have shown that $mC_n$
is sequential when $m$ and $n$ are odd.
Although Graham and Sloane \cite{GS} proved that the  M\"{o}bius ladder $M_3$ 
is not harmonious, Gallian \cite{Ga1} established that all other M\"{o}bius 
ladders\index{M\"{o}bius ladder} 
are sequential (see \S \ref{product_related_graphs} for the definition).
 Chung, Hsu and Rogers \cite{CHR} have shown  that $K_{m,n} + 
K_1$, which includes $S_m + K_1$, is sequential.
Seoud and Youssef \cite{SY7}  proved that if $G$ is sequential and has the same
number of edges as vertices, then $G + \overline{K_n}$ is sequential for
all $n$. 

Singh and Varkey \cite{SiVa} call a graph with $q$ edges 
{\em odd sequential}\subindex{labeling}{odd sequential} if the 
vertices can be labeled with distinct integers from the set $\{0, 1, 2, \ldots, 
q\}$ or, in the case of a tree from the set $\{0, 1, 2, \ldots, 2q -1\},$ so 
that the edge labels induced by addition of the labels of the endpoints 
take on the values $\{1,3,5, \ldots, 2q-1\}$. 
They prove that  combs, grids, stars and  
rooted trees of level 2 are odd sequential while odd cycles are not. 
Singh and Varkey call a graph $G$ 
{\em bisequential}\index{bisequential graph}\subindex{graph}{bisequential} 
if both $G$ and its line graph have a sequential labeling.
They prove paths and cycles are bisequential. 

Among the strongly 1-harmonious (also called 
{\em strongly harmonious}\subindex{labeling}{strongly harmonious})
 are: fans $F_n$ with $n \geq 2$ \cite{CHR};  wheels $W_n$ with $n \not\equiv
2$ (mod 3) \cite{CHR}; $K_{m,n} + K_1$ \cite{CHR}; French windmills $K_4^{(t)}$ 
\cite{Hs}, \cite{KZ};
 the friendship graphs $C_3^{(n)}$ if and only if $n \equiv 0$ or $1$
(mod 4) \cite{Hs}, \cite{KZ};  $C_{4k}^{(t)}$ \cite{SuWa}; and helms 
\cite{RP1}. 


Seoud, Diab and Elsakhawi \cite{SDE} have shown that the following graphs are
strongly harmonious: $K_{m,n}$ with an edge joining two vertices in the
same partite set; $K_{1,m,n}$; the composition
$P_n[P_2]$ (see \S \ref{product_related_graphs} for definition); $B(3,2,m)$ and $B(4,3,m)$ for all
$m$
(see \S \ref{complete_graphs} for notation); 
$P_n^2 ~(n \geq 3)$; and 
$P_n^3 ~(n \geq 3)$. Seoud et al. 
\cite{SDE} have also proved: 
$B_{2n}$ is
strongly $2n$-harmonious; $P_n$ is strongly $\lfloor n/2
\rfloor$-harmonious; ladders $L_{2k+ 1}$ are strongly $(k+1)$-harmonious;
and that if $G$ is strongly $c$-harmonious  and has an equal number of
vertices and edges, then $G + \overline{K_n}$ is also strongly
$c$-harmonious.

Sethuraman and Selvaraju \cite{SS7} have proved that the graph obtained by adjoining 
two complete bipartite graphs at one edge is graceful and strongly harmonious.
They ask whether  these results extend to any number of complete 
bipartite graphs. 

 Acharya and Hegde \cite{AH3} have generalized sequential
labelings as follows. Let $G$ be a graph with $q$ edges and let $k$ and
$d$ be positive integers.  A labeling $f$ of $G$ is said to be 
{\em $(k,d)$-arithmetic}\subindex{labeling}{$(k,d)$-arithmetic} 
if the vertex labels are distinct nonnegative
integers and the edge labels induced by $f(x) + f(y)$ for each edge $xy$
are $k,k+d,k+2d,\ldots,k+(q-1)d$. They obtained a number of necessary
conditions for various kinds of graphs to have a $(k,d)$-arithmetic
labeling. 
The case where $k =1 $ and $d = 1$ was called 
{\em additively graceful}\subindex{labeling}{additively graceful} 
by Hegde \cite{Heg1}. Hegde \cite{Heg1} showed:  $K_n$ is additively 
graceful if
and only if $n =2 ,3$ or 4; every additively graceful graph except $K_2$
or $K_{1,2}$ contains a triangle; and a unicyclic graph is additively
graceful if and only if it is a 3-cycle or a 3-cycle with a single pendant
edge attached.  Jinnah and Singh \cite{JS} noted that $P_n^2$ is additively 
graceful.
Hegde \cite{Heg2} proved that if $G$ is strongly $k$-indexable, then $G$ and $G 
+ \overline{K_n}$ are $(kd,d)$-arithmetic; 
Bu and Shi \cite{BuS1} proved the conjecture of Acharya and Hegde \cite{AH3} that  
$K_n$ is not $(k,d)$-arithmetic for $n\geq 5$. They also proved  
that $K_{m,n}$ is $(k,d)$-arithmetic when $k$ is not of the form $id$ 
for $1 \leq i \leq n-1$. Acharya and Hegde \cite{AH3} showed that for all $d 
\geq 1$ and all $r \geq 0$ the following: 
 $K_{m,n,1}$ is $(d + 2r, d)$-arithmetic;  $C_{4t + 1}$ is $(2dt + 
2r,d)$-arithmetic; $C_{4t + 2}$ is not $(k,d)$-arithmetic for any values 
of $k$ and $d$; $C_{4t + 3}$ is $((2t + 
1)d + 2r, d)$-arithmetic; $W_{4t +2}$ is $(2dt + 2r,d)$-arithmetic; and
$W_{4t}$ is $((2t + 1)d + 2r,d)$-arithmetic.  They conjecture that 
$C_{4t + 1}$ is $(2dt + 2r, d)$-arithmetic for some $r$ and that 
$C_{4t + 3}$ is $((2dt + d + 2r, d)$-arithmetic for some $r$.
Hegde and Shetty \cite{HeSh3} proved the following: the generalized web 
$W(t,n)$ 
(see \S \ref{cycle_related_graphs}) is $((n -1)d/2,d)$-arithmetic and $(3n - 1)d/2$-arithmetic for 
odd $n$; the join of the generalized web $W(t,n)$ with the center removed 
and $\overline{K_p}$ where $n$ is odd is $((n -1)d/2,d)$-arithmetic.


  Yu 
\cite{Yu1} proved that a necessary condition for 
$C_{4t + 1}$ to be $(k,d)$-arithmetic is that $k = 2dt + r$ for some $r 
\geq 0$ and a necessary condition for $C_{4t + 3}$ to be 
$(k,d)$-arithmetic is that $ k = (2t + 1)d + 2r$ for some $r \geq 0$.  
These conditions were conjectured by Acharya and Hegde \cite{AH3}.
Singh  proved that the graph obtained by subdividing every
edge of the ladder $L_n$ is $(5,2)$-arithmetic \cite{Sin3} and that the ladder $L_n$ 
is $(n,1)$-arithmetic
\cite{Sin6}. He also proves  
that $P_m \times C_n$ is $((n-1)/2,1)$-arithmetic when $n$ is odd \cite{Sin6}. 


A graph is called {\em arithmetic}\subindex{graph}{arithmetic} 
if it is $(k,d)$-arithmetic for some $k$ and $d$. 
 Singh and Vilfred \cite{SiVi} showed that 
various classes of trees are arithmetic. Singh \cite{Sin6} has proved that the union 
of an arithmetic graph and an arithmetic bipartite graph is arithmetic. He 
conjectures that  the union of arithmetic graphs is arithmetic. He provides an 
example to show that the converse is not true.

Acharya and Hegde \cite{AH3} introduced a stronger form of
sequential labeling by calling a graph  with $p$ vertices and 
$q$ edges {\em strongly $k$-indexable}\subindex{labeling}{strongly $k$-indexable} 
if there is an injective function from $V$ to $\{0, 1, 2,
\ldots, p-1\}$ such that the set of edge labels induced by adding the vertex
labels is $\{k,k+1,k+2, \ldots, k+q -1\}$. Strongly 1-indexable graphs are 
simply  called {\em strongly indexable}\subindex{labeling}{strongly indexable}.  
Notice that for trees and
unicyclic graphs the notions of sequential labelings and strongly
$k$-indexable labelings coincide. Acharaya and Hegde prove that the only
nontrivial regular graphs that are strongly indexable are $K_2, K_3$ and $
K_2 \times K_3$ and that every strongly indexable graph has exactly one
nontrivial component that is either a star or has a triangle. Acharya and
Hegde \cite{AH3} call a graph with $p$ vertices {\em indexable}\subindex{labeling}{indexable} 
if there is 
an injective labeling of the vertices with labels from $\{0,1,2, \ldots, 
p-1\}$ 
such that the edge labels induced by addition of the vertex labels are
distinct. They conjecture that all unicyclic graphs are indexable. 
This conjecture was proved by Arumugam and Germina \cite{ArG} who also proved 
that all trees are indexable. Bu and Shi \cite{BuS2} also proved that all 
trees are indexable and that all uncyclic graphs with the cycle $C_3$ 
are indexable. Hegde \cite{Heg2} has shown the following: every graph can 
be embedded  as an 
induced subgraph of an indexable graph;  if a connected graph with 
$p$ vertices and $q$ edges ($q\geq 
2$) is $(k,d)$-indexable then $d \leq 2;~ P_m \times P_n$ is indexable for 
all $m$ and $n$; if $G$ is a connected $(1,2)$-indexable graph, then $G$ 
is 
a tree;  the minimum degree of any $(k,1)$-indexable graph with at 
least two vertices is at most 3; a caterpillar with partite sets of 
orders $a$ and $b$ is strongly $(1,2)$-indexable if and only if $|a - 
b| \leq 1$; in  a connected strongly $k$-indexable graph with $p$ 
vertices and $q$ edges, $k 
\leq p - 1$,
and if  a graph with $p$ vertices and $q$ edges is 
$(k,d)$-indexable, then $q \leq (2p -3 -k +d)/d$. As a corollary of the latter, 
it follows that $K_n ~(n \geq 4)$ and wheels are not $(k,d)$-indexable. 
Hegde and Shetty \cite{HeSh3} proved that for $n$ odd the generalized web 
graph 
$W(t,n)$ with the center removed is strongly $(n -1)/2$-indexable. 

Let $T$ be a tree with adjacent edges $u_0$ and $v_0$ and suppose that 
there are two 
pendant edges $u$ and $v$ of $T$ so that the lengths of the paths $u_0-u$ 
and $v_0-v$  are eqaul. The tree obtained from $T$ by deleting the edge 
$u_0v_0$  and joining $u$ and $v$  is called an {\em elementary parallel 
transformation}\index{elem. parallel transformation} 
of $T$. Any tree that can be reduced to a path by a 
sequence of elementary parallel transformations is called a $T_p$-tree.  
Hedge and Shetty \cite{HeSh3} have shown that every $T_p$-tree with $q$ edges 
and every  tree obtained by subdividing every edge of a $T_p$-tree
 exactly once is $(k + (q -1)d,d)$-arithmetic for all $k$ and $d$. 
Hegde and Shetty \cite{HeSh5} define  a 
{\em level joined planar grid}\index{level joined planar grid} as follows. 
Let $u$ be a vertex of $P_m \times P_n$ of degree 2. For every 
every pair of distinct vertices $v$ and $w$ which do not have degree 4, 
introduce 
an edge between $v$ and $w$ provided that the distance from $u$ to $v$  equals 
the distance from $u$ to $w$. They prove that every level joined planar grid is 
strongly indexable. 

Section~\ref{edge_magic_total} of this survey includes a discussion of a labeling method called 
super edge-magic. In 2002 Hegde and Shetty \cite{HeSh5} showed that a graph has a 
strongly 
$k$-indexable labeling if and only if it has a super edge-magic labeling. 


\subsection{Elegant Labelings}\label{elegant_labelings}

An {\em elegant labeling}\index{elegant labeling}\subindex{labeling}{elegant} 
$f$ of a graph $G$ with $q$ edges is an injective function from the 
vertices of $G$ to the set $\{0,1,\ldots,q\}$ such that when each edge $xy$ is assigned the label
$f(x) + f(y)$ (mod $q+1$) the resulting edge labels are distinct and nonzero.
This notion was introduced by Chang, Hsu and Rogers in 1981 \cite{CHR}. 
Note that in contrast to the definition of a harmonious labeling, 
it is not necessary to make an exception for trees.  
While the cycle $C_n$ is harmonious if and only if $n$ is odd, Chang et 
al. \cite{CHR} proved that $C_n$ is elegant when $n \equiv 0$ or $3$ (mod 4) 
and not elegant when $n \equiv 1$ (mod 4). 
Chang et al. further showed that all fans\index{fan} are elegant and 
the paths\index{path} $P_n$ are elegant for $n \not\equiv 0$ (mod 4). 
Cahit \cite{C1} then showed that $P_4$ is the only path that is not elegant.
Balakrishnan, Selvam and Yegnanarayanan \cite{BSY2} have proved numerous 
graphs are elegant. Among them are $K_{m,n}$ and the 
$m$th-subdivision graph of $K_{1,2n}$. They prove that the bistar 
$B_{n,n}$ ($K_2$ with $n$ pendant edges at each endpoint) is elegant if and 
only if $n$ is even. They also prove that every simple graph is a 
subgraph of an elegant graph and that  several families of graphs 
are not elegant. Deb and Limaye  \cite{DL1} have shown that triangular snakes
are elegant if and only if  the number of triangles  is not equal to 3
(mod 4). In
the  case where the  number of triangles is 3 (mod 4) they show the
triangular
snakes satisfy a weaker
condition they call {\em semi-elegant}\subindex{labeling}{semi-elegant} 
whereby the edge label 0 is permitted. In 
\cite{DL3} Deb and Limaye define  a graph $G$ with $q$ edges 
to be  {\em near-elegant}\subindex{labeling}{near-elegant} 
if there is an injective function $f$ 
from the  vertices of $G$ to the set $\{0,1,\ldots,q\}$ such that when
each edge $xy$ is assigned the label
$f(x) + f(y)$ (mod $(q+1)$) the resulting edge labels are distinct and not
equal to $q$. Thus, in a near-elegent labeling, instead of 0 being the
missing value in the edge labels, $q$ is the missing value. Deb and Limaye
show that triangular snakes where the number of triangles is 3 (mod 4) are
near-elegant.  For any positive integers $\alpha \leq
\beta \leq \gamma$ where $\beta$ is at least 2 the {\em theta graph}\index{theta graph}
$\theta_{\alpha, \beta,\gamma}$ consists of three edge disjoint paths of
lengths $\alpha, \beta $ and $\gamma$ having the same end points. Deb and
Limaye \cite{DL3} provide elegant and near-elegnat labelings for some theta
graphs where $\alpha = 1,2$ or 3. 
Seoud and Elsakhawi \cite{SeE1}  have proved that the following graphs are
elegant: $K_{1,m,n}; K_{1,1,m,n}; K_2 + \overline{K_m}; K_3 +
\overline{K_m}$; and $K_{m,n}$
with an edge joining two vertices of the same partite set.

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  - q$. As 
a corollary 
they deduce that every graph is a vertex induced subgraph of a elegant graph. 
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
elegant labeling. 


Sethuraman and Elumalai \cite{SE2}  define  a graph $H$ to be a $K_{1,m}$-star 
extension of a graph $G$ with $p$ vertices and $q$ edges at a vertex $v$ 
of $G$ where $m > p - 1 
-deg(v)$ if $H$ is obtained from $G$ by merging the center of the star $K_{1,m}$ 
with $v$ and merging  $p - 1 -deg(v)$ pendent vertices of $K_{1,m}$ 
with the 
$p -1 -deg(v)$ nonadjacent vertices of $v$ in $G$. They prove that for 
every 
graph $G$ with $p$ vertices and $q$ edges and every vertex $v$ of $G$ and 
every 
$m \geq 2^{p-1} - 1 - q$ 
there is a $K_{1,m}$-star extension 
of $G$ that is both graceful and harmonious. In the case where 
$m \geq 2^{p-1}  - q$ they show that $G$ has a $K_{1,m}$-star extension that is 
elegant. 

Sethuraman and Selvaraju  \cite{SS8} have shown that certain cases of 
the union of any number of 
copies of $K_4$ with one or more  edges deleted and one edge in common are 
elegant.


Gallian extended the notion of harmoniousness to arbitrary finite Abelian 
groups as follows.
Let $G$ be a graph with $q$ edges and $H$ a finite Abelian group (under addition) of order $q$.
Define $G$ to be {\em H-harmonious}\subindex{graph}{H-harmonious} 
if there is an injection $f$ from the vertices of $G$ to $H$ 
such that when each edge $xy$ is assigned the label $f(x) + f(y)$ the resulting edge labels are distinct.
When $G$ is a tree, one label may be used on exactly two vertices.
Beals, Gallian, Headley and Jungreis \cite{BGHJ} have shown that if $H$ is a 
finite Abelian group of order $n > 1$ then $C_n$ is $H$-harmonious if and 
only if $H$ has a non-cyclic or trivial Sylow 2-subgroup and $H$ is not 
of the form $Z_2 \times Z_2 \times \cdots \times Z_2$.
Thus, for example, $C_{12}$ is not $Z_{12}$-harmonious but is $(Z_2 \times Z_2 \times Z_3)$-harmonious.
Analogously, the notion of an elegant graph can be extended to arbitrary finite Abelian groups.
Let $G$ be a graph with $q$ edges and $H$ a finite Abelian group (under addition) with 
$q+1$ elements.
We say $G$ is {\em H-elegant}\subindex{graph}{H-elegant} if there is 
an injection $f$ from the vertices of $G$ to $H$ 
such that when each edge $xy$ is assigned the label $f(x) + f(y)$ 
the resulting set of edge labels is  the non-identity elements of $H$.
Beals et al. \cite{BGHJ} proved that if $H$ is a finite 
Abelian group of order $n$ with $n \not= 1$ and $n \not= 3$, then 
$C_{n-1}$ is $H$-elegant using only the non-identity elements of $H$ as vertex labels if
 and only if $H$ has either a non-cyclic or trivial Sylow 2-subgroup.
This result completed a partial characterization
 of elegant cycles given by Chang, Hsu and Rogers \cite{CHR} by showing
 that $C_n$ is elegant when $n \equiv 2$ (mod 4). Mollard and Payan \cite{MoPa}
 also proved that $C_n$ is elegant when $n \equiv2$ (mod 4) and gave 
another proof that $P_n$ is elegant when $n \neq 4$.

For a graph $G(V,E)$ and an Abelian group $H$ Valentin \cite{V} defines a
{\em polychrome}\subindex{labeling}{polychrome} labeling of $G$ by $H$ to be a bijection $f$ from $V$ to
$H$ such that the edge labels induced by $f(uv) = f(v) + f(u)$ are
distinct.  Valentin investigates the existence of polychrome labelings for
paths and cycles for various Abelian groups. 


\subsection{Felicitous Labelings}

Another generalization of harmonious labelings are felicitous labelings.
An injective function $f$ from the vertices of a graph $G$ with $q$ edges to the set $\{0,1,\ldots,q\}$ 
is called {\em felicitous}\subindex{labeling}{felicitous} if the edge labels induced by 
$f(x) + f(y)$ (mod $q$) for each edge $xy$ are distinct.
This definition first appeared in a paper by Lee, Schmeichel and Shee in 
\cite{LSchS} and is attributed to E. Choo.
Balakrishnan and Kumar \cite{BK2} proved the conjecture of Lee, Schmeichel and 
Shee \cite{LSchS} 
that every graph is a subgraph of a felicitous graph by 
showing the stronger result that every graph is a subgraph of a 
sequential graph.  Among the graphs known 
to be felicitous are: $C_n$ except when $n \equiv 2$ (mod 4) \cite{LSchS};
$K_{m,n}$ when $m,n > 1$ \cite{LSchS};
$P_2 \cup C_{2n+1}$ \cite{LSchS};
$P_2 \cup C_{2n}$ \cite{Tel};
$P_3 \cup C_{2n+1}$ \cite{LSchS};
$S_m \cup C_{2n+1}$ \cite{LSchS};
$K_n$ if and only if $n \leq 4$ \cite{SE4};
$P_n + \overline{K_m}$  \cite{SE4};
the friendship graph $C_3^{(n)}$ for $n$ odd \cite{LSchS};
$P_n \cup C_3$ \cite{ShL};
$P_n \cup C_{n +3}$ \cite{Tel};
 and
the one-point union\index{one-point union} of an odd cycle and a caterpillar \cite{ShL}.
Shee \cite{S1} conjectured that $P_m \cup C_n$ is felicitous when $n > 2$ and 
$m>3$.
Lee, Schmeichel and Shee \cite{LSchS} ask for which $m$ and $n$ is the one-point 
union of $n$ copies of $C_m$ felicitous.
They showed that the case where $mn$ is twice an odd integer is not felicitous.
In contrast to the situation for felicitous labelings, we remark that $C_{4k}$ and $K_{m,n}$ where $m,n > 1$ are not harmonious and the one-point union of an odd cycle and a caterpillar is not always harmonious.
Lee, Schmeichel and Shee \cite{LSchS} conjecture that the $n$-cube  is 
felicitous. This conjecture was proved by Figueroa-Centeno and Ichishima in 
2001 \cite{FI}. 

Balakrishnan, Selvam and Yegnanarayanan \cite{BSY1} obtained numerous results 
on felicitous labelings. The {\em wreath product}\index{wreath product}, $G*H$, of graphs 
$G$ and $H$ has vertex set $V(G) \times V(H)$ and $(g_1,h_1)$ is 
adjacent to $(g_2,h_2)$ whenever $g_1g_2 \in E(G)$ or $g_1 = g_2$ and 
$h_1h_2 \in E(H)$. They define $H_{n,n}$ as the graph with vertex set 
$\{u_1, \ldots, u_n; v_1, \ldots,v_n\}$ and edge set $\{u_iv_j 
|\;1 \leq i \leq j \leq n\}$. They let  $\langle K_{1,n}:m \rangle$ denote 
the graph obtained by taking $m$ disjoint copies of $K_{1,n}$, and joining 
a new vertex to the centers of the $m$ copies of $K_{1,n}$.  
They prove the 
following are felicitous: $H_{n,n}; P_n*\overline{K_2}; 
\langle K_{1,m}:m\rangle; \langle K_{1,2}:m\rangle$ when $m \not\equiv 0$ 
(mod 3) or $m \equiv 3$ (mod 6) or $m \equiv 6 $ (mod 12); 
$\langle K_{1,2n}:m\rangle$ for all $m$ and $n \geq 2; \langle K_{1, 
2t + 1}:2n + 1\rangle$ when $n \geq t; P_n^k$ when $ k = n-1$ and $n 
\not\equiv 2 $ (mod 4) or $k = 2t$ and $n \geq 3$ and $k < n-1$; the join 
of a star and $\overline{K_n}$; 
 and graphs obtained by joining 
two end vertices or two central vertices of stars with an edge.
Yegnanarayanan \cite{Ye1} conjectures that
the graphs obtained from an even cycle by attaching $n$ new vertices to
each vertex of the cycle is felicitous. This conjecture was verified by 
Figueroa-Centeno, Ichishima and Muntaner-Batle in \cite{FIM7}. In \cite{SS4}
Sethuraman and Selvaraju \cite{SS8} have shown that certain cases of 
the union of any number of 
copies of $K_4$ with 3 edges deleted and one edge in common are felicitous.   
 Sethuraman and Selvaraju \cite{SS4} present an 
algorithm that permits one to start with any non-trivial connected graph and 
successively form supersubdivisions (see \S \ref{miscellaneous_results})  
that have  a felcitious labeling.
  


Figueroa-Centeno, Ichishima and Muntaner-Batle \cite{FIM6} define a felicitous graph 
to be {\em strongly felicitous}\subindex{graph}{strongly felicitous} 
if there exists an integer $k$ so that for every edge $uv$ 
min$\{f(u),f(v)\}$\\
$ \leq k <$ max$\{f(u),f(v)\}$. For a graph with $p$ 
vertices 
and $q$ edges with $q \geq p-1$ they show that $G$ is strongly felicitous if and 
only if $G$ has an $\alpha$-valuation\index{$\alpha$-valuation} 
(see \S \ref{alpha_labelings}).  They also show that 
for graphs $G_1$ and $G_2$ with strongly felicitous labelings $f_1$ and $f_2$ the
graph obtained from $G_1$ and $G_2$ by identifying the vertices $u$ and $v$ such
that $f_1(u) = 0 = f_2(v)$ is strongly felicitous  and that the
 one-point union of
two copies of $C_m$  where $m \geq 4$ and $m$ is even is 
strongly
felicitous. As a corollary they have that the one-point union $n$ copies of 
$C_m$  where $m$ is even and at least 4 and
$n \equiv 2$ (mod 4) is  felicitous. They conjecture that the one-point union 
of $n$ copies of $C_m$ is felicitous if and only if $mn \equiv 0,1$ or 3 (mod 
4). In \cite{FIM8} Figueroa-Centeno, Ichishima and Muntaner-Batle prove that $2C_n$ 
is strongly felicitous if and only if  $n$ is even and at least 4. They 
conjecture \cite{FIM8} that 
 $mC_n$ is felicitous if and only if $mn \not\equiv 2$ (mod 4) and that
 $C_m \cup C_n$ is felicitous if and only if $m +n \not\equiv 2$ (mod 4).


Chang, Hsu and 
Rogers \cite{CHR} have given a sequential counterpart to felecitous labelings.
They call a graph {\em strongly $c$-elegant}\subindex{graph}{strongly $c$-elegant} 
if the vertex labels
 are from $\{0,1,\ldots,q\}$ and the 
edge labels induced by addition are $\{c,c+1,\ldots,c+q-1\}$.
(A strongly 1-elegant labeling has also been called a 
{\em consecutive}\subindex{labeling}{consecutive} labeling.) 
Notice that every strongly $c$-elegant graph is felicitous and that 
strongly $c$-elegant is the same as $(c,1)$-arithmetic in the case where the vertex labels are from 
$\{0,1, \ldots,q\}$. Results on strongly $c$-elegant graphs are meager.  Chang et al. \cite{CHR} have 
shown: $K_n$ is strongly 1-elegant if and only if $n = 2,3,4;
~C_n$ is strongly 1-elegant if and only if $n = 3$;
and a bipartite graph is strongly 1-elegant if and only if it is a star.
Shee \cite{S2} has proved that $K_{m,n}$ is strongly $c$-elegant for a 
particular value of $c$ and obtained several more specialized 
results pertaining to graphs formed from complete bipartite graphs.

Seoud and Elsakhawi \cite{SeE2} have shown: $K_{m,n}~(m \leq n)$ with an edge 
joining two
vertices of the same partite set is strongly $c$-elegant for $c = 1,3,5,
\ldots, 2n + 2;~ K_{1,m,n}$ is strongly
$c$-elegant for
$c
=
1,3,5,\ldots ,2m$ when $m =n,$ and for $c = 1,3,5, \ldots, m+n + 1$ when
$m\neq n$; $K_{1,1,m,m}$ is strongly $c$-elegant for $c = 1,3,5, \ldots,
2m 
+1; P_n + \overline{K_m}$ is strongly 
$\lfloor n/2\rfloor$-elegant; $C_m + \overline{K_n}$
 is strongly $c$-elegant for odd $m$ and all $n$ 
for $c = (m -1)/2, (m
-1)/2 + 2, \ldots, 2m$ when $(m -1)/2$ is even
and for $c = (m -1)/2, (m
-1)/2 + 2, \ldots, 2m - (m-1)/2$ when $(m -1)/2$ is odd; 
ladders $L_{2k + 1}~ (k
>1)$ are
strongly $(k + 1)$-elegant; and $B(3,2,m)$ and $B(4,3,m)$ (see \S \ref{complete_graphs} for
notation) are strongly
1-elegant and strongly 3-elegant for all $m$;
the composition
$P_n[P_2]$ (see \S \ref{product_related_graphs}) is strongly $c$-elegant for $1,3,5, \ldots, 5n -6$ when 
$n$ is
odd and for $c= 1,3,5, \ldots, 5n -5$ when $n$ is even; $P_n$ is strongly
$\lfloor n/2 \rfloor$-elegant; $P_n^2$ is strongly $c$-elegant
for $c =1,3,5, \ldots, q$ where $q$ is the number of edges of $P_n^2$; and 
$P_n^3 ~( n> 3)$ is strongly $c$-elegant for 
$c = 1,3,5, \ldots, 6k -1$ when $n = 4k$,
$c = 1,3,5, \ldots, 6k +1$ when $n = 4k + 1$,
$c = 1,3,5, \ldots, 6k +3$ when $n = 4k + 2$,
$c = 1,3,5, \ldots, 6k + 5$ when $n = 4k + 3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of file
