Optimal $L(d,1)$-Labeling of Certain Direct Graph Bundles Cycles over Cycles and Cartesian Graph Bundles Cycles over Cycles

Abstract

An $L(d,1)$-labeling of a graph $G=(V,E)$ is a function f from the vertex set $V\left(G\right)$ to the set of nonnegative integers such that the labels on adjacent vertices differ by at least d and the labels on vertices at distance two differ by at least one, where $d\ge 1$. The span of f is the difference between the largest and the smallest numbers in $f\left(V\right)$. The ${\lambda }_1^d$-number of G, denoted by ${\lambda }_1^d\left(G\right)$, is the minimum span over all $L(d,1)$-labelings of G. We prove that ${\lambda }_1^d\left(X\right)\le 2d+2$, with equality if $1\le d\le 4$, for direct graph bundle $X=C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ and Cartesian graph bundle $X=C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$, if certain conditions are imposed on the lengths of the cycles and on the cyclic ℓ-shift ${\sigma }_{\mathsf{\ell }}$.

1. Introduction

The Frequency Assignment Problem (FAP) is a combinatorial optimization problem that arises in the field of telecommunications and radio frequency (RF) engineering. The goal of the FAP is to assign a set of communication frequencies to a set of transmitters while satisfying certain constraints and minimizing interference. This problem was first formulated as a graph-coloring problem in 1980 by Hale [1]. According to Roberts [2], in order to avoid interference, any two “close” transmitters must receive different channels, and any two “very close” transmitters must receive channels that are at least two channels apart. To translate the problem into the language of graph theory, the transmitters are represented by the vertices of a graph; two vertices are “very close” if they are adjacent and “close” if they are at a distance of two in the graph. Based on this problem, Griggs and Yeh [3] introduced $L(2,1)$-labeling on a simple graph.

Formally, an $L(d,1)$-labeling of a graph G is an assignment f of non-negative integers to vertices of G such that

$$|f\left(u\right)-f\left(v\right)|\ge \left\{\begin{array}{cc}d;\hfill & \hfill d(u,v)=1,\\ 1;\hfill & \hfill d(u,v)=2,\end{array}\right.$$

where $d\ge 1$. The difference between the largest label and the smallest label assigned by f is called the span of f, and the minimum span over all $L(d,1)$-labeling of G is called the ${\lambda }_1^d$-number of G, denoted by ${\lambda }_1^d\left(G\right)$. The general problem of determining ${\lambda }_1^d\left(G\right)$ is $NP$-hard [4].

Griggs and Yeh [3] put forward a conjecture that ${\lambda }_1^2\le {\Delta }^2$ for any graph G with the maximum degree $\Delta \ge 2$. They proved that ${\lambda }_1^2\left(G\right)\le {\Delta }^2+2\Delta$ for a general graph with the maximum degree $\Delta$. Later, Chang and Kuo [5] improved the bound to ${\Delta }^2+\Delta$ while Král’ and Škrekovski [6] further reduced the bound to ${\Delta }^2+\Delta -1$. Furthermore, in 2005, Gonçalves [7] announced the bound ${\Delta }^2+\Delta -2$; the conjecture is still open. The $L(2,1)$-labeling has recently been extensively studied by many researchers; the common trend is either to determine the value of the $L(2,1)$-labeling number or to suggest bounds for particular classes of graphs.

Graph products are one of the natural constructions that develop more complex graphs from simple ones. Graph bundles [8,9], also called twisted products, are a generalization of product graphs; these have been (under various names) frequently used as computer topologies or communication networks. A famous example is the ILIAC IV supercomputer [10]. While the labeling problem of Cartesian and direct products is well studied [11,12,13,14,15,16,17,18], much less is known about the labeling problem of Cartesian and direct graph bundles [8,19].

The central result of this paper is that, for certain direct graph bundles $C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ and certain Cartesian graph bundles $C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$, where ${\sigma }_{\mathsf{\ell }}$ is a cyclic ℓ-shift, the preceding lower bound corresponds to the exact value of ${\lambda }_1^d$. An analogous result is found with respect to the ${\lambda }_1^d$-numbering of direct products of cycles and Cartesian products of cycles [12].

The rest of the paper is organized as follows. In the Section 2, we provide the basic definitions and some preliminary observations that are needed to outline our results. Section 3 deals with the ${\lambda }_1^d$-numbering of direct graph bundle cycles over cycles, while Section 4 presents analogous results for Cartesian graph bundle cycles over cycles. The methods of attack are similar.

2. Terminology and Preliminaries

A finite, simple, and undirected graph $G=\left(V\right(G),E(G\left)\right)$ comprises a set of vertices $V\left(G\right)$ and a set of edges $E\left(G\right)$. As usual, the edge $\{i,j\}\in E\left(G\right)$ is denoted by $ij$. Although here we are interested in undirected graphs, the order of the vertices will sometimes be important; for example, when we will assign automorphisms to the edges of the base graph. In such cases, we assign two opposite arcs $\left\{\right(i,j),(j,i\left)\right\}$ to edge $\{i,j\}$.

Two graphs, G and H, are called isomorphic, denoted by the symbols $G\simeq H$, if there exists a bijection $\phi$ from $V\left(G\right)$ onto $V\left(H\right)$ that preserves the adjacency and nonadjacency. In other words, a bijection $\phi :V\left(G\right)\to v\left(H\right)$ is an isomorphism when $\phi \left(i\right)\phi \left(j\right)\in E\left(H\right)$ if and only if $ij\in E\left(G\right)$. An isomorphism of a graph G onto itself is called an automorphism. The identity automorphism on G will be denoted by $i{d}_G$ or $id$.

The cycle $C_n$ on n vertices is defined by $V\left(C_n\right)=\{0,1,\cdots ,n-1\}$ and $ij\in E\left(C_n\right)$ if $i=(j\pm 1)\mathrm{mod}n$. $P_n$ denotes the path on $n\ge 1$ distinct vertices $0,1,2,\dots ,n-1$ with edges $ij\in E\left(P_n\right)$ if $j=i+1,0\le i<n-1.$ For a graph $G=(V,E)$ the distance $d_G(u,v)$, or $d(u,v)$, between vertices u and v is defined as the number of edges on the shortest $u,v$-path.

The automorphisms of a cycle have two types: a cyclic shift in the cycle by ℓ elements will be referred to as cyclic ℓ-shift and reflections with one, two, or no fixed points (depending on the parity of n). We will focus on the first type. A cyclic ℓ-shift, denoted by ${\sigma }_{\mathsf{\ell }}$, $0\le \mathsf{\ell }<n$, is defined as ${\sigma }_{\mathsf{\ell }}\left(i\right)=(i+\mathsf{\ell })\mathrm{mod}n$ for $i=0,1,\dots ,n-1$. As a special case, we have the identity ($\mathsf{\ell }=0$).

Let $G=\left(V\right(G),E(G\left)\right)$ and $H=\left(V\right(H),E(H\left)\right)$ be connected graphs. The direct product $G\times H$ and the Cartesian product $G\square H$ of G and H are defined as follows: $V(G\times H)=V(G\square H)=V\left(G\right)\times V\left(H\right)$; $E(G\times H)=\left\{\left\{(g_1,h_1)(g_2,h_2)\right\}\right|\{g_1,g_2\}\in E\left(G\right)\mathrm{and}$$\{h_1,h_2\}\in E\left(H\right)\}$ and $E(G\square H)=\left\{\left\{(g_1,h_1)(g_2,h_2)\right\}\right|\{g_1,g_2\}\in E\left(G\right)\mathrm{and}{h}_1=h_2,\mathrm{or}$$\{h_1,h_2\}\in E\left(H\right)\mathrm{and}{g}_1=g_2\}$. For more information on the direct and the Cartesian products of graphs, we refer to [20].

Let B and G be graphs, and $\mathrm{Aut}\left(G\right)$ be the set of automorphisms of G. To any ordered pair of adjacent vertices $u,v\in V\left(B\right)$ we will assign an automorphism of G. Formally, let $\sigma :V\left(B\right)\times V\left(B\right)\to \mathrm{Aut}\left(G\right)$. For brevity, we will write $\sigma (u,v)={\sigma }_{u,v}$ and assume that ${\sigma }_{v,u}={\sigma }_{u,v}^{-1}$ for any $u,v$$\in V\left(B\right)$.

Now, we construct the graphs $X_1$ and $X_2$ as follows. The vertex set of $X_1$ and $X_2$ is the Cartesian product of vertex sets, $V\left(X_1\right)=V\left(X_2\right)=V\left(B\right)\times V\left(G\right)$. The edges of $X_1$ are obtained using the following rule: for any $b_1{b}_2\in E\left(B\right)$ and any $g_1{g}_2\in E\left(G\right)$, the vertices $(b_1,g_1)$ and $(b_2,{\sigma }_{b_1,b_2}\left(g_2\right))$ are adjacent in $X_1$. We refer to $X_1$ as a direct graph bundle with base B and fibre G, and write $X_1=B{\times }^{\sigma }G$. The edges of $X_2$ are obtained using the following rule: for any $g_1{g}_2\in E\left(G\right)$ and any $b\in V\left(B\right)$, the vertices $(b,g_1)$ and $(b,g_2)$ are adjacent in $X_2$, and for any $b_1{b}_2\in E\left(B\right)$ and any $g\in V\left(G\right)$, the vertices $(b_1,g)$ and $(b_2,{\sigma }_{b_1,b_2}\left(g\right))$ are adjacent in $X_2$. We refer to $X_2$ as a Cartesian graph bundle with base B and fibre G, and write $X_2=B{\square }^{\sigma }G$.

Clearly, if all ${\sigma }_{u,v}$ are identity automorphisms, the direct graph bundle is isomorphic to the direct product $B{\times }^{\sigma }G=B\times G$ and the Cartesian graph bundle is isomorphic to the Cartesian product $B{\square }^{\sigma }G=B\square G$.

A graph bundle over a cycle can always be constructed in such a way that all but, at most, one automorphism are identities. Fixing $V\left(C_n\right)=\{0,1,2,\cdots ,n-1\}$, let us denote ${\sigma }_{n-1,0}=\alpha$, ${\sigma }_{i-1,i}=id$ for $i=1,2,\cdots ,n-1$, and write $C_n{\times }^{\alpha }G\simeq C_n{\times }^{\sigma }G$ and $C_n{\square }^{\alpha }G\simeq C_n{\square }^{\sigma }G$. In this article, we will frequently use this fact.

A graph bundle $C_n{\times }^{\alpha }G$ can also be represented as the graph obtained from the product $P_n\times G$ by adding a copy of $K_2\times G$ between vertex sets $\{n-1\}\times V\left(G\right)$ and $\left\{0\right\}\times V\left(G\right)$, such that if $V\left(K_2\right)=\{1,2\}$ and $(1,u)$ is adjacent to $(2,v)$ in $K_2\times G$, then $(n-1,u)$ and $(0,\alpha (v\left)\right)$ are connected by an edge in $C_n{\times }^{\alpha }G$. Similarly, the graph bundle $C_n{\square }^{\alpha }G$ can be represented by the product $P_n\square G$ by adding a copy of $K_2\square G$ between vertex sets $\{n-1\}\times V\left(G\right)$ and $\left\{0\right\}\times V\left(G\right)$.

We shall need the following lemma; see [21].

Lemma 1.

If G is a graph with maximum degree Δ and G includes a vertex with Δ neighbours, each of which is of degree Δ, then ${\lambda }_1^d\left(G\right)\ge \Delta +2d-2$, where $1\le d\le \Delta$.

The following facts will also be useful in the sequel.

Claim 1.

If $a,b$ and n are integers with $n\ge 1$, then $\left|\right(a\mathrm{mod}n)-(b\mathrm{mod}n\left)\right|=\left(\right|a-b\left|\mathrm{mod}n\right)$ or $n-\left(\right|a-b\left|\mathrm{mod}n\right)$.

Corollary 1.

If $a,b,d$ and n are integers with $d,n\ge 1$, then $\left|\right(a\mathrm{mod}n)-(b\mathrm{mod}n\left)\right|\ge d\iff d\le \left(\right|a-b\left|\mathrm{mod}n\right)\le n-d$.

Corollary 2.

If $a,b$ and n are integers with $n\ge 1$, then $|an-b|\mathrm{mod}n=\left(b\mathrm{mod}n\right)$ or $n-\left(b\mathrm{mod}n\right)$.

3. Direct Graph Bundle ${\mathit{C}}_{\mathit{m}}{\mathbf{\times }}^{{\mathit{\sigma }}_{\mathsf{\ell }}}{\mathit{C}}_{\mathit{n}}$

Theorem 1.

Let $d\ge 1$, $m\ge 3$ and $s=2d+3$. Let $X=C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ be a direct graph bundle with fibre $C_n$ and base $C_m$. If n is a multiple of s and ℓ has the form of $\mathsf{\ell }=[ks+{(-1)}^{a}2m]\mathrm{mod}n$ or of $\mathsf{\ell }=[ks-{(-1)}^a(d+1)m]\mathrm{mod}n$, where $a\in \{1,2\}$ and $k\in \mathrm{Z}\mathrm{Z}$, then ${\lambda }_1^d\left(X\right)\le 2d+2$, with equality if $1\le d\le 4$.

Proof. 

To prove this theorem, we will present several labelings of X. We will define four $L(d,1)$ labelings of X using labels $0,1,\dots ,2d+2$ according to the cyclic ℓ-shift ${\sigma }_{\mathsf{\ell }}$. Let $v=(i,j)\in V\left(X\right)$.

(i)

Let $\mathsf{\ell }=[ks+{(-1)}^{a}2m]\mathrm{mod}n$, where $a\in \{1,2\}$ and $k\in \mathrm{Z}\mathrm{Z}$. Define labeling $f_a$ of v as

$$f_a\left(v\right)=\left[i+(d+a)j\right]\mathrm{mod}s$$

(ii)

Let $\mathsf{\ell }=[ks-{(-1)}^a(d+1)m]\mathrm{mod}n$, where $a\in \{1,2\}$ and $k\in \mathrm{Z}\mathrm{Z}$. Define labeling $g_a$ of v as

$$g_a\left(v\right)=\left[(d+a)i+j\right]\mathrm{mod}s$$

All assignments are clearly well-defined.

• Since $C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ can be represented as the graph obtained from the product $P_m\times C_n$ by adding edges between vertex sets $\{m-1\}\times V\left(C_n\right)$ and $\left\{0\right\}\times V\left(C_n\right)$ (i.e., edges corresponding to the nontrivial automorphism ${\sigma }_{\mathsf{\ell }},\mathsf{\ell }\ne 0$), first observe the product $P_m\times C_n$.
  Let X have the labeling $f_a$. Then, v can be assigned the integer

  $$f_a\left(v\right)=\left[i+(d+a)j\right]\mathrm{mod}s.$$
  Let w be a vertex adjacent to v in $P_m\times C_n$, so w is of the form $(i+i^{\prime },(j+j^{\prime })\mathrm{mod}n)$ with one of the following properties:

  (a)

  $i=0,i^{\prime }=1,\left|j^{\prime }\right|=1$,

  (b)

  $i=m-1,i^{\prime }=-1,\left|j^{\prime }\right|=1$,

  (c)

  $i=1,2,\dots m-2,|i^{\prime }|=1,|j^{\prime }|=1$.

  It is clear that

  $$f_a\left(w\right)=\left[i+(d+a)j+i^{\prime }+(d+a)j^{\prime }\right]\mathrm{mod}s.$$
  Corollary 1 can be used to show that $|f_a\left(v\right)-f_a\left(w\right)|\ge d$; therefore, it is sufficient to show that

  $$d\le \left[|i^{\prime }+(d+a)j^{\prime }|\mathrm{mod}s\right]\le s-d=d+3$$

  and, through symmetry, if X has the labeling $g_a$, then

  $$d\le \left[|(d+a)i^{\prime }+j^{\prime }|\mathrm{mod}s\right]\le d+3.$$
  The reader can easily verify that $|i^{\prime }+(d+a)j^{\prime }|\mathrm{mod}s,|(d+a)i^{\prime }+j^{\prime }|\mathrm{mod}s\in \{d,d+1,d+2,d+3\}$.
  Let z be a vertex, at twice the distance from v in $P_m\times C_n$. Then, z takes the form $(i+i^{″},(j+j^{″})\mathrm{mod}n)$, with one of the following properties:

  (a)

  $i\in \{0,1\},i^{″}\in \{0,2\},j^{″}\in \{2,0,-2\}$, $i^{″}$ and $j^{″}$ are not all zero;

  (b)

  $i\in \{m-2,m-1\},i^{″}\in \{0,-2\},j^{″}\in \{2,0,-2\}$, $i^{″}$ and $j^{″}$ are not all zero;

  (c)

  $i\in \{2,3,\dots ,m-3\},i^{″},j^{″}\in \{2,0,-2\}$, $i^{″}$ and $j^{″}$ are not all zero.

  Let X have the labeling $f_a$. Note that z receives the label

  $$f_a\left(z\right)=\left[i+(d+a)j+i^{″}+(d+a)j^{″}\right]\mathrm{mod}s.$$
  To show that $|f_a\left(v\right)-f_a\left(z\right)|\ge 1$, it is enough to show, via Corollary 1, that

  $$1\le \left[|i^{″}+(d+a)j^{″}|\mathrm{mod}s\right]\le 2d+2$$

  and, if X has labeling $g_a$, that

  $$1\le \left[|(d+a)i^{″}+j^{″}|\mathrm{mod}s\right]\le 2d+2.$$
  Since $|i^{″}+(d+a)j^{″}|\mathrm{mod}s,|(d+a)i^{″}+j^{″}|\mathrm{mod}s\in \{1,2,3,2d,2d+1,2d+2\}$, the following hold:
• We will now consider the edges between the fiber over $m-1$ and the fiber over 0 in $X=C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$. These are edges $(m-1,u)(0,(u+j^{\prime }+\mathsf{\ell })\mathrm{mod}n)$, where $u\in V\left(C_n\right)$ and $|j^{\prime }|=1$ or, in another form, $(0,u)(m-1,(u+j^{\prime }-\mathsf{\ell })\mathrm{mod}n)$, where $u\in V\left(C_n\right)$ and $|j^{\prime }|=1$ (recall that ${\sigma }_{\mathsf{\ell }}\left(i\right)=(i+\mathsf{\ell })\mathrm{mod}n$ and ${\sigma }_{\mathsf{\ell }}^{-1}\left(i\right)=(i-\mathsf{\ell })\mathrm{mod}n$).

  (a)

  First, let us consider two adjacent vertices, one from the fiber over $m-1$ and the other from the fiber over 0. Let X has labeling $f_a$ and let $v=(m-1,j)$. If w is a neighbour from the fiber over 0, then w is of the form $w=(0,(j+j^{\prime }+\mathsf{\ell })\mathrm{mod}n)$, where $|j^{\prime }|=1$ and $\mathsf{\ell }=[ks+{(-1)}^{a}2m]\mathrm{mod}n$ for some $k\in \mathrm{Z}\mathrm{Z}$. Then,

  $$f_a\left(v\right)=\left[m-1+(d+a)j\right]\mathrm{mod}s$$

  and

  $$f_a\left(w\right)=\left[(d+a)(j+j^{\prime }+\mathsf{\ell })\right]\mathrm{mod}s.$$

  To show that $|f_a\left(v\right)-f_a\left(w\right)|\ge d$, it is sufficient to show that

  $$d\le \left[\right|m-1-(d+a)(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le d+3,$$

  (1)

  through Corollary 1.

  Because $\mathsf{\ell }=[ks+{(-1)}^{a}2m]\mathrm{mod}n$ for some $k\in \mathrm{Z}\mathrm{Z}$, there exists $k^{\prime }\in \mathrm{Z}\mathrm{Z}$ such that $\mathsf{\ell }=k^{\prime }s+{(-1)}^{a}2m$. Hence,

  $$|m-1-(d+a)(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|m-1-(d+a)(j^{\prime }+k^{\prime }s+{(-1)}^{a}2m)|\mathrm{mod}s$$

  $$=|m(1-{(-1)}^{a}2d-{(-1)}^{a}2a)-1-(d+a)j^{\prime }-(d+a)k^{\prime }s\left)\right|\mathrm{mod}s$$

  For $a=1$, we can receive

  $$|ms-1-(d+1)j^{\prime }-(d+1)k^{\prime }s|\mathrm{mod}s=$$

  $$|s(m-(d+1)k^{\prime })-(1+(d+1)j^{\prime })|\mathrm{mod}s$$

  and for $a=2$

  $$|-ms-1-(d+2)j^{\prime }-(d+2)k^{\prime }s\left)\right|\mathrm{mod}s=$$

  $$|s(-m-(d+2)k^{\prime })-(1+(d+2)j^{\prime })|\mathrm{mod}s.$$

  Since $(1+(d+a)j^{\prime })\mathrm{mod}s\in \{d+2,d+3\}$ and $s-(1+(d+a)j^{\prime })\mathrm{mod}s\in \{d,d+1\},$ the claim is true according to Corollary 2.

  Let X have the labeling $g_a$. Then, $\mathsf{\ell }=k^{\prime }s-{(-1)}^a(d+1)m$ for some $k^{\prime }\in \mathrm{Z}\mathrm{Z}$, and for adjacent vertices $v=(m-1,j)$ and $w=(0,(j+j^{\prime }+\mathsf{\ell })\mathrm{mod}n)$, we need to show that

  $$d\le \left[\right|(d+a)(m-1)-(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le d+3.$$

  (2)

  Note that

  $$\begin{gathered} |(d+a)(m-1)-(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|(d+a)(m-1)-(j^{\prime }+k^{\prime }s-{(-1)}^a(d+1)m)|\mathrm{mod}s \\ =|m(d+a+{(-1)}^{a}d+{(-1)}^a)-(d+a)-j^{\prime }-k^{\prime }s|\mathrm{mod}s. \end{gathered}$$

  For $a=1$, we obtain

  $$|-k^{\prime }s-((d+1)+j^{\prime })|\mathrm{mod}s$$

  and for $a=2$

  $$|ms-(d+2)-j^{\prime }-k^{\prime }s|\mathrm{mod}s=|s(m-k^{\prime })-((d+2)+j^{\prime })|\mathrm{mod}s.$$

  Since $((d+1)+j^{\prime })\mathrm{mod}s,s-((d+2)+j^{\prime })\mathrm{mod}s\in \{d,d+2\}$ and $((d+2)+j^{\prime })\mathrm{mod}s,s-((d+1)+j^{\prime })\mathrm{mod}s\in \{d+1,d+3\}$, the desired result follows.

  (b)

  Finally, observe vertices at a distance of two, where the shortest path between them contains at least one edge between the fiber over $m-1$ and the fiber over 0. Let v and z be two such vertices. We claim that the label of v is not equal to the label of z.

  First, let v and z be vertices from the fiber over $m-1$ (this is analogous if both vertices are from the fiber over 0). Let $v=(m-1,j)$. Then, z is of the form $z=(m-1,(j+j^{\prime })\mathrm{mod}n)$, where $|j^{\prime }|=2$ (using the fact that $(m-1,j)$ and $(m-1,(j+2\left)\mathrm{mod}n\right)$ have a common neighbour $(0,(j+1+\mathsf{\ell }\left)\mathrm{mod}n\right)$ and $(m-1,j)$ and $(m-1,(j-2\left)\mathrm{mod}n\right)$ have a common neighbour $(0,(j-1+\mathsf{\ell }\left)\mathrm{mod}n\right)$). We already considered such vertices when we considered vertices at a distance of two in the graph $P_m\times C_n$.

  Let v be a vertex from the fiber over $m-1$ and z a vertex from the fiber over 1 (similarly, v is from the fiber over $m-2$ and z is from the fiber over 0).

  Let $v=(m-1,j)$. Then, z is of the form $z=(1,(j+j^{\prime }+\mathsf{\ell })\mathrm{mod}n)$, where $j^{\prime }\in \{-2,0,2\}$. Let X have the labeling $f_a$:

  $$f_a\left(v\right)=\left[m-1+(d+a)j)\right]\mathrm{mod}s$$

  and

  $$f_a\left(z\right)=\left[1+(d+a)(j+j^{\prime }+\mathsf{\ell })\right]\mathrm{mod}s.$$

  In this case, it is enough to show, via Corollary 1, that

  $$1\le \left[\right|m-2-(d+a)(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le 2d+2.$$

  In the proof of (1), we showed that $m-1-(d+a)(j^{\prime }+\mathsf{\ell })=k^{″}s-(1+(d+a)j^{\prime })$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$. Therefore,

  $$|m-2-(d+a)(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|k^{″}s-(2+(d+a)j^{\prime })|\mathrm{mod}s.$$

  Since $(2+(d+a)j^{\prime })\mathrm{mod}s\in \{1,2,3\}$ and $s-(2+(d+a)j^{\prime })\mathrm{mod}s\in \{2d,2d+1,2d+2\},$ the claim is true according to Corollary 2.

  Now, observe labeling $g_a$. We will consider this as similar to the above. We claim that

  $$1\le \left[\right|(d+a)(m-2)-(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le 2d+2.$$

  In the proof of (2), we see that $(d+a)(m-1)-(j^{\prime }+\mathsf{\ell })=k^{″}s-((d+a)+j^{\prime })$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$. Therefore,

  $$|(d+a)(m-2)-(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|k^{″}s-(2(d+a)+j^{\prime })|\mathrm{mod}s.$$

  Since $(2(d+a)+j^{\prime })\mathrm{mod}s,s-\left((2(d+a)+j^{\prime })\mathrm{mod}s\right)\in \{1,3,2d,2d+2\}$, the desired result follows. Accordingly, two vertices that are at a distance of two from each other receive different labels.

We showed that ${\lambda }_1^d\left(C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n\right)\le 2d+2$. Further, as $C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ is a regular graph of degree 4, the application of Lemma 1 to the preceding statement shows that ${\lambda }_1^d\left(C_m{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_n\right)=2d+2$, if $1\le d\le 4$. □

Example 1.

The aforementioned scheme is illustrated in Figure 1, where an $L(2,1)$-labeling of $P_9\times P_7$ occurs following that of $C_9{\times }^{{\sigma }_{\mathsf{\ell }}}{C}_7$ for $\mathsf{\ell }=1,3,4,6$.

4. Cartesian Graph Bundle ${\mathit{C}}_{\mathit{m}}{\mathbf{\square }}^{{\mathit{\sigma }}_{\mathsf{\ell }}}{\mathit{C}}_{\mathit{n}}$

Theorem 2.

Let $d\ge 1$, $m\ge 3$ and $s=2d+3$. Let $X=C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ be a Cartesian graph bundle with fibre $C_n$ and base $C_m$ and let n be a multiple of s. Then, ${\lambda }_1^d\left(X\right)\le 2d+2$, with equality if $1\le d\le 4$, if one of the following statements holds:

(a) 

ℓ has the form $\mathsf{\ell }=[ks+{(-1)}^{a}2dm]\mathrm{mod}n$, where $a\in \{1,2\}$ and $k\in \mathrm{Z}\mathrm{Z}.$

(b) 

$d=3t+2$ for some $t\in \{0,1,\dots \}$ and ℓ has the form

$$\mathsf{\ell }=\left[ks-(2t+3)(d+a)m\right]\mathrm{mod}n,\mathrm{where}a\in \{1,2\}\mathrm{and}k\in \mathrm{Z}\mathrm{Z}.$$

(c) 

$d=3t+1$ for some $t\in \{0,1,\dots \}$ and ℓ has the form

$$\mathsf{\ell }=\left[ks+(2t+1)(d+a)m\right]\mathrm{mod}n,\mathrm{where}a\in \{1,2\}\mathrm{and}k\in \mathrm{Z}\mathrm{Z}.$$

(d) 

$d=3t$ for some $t\in \{1,2,\dots \}$, $m=ps+3t^{\prime }\ge 3$ for some $p\in \{0,1,\dots \}$ and some $t^{\prime }\in \{0,1,\dots ,2t\}$ and ℓ has the form

$$\mathsf{\ell }=\left[ks+(i+a-1){\displaystyle \frac{s}{3}}-{(-1)}^a{t}^{\prime }\right]\mathrm{mod}n,\mathrm{where}a\in \{1,2\},k\in \mathrm{Z}\mathrm{Z}\mathrm{and}i\in \{0,1,2\}.$$

Proof. 

We will present four $L(d,1)$ labelings of $C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ using labels $0,1,\dots ,2d+2$ according to the cyclic ℓ-shift ${\sigma }_{\mathsf{\ell }}$. Let $v=(i,j)\in V\left(X\right)$.

(i)

Assume that statement (a) from the theorem holds. For $a\in \{1,2\}$ define labeling $f_a$ of v as

$$f_a\left(v\right)=\left[di+(d+a)j\right]\mathrm{mod}s.$$

(ii)

Assume that one of statements (b), (c) or (d) holds. For $a\in \{1,2\}$, define labeling $g_a$ of v as

$$g_a\left(v\right)=\left[(d+a)i+dj\right]\mathrm{mod}s.$$

All assignments are clearly well-defined.

• Since $C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ can be represented as the graph obtained from the product $P_m\square C_n$ by adding edges between vertex sets $\{m-1\}\times V\left(C_n\right)$ and $\left\{0\right\}\times V\left(C_n\right)$, first observe the product $P_m\square C_n$.
  Let X have labeling $f_a$. Then, v can be assigned the integer

  $$f_a\left(v\right)=\left[di+(d+a)j\right]\mathrm{mod}s.$$
  Let w be a vertex adjacent to v in $P_m\square C_n$. Then, v and w differ in exactly one coordinate. More precisely, w has the form $w=(i+i^{\prime },(j+j^{\prime })\mathrm{mod}n)$, with one of the following properties:

  (a)

  if $i=0$, then $i^{\prime }=1,j^{\prime }=0$ or $i^{\prime }=0,\left|j^{\prime }\right|=1$;

  (b)

  if $i=m-1$, then $i^{\prime }=-1,j^{\prime }=0$ or $|j^{\prime }|=1,i^{\prime }=0$;

  (c)

  if $i\in \{1,2,\dots ,m-2\}$, then $|i^{\prime }|=1,j^{\prime }=0$ or $|j^{\prime }|=1,i^{\prime }=0$.

  It is clear that

  $$f_a\left(w\right)=\left[di+(d+a)j+d{i}^{\prime }+(d+a)j^{\prime }\right]\mathrm{mod}s.$$
  Corollary 1 can show that $|f_a\left(v\right)-f_a\left(w\right)|\ge d$; therefore, it is sufficient to show that

  $$d\le \left[|d{i}^{\prime }+(d+a)j^{\prime }|\mathrm{mod}s\right]\le s-d=d+3$$

  and, using symmetry, if X has labeling $g_a$,

  $$d\le \left[|(d+a)i^{\prime }+d{j}^{\prime }|\mathrm{mod}s\right]\le d+3.$$
  Both claims are true since $|d{i}^{\prime }+(d+a)j^{\prime }|\mathrm{mod}s,|(d+a)i^{\prime }+j^{\prime }|\mathrm{mod}s\in \{d,d+1,d+2,d+3\}$.
  Next, let z be a vertex at a distance of two from v in $P_m\square C_n$. Then, z is of the form $z=(i+i^{″},(j+j^{″})\mathrm{mod}n)$, where v and z differ in exactly one (i) or both coordinates (ii). In all cases, there are three options for the values of $i^{″}$ and $j^{″}$. In (i):

  (a)

  if $i\in \{0,1\}$, then $i^{″}=0,\left|j^{″}\right|=2$ or $i^{″}=2$ and $j^{″}=0$;

  (b)

  if $i\in \{m-2,m-1\}$, then $i^{″}=0,\left|j^{″}\right|=2$ or $i^{″}=-2$ and $j^{″}=0$;

  (c)

  otherwise, $i^{″}=0,\left|j^{″}\right|=2$ or $|i^{″}|=2,j^{″}=0$.

  In (ii):

  (a)

  if $i=0$, then $i^{″}=1,\left|j^{″}\right|=1$;

  (b)

  if $i=m-1$, then $i^{″}=-1,\left|j^{″}\right|=1$;

  (c)

  otherwise, $|i^{″}|=1,|j^{″}|=1$.

  Let X have labeling $f_a$. Then,

  $$f_a\left(z\right)=\left[di+(d+a)j+d{i}^{″}+(d+a)j^{″}\right]\mathrm{mod}s.$$
  Since we want to prove that $|f_a\left(v\right)-f_a\left(z\right)|\ge 1$, it is sufficient to prove, using Corollary 1, that

  $$1\le \left[\right|d{i}^{″}+(d+a)j^{″}\left|\mathrm{mod}s\right]\le 2d+2,$$

  and if X has the labeling $g_a$, that

  $$1\le \left[\right|(d+a)i^{″}+d{j}^{″}\left|\mathrm{mod}s\right]\le 2d+2.$$
  The reader can verify that in (i) we can obtain $|d{i}^{″}+(d+a)j^{″}|\mathrm{mod}s,|(d+a)i^{″}+d{j}^{″}|\mathrm{mod}s\in \{1,3,2d,2d+2\}$ and in (ii) $|d{i}^{″}+(d+a)j^{″}|\mathrm{mod}s,|(d+a)i^{″}+d{j}^{″}|\mathrm{mod}s\in \{1,2,2d+1,2d+2\}$. Hence, both results follow.
• In the following, we are interested in edges in $X=C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ between the fiber over vertex $m-1$ and the fiber over vertex 0. These are edges $(m-1,u)(0,(u+\mathsf{\ell })\mathrm{mod}n),u\in V\left(C_n\right)$ or in another form $(0,u)(m-1,(u-\mathsf{\ell })\mathrm{mod}n),u\in V\left(C_n\right)$.
  • Let us first observe two adjacent vertices v and w. Let X have the labeling $f_a$ and let $v=(m-1,j)$. Then, w is of the form $w=(0,(j+\mathsf{\ell }\left)\mathrm{mod}n\right)$, where $\mathsf{\ell }=[ks+{(-1)}^{a}2dm]\mathrm{mod}n$ for some $k\in \mathrm{Z}\mathrm{Z}$. Vertex v can be assigned the integer

    $$f_a\left(v\right)=\left[d(m-1)+(d+a)j\right]\mathrm{mod}s$$

    and w can be assigned the integer

    $$f_a\left(w\right)=\left[(d+a)(j+\mathsf{\ell })\right]\mathrm{mod}s.$$
    We claim that $|f_a\left(v\right)-f_a\left(w\right)|\ge d$ or, through Corollary 1, that

    $$d\le \left[\right|d(m-1)-(d+a)\mathsf{\ell }\left|\mathrm{mod}s\right]\le d+3.$$

    (3)
    Since there exists $k^{\prime }\in \mathrm{Z}\mathrm{Z}$ such that $\mathsf{\ell }=k^{\prime }s+{(-1)}^{a}2dm$, it follows that

    $$\begin{gathered} |d(m-1)-(d+a)\mathsf{\ell }|\mathrm{mod}s=|d(m-1)-(d+a)(k^{\prime }s+{(-1)}^{a}2dm\left)\right|\mathrm{mod}s= \\ =|dm(1-{(-1)}^{a}2d-{(-1)}^{a}2a)-d-(d+a)k^{\prime }s|\mathrm{mod}s= \\ {=|dm(-1)}^{a+1}s-d-(d+a)k^{\prime }s|\mathrm{mod}s=|s(dm{(-1)}^{a+1}-(d+a)k^{\prime })-d|\mathrm{mod}s \end{gathered}$$

    (since $1-{(-1)}^{a}2d-{(-1)}^{a}2a$ equals s for $a=1$ and $-s$ for $a=2$). Using Corollary 2, this can be shown to be equal to d or to $s-d=d+3$ and the claim is true.
    Further, observe labeling $g_a$. Then, one of the statements—(b), (c) or (d)—of the Theorem applies. Let these be Cases (b), (c) and (d), accordingly. Since

    $$g_a\left(v\right)=\left[(d+a)(m-1)+dj\right]\mathrm{mod}s$$

    and

    $$g_a\left(w\right)=\left[d(j+\mathsf{\ell })\right]\mathrm{mod}s,$$

    in all three cases we have to show that

    $$d\le \left[\right|(d+a)(m-1)-d\mathsf{\ell }\left|\mathrm{mod}s\right]\le d+3,$$

    (4)

    using Corollary 1.
    Case (b) Let $d=3t+2$ (then $s=6t+7$). Since $\mathsf{\ell }=k^{\prime }s-(2t+3)(d+a)m$ for some $k^{\prime }\in \mathrm{Z}\mathrm{Z}$, we can obtain

    $$\begin{gathered} |(d+a)(m-1)-d\mathsf{\ell }|\mathrm{mod}s=|(d+a)(m-1)-d(k^{\prime }s-(2t+3)(d+a)m\left)\right|\mathrm{mod}s= \\ |(d+a)m(1+d(2t+3))-(d+a)-d{k}^{\prime }s|\mathrm{mod}s= \\ |(d+a)m(t+1)s-(d+a)-d{k}^{\prime }s|\mathrm{mod}s=|s((d+a)m(t+1)-d{k}^{\prime })-(d+a)|\mathrm{mod}s. \end{gathered}$$
    Using Corollary 2, this is shown to be equal to $(d+a)\mathrm{mod}s,s-\left(\right(d+a\left)\mathrm{mod}s\right)\in \{d+1,d+2\}$.
    Case (c) Let $d=3t+1$ (then $s=6t+5$). Since $\mathsf{\ell }=k^{\prime }s+(2t+1)(d+a)m$ for some $k^{\prime }\in \mathrm{Z}\mathrm{Z}$, it holds that

    $$\begin{gathered} |(d+a)(m-1)-d\mathsf{\ell }|\mathrm{mod}s=|(d+a)(m-1)-d(k^{\prime }s+(2t+1)(d+a)m\left)\right|\mathrm{mod}s= \\ |(d+a)m(1-d(2t+1))-(d+a)-d{k}^{\prime }s|\mathrm{mod}s= \\ |(d+a)m(-ts)-(d+a)-d{k}^{\prime }s|\mathrm{mod}s=|s(-mt(d+a)-d{k}^{\prime })-(d+a)|\mathrm{mod}s. \end{gathered}$$
    As in case (a), this is equal to $d+1$ or $d+2$.
    Case (d) Let $d=3t$ (then $s=6t+3$). Since $\mathsf{\ell }=k^{\prime }s+(i+a-1){\displaystyle \frac{s}{3}}-{(-1)}^a{t}^{\prime }$ for some $k^{\prime }\in \mathrm{Z}\mathrm{Z}$, it holds that

    $$\begin{gathered} \left|\right(d+a\left)\right(m-1)-d\mathsf{\ell }|\mathrm{mod}s= \\ |(d+a)(ps+3t^{\prime }-1)-d(k^{\prime }s+(i+a-1){\displaystyle \frac{s}{3}}-{(-1)}^a{t}^{\prime })|\mathrm{mod}s= \\ |s[p(d+a)-d{k}^{\prime }-t(i+a-1)]+(d+a)(3t^{\prime }-1)+d{(-1)}^a{t}^{\prime }|\mathrm{mod}s= \\ |s[p(d+a)-d{k}^{\prime }-t(i+a-1)]+t^{\prime }(3(d+a)+d{(-1)}^a)-(d+a)|\mathrm{mod}s. \end{gathered}$$
    For $a=1$, we can obtain

    $$|s[p(d+1)-d{k}^{\prime }-ti)]+s{t}^{\prime }-(d+1)|\mathrm{mod}s$$

    and for $a=2$, we can obtain

    $$|s[p(d+2)-d{k}^{\prime }-t(i+1)]+2s{t}^{\prime }-(d+2)|\mathrm{mod}s.$$
    The desired result follows, since, in this case, we can also obtain $d+1$ or $d+2$.
  • Finally, observe vertices at a distance of two, where the shortest path between them contains some edge between the fiber over $m-1$ and the fiber over 0. Let v and z be two such vertices. Then, v and z are from adjacent fibers (from fiber over $m-1$ and over 0) or from non-adjacent fibers (from fiber over $m-2$ and over 0 or from fiber over $m-1$ and over 1). Let us first observe the case where v and z are from non-adjacent fibers.

    (a)

    Let $v=(m-2,j)$. Then, z is of the form $z=(0,(j+\mathsf{\ell }\left)\mathrm{mod}n\right)$, where $\mathsf{\ell }=[ks+{(-1)}^{a}2dm]\mathrm{mod}n$ for some $k\in \mathrm{Z}\mathrm{Z}$ (similarly, $v=(m-1,j)$ and $z=(1,(j+\mathsf{\ell })\mathrm{mod}n$). Let X have the labeling $f_a$. Vertex v be assigned the integer

    $$f_a\left(v\right)=\left[d(m-2)+(d+a)j\right]\mathrm{mod}s$$

    and vertex z be assigned the integer

    $$f_a\left(z\right)=\left[(d+a)(j+\mathsf{\ell })\right]\mathrm{mod}s.$$

    We claim that $|f_a\left(v\right)-f_a\left(z\right)|\ge 1$ or, using Corollary 1, that

    $$1\le \left[\left|d\right(m-2)-(d+a)\mathsf{\ell }|\mathrm{mod}s\right]\le 2d+2.$$

    In the proof of (3), we showed that $d(m-1)-(d+a)\mathsf{\ell }=k^{″}s-d$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$. Therefore,

    $$|d(m-2)-(d+a)\mathsf{\ell }|\mathrm{mod}s=|d(m-1)-d-(d+a)\mathsf{\ell }|\mathrm{mod}s=|k^{″}s-2d|\mathrm{mod}s.$$

    Using Corollary 2, this is equal to $2d$ or to $s-2d=3$, and the desired results follow.

    Let X have labeling $g_a$. We need to show that

    $$1\le \left[\right|(d+a)(m-2)-d\mathsf{\ell }\left|\mathrm{mod}s\right]\le 2d+2.$$

    When we proved (4), in all three cases, we found that $(d+a)(m-1)-d\mathsf{\ell }=k^{″}s-(d+a)$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$. Therefore, we can obtain

    $$\begin{gathered} \left|\right(d+a\left)\right(m-2)-d\mathsf{\ell }|\mathrm{mod}s=\left|\right(d+a\left)\right(m-1)-(d+a)-d\mathsf{\ell }|\mathrm{mod}s= \\ |k^{″}s-2(d+a)|\mathrm{mod}s. \end{gathered}$$

    Since $\left(2\right(d+a\left)\right)\mathrm{mod}s,s-\left(\right(2(d+a)\left)\mathrm{mod}s\right)\in \{1,2d+2\},$ the desired result follows.

    (b)

    Let v and z be from adjacent fibers, and let $v=(m-1,j)$. Let X have the labeling $f_a$. Then, z is of the form $z=(0,(j+j^{\prime }+\mathsf{\ell })\mathrm{mod}n)$, where $|j^{\prime }|=1$ and $\mathsf{\ell }=[ks+{(-1)}^{a}2dm]\mathrm{mod}n$ for some $k\in \mathrm{Z}\mathrm{Z}$. In this case,

    $$f_a\left(v\right)=\left[d(m-1)+(d+a)j\right]\mathrm{mod}s$$

    and

    $$f_a\left(z\right)=\left[(d+a)(j+j^{\prime }+\mathsf{\ell })\right]\mathrm{mod}s.$$

    Again, it is sufficient to show that

    $$1\le \left[\right|d(m-1)-(d+a)(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le 2d+2.$$

    Recall that $d(m-1)-(d+a)\mathsf{\ell }=k^{″}s-d$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$ (see the proof of (3)). Therefore,

    $$\begin{gathered} |d(m-1)-(d+a)(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|d(m-1)-(d+a)j^{\prime }-(d+a)\mathsf{\ell }|\mathrm{mod}s= \\ |k^{″}s-(d+(d+a)j^{\prime })|\mathrm{mod}s. \end{gathered}$$

    The reader can verify that $(d+(d+a)j^{\prime })\mathrm{mod}s\in \{2d+1,2d+2\}$ and $s-\left((d+(d+a)j^{\prime })\mathrm{mod}s\right)\in \{1,2\}$, so the desired result follows.

    Let X have the labeling $g_a$. We need to show that

    $$1\le \left[\right|(d+a)(m-1)-d(j^{\prime }+\mathsf{\ell })\left|\mathrm{mod}s\right]\le 2d+2.$$

    Recall that $(d+a)(m-1)-d\mathsf{\ell }=k^{″}s-(d+a)$ for some $k^{″}\in \mathrm{Z}\mathrm{Z}$ (see the proof of (4)). Therefore,

    $$|(d+a)(m-1)-d(j^{\prime }+\mathsf{\ell })|\mathrm{mod}s=|k^{″}s-((d+a)+d{j}^{\prime })|\mathrm{mod}s.$$

    Since $((d+a)+d{j}^{\prime })\mathrm{mod}s,s-\left(((d+a)+d{j}^{\prime })\mathrm{mod}s\right)\in \{1,2,2d+1,2d+2\}$, the desired result follows.

    Accordingly, two vertices in $C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ at a distance of two from each other receive different labels.

We showed that ${\lambda }_1^d\left(C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n\right)\le 2d+2$. Further, as $C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n$ is a regular graph of degree 4, the application of Lemma 1 to the preceding statement shows that ${\lambda }_1^d\left(C_m{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_n\right)=2d+2$, if $1\le d\le 4$.

□

Example 2.

The presented scheme is illustrated in Figure 2, where an $L(2,1)$-labeling of $P_9\square P_7$ appears similar to that of $C_9{\square }^{{\sigma }_{\mathsf{\ell }}}{C}_7$ for $\mathsf{\ell }=1,3,4,6$.

5. Conclusions

The frequency assignment problem for wireless networks is that networks need to assign a channel to each radio transmitter so that close transmitters receive these channels to avoid interference. This situation can be modeled by a graph whose vertices are the radio transmitters, where the adjacency indicates possible interference. Motivated by this problem, I studied the ${\lambda }_1^d$-number of the direct and Cartesian graph bundles cycles over cycles. I demonstrated that the upper bound of $L(d,1)$-labeling of these graph bundles is $2d+2$ if certain conditions are imposed on the lengths of the cycles and on the cyclic ℓ-shifts ${\sigma }_{\mathsf{\ell }}$. Is optimality achievable? I showed that the ${\mathit{\lambda }}_1^d$-number of these graphs is $2d+2$ if the condition $1\le d\le 4$ is also satisfied.