Radio-$k$-Labeling of Cycles for Large $k$^††thanks: Research is partially supported by the National Science Foundation grant DMS-1600778 and NASA NASA MIRO grant NX15AQ06A.

Radio-$k$-labeling is motivated by the channel assignment problem which was first introduced by Hale [8]. In the channel assignment problem, we must both avoid signal interference between radio stations and minimize the range of frequencies used. Radio-$k$-labeling models this problem with a graph where each station or transmitter is a vertex and neighboring stations are connected by an edge. The distance between two stations is then the usual distance between vertices on a graph, and a station’s assigned frequency is represented by a non-negative integer label of the corresponding vertex. If two stations are close enough for their signals to interfere, they must be assigned frequencies whose difference is determined by their proximity: The closer the stations are geographically, the larger their separation in assigned frequencies must be. The goal is to assign frequencies to all stations in a way that minimizes the range of the frequencies used while still avoiding interference.

Let $G$ be a graph. The distance between two vertices $u$ and $v$, denoted by $\operatorname{d}(u,v)$, is the length of a shortest path between $u$ and $v$. The diameter of $G$ is the largest distance between any two vertices in $V(G)$, which we denote by ${\rm diam}(G)$ or sometimes $d$ when the graph is clear in the context.

For a positive integer $k$, a function $f\colon V(G)\to\{0,1,2,3,\cdots\}$ is a radio-$k$-labeling of a graph $G$, if for all $u,v\in V(G)$, $u\neq v$,

Sometimes we say $f$ is a labeling instead of radio-$k$-labeling or omit mentioning the labeled graph $G$ if it is clear from the context. The span of a radio-$k$-labeling $f$ of $G$ is defined as $\operatorname{span}(f)\coloneqq\max\{|f(u)-f(v)|:u,v\in V(G)\}.$ We follow the convention of labeling at least one vertex $0$, so the span of any radio-$k$-labeling is the largest label assigned to a vertex $v\in V(G)$.

The radio-$k$-number of $G$ is the minimum span of a radio-$k$-labeling admitted by $G$. We call a radio-$k$-labeling $f$ of a graph $G$ optimal if the span is equal to the radio-$k$-number. A special case for the radio-$k$-labeling of a graph $G$ is when $k={\rm diam}(G)=d$, in which a radio-$d$-labeling is also known as radio labeling and the radio number of $G$ is denoted by $rn(G)$, where $rn(G)=rn_{d}(G)$.

The notion of radio labeling was introduced by Chartrand, Erwin and Zhang [4]. The radio number for special families of graphs has been studied widely in the literature. Liu and Zhu [15] determined the radio number of cycles and paths. A general lower bound of the radio number of trees was given by Liu [13], and then applied by several authors to special families of trees (cf. [12, 7, 2, 14]). Khennoufa and Togni [11] studied the radio number for hypercubes by using generalized binary Gray codes. Zhou [20, 21, 22] and Martinez et al. [16] investigated the radio number for Cayley graphs and generalized prism graphs, respectively. Niedzialomski [18] studied radio graceful graphs (where $G$ admits a surjective radio labeling from $V(G)$ to $\{1,2,\cdots,|V(G)|\}$) and showed that the Cartesian product of $t$ copies of a complete graph is radio graceful for certain $t$, providing infinitely many examples of radio graceful graphs of arbitrary diameter. For two positive integers $m,n\geqslant 3$, the toroidal grid $G_{m,n}$ is the Cartesian product of cycles $C_{m}$ and $C_{n}$, $C_{m}\Box C_{n}$. Morris et al. [17] determined $rn(G_{n,n})$, and Saha and Panigrahi [19] determined $rn(G_{m,n})$ when $mn\equiv 0\pmod{2}$. Bantva and Liu [1] considered the radio number for block graphs and line graphs of trees.

When $k=1$, radio-$k$-labeling is equivalent to vertex coloring. Radio-$k$-labelings of graphs for other values of $k$ have have also been studied extensively. There are many known results when $k=2$ (cf. [6, 3]), this case is called $L(2,1)$-labeling, which can be generalized to $L(h,k)$-labeling. Recently, Chavez et al. studied optimal radio-$k$-labeling for trees [5].

For cycles $C_{n}$ with $n\geqslant 3$, the value of $rn_{d}(C_{n})$ was completely determined in [15]. Also, $rn_{d-1}(C_{n})$ when $n\not\equiv 0\pmod{4}$ has been determined in [9], where bounds are given for the case when $n\equiv 0\pmod{4}$. Karst, Langowitz, Oehrlein, and Troxell in [10] studied radio-$k$-labeling when $k\geqslant{\rm diam}(C_{n})$ and determined the value of $rn_{k}(C_{n})$ when $k={\rm diam}(C_{n})+1$.

In this paper we investigate the values of $rn_{k}(C_{n})$ for all $k\geqslant{\rm diam}(C_{n})$. In particular, we determine the values of $rn_{k}(C_{n})$ for $k\geqslant n-3$, and for $k<n-3$ with $n\equiv k$ (mod 2). For $k<n-3$ and $k\not\equiv n$ (mod 2), we establish lower and upper bounds and show these bounds are sharp for some values of $k$ and $n$. A major tool we use is a combination of a lower bound approach (see 3) with some basic properties of finite cyclic groups.

In what follows, we let $\mathbb{Z}$ denote the set of integers, $\mathbb{N}$ the set of natural numbers and $\mathbb{N}_{0}\coloneqq\mathbb{N}\cup\{0\}$. For $n,m\in\mathbb{Z}$, such that $n\leqslant m$, we define $[n,m]\coloneqq\{n,n+1,\ldots,m\}$. For $n\in\mathbb{N}$, we let $\mathbb{Z}_{n}$ denote the cyclic group of order $n$. For $m\in\mathbb{Z}_{n}$, let $\langle m\rangle$ be the subgroup of $\mathbb{Z}_{n}$ generated by $m$. That is, $\langle m\rangle=\{tm:t\in\mathbb{Z}\}$ (mod $n$). Let $\mathbb{Z}_{n}/\langle m\rangle$ denote the cyclic quotient group of $\mathbb{Z}_{n}$ modulo $\langle m\rangle$, which is defined on the cosets $i/\langle m\rangle\coloneqq\{j\in\mathbb{Z}_{n}:i-j\in\langle m\rangle\}$ for $i\in\mathbb{Z}_{n}$.

We regard $C_{n}$ as a Cayley graph with vertex set $\mathbb{Z}_{n}$ and edges generated by $\pm 1$. That is, $V(C_{n})=\{0,1,2,\cdots,n-1\}$ where $u$ and $v$ are adjacent if $u\equiv v\pm 1$ (mod $n$). In the proofs we will often make use of an additive structure on $V(C_{n})=\mathbb{Z}_{n}$ which is addition modular $n$. The modest amount of group theory mentioned in this paper can be found in any introductory textbook on abstract algebra.

By definition, when $k\geqslant{\rm diam}(G)$, every radio-$k$-labeling of $G$ is injective. So we can order the vertices of $G$ such that the labeling is strictly increasing. Thus, given a radio-$k$-labeling $f$ of $C_{n}$ with $k\geqslant\lfloor n/2\rfloor$, we denote the vertices of $V(C_{n})$, $x_{i}$ for $i\in[0,n-1]$ such that if $i<j$, then $f(x_{i})<f(x_{j})$ for $i,j\in[0,n-1].$ For $i\in[0,n-2]$, we define the label gap and the distance gap respectively by

These notations are used throughout the paper. By definition, $f_{i}\geqslant k+1-d_{i}$.

Here is an example of Definition 2.

Notice that in 1, the jump sequence does not determine a permutation and so does not define a labeling for $C_{n}$. In practice, we will define a jump sequence and then prove that it determines a permutation of the vertices of $C_{n}$.

We will frequently use the following lemma in our proofs.

Denote the lower bounds of $rn_{k}(C_{n})$ from 3 by ${\rm LB}(n,k)$:

The next result from [10] greatly reduces the number of inequalities to verify when determining if a map $f$ is a radio-$k$-labeling.

In this section, we completely determine the radio-$k$-number for $C_{n}$ when $k\geqslant n-3$ (Theorem 6) and when $k<n-3$ wile $n$ and $k$ have the same parity (Theorem 8).

For $k\geqslant n-3$, we make use of the following lemma, which is a stronger version of Proposition 4 for the special case when $k\geqslant n-3$.

Now we turn to the case when $d\leqslant k<n-3$ and $n\equiv k$ (mod $2$). Recall $\varPhi(n,k)$ and ${\rm LB}(n,k)$ from Eq. 1 and Eq. 2, respectively.

7 shows that when $n$ and $k$ have the same parity, in order to keep the $\varPhi$-function value for any three consecutive vertices, $x_{i},x_{i+1},x_{i+2}$, the distance between $x_{i}$ and $x_{i+2}$ must be either $\frac{n-k}{2}$ or $\frac{n-k}{2}-1$.