% 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) 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