% 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}
% 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}
\begin{document}
\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{proof}
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{proof}
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