% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}
\usepackage{amstext}
\usepackage{amssymb,latexsym}
\usepackage{amsmath}



% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
%\usepackage{amssymb}

%\def \diam {\text{diam}}

%\newtheorem{thm}{Theorem}[section]
%\newtheorem*{thmM}{Main Theorem}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{notation}[thm]{Notation}
%\newtheorem{quest}[thm]{Question}
%\newtheorem{defin}[thm]{Definition}
%\newtheorem{remark}[thm]{Remark}
%\newtheorem{lemma}[thm]{Lemma}
%\newtheorem{note}[thm]{Note}

\newtheorem{pro2}{Proof}

\begin{document}
\setcounter{page}{163}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Radio Labeling Cartesian Graph Products\thanksref{label1}}
% \thanks[label1]{}
% \author{Cynthia Wyels\corauthref{cor1}\thanksref{label2}}
% \ead{cynthia.wyels\@csuci.edu}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Mathematics, California State University Channel Islands\thanksref{label3}}
% \thanks[label3]{}

\title{Radio Labeling Cartesian Graph Products}

% use optional labels to link authors explicitly to addresses:
 \author[label1]{Cynthia Wyels}
 \address[label1]{California State University Channel Islands}
% \address[label1]{Department of Mathematics, California State University Channel Islands, 1 University Dr., Camarillo, CA  93012}% \email{cynthia.wyels\@csuci.edu}
 \author[label2]{Maggy Tomova}
 \address[label2]{University of Iowa}
% \address[label2]{Department of Mathematics, University of Iowa, 14 MacLean Hall, Iowa City, IA 52242-1419}% \email{mtomova\@math.uiowa.edu}

%\author{}

%\address{}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
radio number \sep radio labeling \sep Cartesian product
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{}

Radio labeling is derived from the assignment of radio frequencies
(channels) to a set of transmitters.  The frequencies assigned
depend on the geographical distance between the transmitters: the
closer two transmitters are, the greater the potential for
interference between their signals. Thus when the distance between
two transmitters is small, the difference in the frequencies
assigned must be relatively large, whereas two transmitters at a
large distance may be assigned frequencies with a small difference.

The use of graphs to model the ``channel assignment" problem was
first proposed by Hale in 1980 \cite{Hale}. Several schemes for distance labeling were subsequently introduced and have been extensively studied; Chartrand et al
introduced the variation known as radio labeling in 2001
\cite{CEHZ}.

In the graph model of the channel assignment problem, the vertices
correspond to the transmitters, and graph distance plays the role of
geographical distance. We assume all graphs are connected and
simple. The \emph{distance} between two vertices $u$ and $v$ of a
graph $G$, $d(u,v)$, is the length of a shortest path between $u$
and $v$. The \emph{diameter} of $G$, $diam(G)$, is the maximum
distance, taken over all pairs of vertices of $G$. A \emph{radio
labeling} of a graph $G$ is then defined to be a function $c:V(G)
\to \mathbb Z_+$ satisfying
\begin{equation}
\label{radiocond}
d(u,v)+|c(u)-c(v)|\geq 1+ diam(G)
\end{equation}
for all distinct pairs of vertices $u,v \in V(G)$. The \emph{span}
of a radio labeling $c$ is the maximum integer assigned by $c$. The
\emph{radio number} of a graph $G$, $rn(G)$, is the minumum span,
taken over all radio labelings of $G$\footnote{We use the convention, established in \cite{CEHZ}, that the co-domain of a radio labeling is $\mathbb Z_+ = \{1, 2, \dots \}$. Some authors use $\{0, 1, 2, \dots \}$ as the co-domain; radio numbers specified using the non-negative integers as co-domain are one less than those determined using the positive integers.}.

As Liu and Zhu write, ``It is surprising that determining the radio number seems a difficult problem even for some basic families of graphs." \cite{LiuZhu} The radio number is known exactly for only a few graph families, including paths and cycles \cite {LiuZhu} and the squares of paths \cite{LiuXieP} and cycles \cite{LiuXieC}; wheels and gears \cite{gears}, some generalized prisms \cite{prisms}, and Cartesian products of a cycle with itself \cite{cycleprod}. Meanwhile, bounds for the radio numbers of trees \cite{Liu}, ladders \cite{ladders}, and square grids \cite{grids} have been identified, while the radio number of cubes of the cycles $C_n^3$ for $n\leq 20$ and $n \equiv 0$, $2$, or $4\pmod 6$ is known \cite{SR}.

In this investigation we focus as follows:

\noindent \textbf{Question:} \emph{What may be said about the radio number of the Cartesian product of two graphs?}

The Cartesian product of two graphs $G$ and $H$ has vertex set $V(G
\square H) = V(G) \times V(H) = \{(g,h)\,|\, g \in V(G)$ and
 $h\in V(H)\}$. The edges of $G\square H$ consist of those pairs of
vertices $\{(g,h),\,(g',h')\}$ satisfying $g=g'$ and $h$ is adjacent
to $h'$ in $H$ or $h=h'$ and $g$ is adjacent to $g'$ in $G$. We note the following facts about Cartesian products:
\begin{itemize}
\item The order of a product is the product of the orders of the factor graphs, i.e., $G \square H$ has $|V(G)|\cdot|V(H)|$ vertices.
\item Distances in products are sums of distances between corresponding vertices in factor graphs, i.e., $d_{G\square H}\left( (g_1,h_1),(g_2,h_2) \right) = d_G(g_1,g_2) + d_H(h_1,h_2)$.
\item In particular, the diameter of a product is the sum of the diameters of the factors, i.e.,
$diam(G \square H)=diam(G)+diam(H)$.
\end{itemize}

In Section \ref{lower} we provide three lower bounds for the radio number of a Cartesian product, each of which outperforms the others in specific cases. Two upper bounds are provided in Section \ref{upper}, along with some comments as to their efficacy.

\section{Lower Bounds}
 \label{lower}
 Our first bound follows directly from the fact that a radio labeling is an injection. As such, the span of any radio labeling may never be less than the number of vertices of the associated graph.
 \begin{thm}(Vertex Lower Bound)
$$rn(G\square H) \geq |V(G)|\cdot|V(H)|.$$
 \end{thm}
This lower bound is tight for the product of the Petersen graph with itself.

The second lower bound is stated in terms of the radio numbers of the factor graphs.
 \begin{thm}(Radio Number Lower Bound)Let $G$ and $H$ be graphs.
$$rn(G\square H) \geq rn(G) + rn(H) - 1.$$
 \end{thm}
\begin{pro2}
The proof hinges on relationships between label values of vertices in the factor graphs and the product graph. Let $c$, $c_G$, and $c_H$ be optimal radio labelings of $G\Box H$, $G$, and $H$, respectively, and let $g_1, g_2 \in V(G)$ and $h_1, h_2 \in V(H)$.

\noindent \textbf{Claim}: $|c(g_1, h_1)-c(g_2, h_2)|\geq |c_G(g_1)-c_G(g_2)|+|c_H(h_1)-c_H(h_2)|-1$.

For ease of following some algebraic manipulations, we define
\begin{itemize}
\item $A = d((g_1, h_1),(g_2, h_2))+ |c(g_1, h_1)-c(g_2,h_2)|$, and
\item $B = |c_G(g_1)-c_G(g_2)|+|c_H(h_1)-c_H(h_2)|$.
\end{itemize}
As $d((g_1, h_1),(g_2, h_2))=d(g_1, g_2)+ d(h_1, h_2)$, we have
$$ A = d(g_1, g_2)+ d(h_1, h_2) + |c(g_1, h_1)-c(g_2, h_2)| + B - B.
$$
Rewriting this equation by regrouping terms yields
$$\begin{aligned}
A=&\left(d(g_1, g_2)+ |c_G(g_1)-c_G(g_2)|\right)+\left(d(h_1, h_2)+ |c_H(h_1)-c_H(h_2)|\right)\\
&+|c(g_1,h_1)-c(g_2,h_2)|-B.
\end{aligned}$$
As $c_G$ and $c_H$ satisfy the radio condition, we now have
$$ A \geq \diam(G)+1 + \diam(H)+1 + |c(g_1,h_1)-c(g_2,h_2)|-B,$$
i.e.,
$$A \geq \diam(G\Box H) + 2 + |c(g_1,h_1)-c(g_2,h_2)|-B.$$
As $c$ must also satisfy the radio condition, we may conclude that $1 + |c(g_1,h_1)-c(g_2,h_2)|-B \geq 0$, or equivalently, $|c(g_1, h_1)-c(g_2, h_2)|\geq B-1$, as claimed.

%As all our labelings are optimal labelings, the maximum label assigned to a vertex of any graph is the radio number of that graph. The minimum label assigned is 1. So
Choose $g_1, g_2, h_1$ and $h_2$ so that $c_G(g_1)=rn(G)$, $c_G(g_2)=1$, $c_H(h_1)=rn(H)$ and $c_H(h_2)=1$. As $c(u) \leq rn(G\Box H)$ and $c(v) \geq 1$ for all $u,v \in V(G\Box H)$, we have
$$ \begin{aligned}
rn(G\Box H)-1&\geq |c(g_1, h_1)-c(g_2, h_2)|\\
&\geq |c_G(g_1)-c_G(g_2)|+|c_H(h_1)-c_H(h_2)|-1\\
&=rn(G)-1+rn(H)-1.
\end{aligned}$$
Hence $rn(G\Box H)\geq rn(G)+rn(H)-1$.
\end{pro2}

This bound outperforms the Vertex Lower Bound on prism graphs, which are products of 2-paths with $n$-cycles. These prism graphs have $2n$ vertices (so the Vertex Lower Bound states the radio number is not less than $2n$); the Radio Lower Bound gives a lower bound that is $O(n^2)$.

To specify the third lower bound, an additional term, the ``gap," must be introduced. Essentially, the gap of $G$ is the smallest possible difference between the $i$th and $(i+2)$nd largest labels in a radio labeling of $G$.
\begin{defn}
Let $c$ be a radio labeling of a graph $G$, and let $\{x_1, x_2, \dots , x_n\}$ be the vertices of $G$, arranged so that $c(x_i) < c(x_j)$ whenever $i<j$. Define $\phi(G,c)$ to be the smallest integer satisfying $\phi(G,c) \geq c(x_{i+2}) - c(x_i)$ for all $i\in \{1, 2, \dots, n-2\}$. Finally, define $\phi(G)$ to be the minimum of $\phi(G,c)$ taken over all radio labelings $c$ of $G$.
\end{defn}
Our third lower bound is expressed in terms of this gap.
\begin{thm} (Gap Lower Bound)
$$rn(G\square H) \geq \left( \left\lfloor \frac 12 |V(G)|\cdot|V(H)|\right\rfloor-1\right)\left(\phi(G)+\phi(H)-2\right) +a,$$
where $a = 1$ when $|V(G)|\cdot|V(H)|$ is odd and $a=2$ otherwise.
\end{thm}
This lower bound is again sharp for the product of the Petersen graph with itself. Moreover, it is significantly more effective than the Vertex and Radio Lower Bounds on products of cycles with themselves and products of paths with themselves. The Vertex and Radio Lower Bounds give lower bounds that are $O(n^2)$ for each; the Gap Lower Bound gives $O(n^3)$ bounds. (We note that the radio number of both families of products has been shown to be $O(n^3)$ \cite{grids}, \cite{cycleprod}.)


\section{Upper Bounds}
 \label{upper}
In this section we turn our attention to determining upper bounds for radio numbers of Cartesian products of graphs. The radio condition (\ref{radiocond}) depends on distance and diameter; without knowledge of specific distances between pairs of vertices in the product graph, it is unreasonable to expect upper bounds to be sharp. Nonetheless, we present two upper bounds with varied hypotheses.
\begin{thm}
Let $G$ be a graph with diameter $2$ and $rn(G) = |V(G)| = n$. Then
$$rn(G \square G) \leq n^2 + 2(2n-2)+\left( 2\left\lfloor\frac n2\right\rfloor -1\right)\left\lfloor\frac{n-1}2\right\rfloor.$$
\end{thm}
The statement of the next theorem is similar in spirit.
\begin{thm}
Assume $G$ and $H$ are graphs satisfying $rn(G) = |V(G)| = n$, $rn(H) = |V(H)| = m$, and $diam(G)-diam(H)\geq 2$. Then
$$rn(G \square H) \leq diam(G)(n+m-2)+2mn-2m-4n+a,$$
where $a=7$ when $m$ and $n$ have opposite parity, $a = 8$ when both $m$ and $n$ are odd, and $a=6$ when both $m$ and $n$ are even.
\end{thm}
To establish both of these theorems, one must replace the radio condition (\ref{radiocond}) with conditions sufficient for labelings of the products to be radio labelings. As nothing is assumed regarding distances between vertices, the bounds necessarily involve products of the diameters of the factor graphs. It would be of interest to investigate additional upper bounds resulting from removing the hypotheses that the factor graphs have the smallest possible radio numbers, or by including additional hypotheses regarding structure of the factor graphs.

\begin{thebibliography}{11}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\bibitem{grids}
Calles, L., Gomez, H., Tomova, M., and Wyels, C., {Bounds for the radio number of square grids}, in preparation.

\bibitem{CEHZ}
Chartrand, G., Erwin, D., Zhang, P. and Harary, F.,
{Radio labelings of graphs}, Bull. Inst. Combin. Appl.,
\textbf{33} (2001), 77--85.

\bibitem{gears}
Fernandez, C., Flores, A., Tomova, M., and Wyels, C., {The radio number of gear graphs}, preprint available at front.math.ucdavis.edu/0809.2623.

\bibitem{ladders}
Flores, J., Lewis, K., Tomova, M., and Wyels, C., {The radio number of ladder graphs}, in preparation.

\bibitem{Hale}
Hale, W.K.,{Frequency assignment: theory and application},
Proc. IEEE, \textbf{68} (1980), 1497--1514.

\bibitem{Liu}
Liu, D.D.-F., {Radio number for trees}, Discrete Math. \textbf{308} (2008), no. 7, 1153--1164.

\bibitem{LiuXieC}
Liu, D.D.-F., and Xie, M., {Radio number for square cycles}, Congr. Numer. \textbf{169} (2004), 105–125.

\bibitem{LiuXieP}
Liu, D.D.-F., and Xie, M., {Radio number for square paths}, preprint available at www.calstatela.edu/faculty/dliu/ArsComFinal.pdf.

\bibitem{LiuZhu}
Liu, D.D.-F., Zhu, X., {Multilevel distance
labelings for paths and cycles}, SIAM J. Discrete Math. \textbf{19}
(2005), No. 3, 610--621.

\bibitem{cycleprod}
Morris-Rivera, M., Tomova, M., Wyels, C., and Yeager, A., {The Radio Number of $C_{n} \square C_{n}$}, preprint available at faculty.csuci.edu/cynthia.wyels/REU/aids.htm.

\bibitem{prisms}
Ortiz, J.P., Martinez, P., Tomova, M., and Wyels, C., {Radio numbers of some generalized prism graphs}, preprint available at faculty.csuci.edu/cynthia.wyels/REU/aids.htm.

\bibitem{SR}
Sooryanarayana, B., and Raghunath, P., {Radio labeling of cube of a cycle}, Far East J. Appl. Math. \textbf{29} (2007), no. 1, 113--147.

\end{thebibliography}

\end{document}

It would be interesting to determine the general relationship
between the radio number of a Cartesian product of graphs and the
radio numbers of the factor graphs (i.e.,between $rn(G\square H)$,
$rn(G)$, and $rn(H)$). For instance, $rn(K_m)=m$ and $rn(K_m \square
K_n) = mn = |V(K_m \square K_n)|$. While this might lead to the hope
that $rn(G\square H) = rn(G)rn(H)$, the result in this paper
together with Liu and Zhu's result on the radio number of cycles
\cite{LiuZhu} shows that this is not the case:
$$\begin{aligned}
rn(C_{2k}) &= k^2+k+2\text{, and} \\
rn(C_{2k+1}) &=
       \begin{cases}
          k^2+k+1, &\text{ when $k$ is even,}\\
          k^2+2k+1, &\text{ when $k$ is odd,}
        \end{cases}
\end{aligned}
$$
whereas
$$\begin{aligned}
rn(C_{2k}\square C_{2k}) &= \bigl(\frac{(2k)^2-2}2\bigr)(k+2)+2\text{, and} \\
rn(C_{2k+1} \square C_{2k+1})&=\bigl(\frac{(2k+1)^2-1}2\bigr)(k+1)+1.
\end{aligned}
$$
From this, we see that $rn(C_n \square C_n)$ is markedly less than
$rn(C_n)^2$.  At this point, not enough is known about radio
numbers of Cartesian products to venture a conjecture regarding the
relationship of $rn(G\square H)$ to $rn(G)$ and $rn(H)$.
