% 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