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

\section{Miscellaneous Labelings}

\subsection{Sum Graphs}

In 1990, Harary \cite{Ha1} introduced the notion of a sum graph.  A graph
$G(V,E)$ is called a {\em sum graph}\index{sum graph}\subindex{labeling}{sum graph} if there is an bijective labeling
$f$ from $V$ to a set of positive integers $S$ such that $xy \in E$ if and
only if $f(x) + f(y) \in S$. Since the vertex with the highest label in a
sum graph cannot be adjacent to any other vertex, every sum graph must
contain isolated vertices. In 1991 Harary, Hentzel and Jacobs \cite{HHJ}
defined a {\em real sum graph}\index{real sum graph}\subindex{sum graph}{real} 
in an analogous way by allowing $S$ to be any
finite set of positive real numbers. However, they proved that every real sum
graph is a sum graph. Bergstrand et al. \cite{BHJ} defined a 
{\em product graph}\index{product graph} 
analogous to a sum graph except that 1 is not permitted  to belong to $S$. They 
proved that every product graph is a sum graph and vice versa.

 For a connected graph $G$, let $\sigma(G)$, the 
{\em sum number of G}\index{sum number}, denote the minimum number of isolated vertices that must
be added to $G$ so that the resulting graph is a sum graph (some authors
use $s(G)$ for the sum number of $G$). A labeling that makes 
 $G$ together with $\sigma(G)$ isolated points a sum graph is called an 
{\em optimal sum graph}\subindex{labeling}{optimal sum graph}\subindex{optimal}{sum graph} 
labeling.
Ellingham \cite{El} proved the
conjecture of Harary \cite{Ha1} that $\sigma(T)=1$ for every tree $T \not= K_1$.
Smyth \cite{Smy1} proved that there is no graph $G$ with $e$ edges and 
$\sigma(G) = 1$ when $n^2/4 < e \leq n(n-1)/2$. 
Smyth \cite{Smy2} conjectures that the disjoint union of graphs 
with sum number 1 has sum number 1. More generally, 
Kratochvil, Miller and 
Nguyen \cite{KrMN} conjecture that  $\sigma(G \cup H) \leq \sigma(G) + \sigma(H) -1$.  
Hao 
\cite{Hao} 
has shown that if $d_1 \leq d_2 
\leq \cdots \leq d_n$ is the degree sequence of a graph $G$ then $\sigma(G) > 
\mbox{max}(d_i -i)$ where the maximum is taken over all $i$. Bergstand et 
al. 
\cite{BHHJKW} proved that $\sigma(K_n) = 2n-3$. Hartsfield 
and Smyth \cite{HaSm} claimed to have proved that $\sigma(K_{m,n}) = \lceil 3m + n -
3\rceil/2$ when $n \geq m$ but Yan and Liu \cite{YL1} found counterexamples to
this assertion when $m \neq n$. Pyatkin \cite{Py}, Liaw, Kuo and Chang \cite{LKC}, Wang 
and Liu \cite{WL} and He 
et al. \cite{HSWCKY}
have shown that for $2 \leq m \leq n,
 ~~~\sigma(K_{m,n})  =\lceil \frac{n}{p} + \frac{(p + 1)(m 
- 1)}{2}\rceil$ where
$ p = \lceil \sqrt{\frac{2n}{m-1} +\frac{1}{4}} - \frac{1}{2} \rceil$ is
the unique integer such that 
$\frac{(p-1)p(m -1)}{2} < n \leq    
\frac{(p+1)p(m -1)}{2}$. 

 Miller et 
al. \cite{MRSS} proved that $\sigma(W_n) = \frac{n}{2} 
+ 2$ for  $n$ even and $\sigma(W_n) = n$ for $n \geq 5$ and $n$ odd (see 
also \cite{SuM2}). Miller, Ryan and Smyth \cite{MRSm} prove that the complete $n$-partite 
graph\subindex{complete}{$n$-partite graph} on 
$n$ sets of 2 nonadjacent vertices has sum number $4n - 5$ and obtain 
upper and lower bounds on the complete $n$-partite graph on $n$ sets of 
$m$ nonadjacent vertices. 
 Gould and R\"{o}dl 
\cite{GR} investigated bounds on the number of isolated points in a sum graph.
A group of six undergraduate students \cite{GBGGGJ} proved that
 $\sigma(K_n -\mbox{edge}) \leq 2n-4.$ 
The same group of six  students also investigated the difference between the 
largest and smallest labels in a sum graph, which they called the {\em spum}\index{spum}.
They proved spum of $K_n$ is $4n-6$ and the spum of $C_n$ is at most $4n-10$.
Kratochvil, Miller and Nguyen \cite{KrMN} have proved that every sum graph on $n$ 
vertices has a sum labeling such that every label is at most $4^n$. 


At a conference in 2000 Miller \cite{Mi} posed the following two problems.
Given any graph $G$, does there exist an optimal sum graph labeling that
uses the label 1? 
Find a class of graphs $G$ that have sum
number of the order $|V(G)|^s$ for $s > 1$.  (Such graphs were shown to
exist for $s = 2$ by
Gould and R\"{o}dl in  \cite{GR}). 
  

Chang \cite{Cha} generalized the notion of sum graph by permitting $x = y$
in the definition of sum graph. He calls graphs that have this kind of labeling 
{\em strong sum graphs}\subindex{strong}{sum graph}
and uses $i^*(G)$ to denote the minimum positive integer 
$m$ such that $G \cup mK_1$ is a strong sum graph. Chang proves that
 $i^*(K_n) =\sigma(K_n)$ for $n = 2, 3 $ and 4 and 
 $i^*(K_n) > \sigma(K_n)$ for $n \geq 5$. He further shows that for $n \geq 5,~ 
3n^{\mbox{log}_{2}3} > i^*(K_n) \geq 12 \lfloor n/5 \rfloor - 3$.  

In 1994 Harary \cite{Ha2} generalized sum graphs by permitting $S$ to be any 
set of integers. He calls these graphs 
{\em integral sum graphs}\subindex{integral sum}{graphs}\subindex{sum graphs}{integral}. 
Unlike sum 
graphs, integral sum graphs need not have isolated vertices. Sharary 
\cite{Sha} has shown that $C_n$ and $W_n$ are integral sum graphs for all $n 
\neq 4$. 
Chen \cite{Che2} proved that trees obtained from a star by extending each edge 
to a path and trees all of whose vertices of degree not 2 are at least 
distance 4 apart  are integral 
sum graphs. He conjectures that all trees are integral sum graphs. In \cite{Che2} 
and \cite{Che4} Chen gives methods for constructing new connected 
integral sum graphs from given integral sum graphs by identifying 
verticies. Chen 
\cite{Che4} has shown that every  graph is an induced subgraph of a connected 
integral sum graph. Chen \cite{Che4} calls a vertex of a graph 
{\em saturated}\index{saturated vertex} if it  is adjacent 
to every other vertex of the graph. He proves that every integral sum graph 
except  $K_3$ has 
at most two saturated vertices and gives the exact structure of  all integral 
sum graphs 
that have
exactly two saturated vertices. Chen \cite{Che4} also proves that a connected 
integral sum  graph with $p 
>1$ vertices and $q$ edges and no saturated vertices satisfies $q \leq p(3p 
-2)/8 -2.$  Wu, Mao and Le \cite{WML} proved 
that $mP_n$ are integral sum graphs. They also show that the conjecture of 
Harary \cite{Ha2} that the sum number of $C_n$ equals the integral sum number 
of $C_n$   if and only if $n  \not = 3$ or 5 is false and  
that for  $n \not = 4$ or 6 the integral sum 
number of $C_n$ is at most 1.

B. Xu \cite{XuB} has shown that the following are 
integral sum graphs: 
the union of any three stars; $T \cup K_{1,n}$ for all trees $T$; $mK_3$
for all $m$; and the union\index{union} of any number of 
 integral sum trees\subindex{integral sum}{tree};
 Xu also proved that if $2G$ and $3G$ are integral
sum graphs, then so is $mG$ for all $m >1$. Xu poses the question as to whether
all disconnected forests are integral sum graphs.
Nicholas and Somasundaram \cite{NS} prove that all banana trees (see Section~\ref{trees}) and 
the union of any 
number of stars are integral sum graphs.  


Liaw, Kuo and Chang \cite{LKC} proved that all caterpillars are 
intergral sum graphs (see also \cite{WML}  and \cite{XuB} for some special 
cases of caterpillers). This shows that
the assertion by  Harary
in \cite{Ha2} that  $K(1,3)$ and $S(2,2)$  are not integral sum graphs is 
incorrect. 
They also prove that
 all cycles
except $C_4$ are integral sum graphs and they conjecture that every tree
is an integral sum graph. Singh and Santhosh  show that the crowns\index{crown}
$C_n \odot K_1$ are integral sum graphs for $n \geq 4$ ~\cite{SiSa} and that the subdivsion 
graphs of $C_n \odot K_1$ are integral sum graphs for $n \geq 3$ ~\cite{SaSi1}.  

Melnikov and Pyatkin \cite{MePy} have shown that every 2-regular graph except $C_4$
is an integral sum graph and that for every positive integer $r$ there exists an
$r$-regular integral sum graph. They also show that the cube is not an integral
sum graph. For any integral sum graph $G,$ Melnikov and Pyatkin define the 
{\em integral radius of G}\index{integral radius} as the smallest natural number $r(G)$ that has all its
vertex labels in the interval $[-r(G), r(G)]$. For the family of all integral
sum graphs of order $n$ they use $r(n)$ to denote maximum integral radius among
all members of the family. Two questions they raise are: Is there a 
constant
$C$ such that $r(n) \leq Cn$;  for $n >2 $, is $r(n)$ equal to the $(n 
-2)$th
prime.


The concepts of sum number and integral sum number have been extended to
hypergraphs\index{hypergraph}.
 Sonntag and Teichert \cite{SoTe1} 
 prove that every hypertree (i.e., every connected, non-trivial, cycle-free
hypergraph) has sum number 1 provided that a certain cardinality condition for 
the number of edges is fulfilled. In \cite{SoTe2} the same authors prove 
that for $d\geq 3$  every $d$-uniform hypertree is an integral sum graph and 
that for $n \geq d + 2$ the sum number of the complete $d$-uniform 
hypergraph 
on $n$ vertices is 
$d(n-d) + 1$. They also prove that  the integral sum number for the 
complete $d$-uniform hypergraph on $n$ vertices is 0 when $d = n$ or $n-1$ and  
is between $(d-1)(n-d-1)$ and $d(n -d) + 1$ for $d \leq n-2$. They conjecture 
that 
for $d \leq n-2$ the sum number and the integral sum number of the complete 
$d$-uniform hypergraph are equal. 


 Teichert 
\cite{Tei2} proves that hypercycles\index{hypercycle} have 
sum
number 1 when each edge has cardinality at least 3 and that 
hyperwheels\index{hyperwheel} have sum
number 1 under certain restrictions  for the edge cardinalities.
Teichert \cite{Tei1} determined an upper bound for  the sum number of the 
$d$-partite complete hypergraph  $ K\sp d\sb{n\sb 1, \ldots, n\sb d}$.
In \cite{Tei3} Teichert defines  the {\em strong hypercycle}\subindex{hypercycle}{strong}
${\mathcal{C}}_n^d$ to be the $d$-uniform
hypergraph  with  the same vertices as $C_n$ where any $d$ consecutive
vertices of $C_n$   form 
an edge of ${\mathcal{C}}_n^d$. He proves that for $n \geq 2d + 1
\geq 5,~
\sigma({\mathcal{C}}_n^d) = d$ and for $d \geq 2,~
\sigma({\mathcal{C}}_{d +
1}^d) = d.$
 He also shows that $\sigma({\mathcal{C}}_5^3) = 3;
\sigma({\mathcal{C}}_6^3) = 2$ and he
conjectures that $\sigma({\mathcal{C}}_n^d) <d$ for $d \geq 4$ and $d
+ 2 \leq n \leq 2d.$ 


The {\em integral sum number}\subindex{integral sum}{number}, 
$\zeta(G)$, of $G$, is the minimum number of
isolated vertices that must be added to $G$ so that the resulting graph is an
integral sum graph. Thus, by definition, $G$ is a integral sum graph if and only
if $\zeta(G) = 0$.  Harary \cite{Ha2} conjectured that for $n \geq 4$ the integral
sum number $\zeta(K_n) = 2n - 3$. This conjecture was verified by Chen \cite{Che1},
by Sharary \cite{Sha} and by B. Xu \cite{XuB}. Yan and Liu proved: 
  $\zeta(K_n-E(K_r)) = n - 1$ when $n 
\geq 6, n\equiv 0$ (mod 3) and $r = 2n/3 - 1$ \cite{YL2}; $\zeta(K_{m.m}) = 2m 
-1$ for $m \geq 2$ \cite{YL2}; $\zeta(K_n -\mbox{edge}) = 2n - 4$ for $n \geq 
4$ \cite{YL2}, \cite{XuB}; if $n \geq 5$ and  $ n -3 \geq r$, then
 $\zeta(K_n - E(K_r)) \geq n -1$ 
\cite{YL2}; if $\lceil 2n/3 \rceil -1 > r \geq 2$, then
 $\zeta(K_n - E(K_r)) 
\geq 2n - r -2$ \cite{YL2}; and 
 if $2 \leq m < n,$ 
and $ n = (i + 1)(im - i + 2)/2$, then  
$\sigma(K_{m,n}) = \zeta(K_{m,n}) = (m -1)(i+ 1) + 1$ while if $ (i + 1)(im - i
+ 
2)/2 < n < (i + 
2)[(i +1)m - i + 1]/2$, then $\sigma(K_{m,n})= \zeta(K_{m,n}) = \lceil ((m - 
1)(i + 1)(i + 2) + 2n)/(2i + 2) \rceil$ \cite{YL2}.


Nagamochi, Miller and Slamin \cite{NMS} have determined upper and lower 
bounds  on the sum number a graph.  For most graphs $G(V,E)$ they show that 
$ \sigma(G) = \Omega(|E|)$. 
He et al. \cite{HYMXSW} investigated  
$\zeta(K_n - E(K_r))$ 
where $n \geq 5$ and $r \geq 2$. They proved that  $\zeta(K_n - E(K_r)) 
= 0$ when $ r = n $ or $n -1$; 
 $\zeta(K_n - E(K_r)) = n- 2$ when $r = n - 2;
 \zeta(K_n - E(K_r)) = n- 1$ when $n - 3
\geq r \geq \lceil 2n/3 \rceil - 1;  \zeta(K_n - E(K_r)) = 3n - 2r -4$
when $\lceil 2n/3 \rceil -1 > r \geq n/2;  \zeta(K_n - E(K_r)) = 2n - 4$
when $\lceil 2n/3 \rceil - 1 \geq n/2 > r \geq 2$. Moreover, they prove that if
$ n \geq 5, r \geq 2 $ and $r\neq n -1$, then  $\sigma(K_n - E(K_r)) =  
\zeta(K_n - E(K_r))$. 
 

In \cite{NV} Nicholas and Vilfred define the 
{\em edge reduced sum number}\subindex{edge reduced}{sum number} of a graph 
as the minimum number of edges whose removal from the graph results in a sum 
graph. They show that for $K_n,~n \geq 3, $ this number is $(n(n-1)/2 + \lfloor 
 n/2 \rfloor)/2$. They ask for a characterization of graphs  for which the edge 
reduced sum number is the same as its sum number. They conjecture that an 
integral sum graph of order $p$ and size $q$ exists if and only if $ q \leq 
3(p^2 -1)/8 - \lfloor (p-1)/4 \rfloor$ when $p$ is odd and $q \leq 3(3p 
-2)/8 $ when $p$ is even. They also define the 
{\em edge reduced integral sum number}\subindex{edge reduced}{integral sum number} in an analogous way and conjecture that for $K_n$
this number is $(n -1)(n -3)/8 + \lfloor (n -1)/4 \rfloor$ when $n$ is odd
and $n(n-2)/8$ when $n$ is even. 


 
Alon and Scheinermann \cite{AlSc} generalized sum graphs by replacing the 
condition $f(x) + f(y) \in S$ with $g ( f(x), f(y) ) \in S$ where $g$ is an arbitrary symmetric polynomial.
They called a graph with this property a {\em $g$-graph}\subindex{graph}{$g$-graph} and 
proved that for a given symmetric polynomial $g$ not all graphs are $g$-graphs.
On the other hand, for every symmetric polynomial $g$ and every graph $G$ there is some vertex labeling so that $G$ together with at most ${\mid}E(G){\mid}$ isolated vertices is a $g$-graph.

Boland, Laskar, Turner, and Domke \cite{BLTD} investigated a modular version of sum graphs.  
They call a graph $G(V,E)$ a {\em mod sum graph}\index{mod sum graph}\subindex{sum graph}{mod} 
 (MSG) if there 
exists a positive integer $n$ and an 
injective labeling from $V$ to $\{1,2,\ldots,n-1\}$ such that $xy \in E$ if and only if $f(x) + f(y)$ (mod $n$) $= f(z)$ for some vertex $z$.
Obviously, all sum graphs are mod sum graphs.
However, not all mod sum graphs are sum graphs.
Boland et al. \cite{BLTD} have shown the following graphs are MSG: 
all trees\index{tree} on 3 or more vertices;
all cycles\index{cycle} on 4 or more vertices;
and all $K_{2,n}$. 
They further proved that $K_p\;(p \geq 2)$ is not MSG (see also \cite{GLPF})
and  that $W_4$ is MSG. They 
conjecture that $W_p$ is 
MSG for $p \geq 4$. This conjecture was refuted by Sutton, Miller, Ryan 
and Slamin \cite{SMRS} who proved that for $n \neq 4,~ W_n$ is not MSG (the
case where $n$ is prime had been proved in 1994 by Ghoshal et al. \cite{GLPF}).
In the 
same paper Sutton et al. also showed that for $n \geq 3,~K_{n,n}$ is not
MSG. Ghoshal, Laskar, Pillone and Fricke \cite{GLPF} proved that every
connected
graph is an induced subgraph of a connected MSG graph  and any graph with 
$n$ vertices and at least two vertices of degree $n-1$ is not MSG.
Sutton et al. define the {\em mod sum number}\index{mod sum number}, $\rho(G),$ of a connected 
graph $G$ to be the least integer $r$ such that $G + \overline{K_r}$ is 
MSG. Sutton and Miller \cite{SuM1} define the cocktail party  
 graph $H_{m,n},~m,n \geq 2,$ as the graph  with a  vertex 
set $V = \{ v_1, v_2, v_3, \dots , v_{mn}\}$ partitioned
into 
$n$ independent sets $V  = \{I_1, I_2, \dots ,I_n\}$ each of size
$m$ 
such that $v_iv_j \in E$ for all $i,j \in \{1,\dots ,{mn}\}$
where $i \in I_p, \ j \in I_q, \ p \neq q$. The graphs $H_{m,n}$ can be used to
model relational database management systems (see \cite{Sut}). 
Sutton and Miller prove that $H_{m,n}$  
is not MSG for $n > m \geq 3$ and   $\rho(K_n) = n$ for $n\geq 4$.
In \cite{SDM} Sutton, Draganova and Miller prove that for $n$ odd and $n\geq
5,~
\rho(W_n)  = n$ and when $n$ is even, $\rho(W_n) = 2$.   Draganova \cite{Dr} 
has shown that for $n 
\geq 5$ and $n$ odd,  $\rho(F_n) = n$. She poses as an open problem
the determination of the mod sum number of the $t$-point suspension of
$C_n.$
Wallace \cite{Wa} has proved that
$K_{m,n}$ is MSG when $n$ is even and $n \geq 2m$ or when $n$
is odd and $n \geq 3m -3$ and that $\rho(K_{m,n}) = m$ when $3 \leq m \leq
n <
2m$. He also proves that the complete $m$-partite $K_{n_1,n_2,\ldots, 
n_m}$ is not MSG when there exist $n_i$ and $n_j$ such that $n_i < n_j 
<2n_i$. He poses the following conjectures:  $\rho(K_{m,n}) = n $ when $3m -3
> n \geq m \geq 3$;
 if $K_{n_1, n_2,\ldots, n_m}$ where $n_1 > n_2 > \cdots > n_m$, is not
MSG then $(m -1)n_m \leq \rho(K_{n_1,n_2, \ldots, n_m}) \leq (m -1)n_1$;
if $G$ has $n$ vertices then $\rho(G) \leq n$; determining  the mod sum 
number of
a graph is $NP$-complete (Sutton has observed that Wallace probably meant to say
`$NP$-hard');
Miller \cite{Mi} has asked if it is
possible for the mod sum number of
a graph $G$ be of the order $|V(G)|^2$.

Grimaldi \cite{Gr} has investigated labeling the vertices of a
 graph $G(V,E)$ with $n$ vertices with distinct elements of 
the ring $Z_n$ so that $xy \in E$ whenever $(x+y)^{-1}$  exists in $Z_n$

In his 2001 Ph.D. thesis Sutton \cite{Sut} introduced two methods of graph labelings with 
applications to storage and manipulation of relational database links 
specifically in mind.  He calls a graph $G = (V_p \cup V_i, E)$ a 
{\em sum* graph}\index{sum* graph} of 
$G_p = (V_p,E_p)$ if there is an injective labeling $\lambda$ of the vertices of $G$ 
with 
non-negative integers  with the property that $uv \in E_p $ if and only if $\lambda(u) 
+ \lambda(v) = \lambda (z)$ for some vertex $z \in G$. 
The {\em $sum^*$ number}\index{$sum^*$ number}, 
$\sigma^*(G_p),$ is the minimum cardinality of a set of new vertices $V_i$ (members of 
$V_i$ are called {\em incidentals}\index{incidental}) such that there exists  
a sum* graph of $G_p$ on 
the set of vertices $V_p \cup V_i$.
   A {\em mod sum* graph}\index{mod sum* graph} of $G_p$ is defined in the 
identical fashion  except the sum $\lambda(u) + \lambda(v)$ is taken modulo $n$ where 
the 
vertex labels of $G$ are restricted to $\{0,1, 2, \ldots, n -1\}$.  The 
{\em mod sum* number}\index{mod sum* number}, $\rho^*(G_p),$  of a graph $G_p$  is defined in the analogous way.  Sum* 
graphs 
are a 
generalization of sum graphs and mod sum* graphs are a generalization of 
mod sum graphs.    
Sutton shows that every graph is an 
induced subgraph of a  connected sum* graph.
  
The following table summarizing what is known  about sum graphs, mod sum 
graphs, sum* graphs and mod sum* graphs is 
reproduced from Sutton's Ph. D.
thesis \cite{Sut}. The results on sum* and mod sum* graphs are found in \cite{Sut}. Sutton 
\cite{Sut} poses  
the following conjectures: $\rho(H_{m,n}) \leq mn$ for $m,n \geq 2,~ \sigma^*(G_p) \leq 
|V_p|, ~\rho^*(G_p) \leq |V_p|.$

%\usepackage{amsmath}

% Remember table counter for the tables on next pages
\setcounter{thistable}{\value{table}}
% Table
\begin{table}[bht]
 \caption{\bf Summary of \bf sum graph Labelings} 
 \addcontentsline{toc}{subsubsection}{Table \thetable: Summary of sum graph Labelings}
 \vspace{0.25in}
%% \begin{figure}[htb]
%% \addcontentsline{toc}{subsubsection}{Table 3: Summary of $sum^*$ Graph Labelings}
%% \begin{center}
 \begin{tabular}{|p{\bigcol}|c|c|c|c|}
 \hline
 \begin{tablepage}{\bigcol}

\textbf{Graph}\end{tablepage}&$\sigma(G)$&$\rho(G)$
&$\sigma^*(G)$&$\rho^*(G)$\\
 \hline
 \begin{tablepage}{\bigcol}
 $K_2=S_1$\end{tablepage}&$1$&$1$&$0$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Stars, $S_n,~n \geq 2$\end{tablepage}&$1$&$0$&$0$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Trees, $T_n,~n \geq 3$ when $T_n \neq S_n$\end{tablepage}&$1$&$0$&$1$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Cycle, $C_3$\end{tablepage}&$1$&$0$&$1$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Cycles, $C_4$\end{tablepage}&$3$&$0$&$2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Cycles, $C_n,~n\geq4$\end{tablepage}&$2$&$0$&$2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Wheels, $W_4$\end{tablepage}&$4$&$0$&$2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Wheels, $W_n,~n \geq 5,~n$ odd\end{tablepage}&$n$&$n$&$2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Wheels, $W_n,~n \geq 6,~n$
even\end{tablepage}&$\frac{n}{2}+2$&$2$&$2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Fans, $F_n,~n \geq 5, ~ n$ odd\end{tablepage}&?&$n$&$1$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Complete graphs, $K_n,~n \geq 3$\end{tablepage}&$2n-3$&$n$&$n - 2$&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Cocktail party graphs, $H_{2,n}$\end{tablepage}&$4n-5$&$0$&?&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 Complete symmetric bipartite graphs, $K_{n,n}$\end{tablepage}&$\left\lceil
 \frac{4n-3}{2} \right\rceil$&?&?&?\\
 \hline
 \begin{tablepage}{\bigcol}
 	Complete bipartite graphs, $K_{m,n}$\\
 	$2nm\geq n \geq 3$
 \end{tablepage}&?&$n$&?&?\\
 \hline
 \begin{tablepage}{\bigcol}
 	Complete bipartite graphs, $K_{m,n}$\\
 	$m \geq 3n-3,\,n\geq 3,~m$ odd
 \end{tablepage}&?&$0$&?&$0$\\
 \hline
 \begin{tablepage}{\bigcol}
 	Complete bipartite graphs, $K_{m,n}$\\
 	$m \geq 2n,\,n\geq 3,~m$ even
 \end{tablepage}&?&$0$&?&$0$\\
 \hline
 \end{tabular}
%% \end{center}
%%\caption{Whatever you would like here}
%%\end{figure}
\end{table}

\newpage


\subsection{Prime and Vertex Prime Labelings}

The notion of a prime labeling originated with Entringer and was
introduced in a paper by Tout, Dabboucy and Howalla (see \cite{LWY}). A graph
with vertex set $V$ is said to have a 
{\em prime labeling}\index{prime labeling}\subindex{labeling}{prime} if its
vertices are
 labeled with distinct integers $1,2,\ldots,{\mid}V{\mid}$ such that for each
edge $xy$ the labels assigned to $x$ and $y$ are relatively prime. Around 1980,
Entringer conjectured that all trees have a prime labeling. So far, there has
been little progress towards proving this conjecture.  Among the classes of
trees known to have prime labelings are:
 paths, stars, caterpillars, complete binary trees,
 spiders (i.e., trees
with a one vertex of degree at least 3 and with all other vertices with
degree at most 2) and all trees of order up
50 (see \cite{Pi1}, \cite{Pi2} and \cite{FH}).

 Other graphs with prime labelings include
all cycles
and the disjoint union of $C_{2k}$ and $C_n$ \cite{DLM}. The complete graph
$K_n$ does not have a prime labeling for $n \geq 4$ and $W_n$ is prime if
and only if $n$ is even (see \cite{LWY}). 

Seoud, Diab and Elsakhawi \cite{SDE} have shown the following graphs are prime:
fans\index{fan}; helms\index{helm}; flowers\index{flower} 
(see \S \ref{cycle_related_graphs}); stars; $K_{2,n}$; and $K_{3,n}$ unless 
$n =3$ or $7$.
 They also shown that 
$P_n + \overline{K_m} ~(m \geq 3)$ is not prime.
 
 For $m$ and $n$ at least 3, Seoud and Youssef \cite{SY6} define $S_n^{(m)}$, the
{\em $(m,n)$-gon star}\index{$(m,n)$-gon star}, as the graph obtained from the cycle $C_n$ by
joining the two end vertices of the path $P_{m-2}$ to every pair of
consecutive vertices of the cycle such that each of the end vertices of
the path is connected to exactly one vertex of the cycle.
Seoud and Youssef \cite{SY6} have proved the following graphs
 have prime labelings:
  books,  $S_n^{(m)}, C_n \odot P_m, P_n + {\overline K_2}$ if and
only if $n = 2$ or $n$ is odd, and $C_n \odot K_1$ with a
complete 
binary tree of order $2^k -1 ~(k \geq 2)$ attached at each pendant vertex.
They also prove that every spanning subgraph of a prime 
graph\index{prime graph}\subindex{graph}{prime} is
prime and every graph is a subgraph of a prime graph. They conjecture that
all
unicycle graphs have prime labelings. Seoud and Youssef \cite{SY6} prove the
following graphs are not prime: $C_m + C_n; C_n^2$ for $ n\geq 4$;
$P_n^2$
for $n = 6$ and for $n \geq 8$; and M\"{o}bius ladders\index{M\"{o}bius 
ladder} 
$M_n$ for $n$ even.  
They also give an
exact formula for the maximum number of edges in a prime graph of order
$n$ and an upper bound for the chromatic number of a prime graph.

Youssef \cite{Yo5} has shown that helms, the union\index{union} of stars $S_m \cup 
S_n,$ and the union of cycles and stars $C_m \cup S_n$ are prime. He has 
also proved: $K_m \cup P_n$ is 
prime if 
and only if $m$ is at most 3 or if $m =4$ and $n$ is odd; $K_n \odot K_1$ is 
prime if and only if $n \leq 7;~ K_m \cup S_n$ is prime if and only if the 
number of primes less than or equal to $m + n + 1$ is at least $m$; and that the 
complement of every prime graph with odd order at least 21 and every even order 
graph of order at least 16 is not prime. 

 Salmasian \cite{Sa} has shown that every tree with $n$ vertices ($n \geq 50)$ can be
labeled with $n$ integers between 1 and $4n$ so that every two adjacent vertices
have relatively prime labels.
Pikhurko \cite{Pi2} has improved this by showing  that 
for any $c>0$ there is an $N$ such that any tree of order $n>N$ can be 
labeled
with $n$ integers between 1 and $(1+c)n$ so that adjacent labels are 
relatively prime.


Varkey  and Singh (see \cite{Var}) have shown the following graphs have prime labelings:
ladders\index{ladder}, crowns\index{crown}, cycles\index{cycle} with a 
chord\index{chord}, books\index{book}, one point unions\index{one-point union} of $C_n$, cycles with 
a chord, $L_n + K_1$.  Varkey \cite{Var} has shown that graph obtained by 
connecting 
two points with internally disjoint paths of equal length are prime.   
Varkey defines a {\em twig}\index{twig} as a graph obtained from a path by attaching 
exactly two pendent edges to each internal vertex of the path. He proves that 
twigs obtained from a path of odd length (at least 3) and 
 lotus inside a circle (see Section~\ref{magic_labeling}) 
graphs are prime.    

Given a collection of graphs $G_1,\ldots,G_n$ and some fixed vertex $v_i$ from
each $G_i$, Lee, Wui and Yeh \cite{LWY} define $Amal\{(G_i,v_i)\}$, the almagamation
of $\{(G_i,v_i){\mid}~i=1,\ldots,n\}$, as the graph obtained by taking the union
of the $G_i$ and identifying $v_1,v_2,\ldots,v_n$. Lee et al. \cite{LWY} have shown
$Amal\{(G_i,v_i)\}$ has a prime labeling when $G_i$ are paths and when $G_i$ are
cycles. They also showed that the almagamation of any number of copies of $W_n$,
$n$ odd, with a common vertex is not prime. They conjecture that for any tree
$T$ and $v$ from $T$, the almagamation of two or more copies of $T$ with $v$ in
common is prime. They further conjecture that the almagamation of two or more
copies of $W_n$ that share a common point is prime when $n$ is even ($n \not =
4$). Vilfred, Somasundaram and Nicholas \cite{VSN} have proved this conjecture for 
the case that $n \equiv 2$ (mod 4) where the central vertices are identified.

Vilfred, Somasundaram and Nicholas \cite{VSN} have also proved the following:  
 helms are prime; the grid $P_m \times P_n$ is prime  when $m \leq 3$ and $n$ 
is a 
prime  greater than $m$; the ladder $P_2 \times P_n$ is prime in the cases that 
$2n + 1, n + 
1$ or $n + 2$ is prime; the double cone $C_n + \overline{K_2}$ is prime only for 
$n = 3$; the double fan $P_2 \times \overline{K_2} (n \neq 2)$ is prime  if and 
only if $n$ is odd; every cycle with a $P_k$-chord is prime. They  conjecture 
that the  grid $P_m \times P_n$ is prime when $n$ is prime and $n > m$.


For any finite collection $\{G_i, u_iv_i\}$ of graphs $G_i$, each with a 
fixed edge $u_iv_i,$ Carlson \cite{Ca} defines the edge  amalgamation 
{\em Edgeamal}\index{edgeamal}$\{(G_i,u_iv_i)\}$ as the graph obtained  by taking the union of 
all the $G_i$ and identifying their fixed edges. The case where all the 
graphs are cycles she calls 
{\em generalized books}\subindex{generalized}{book}\subindex{book}{generalized}. 
She proves that all 
generalized books are prime graphs. Moreover, she shows that graphs obtained 
by  taking the union of cycles and identifying in 
each cycle the path $P_n$ are also prime.  Carlson also proves that 
$C_m$-snakes  are prime.
  

A dual of prime labelings has been introduced by Deretsky, Lee and Mitchem
\cite{DLM}.  They say a graph with edge set $E$ has a 
{\em vertex prime labeling}\index{vertex prime labeling}\subindex{labeling}{vertex prime} 
if its edges can be labeled with distinct integers
$1,\ldots,{\mid}E{\mid}$ such that for each vertex of degree at least 2 the
greatest common divisor of the labels on its incident edges is 1. Deretsky,
Lee and Mitchem show the following graphs have vertex prime labelings:
forests; all connected graphs; $C_{2k} \cup C_n$; $C_{2m} \cup C_{2n} \cup
C_{2k+1}$; $C_{2m} \cup C_{2n} \cup C_{2t} \cup C_k$; and $5C_{2m}$. They
further prove that a graph with exactly two components, one of which is not
an odd cycle, has a vertex prime labeling and a 2-regular graph with at
least two odd cycles does not have a vertex prime labeling. They conjecture
that a 2-regular graph has a vertex prime labeling if and only if it does
not have two odd cycles. 
 Let $G=\bigcup\sb {i=1}\sp tC\sb {2n\sb
i}$ and $N=\sum\sb {i=1}\sp tn\sb i$.
In \cite{BHH} Borosh, Hensley and Hobbs proved that there is a positive constant 
$n\sb 0$ such 
that the conjecture of Deretsky et al. is true for the cases that (i) 
$G$ is the disjoint
union\index{union} of at most seven cycles, or (ii) $G$ is a union of cycles all of the
same even length $2n$ if $n\le150\,000$ or if
$n\ge n\sb 0$, or (iii) $n\sb i\ge(\log N)\sp {4\log\log\log n}$ for all
$i=1,\ldots,t$, or (iv) each $C\sb {2n\sb i}$ is
repeated at most $n\sb i$ times. 
They  end their paper with a discussion of graphs whose 
components\index{component} are
all even cycles, and of graphs with
some components that are not cycles and some components that are odd
cycles.


\subsection{Edge-graceful Labelings}

In 1985, Lo \cite{Lo} introduced the notion of edge-graceful graphs. A graph
$G(V,E)$ is said to be {\em edge-graceful}\subindex{labeling}{edge-graceful} 
if there exists a bijection
$f$ from $E$ to $\{1,2,\ldots,{\mid}E{\mid}\}$ so that the induced mapping
$f^+$ from $V$ to $\{0,1,\ldots,{\mid}V{\mid}-1\}$ given by
 $f^+(x) = \sum
\{ f(xy){\mid}xy \in E\}$ (mod ${\mid}V{\mid}$) 
is a bijection. Note that an edge-graceful graph is anti-magic (see \S \ref{antimagic_labeling}).
A necessary condition for a graph with $p$ vertices and $q$ edges to be
edge-graceful is that $q(q + 1) \equiv p(p+1)/2 $ (mod $p$). Lee \cite{L3} notes
that this necessary condition extends to any multigraph\index{multigraph} with $p$ vertices 
and $q$ edges. Lee, 
Lee and
Murthy
\cite{LLM} proved that $K_n$ is edge-graceful if and only if $ n \not\equiv 2$ 
(mod 4). (An edge-graceful labeling for $K_n$ for 
$n \not\equiv 2$  (mod 4) in \cite{Lo}
was incorrect.)  Lee \cite{L3} notes that   a multigraph with $p \equiv 2$
 (mod 4)
vertices
is not edge-graceful and conjectures that this condition is sufficient for the
edge-gracefulness of connected graphs.  Lo proved that
all odd cycles are edge-graceful and  
Wilson 
and Riskin \cite{WR} proved the Cartesian product\index{Cartesian product} 
of any number of odd cycles
is edge-graceful.
Lee \cite{L2} 
has conjectured that all trees of  odd order are edge-graceful.
 Small \cite{Sma} has proved that spiders (see \S \ref{edge_magic_total} for the
definition) 
 of odd degree  with the 
property that the distance from the vertex of degree greater than 2 to 
each end vertex is the same are edge-graceful. Keene and Simoson \cite{KS} 
proved that all spiders of odd order with exactly three end vertices are 
edge-graceful. Cabaniss, Low and Mitchem \cite{CLM} have shown that regular 
spiders of odd order are edge-graceful. Lee and Seah \cite{LSe2} have shown that 
$K_{n,n,\ldots,n}$ is 
edge-graceful if and only if $n$ is odd and the number of partite sets is 
either odd 
or a multiple of 4. Lee and Seah \cite{LSe1} have also proved that $C_n^k$ 
(the $k$th power of $C_n$) is 
edge-graceful for $k < \lfloor n/2 \rfloor$ if and only if $n$ is odd and 
$C_n^k$ is edge-graceful for $k \geq \lfloor n/2 \rfloor$ if and only if
$n$ is a multiple of 4 or 
$n$ is odd (see also \cite{CLM}). Lee, Seah and Wang \cite{LSW} gave a complete 
characterization of edge-graceful $P_n^k$ graphs. 
Shiu, Lam and Cheng \cite{SLC1} proved that the 
composition\index{composition} of the path $P_3$
and any null graph of odd order is edge-graceful. Shiu, Lee and Schaffer
\cite{SLS} investigated the edge-gracefulness of multigraphs derived from
paths,
combs and spiders obtained by replacing each edge by $k$ parallel edges.
 Lee and Seah \cite{LSe3} have also investigated edge-gracefulness of 
various multigraphs.


Lee and  Seah (see \cite{L3}) define a {\em sunflower}\index{sunflower} 
graph $SF(n)$ as the graph
obtained by starting with an $n$-cycle with consecutive vertices $v_1, v_2,
\ldots, v_n$ and creating new vertices $w_1, w_2, \ldots, w_n$
 with $w_i$ connected to $v_i$ and $v_{i + 1}~ (v_{n +1}$ is $v_1).$  In 
\cite{LSe4} they
prove that $SF(n)$ is edge-graceful if and only if $n$ is even.  In the same 
paper they prove that $C_3$ is the only triangular snake that is edge-graceful.
Lee and Seah \cite{LSe1} prove that for $k \leq n/2,~ C_n^k$ is edge-graceful
if and
only if $n$ is odd and, for $k \geq n/2, ~ C_n^k$ is edge-graceful if and
only if
$ n \not \equiv 2$ (mod 4). Lee, Seah and Lo (see \cite{L3}) have proved
that for
$n$ odd, $C_{2n} \cup C_{2n + 1}, C_n \cup C_{2n + 2}$ and $C_n \cup C_{4n}$ are
edge-graceful. They also show that for odd $k$ and odd $n, ~kC_n$ is
edge-graceful. Lee and Seah (see \cite{L3}) prove that the generalized Petersen graph
$P(n,k)$ (see Section~\ref{miscellaneous_results}) is edge-graceful if and only if $n$ is even and $k <
n/2.$ In particular, $P(n,1) = C_n \times P_2$ is edge-graceful if and
only if $n$ is
even. Lee and Schaffer \cite{ScL} proved that $C_m \times C_n ~(m > 2, n >2)$ 
is
edge-graceful if and only if $m$ and $n$ are odd.  They also 
 showed that  if $G$ and $H$ are edge-graceful regular graphs 
of odd order then $G \times H$ is edge-graceful and  
that  if $G$ and $H$ are edge-graceful graphs where $G$ is 
$c$-regular of odd order $m$ and $H$ is $d$-regular of odd order $n$, then 
$G \times H$ is edge-magic if gcd($c,mn)$ = gcd$(d,m) = 1$.
They further show that if $H$ has odd order, is $2d$-regular and  
edge-graceful 
with gcd($d,m) = 1$, then $C_{2m} \times H$ is edge-magic and if $G$ is 
odd-regular, edge-graceful of even order $m$ which is not divisible by 3, 
and $G$ can be partitioned into 1-factors, then $G \times C_m$ is 
edge-graceful. 

In 1987 Lee (see \cite{LSL}) conjectured that $C_{2m} \cup C_{2n + 1}$ is 
edge-graceful for all $m$ and $n$ except for $C_4 \cup C_3$. Lee, Seah and Lo \cite{LSL}
have proved this for the case that $m = n$ and $m$ is odd. They also prove: 
the disjoint union of an  odd number copies of $C_m$ is edge-graceful when 
$m$ is odd; 
$C_n \cup C_{2n + 2}$ is edge-graceful; and $C_n \cup C_{4n}$ is edge-graceful 
for $n$ odd.     


Kendrick and Lee (see 
\cite{L3}) proved that there are only finitely many $n$ for which $K_{m,n}$ is
edge-graceful and they completely solve the problem for $m = 2$ and $m= 3.$
Ho, Lee and Seah \cite{HLSe} use $S(n;a_1,a_2, \ldots, a_k)$  where $n$ is odd and 
$1 \leq a_1\leq a_2\leq \cdots \leq a_k < n/2$ to denote the
$(n,nk)$-multigraph with vertices $v_0, v_1, \ldots, v_{n-1}$ and edge set
$\{v_iv_j|~ i \neq j, i -j \equiv a_t ~ (\bmod n) \mbox{ for } t= 1,2,
\ldots,
k\}$. They prove that all such multigraphs are edge-graceful. Lee and
Pritikin
(see \cite{L3}) prove that the M\"{o}bius ladders\index{M\"{o}bius ladder} 
of order $4n$ are edge-graceful. 
Lee, Tong and Seah \cite{LTS} have conjectured that the total graph of a
$(p,p)$-graph is edge-graceful if and only if $p$ is even. They have proved this
conjecture for cycles.  


Kuang, Lee, Mitchem and Wang \cite{KLMW} have conjectured that unicyclic graphs of odd
order are edge-graceful. They have verified this conjecture in the following
cases:  graphs obtained by identifying the end point of a path $P_m$ with a
vertex of $C_n$ when $m + n$ is even; crowns with one pendant edge deleted;
graphs obtained from crowns by identifying an endpoint of $P_m,~ m $ odd, with a
vertex of degree 1;  amalgamations of a cycle and a star obtained by identifying
the center of the star with a cycle vertex where the resulting graph has odd
order;  graphs obtained from $C_n$ by joining a pendant edge  to $n -1$ of the
cycle vertices and two pendant edges to the remaining cycle vertex. 


In 1997 Yilmaz
and Cahit \cite{YC} introduced a weaker version of edge-graceful called 
 $E$-cordial. Let $G$ be a  graph  with vertex set $V$ and edge set 
$E$  and let $f$ a function from $E$ 
to $\{0,1\}$. Define $f$ on $V$   by 
 $f(v) = \sum
\{ f(uv){\mid}uv \in E\}$ (mod 2).
The function $f$  is called an {\em E-cordial}\subindex{labeling}{E-cordial} 
labeling of $G$  
if  the number of vertices labeled 0 and the number of vertices labeled 1 
differ by at most 1 and the  
 the number of edges labeled 0 and the number of edges labeled 1 
differ by at most 1. A graph that admits an $E$-cordial labeling is 
called {\em $E$-cordial}\subindex{graph}{$E$-cordial}. 
Yilmaz and Cahit prove the following graphs are 
$E$-cordial: trees with $n$ vertices if and only if $n \not\equiv  2$ (mod
4); 
$K_n$ if and only if $n \not\equiv 2$ (mod 4); $K_{m,n}$ if and only if $m
+n 
\not\equiv 2$ (mod 4); $C_n$ if and only if $n \not\equiv  2$ (mod 4);
regular
graphs 
of degree 1 on $2n$ vertices if and only if $n$ is even; 
friendship graphs $C_3^{(n)}$ for all $n$ (see \S \ref{cycle_related_graphs}); fans $F_n$ if and 
only if $n 
\not \equiv 1$ 
(mod 4); and wheels $W_n$ if and only if $n \not\equiv 1$ (mod 4). They
observe 
that graphs with $n \equiv 2$ (mod 4) vertices can not be $E$-cordial.
They generalize $E$-cordial labelings to $E_k$-cordial ($k > 
1$) labelings by replacing $\{0,1\}$ by $\{0,1,2,\ldots, k-1\}$. Of
course, 
$E_2$-cordial is the same as $E$-cordial.


\subsection{Line-graceful Labelings}

Gnanajothi \cite{Gn} has defined a concept similar to edge-graceful. She calls
a graph with $n$ vertices 
{\em line-graceful}\subindex{graph}{line-graceful}\subindex{labeling}{line-graceful}
if it is possible to label
its edges with $0, 1, 2, \ldots, n$ so that when each vertex is assigned
the sum modulo $n$ of all the edge labels incident with that vertex the
resulting vertex labels are $0, 1,\ldots, n-1$.
A necessary condition for the line-gracefulness of a graph is that its 
order is not congruent to 2 (mod 4).
Among line-graceful graphs are (see \cite[pp. 132--181]{Gn})
$P_n$ if and only if $n \not\equiv 2$ (mod 4);
$C_n$ if and only if $n \not \equiv 2$ (mod 4);
$K_{1,n}$ if and only if $n \not \equiv 1$ (mod 4);
$P_n \odot K_1$ (combs) if and only if $n$ is even;
$(P_n \odot K_1) \odot K_1$ if and only if $n \not \equiv2$ (mod 4);
 (in general, if $G$ has order $n, ~ G \odot H$ is the graph obtained by 
taking one copy of $G$ and $n$ copies of $H$ and joining the $i$th vertex 
of $G$ with an edge to every vertex in the $i$th copy of $H$);
 $mC_n$ when $mn$ is odd;
$C_n \odot K_1$ (crowns\index{crown}) if and only if $n$ is even;
$mC_4$ for all $m$;
complete $n$-ary trees when $n$ is even;
$K_{1,n} \cup K_{1,n}$ if and only if $n$ is odd;
odd cycles with a chord; even cycles with a tail;
even cycles with a tail of length 1 and a chord;
graphs consisting of two triangles having a common vertex and 
tails of equal length attached to a vertex other than the common one;
the complete $n$-ary tree when $n$ is even;
trees for which exactly one vertex has even degree.
She conjectures that all trees  with $p \not \equiv 2$ (mod 4) 
vertices are line-graceful and proved this conjecture for $p \leq 9$.

Gnanajothi \cite{Gn} has investigated the line-gracefulness of several graphs 
obtained from stars\index{star}.
In particular, the graph obtained from $K_{1,4}$ by subdividing one spoke 
to form a path of even order (counting the center of the star) is line-graceful;
the graph obtained from a star by inserting one vertex in a single spoke is 
line-graceful if and only if the star has $p \not \equiv 2$ (mod 4) vertices;
the graph obtained from $K_{1,n}$ by replacing each spoke with a path of 
length $m$ (counting the center vertex) is line-graceful in the following cases:
$n=2$; $n=3$ and $m \not \equiv 3$ (mod 4);
$m$ is even and $mn + 1 \equiv 0$ (mod 4).

Gnanajothi studied graphs obtained by joining disjoint graphs $G$ and $H$ with an edge.
She proved such graphs are line-graceful in the following circumstances:
$G = H$; $G = P_n, H=P_m$ and $m + n \not \equiv 0$ (mod 4);
 and $G = P_n \odot K_1$, $H = P_m \odot K_1$ and $m+n \not \equiv 0$ 
(mod 4).


\subsection{Radio Labelings}

In 2001 Chartrand, Erwin, Zhang and Harary \cite{CEZH} were motivated by 
regulations for channel assignments of FM radio stations to introduce 
radio labelings of graphs. 
A {\em radio labeling}\subindex{labeling}{radio} of a connected graph 
$G$ is an injection  $c$ from the vertices of $G$ to the natural numbers 
such that 
 \[d(u,v) + |c(u) - c(v)| \geq 1 + diam(G)\]
for every two distinct vertices $u$ and $v$ of $G$. 
The {\em radio number}\index{radio number}
of $c, rn(c)$, is the maximum number assigned to any vertex of $G$. The 
{\em radio number}\index{radio number of a graph} 
of $G, rn(G)$, is the minimum value of $rn(c)$ taken 
over all radio labelings $c$ of $G$. Among the results of Chartrand et al.  
are:
 for $k \geq 2, rn(C_{2k + 1} \leq k^2 + 1$; 
 for $k \geq 3, rn(C_{2k} \leq k^2 -k + 2$; 
 for $k \geq 6, rn(C_k) \geq 3 \lceil n/2 -1\rceil; 
rn(C_3) = 3; rn(C_4) = 5; 
rn(C_6) = 8; rn(C_7) = 10; rn(C_8) = 14; rn(K_{n_1,n_2,\ldots,n_k}) =
n_1 + n_2 +\cdots + n_k + k -1$. They also prove that if $G$ is a 
connected graph of order $n$ and diameter 2, then $n \leq rn(G) \leq 2n 
-2$ and that for every pair of integers $k$ and $n$ with $n \leq k \leq 2n 
-2$, there exists a connected graph of order $n$ and diameter 2 with 
$rn(G) = k$.  They further provide a characterization of 
connected graphs of order $n$ and diameter 2 with prescribed radio number.

Zhang \cite{ZhP} proved the following: 
for $k \geq 2, 
rn(C_{4k + 1} \geq 2k^2 + 2k + 1$;
for $k$ even and $k \geq 2, rn(C_{4k + 2}) = 
2k^2  + 5k + 2$;
for $k$ odd and $k \geq 2,~  2k^2 + 5k + 2 \leq rn(C_{4k + 2}) \leq  2k^2 
+ 5k + 3; 
rn(C_{4k + 3} = 2k^2 + 2k + 3;
rn(C_{4k + 4} \geq 2k^2 + 6k + 4$; and
 for $k \geq 3,~ rn(C_{2k + 1}) \leq k^2 - \lfloor d/2 \rfloor + 2$. 


\subsection{Representations of Graphs modulo $n$}

In 1989 Erd\H{o}s and Evans \cite{EE} defined a 
{\em representation}\index{representation} modulo $n$ of a graph $G$ 
with vertices $\{v_1, v_2,
\ldots,v_r\} $ as a set $\{a_1,\ldots, a_r\}$ of distinct, nonnegative 
integers
each less than $n$ satisfying gcd($a_i - a_j, n) = 1$ if and only if $v_i$ is
adjacent to $v_j$. They proved that every finite graph can
be represented modulo some positive integer. 
The {\em representation number}\index{representation number},
Rep($G$), is smallest such integer.
Obviously the representation number of a graph is prime if and only if a graph 
is complete.
 Evans, Fricke, Maneri, McKee and Perkel \cite{EFMMP}  have
shown that a graph is representable modulo a product of a pair of distinct
primes if and only if the graph does not contain an induced subgraph isomorphic
to $K_2 \cup 2K_1, K_3 \cup K_1$, or the complement of a chordless 
cycle of
length at least five.  Ne\v{s}et\v{r}il and Pultr \cite{NP} showed that every graph
can be represented modulo a product of some set of distinct primes.
Evans et al. \cite{EFMMP} proved that if  $G$ is representable modulo $n$ and 
$p$ is 
a prime divisor of $n$, then $p \geq \chi(G).$  Evans, Isaak and Narayan \cite{EIN} 
determined representation numbers for specific families as follows 
(here we use $q_i$ to denote the $i$th
prime and for any prime $p_i$ we use $p_{i+ 1}, p_{i + 2}, \ldots, p_{i + k}$ 
to denote the next $k$ primes larger than $p_i$):
 Rep($P_n$) = $2\cdot 3 \cdot
\cdots \cdot q_{\lceil \mbox{log}_2(n -1)\rceil};$ 
 Rep($C_4$) = 4 and for $n \geq 
3$,
Rep($C_{2n}$) = $2 \cdot 3 \cdot \cdots \cdot q_{\lceil\mbox{log}_2(n 
-1)\rceil + 1}$;
Rep($C_5$) = $ 3 \cdot 5 \cdot 7 = 105$ and for $n \geq 4$ and not a power 
of 2,
Rep($C_{2n + 1}$) = $3 \cdot 5\cdot \cdots \cdot q_{\lceil\mbox{log}_2 
n\rceil + 1}$;
if $m\geq n \geq 3$, then Rep($K_m-P_n$) = $p_ip_{i + 1}$ where $p_i$ is the
smallest prime greater than or equal to $m - n = \lceil n/2 \rceil$;
if $m \geq n \geq 4$, 
and $p_i$ is the smallest
prime greater than or equal to $m - n = \lceil n/2 \rceil$ 
then Rep($K_m-C_n$) = $q_iq_{i + 1}$ if $n$ is even and  
 Rep($K_m-C_n$) = $q_iq_{i + 1}q_{i + 2}$ if $n$ is odd; if $n \leq m -1$, then
Rep($K_m - K_{1,n}$) = $p_sp_{s+1}\cdots p_{s +n -1}$ where $p_s$ is the
smallest
prime greater than or equal to $m -1$; Rep($K_m$) is the smallest
 prime greater
than or equal to $m$; Rep($nK_2$) = $2 \cdot 3 \cdot \cdots
q_{\lceil\mbox{log}_2n \rceil + 1}$; if $n,m \geq 2$, 
then Rep($nK_m$) = $p_ip_{i +1}\cdots p_{i +m -1}$, where $p_i$ is the smallest
prime satisfying $p_i \geq m$, if and only if there exists a set of $n -1$
mutually orthogonal Latin squares of order $m$; Rep($mK_1$) = $2m$; if $t \leq
(m -1)!$, then Rep($K_m + tK_1$) = $p_sp_{s+ 1}\cdots p_{s +m -1}$ where $p_s$ is
the smallest prime greater than or equal to $m$.    

In \cite{Na} Narayan asked for the values of  
Rep($C_{2^k + 1}$) 
when $k \geq 3$ and  Rep($G$) when $G$ is a complete multipartite graph or 
a disjoint union of complete graphs. He also asked about the behavior of 
the representation number for ramdom graphs. 


\subsection{$k$-sequential Labelings}

In 1981 Bange, Barkauskas and Slater \cite{BBS1} defined a
 {\em $k$-sequential}\subindex{labeling}{$k$-sequential} 
labeling $f$ of a graph $G(V,E)$ as one for which
$f$ is a bijection from $V \cup E$ to $\{k,k+1,\ldots,{\mid}V \cup
E{\mid}+k-1\}$ such that for each edge $xy$ in $E$, ~ $f(xy) =
{\mid}f(x)-f(y){\mid}$. This generalized the notion of 
{\em simply sequential}\subindex{labeling}{simply sequential} 
where $k=1$ introduced by Slater. Bange, Barkauskas and
Slater showed that cycles are 1-sequential and if $G$ is 1-sequential then
 $G + K_1$  is graceful. Hegde \cite{Heg3} proved that every graph can be 
embedded as an induced subgraph of a 1-sequential graph. Hegde and Shetty 
\cite{HeSh1} have shown that every $T_p$-tree (see \S \ref{elegant_labelings} for the definition) 
is 1-sequential. In \cite{Sl1}, Slater proved: $K_n$ is
1-sequential if and only if $n \leq 3$; for $n \geq 2$, $K_n$ is not
$k$-sequential for any $k \geq 2$; and $K_{1,n}$ is $k$-sequential if and
only if $k$ divides $n$. Acharya and Hegde \cite{AH1} proved: 
If $G$ is $k$-sequential then $k$ is at most the independence number of $G$;
$P_{2n}$ is
$n$-sequential for all $n$  and $P_{2n+1}$ is both
$n$-sequential and $(n+1)$-sequential for all $n$;~
$K_{m,n}$ is $k$-sequential for $k = 1, m$ and $n; ~K_{m,n,1}$ is
1-sequential;  and the join of any caterpillar and ${\overline{K_t}}$ is
1-sequential. Acharya \cite{A1} showed that if $G(E,V)$ is an odd graph with
${\mid}E{\mid}+{\mid}V{\mid} \equiv 1$ or $2$ (mod 4) when $k$ is odd or
${\mid}E{\mid}+{\mid}V{\mid} \equiv 2$ or $3$ (mod 4) when $k$ is even,
then $G$ is not $k$-sequential. Acharya also observed that as a
consequence of results of Bermond, Kotzig and Turgeon \cite{BKT} we have: $mK_4$
is not $k$-sequential for any $k$ when $m$ is odd and $mK_2$ is not
$k$-sequential for any odd $k$ when $m\equiv 2$ or $3$ (mod 4) or for any
even $k$ when $m \equiv 1$ or $2$ (mod 4). He further noted that $K_{m,n}$
is not $k$-sequential when $k$ is even and $m$ and $n$ are odd, while 
$K_{m,k}$ is $k$-sequential
for all $k$. Acharya \cite{A1} points out that the following result of Slater's
\cite{Sl2} for $k = 1$ linking $k$-graceful graphs and $k$-sequential graphs
holds in general: A graph is $k$-sequential if and only if $G+v$ has a
$k$-graceful labeling $f$ with $f(v) = 0$. Slater \cite{Sl1} also proved that a
$k$-sequential graph with $p$ vertices and $q > 0$ edges must satisfy $k
\leq p-1$. 
 Hegde \cite{Heg3} proved that every graph can be embedded as an
induced subgraph of a simply sequential graph\subindex{graph}{simply sequential}. 
In \cite{A1} Acharya conjectured that if $G$ 
is a connected  $k$-sequential graph of order $p$ with $k > \lfloor p/2  
\rfloor$, then $k = p-1$ and $G = K_{1, p-1}$
and that, except for $K_{1,p-1},$ every  tree  in which all 
vertices are odd  is 
$k$-sequential for all odd positive integers $k \leq p/2$.  Hegde 
\cite{Heg3} 
gave counterexamples for both of these conjectures. 


\subsection{Binary Labelings}

In 1996 Caccetta and Jia \cite{CJ} introduced  binary labelings of graphs. 
Let $G=(V,E)$ be a graph. A mapping $f:E\mapsto\{0,1\}^m$ is called 
an {\em {\rm M}-coding}\index{M-coding} if the induced mapping 
$g: V\mapsto\{0,1\}^m$, defined as
$g(v)=\sum_{u\in V,\;uv\in E} f(uv)$ is injective, where the summation is
$\mbox{modulo } 2$. An M-coding is called 
{\em positive}\subindex{M-coding}{positive} if the zero vector 
is not assigned to an edge and a vertex of $G$.
 Cacetta and Jia  show that the minimal $m$ for a positive M-coding equals
$k+1$ if $|V|\in \{2^k,2^k-2,2^k-3\}$ and $k$ otherwise, where $k=\lceil
\log_2|V| \rceil$.


\subsection{Average Labelings}

In 1997 Harminc \cite{Har} introduced a new kind of labeling in an effort to 
characterize forests and graphs without edges.
Let $G=(V,E)$ be a graph. A mapping $f:V\mapsto N$ is called 
{\em average labeling\/}\subindex{labeling}{average} 
if for any $(v,u),(u,w)\in E$ one has $f(u)=
(f(v)+f(w))/2$. A labeling is called 
{\em nontrivial}\subindex{labeling}{nontrivial} if any connected
component of $G$ (excluding isolated vertices) has at least two
differently labeled vertices.
Harminc  provides three results towards the characterization of hereditary
graphs properties in terms of average labelings. In particular, all
maximal connected subgraphs of $G$ are exactly paths (i.e., $G$ is a
linear
forest) if and only if there exists a nontrivial average labeling of $G$. 
He also characterizes forests and graphs without
edges by introducing a bit more complicated average-type labelings.
In 2001 Harminc and Sot\'{a}k \cite{HaSo} gave a characterization
of all non-complete connected graphs that have a non-trivial
average labeling. 


\subsection{Sequentially Additive Graphs}

Bange, Barkauskas and 
Slater \cite{BBS2} defined a
{\em $k$-sequentially additive labeling}\subindex{labeling}{$k$-sequentially additive} 
$f$ of a graph $G(V,E)$ to be a
bijection from $V \cup E$ to $\{k,  \ldots, k + {\mid}V \cup E{\mid}
-1 \}$ such that for each edge $xy, f(xy) = f(x)+ f(y)$.
They proved:
$K_n$ is 1-sequentially additive if and only if $n \leq 3$;
$C_{3n+1}$ is not $k$-sequentially additive for $k \equiv 0$ or 2 (mod
3);
$C_{3n+2}$ is not $k$-sequentially additive for $k \equiv 1$ or 2 (mod
3);
$C_n$ is 1-sequentially additive if and only if $n \equiv 0$ or 1 (mod 3);
and
$P_n$ is 1-sequentially additive.
They conjecture that all trees are 1-sequentially additive.
Hegde \cite{Heg4} proved that $K_{1,n}$ is $k$-sequentially additive if and 
only if $k$ divides $n$. 

Acharya and Hegde \cite{AH3} have generalized $k$-sequentially additive 
labelings by allowing the image of the bijection to be $\{k, k+d, \ldots, 
(k+{\mid}V{\cup}E{\mid}-1)d\}$.
They call such a labeling 
{\em additively $(k,d)$-sequential}\subindex{labeling}{additively $(k,d)$-sequential}.


\subsection{Divisor Graphs}

G. Santhosh and G. Singh \cite{SaSi2} call a graph $G(V,E)$  a 
{\em divisor graph}\index{divisor graph}\subindex{graph}{divisor} 
if $V$ is a set of integers and $uv \in E$ if and only if 
$u$ divides $v$ or vice versa. They prove the following are divisor graphs:
trees, $mK_n$, induced subgraphs of divisor graphs,
  $H_{m,n}$ (see Section~\ref{antimagic_labeling}), the one-point 
union of complete graphs of different orders, complete bipartite graphs,
$W_n$ for $n$ even and $n>2$, and $P_n + {\overline K_t}$. They also prove that 
$C_n ~(n\geq 4)$ is a 
divisor graph if and only if $n$ is even  and if $G$ is a divisor graph 
then for 
all $n$ so is 
$G + K_n$. 


\subsection{Strongly Multiplicative Graphs}

Beineke and  Hegde \cite{BeHe} call a graph with $p$ vertices 
{\em strongly multiplicative}\subindex{graph}{strongly multiplicative} 
if the  vertices of $G$ can be labeled 
with distinct integers $1,2,\dots,p$ so that the labels induced on the edges by 
the product of the end vertices are distinct.  
They prove the following graphs are strongly multiplicative: 
trees; cycles; wheels;
$K_n$ 
if and only if $n \leq 5; ~ K\sb {r,r}$  
 if and only if $r \leq 4$; and $P_m \times P_n$. 
They then consider the 
maximum number of edges a strongly multiplicative graph on $n$ vertices 
can have. Denoting this number by $\lambda(n)$, they show that 
$\lambda(4r) \leq 6r\sp 2, \lambda(4r+1) \leq 6r\sp 2 +4r, \lambda(4r+2) 
\leq 6r\sp 2 +6r +1$, and $\lambda(4r+3) \leq 6r\sp 2 + 10r +3$.  
It remains an open problem to find a nontrivial lower bound for 
$\lambda(n)$.

Seoud and Zid \cite{SeZi} prove the following graphs are multiplicative:
Wheels; $rK_n$ for all $r$ and $n$ at most 5; $rK_n$ for $r \geq 2$ and $n 
= 6$ or 7; $rK_n$ for $r \geq 3$ and $n = 8 $ or 9;
$K_{4,r}$ for all $r$; the corona of $P_n$ and $K_m$ for all $n$ and $2 
\leq m \leq 8$.\

\subsection{Strongly $\star$-graphs}

A variation  of strong multiplicity of graphs
is a stronly $\star$-graph.
A graph of order $n$ is said to be a 
{\em strongly $\star$-graph}\index{strongly $\star$-graph} 
if its
vertices can be assigned the values $1,2,\dots ,n$ in such a way that,
when an edge whose vertices are labeled $i$ and $j$ is labeled with the
value $i+j+ij$, all edges have different labels. 
C. Adiga and D.  Somashekara \cite{AdSo} have  shown that all trees, cycles, 
and grids 
are strongly $\star$-graphs.  They further
consider the problem of determining the maximum number of
edges in any strongly $\star$-graph of given order and relate it to the
corresponding problem for strongly multiplicative graphs.


\subsection{Sigma Labelings}

Vilfred and Jinnah \cite{ViJi} call a labeling $f$ from $V(G)$ to $\{1,2, \ldots, 
|V(G)|\}$ a {\em sigma labeling}\index{sigma labeling}\subindex{labeling}{sigma} 
if for every vertex $u$ the sum of all $f(v)$ such 
that $v$ is adjacent to $u$ is a constant independent of $u$. 
This notion was first introduced by Vilfred in his Ph. D. thesis in 1994. In 
\cite{ViJi} Vilfred and Jinnah 
give a number of necessary conditions for a graph to have a sigma labeling. One 
of them is that if $u$ and $v$ are vertices of a graph with a sigma labeling 
then the order of the symmetric difference of $N(u)$ and $N(v)$ is not 1 or 2. 
This condition rules out a large class of graphs as having sigma labelings. 
Vilfred and Jinnah 
raise a number of open questions:  Does there exist  connected 
graphs that have sigma labelings other than complete multipartite graphs (in 
\cite{Vil2} it is shown that $K_{2,2, \ldots,2}$ has a sigma labeling); 
 Which complete multipartite graphs  have sigma labelings; Is it 
true that $P_m \times 
C_n~(m >1)$ does not have a sigma labeling;
Is every graph an induced subgraph of a graph with a sigma 
labeling (thye show that every graph is a subgraph of a graph with a sigma 
labeling)?  


\subsection{Set Graceful and Set Sequential Graphs}

The notions of set graceful and set sequential graphs were  introduced in 
by Acharaya in 1983.
 A graph is called {\em set graceful}\subindex{graph}{set graceful}
 if there is an 
assignment of nonempty subsets of a finite set  to the vertices and 
edges of the graph so that the value given to each edge is the symmetric 
difference of the sets assigned to the endpoints of the edge,  
the assignment of sets to the
 vertices is injective and the  assigment to the edges is bijective. 
 A graph is called {\em set sequential}\subindex{graph}{set sequential} if there is an 
assignment of nonempty subsets of a finite set  to the vertices and 
edges of the graph so that the value given to each edge is the symmetric 
difference of the sets assigned to the endpoints of the edge and the 
the assignment of sets to the
 vertices and the edges is bijective. The following has been shown:
no cycle is set sequential \cite{AH2}; a necessary condition for $K_n$ to be 
set sequential is the $n$ has the form $(\sqrt{2^{m + 3} + 7} - 1 )/2$ for 
some $m$ \cite{AH2};
a necessary condition for  $K_{a,b,c}$ to be set sequential 
is that $a,b$ and $c$ cannot have the same parity;
  $K_{2,b,c}$ is not set sequential 
when $b$ and $c$ are odd \cite{Heg6}; $P_n~ (n >3)$ is not set graceful 
\cite{Heg6};
no theta graph is set graceful \cite{Heg6}; 
the complete nontrivial $n$-ary 
tree is set sequential if and only if $n + 1$ is a power of 2 and the 
number of levels is 1 \cite{Heg6}; 
a tree is set sequential graceful if and only if 
it is set graceful \cite{Heg6};
 every graph  can be embedded as an 
induced subgraph of a connected set sequential graph  \cite{Heg6}; 
 every graph  can be embedded as an 
induced subgraph of a connected set graceful graph  \cite{Heg6}. 
\\

Acknowledgement: I wish to thank  
Petr Kovar and Tereza Kovarova for 
 their careful proofreading of the entire survey, for preparing the 
tables in Section 5 and for preparing the  
index.

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