L(h, k)-Labeling of Circulant Graphs

Sarbari Mitra, Soumya Bhoumik

Department of Mathematics, Fort Hays State University, Hays, KS, USA.

DOI: 10.4236/jamp.2023.115094                

Abstract

An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ_h^k  ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z_n. In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n.

Keywords

Channel Assignment, L(h, k)-Labeling, Circulants, Connection Set

1. Introduction

1.1. Background

In the past few decades, rigorous works have been carried out in the area of $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -Labeling. There is a note to the reader that while defining the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -Labeling, some authors prefer to use 2 length path, instead of using the concept of distance 2 (although in this paper we have use the concept of dist). The reason behind this is the situation when $h<k$ . In this case, the vertices of any triangle in the graph must be colored by three colors at least $\max \mathrm{<mo>\; \{\; </mo>}h\mathrm{,}k\mathrm{<mo>\; \}\; </mo>}$ apart from each other. Note that it works fine whenever $h\ge k$ . Griggs and Yeh considered the special case $h=2$ and $k=1$ , and proposed the conjecture [1] ${\lambda }_2^1\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le {\Delta }^2$ , where $\Delta \ge 2$ is the maximum degree of the graph G, which has been verified for various families of graphs [2] [3] [4] [5] over the past decade. It was established that finding the exact value of the ${\lambda }_2^1$ is NP-hard even for families of simpler graphs like planar graphs, bipartite graphs and chordal graphs [1] [6]. Obviously no one expects $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -Labeling problems ( $h>k\ge 1$ ) is any easier than $L\mathrm{<mo\; stretchy="false">\; (\; </mo>2,1\; <mo\; stretchy="false">\; )\; </mo>}$ .

In terms of bounds of the span for $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling, ${\lambda }_h^k\ge h+\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Delta +\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}k$ [7]. The structure of the graphs with ${\lambda }_h^k=h+\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Delta +\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}k$ for $\Delta \ge 1$ is studied in [7], and they are called ${\lambda }_h^k$ -minimal graph. Also another interesting fact for r-regular graph G is that it can be easily observed that ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge h+\mathrm{<mo\; stretchy="false">\; (\; </mo>2}r-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}k$ if $h\ge rk$ , and ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge h+\mathrm{<mo\; stretchy="false">\; (\; </mo>}r-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}k$ otherwise. In 2008 Havet, Reed and Sereni [8] proved Griggs and Yeh’s conjecture for sufficiently large values of $\Delta$ ( $\Delta \ge {10}^{69}$ ) for any h and k. They also provided the upper bound of ${\lambda }_h^1\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ to be ${\delta }^2+c\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for any $\Delta$ , where $c\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ is a constant, depending on the parameter h. For a detailed survey on $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -Labeling readers may be read [6].

In this paper, we have considered the Cayley graphs of Cyclic groups. $L\mathrm{<mo\; stretchy="false">\; (\; </mo>2,1\; <mo\; stretchy="false">\; )\; </mo>}$ labeling of Cayley graphs were investigated by Zhao [9] [10] on abelian groups, by Bahls [11] on more general groups. Recently Li et al. [12] investigated the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>2,1\; <mo\; stretchy="false">\; )\; </mo>}$ labeling of cubic Cayley graphs on dihedral groups. We observed that compared to other families of graphs, $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling of Cayley graphs has not been explored at all. To start with, we first narrow down our focus into circulants, since it would surely give us a flavor of the general situation for all Cayley graphs. Connected circulants with smallest connection set are nothing but cycles, bounds of $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,1\; <mo\; stretchy="false">\; )\; </mo>}$ -labeling for which are already been established [13]. It is comparatively more challenging to find the bounds when there are more edges. Hence we emphasize on circulants with large connection sets. We obtained the bounds for the spans of the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>2,1\; <mo\; stretchy="false">\; )\; </mo>}$ [14] and $L\mathrm{<mo\; stretchy="false">\; (\; </mo>3,1\; <mo\; stretchy="false">\; )\; </mo>}$ [15] labeling of circulants previously and we wish to further extend our observation. In this paper, we aim to examine the upper bounds for the span of $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ labeling of circulants and hence extend our work to propose to bounds for $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ labeling of the Cayley graphs in general, in future.

1.2. Preliminaries

In this section, we shall discuss basic definitions from the graph labeling as well as the Cayley Graphs.

Definition 1.1. $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling of a simple connected and undirected graph $\Gamma =\mathrm{<mo\; stretchy="false">\; (\; </mo>}V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>,}E\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ is an assignment $f\mathrm{<mo>\; :\; </mo>}V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\to {\mathbb{Z}}^{+}\cup \mathrm{<mo>\; \{\; </mo>0\; <mo>\; \}\; </mo>}$ such that for any pair of vertices $x\mathrm{,}y\in V\mathrm{<mo\; stretchy="false">\; (\; \Gamma \; )\; </mo>}$

$\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}x\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}y\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge (\begin{array}{ll}h\mathrm{,}\hfill & \text{if}xy\in E\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\hfill \\ k\mathrm{,}\hfill & \text{if}d\mathrm{<mo\; stretchy="false">\; (\; </mo>}x\mathrm{,}y\mathrm{<mo\; stretchy="false">\; )\; </mo>}=2\hfill \end{array}$

Definition 1.2. Let ${\mathbb{Z}}_n$ be a cyclic group and $S\subset {\mathbb{Z}}_n$ such that $\mathrm{<mo>\; \{\; </mo>0\; <mo>\; \}\; </mo>}\notin S$ . Define a graph $\Gamma =\Gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{\mathbb{Z}}_n\mathrm{,}S\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ by $V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}={\mathbb{Z}}_n$ and $E\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}=\mathrm{<mo>\; \{\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}u\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; :\; </mo>}v-u\in S\mathrm{<mo>\; \}\; </mo>}$ . Such a graph is a circulant graph of order n with connection set S. Note that $S=S^{-1}=\mathrm{<mo>\; \{\; </mo>}-s\mathrm{<mo>\; :\; </mo>}s\in S\mathrm{<mo>\; \}\; </mo>}$ for circulant graphs.

We start our work with “large” connection sets, and finally generalize the results for any connection set, S. Note that $\left|S\right|\le n-1$ , since $\mathrm{<mo>\; \{\; </mo>0\; <mo>\; \}\; </mo>}\notin S$ (no loops). Also when $\left|S\right|=n-1$ , then $\Gamma$ becomes a complete graph ( $K_n$ ), one can easily verify that ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}{K}_n\mathrm{<mo\; stretchy="false">\; )\; </mo>}=h\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}$ .

The rest of paper is structured as follows. Section (2) consists of the main results in the form of theorems and supporting lemmas describing the upper bounds of the span for the circulants with the connection sets with cardinalities $n-\mathrm{2,}n-3$ and $n-4$ respectively. In Section (3) we provide the algorithms for assignment of vertex labels to generalized cases followed by providing the lower bounds as well.

2. Main Results

First we define the notations that we will be using throughout this paper. For the vertices $i\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $a\in V(\Gamma )\backslash S$ (without loss of generality we will assume that $a\in {\mathbb{Z}}_{n\mathrm{<mo>\; /\; </mo>2}}\backslash S$ ), let $d=\gcd (n,a)$ . Also let ${\mathcal{l}}_i=i\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; <mi>\; \%\; </mi>\; <mtext>\; \hspace{0.17em}\; </mtext>}d$ , and we can rewrite it as ${\mathcal{l}}_i=q_i\mathrm{<mo\; stretchy="false">\; (\; </mo>}d\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; )\; </mo>}+r_i$ (when d is even), where $q_i\mathrm{,}{r}_i\in \mathbb{Z}$ , for each $i\in {\mathbb{Z}}_n$ . It can be observed that $q_i\in \mathrm{<mo>\; \{\; </mo>0,1\; <mo>\; \}\; </mo>}$ , and $r_i\in \mathrm{<mo>\; \{\; </mo>0,1,}\cdots \mathrm{,}d\mathrm{<mo>\; /\; </mo>2}-\mathrm{1\; <mo>\; \}\; </mo>}$ . For any $a\in V(\Gamma )\backslash S$ , let $p_i$ and $p^{\prime }$ are the smallest non-negative integers for which $a\mathrm{<mo>\; |\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n{p}_i+\mathrm{<mo\; stretchy="false">\; (\; </mo>}i-{\mathcal{l}}_i\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ and $a\mathrm{<mo>\; |\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n{p}^{\prime }+n\mathrm{<mo>\; /\; </mo>2}-a-d\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; )\; </mo>}$ respectively. Note that $p^{\prime }$ is constant for fixed a, and n.

Theorem 2.1. If $\left|S\right|=n-2$ then ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le n\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h$ .

Proof. We begin this proof with the observation that n needs to be even. Since $\mathrm{<mo>\; \{\; </mo>0\; <mo>\; \}\; </mo>}\notin S$ , $\left|S\right|=n-2$ is only possible when $n\mathrm{<mo>\; /\; </mo>2}\notin S$ . Now we introduce the function $f\mathrm{<mo>\; :\; </mo>}V\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}\to \mathbb{Z}$ .

$f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}=(\begin{array}{ll}\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}i\mathrm{,}\hfill & \text{if}i\in \mathrm{<mo>\; \{\; </mo>0,1,}\cdots \mathrm{,}\frac{n}{2}-\mathrm{1\; <mo>\; \}\; </mo>}\hfill \\ \mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}i-n\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{,}\hfill & \text{if}i\in \mathrm{<mo>\; \{\; </mo>}\frac{n}{2}\mathrm{,}\frac{n}{2}+\mathrm{1,}\cdots \mathrm{,}n-\mathrm{1\; <mo>\; \}\; </mo>}\hfill \end{array}$

Our claim is $f\cong L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , i.e. $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge h$ if $j-i\in S$ and $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge k$ if $\text{dist}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=2$ . Let us first consider that $i\mathrm{,}j\in \mathrm{<mo>\; \{\; </mo>0,1,}\cdots \mathrm{,}\frac{n}{2}-\mathrm{1\; <mo>\; \}\; </mo>}$ , then $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|=\left|\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}i-j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|>h$ , for $i\ne j$ which clearly satisfies the requirement. Similarly the assumption $i\mathrm{,}j\in \mathrm{<mo>\; \{\; </mo>}\frac{n}{2}\mathrm{,}\frac{n}{2}+\mathrm{1,}\cdots \mathrm{,}n-\mathrm{1\; <mo>\; \}\; </mo>}$ also meets the requirement.

Now it remains to consider the case when $i\in \mathrm{<mo>\; \{\; </mo>0,1,}\cdots \mathrm{,}\frac{n}{2}-\mathrm{1\; <mo>\; \}\; </mo>}$ , and $j\in \mathrm{<mo>\; \{\; </mo>}\frac{n}{2}\mathrm{,}\frac{n}{2}+\mathrm{1,}\cdots \mathrm{,}n-\mathrm{1\; <mo>\; \}\; </mo>}$ or vice-versa. Without loss of generality we can assume the former one. In that case $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|=\left|\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>2}+i-j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-k\right|$ . As, it can be easily verified that f is injective, $\left|\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>2}+i-j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-k\right|$ is greater than k, only if $j-i=n\mathrm{<mo>\; /\; </mo>2}$ , that is, $\text{dist}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=2$ . Otherwise, for any other choice of $i\mathrm{,}j$ it is obvious that $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge h$ . Moreover, as it can be easily observed that ${\max }_{i\in {\mathbb{Z}}_n}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}=\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>2}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k$ , we get that ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le n\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h$ . ¨

Next we will consider $\left|S\right|=n-3$ , which is possible only if $\mathrm{<mo>\; \{\; </mo>0,}a\mathrm{,}n-a\mathrm{<mo>\; \}\; </mo>}\notin S$ , where a is any non-negative integer. For this specified connection set, we define the vertex labeling function f below, and prove that f provides a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling in Theorem (2.2), and Theorem (2.3). But first we need to consider the following lemma [14], which is very useful to proceed further in this paper.

Lemma 2.1. There exists a non-negative integer $p_i<a/d$ such that $a\mathrm{<mo>\; |\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n{p}_i+\mathrm{<mo\; stretchy="false">\; (\; </mo>}i-{\mathcal{l}}_i\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ for any $i\in {\mathbb{Z}}_n$ .

Now we propose the function that will assign the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,1\; <mo\; stretchy="false">\; )\; </mo>}$ -labeling to the $\Gamma =\text{Cir}\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{,}S\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , where $\left|S\right|=n-3$ . For the sake of simplicity, for any $i\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ we consider $C_i=\frac{n{p}_i+\mathrm{<mo\; stretchy="false">\; (\; </mo>}i-{\mathcal{l}}_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}}{a}$ . Note that $C_i\le \mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}$ .

$f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}=(\begin{array}{ll}s\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{C_i-b_i}{2}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_i+{\mathcal{l}}_i\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{n}{d}-1-e\mathrm{<mo\; stretchy="false">\; )\; </mo>}+ek\mathrm{<mo\; stretchy="false">\; )\; </mo>,}\hfill & \text{if}n\ne 3d\hfill \\ C_{i}k+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{\mathcal{l}}_i\mathrm{,}\hfill & \text{if}n=3d\hfill \end{array}$

where $s=(\begin{array}{ll}h\mathrm{,}\hfill & \text{if}h\ge 2k\hfill \\ 2k\mathrm{,}\hfill & \text{if}h<2k\hfill \end{array}$ , $b_i=(\begin{array}{ll}\mathrm{0,}\hfill & \text{if}{C}_i\text{is}\text{even}\hfill \\ \mathrm{1,}\hfill & \text{if}{C}_i\text{is}\text{odd}\hfill \end{array}$ , and

$e=(\begin{array}{ll}\mathrm{1,}\hfill & \text{if}n\mathrm{<mo>\; /\; </mo>}d\text{is}\text{even}\hfill \\ \mathrm{0,}\hfill & \text{if}n\mathrm{<mo>\; /\; </mo>}d\text{is}\text{odd}\hfill \end{array}$ .

First we will consider the case $n=3d$ . It can be easily observed that f is injective. Now $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=k{C}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{\mathcal{l}}_{ij}$ , where $C_{ij}=C_i-C_j$ , and ${\mathcal{l}}_{ij}={\mathcal{l}}_i-{\mathcal{l}}_j$ . Note that, as $\left|C_{ij}\right|\le \mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}=2$ if ${\mathcal{l}}_{ij}=0$ , then $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|<h$ , only when $i-j=a$ , or 2a, which is impossible. Otherwise ( ${\mathcal{l}}_{ij}\ne 0$ ), without loss of generality we may assume that ${\mathcal{l}}_{ij}>0$ . In this case, using Lemma (2.1), $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge -2k+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{\mathcal{l}}_{ij}\ge h$ . Thus we have $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge h$ if $i-j\in E\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Finally, it can be easily observed that ${\max }_{i\in {\mathbb{Z}}_n}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}k+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}=\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>}d-h$ (since $d=a$ , if $n\mathrm{<mo>\; /\; </mo>}d=3$ ). From above discussion we can derive Theorem (2.2).

Theorem 2.2. If $\left|S\right|=n-3$ , and $n=3d$ then f admits a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling on $\Gamma$ , and ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \mathrm{<mo\; stretchy="false">\; (\; </mo>}h+2k\mathrm{<mo\; stretchy="false">\; )\; </mo>}d-h$ .

Theorem 2.3. If $\left|S\right|=n-3$ , and $n\ne 3d$ then f provides a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling on $\Gamma$ . Moreover

${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le (\begin{array}{ll}sn\mathrm{<mo>\; /\; </mo>2}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}d-h\mathrm{,}\hfill & \text{if}\frac{n}{d}\text{is}\text{even}\hfill \\ s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}+h\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>,}\hfill & \text{if}\frac{n}{d}\text{is}\text{odd}\hfill \end{array}$

Proof. In this proof, we skip the part to show that $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge k$ , if $\text{dist}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=2$ , since it is easy to verify. Also without loss of generality we assume that $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}>f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Note that

$f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}{C}_{ij}-b_{ij}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_{ij}+{\mathcal{l}}_{ij}\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-1-e\mathrm{<mo\; stretchy="false">\; )\; </mo>}+ek\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ (1)

First consider the case that ${\mathcal{l}}_{ij}=0$ . Note that if $C_{ij}-b_{ij}\ge 3$ , the from Equation (1) immediately implies $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}>h$ . Now we first notice $b_{ij}=0$ , if $C_{ij}$ is even. Thus $0\le C_{ij}-b_{ij}\le 2$ , only when one of these four possibilities occurs, viz. $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{C}_{ij}\mathrm{,}{b}_{ij}\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ are either $\mathrm{<mo\; stretchy="false">\; (\; </mo>3,1\; <mo\; stretchy="false">\; )\; </mo>,\; <mo\; stretchy="false">\; (\; </mo>2,0\; <mo\; stretchy="false">\; )\; </mo>,\; <mo\; stretchy="false">\; (\; </mo>1,}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}$ , or $\mathrm{<mo\; stretchy="false">\; (\; </mo>1,1\; <mo\; stretchy="false">\; )\; </mo>}$ . The former two cases provides us $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge h$ . The latter two cases $C_{ij}=(n{p}_{ij}-(i-j))/a=1$ implies $i-j=a$ , which is a contradiction.

On the other hand if ${\mathcal{l}}_{ij}\ne 0$ , is can be easily deduced that ${\mathcal{l}}_{ij}>0$ . Hence from Equation (1), we get

$f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge \frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}{C}_{ij}+\frac{n}{d}-b_{ij}-1-e\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h+k{b}_{ij}+ek$ (2)

Now if n/d is even, then $e=1$ , and $C_{ij}=C_i-C_j\ge -\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}$ . But note that in this case $b_{ij}=-1$ . Hence Inequality (2) implies that $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge h$ . The case n/d is odd, follows similarly.

Finally it remains to verify the upper bound for ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Consider n/d is even, we get $e=1$ . Also $C_{ij}\le 0-\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}=1-n\mathrm{<mo>\; /\; </mo>}d$ . But in this case $b_i=1$ . Thus

$\begin{array}{c}\underset{i\in {\mathbb{Z}}_n}{\max }\mathrm{<mo>\; \{\; </mo>}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; \}\; </mo>}=\underset{i\in {\mathbb{Z}}_n}{\max }\mathrm{<mo>\; \{\; </mo>}s\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{C_i-b_i}{2}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_i+{\mathcal{l}}_i\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{n}{d}-1-e\mathrm{<mo\; stretchy="false">\; )\; </mo>}+ek\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; \}\; </mo>}\\ =\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{n}{d}-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}+k+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}h+\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{n}{d}-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}\end{array}$

Hence it is easy to verify that when n/d is even then ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le sn\mathrm{<mo>\; /\; </mo>2}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}d-h$ . On the other hand, it can be easily derived that ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}$ when n/d is odd. ¨

Corollary 2.2. If a is coprime to n then

${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \{\begin{array}{ll}s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>2}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\hfill & \text{if}n\text{is}\text{even}\hfill \\ s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}\hfill & \text{if}n\text{is}\text{odd}\hfill \end{array}$

The above corollary follows immediately from Theorem (2.3), hence we skip the proof. Next we consider the case when $\left|S\right|=n-4$ . First note that in this case n must be even, and the connection set S should be such that ${\mathbb{Z}}_n\backslash S=\mathrm{<mo>\; \{\; </mo>0,}a\mathrm{,}n\mathrm{<mo>\; /\; </mo>2,}n-a\mathrm{<mo>\; \}\; </mo>}$ for some $a\in {\mathbb{Z}}_n^{\mathrm{<mo>\; *\; </mo>}}$ . Without loss of generality, we assume a is the smallest integer in the set ${\mathbb{Z}}_n^{\mathrm{<mo>\; *\; </mo>}}\backslash S$ . It can be easily observed that when $n\mathrm{<mo>\; /\; </mo>}d=2m$ for $m\ge 2$ , then $n\mathrm{<mo>\; /\; </mo>2}=dm\in \langle a\rangle$ . As a consequence the vertex labeling, and hence the upper bound of ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ will be same as that of $\left|S\right|=n-3$ case. So in the rest of this section we restrict $n\mathrm{<mo>\; /\; </mo>}d$ to be odd. Let us first prove a lemma before we propose the function that assign the labeling to $\Gamma$ .

Lemma 2.3. If d does not divide n/2 then d must be even.

Proof. Let us consider the prime power decomposition of $n=2^{a_0}\cdot p_1^{a_1}\cdots p_n^{a_k}$ , where $a_0\ge 1$ . Let us also consider $d=2^{b_0}\cdot p_1^{b_1}\cdots p_n^{b_k}$ , where $b_i\le a_i$ for all $i\in \mathrm{<mo>\; \{\; </mo>0,1,}\cdots \mathrm{,}k\mathrm{<mo>\; \}\; </mo>}$ . But as $d\nmid \mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; )\; </mo>}$ , then it is clear that b has at least a prime factor that does not divide $n/2=2^{a_0-1}\cdot p_1^{a_1}\cdots p_n^{a_k}$ , which is only possible when $b_0>a_0-1\ge 0$ . Hence d is even integer. ¨

For any $i\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ let us define $F_a=\frac{n{p}^{\prime }-a+\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}}{a}$ , and ${C^{\prime }}_i=C_i+q_i\mathrm{<mo\; stretchy="false">\; (\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>1}+t_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F_a\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , where

$t_i=\{\begin{array}{ll}0\hfill & C_i\ge F_a\hfill \\ 1\hfill & C_i<F_a\hfill \end{array}$

We can easily figure out the bounds for ${C^{\prime }}_i$ , and $F_a$ , such that $0\le {C^{\prime }}_i\le 2n\mathrm{<mo>\; /\; </mo>}d-1$ for any $i\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , and $0\le F_a\le n\mathrm{<mo>\; /\; </mo>}d-2$ , as $p_i\mathrm{,}{p}^{\prime }\le a\mathrm{<mo>\; /\; </mo>}d-1$ . Now the following function will assign $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling to the graph $\Gamma$ , which we will show in the following theorem.

$F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}=(\begin{array}{ll}\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}{C^{\prime }}_i-b_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_i+r_i\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{nh}{d}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>,}\hfill & \text{if}n\ne 3d\hfill \\ k{C}_i+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{q}_i+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{r}_i\mathrm{,}\hfill & \text{if}n=3d\hfill \end{array}$

We claim that this function assigns the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling to the circulants $\Gamma$ with $\left|S\right|=n-4$ , as well as provided a bound of the ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . First we prove the claim for $n=3d$ in Theorem (2.4), and then in Theorem (2.5) we prove the same for the case $n\ne 3d$ . For our convenience, we will use the notations $C_{ij}=C_i-C_j$ , $p_{ij}=p_i-p_j$ , ${\mathcal{l}}_{ij}={\mathcal{l}}_i-{\mathcal{l}}_j$ , $q_{ij}=q_i-q_j$ and $r_{ij}=r_i-r_j$ whenever required.

Theorem 2.4. If $\left|S\right|=n-4$ (i.e., $\mathrm{<mo>\; \{\; </mo>0,}a\mathrm{,}n\mathrm{<mo>\; /\; </mo>2,}n-a\mathrm{<mo>\; \}\; </mo>}\notin S$ for any $a\in {\mathbb{Z}}_{n\mathrm{<mo>\; /\; </mo>2}}^{\mathrm{<mo>\; *\; </mo>}}$ ), and $n=3d$ then F defines a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ labeling on $\Gamma$ . Moreover, ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h$ .

Proof. Without loss of generality, we assume that $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Now, $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}=k{C}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{q}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{r}_{ij}$ . Based on our assumption we clearly have $r_{ij}\ge 0$ . If $r_{ij}>0$ , then we have $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge k{C}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{q}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+h+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{r}_{ij}\ge -2k-\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+h+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>}{r}_{ij}>h$ . On the other hand if $r_{ij}=0$ , then either $q_{ij}=0$ , or $q_{ij}=1$ . Now if $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}<h$ then $q_{ij}=0$ implies that $C_{ij}=\mathrm{<mo\; stretchy="false">\; (\; </mo>}n{p}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}i-j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>}a=1$ , or 2, which is only possible either $i-j=a$ , or 2a. Finally when $q_{ij}=1$ , then $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}<h$ implies $C_{ij}+h+1<h$ , which is only possible when $C_{ij}=-2$ . Hence we get $(n{p}_{ij}+(i-j)-{\mathcal{l}}_{ij})/a=-2$ , which simplifies to $j-i=2a-{\mathcal{l}}_{ij}=2a-a/2=n/2$ , which is absurd.

Finally it is easy to verify that ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le k\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}d\mathrm{<mo>\; /\; </mo>2}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; =\; </mo>}d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s+3k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h$ . ¨

Theorem 2.5. If $\left|S\right|=n-4$ (i.e., $\mathrm{<mo>\; \{\; </mo>0,}a\mathrm{,}n\mathrm{<mo>\; /\; </mo>2,}n-a\mathrm{<mo>\; \}\; </mo>}\notin S$ for any $a\in {\mathbb{Z}}_{n\mathrm{<mo>\; /\; </mo>2}}^{\mathrm{<mo>\; *\; </mo>}}$ ), and $n\mathrm{<mo>\; /\; </mo>}d=2k+\mathrm{1,}k\ge 2$ then F defines a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ labeling on $\Gamma$ . Moreover, ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}+d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h\mathrm{.}$

Proof. Lemma 2.3 suggests that d can’t be odd, as $d\nmid n\mathrm{<mo>\; /\; </mo>2}$ . In this proof, we will show that $\left|F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge h$ when $\mathrm{<mo\; stretchy="false">\; (\; </mo>}ij\mathrm{<mo\; stretchy="false">\; )\; </mo>}\in E\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , i.e. $j-i\in S$ . Establishing the fact that $\left|F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge 1$ when $\text{dist}\mathrm{<mo\; stretchy="false">\; (\; </mo>}ij\mathrm{<mo\; stretchy="false">\; )\; </mo>}=2$ is very similar, and hence omitted here.

$F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}=s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}{C^{\prime }}_{ij}-b_{ij}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_{ij}+r_{ij}\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ (3)

In this proof, without loss of generality, we assume that $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}>F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , which immediately implies that $r_{ij}\ge 0$ . First we consider that $r_{ij}>0$ , which gives us,

$\begin{array}{c}F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge r_{ij}\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}-s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}{C^{\prime }}_j-b_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-k{b}_j\\ \ge \mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}-s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}{C}_j+q_j\mathrm{<mo\; stretchy="false">\; (\; </mo>\; <mo\; stretchy="false">\; (\; </mo>1}+t_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-F_a\mathrm{<mo\; stretchy="false">\; )\; </mo>}-b_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-k{b}_j\\ \ge h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k-s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-1+n\mathrm{<mo>\; /\; </mo>}d-b_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-k{b}_j\\ =h+\mathrm{<mo\; stretchy="false">\; (\; </mo>}s\mathrm{<mo>\; /\; </mo>2}-k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}{b}_j-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\end{array}$

Note that in this case we have assumed ${C^{\prime }}_j=2n/d-1$ , which implies $b_j=1$ , thus we get $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge h$ . Now we consider the case $r_{ij}=0$ simplifies Equation (3) to

$F(j)-F(i)=h/2({C^{\prime }}_{ij}-b_{ij})+b_{ij}$

Now it can be easily observed that in order to have $\left|F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}-F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|<h$ , either ${C^{\prime }}_{ij}-b_{ij}<2$ , or ${C^{\prime }}_{ij}-b_{ij}=2$ , and $b_{ij}=-1$ . Note that the latter case implies ${C^{\prime }}_{ij}=1$ immediately. From the former case, it can be easily deduced that ${C^{\prime }}_{ij}-b_{ij}=0$ (as ${C^{\prime }}_k-b_k$ is even for all k), and hence $b_{ij}=1$ (as we have already assumed that $F\mathrm{<mo\; stretchy="false">\; (\; </mo>}j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; >\; </mo>}F\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ ), hence we have same conclusion that ${C^{\prime }}_{ij}=1$ . Now the following claim proves the rest.

Claim: ${C^{\prime }}_{ij}=1$ only when $i-j\in S^c$ .

First we simplify ${C^{\prime }}_{ij}=1$ into,

$C_{ij}+n/d(q_i(1+t_i)-q_j(1+t_j))-q_{ij}{F}_a=1$ (4)

Once again we use our assumption $F(i)>F(j)$ to conclude that $q_i\ge q_j$ . Now if $q_i=q_j=0$ , Equation (4) implies that $C_{ij}=(n{p}_{ij}+(i-j))/a=1$ ( ${\mathcal{l}}_{ij}=0$ ), which is only possible when $i-j=a$ . Now if $q_i=q_j=1$ , Equation (4) simplifies to $(n{p}_{ij}+(i-j))/a+n/d=1$ , which implies $i-j=a-(a/d-p_{ij})n$ . This is again possible when either $i-j=a$ or $j-i=n-a$ .

Finally it remains to consider that case $q_i>q_j$ . Obviously in this case $q_i=1$ , and $q_j=0$ . This gives us (from Equation (4))

$C_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>1}+t_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-F_a=1$ (5)

First of all we note that $C_i\ge F_a$ , because otherwise $t_i=1$ , which implies $(C_i-F_a+n/d)+(n/d-C_j)>1$ , a contradiction. Thus $C_i\ge F_a$ implies $t_i=0$ , which provides us $\mathrm{<mo\; stretchy="false">\; (\; </mo>}n{p}_{ij}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}i-j\mathrm{<mo\; stretchy="false">\; )\; </mo>}-{\mathcal{l}}_{ij}-n{p}^{\prime }+a-n\mathrm{<mo>\; /\; </mo>2}+d\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; )\; </mo>}=1-n\mathrm{<mo>\; /\; </mo>}d$ Using the fact that in this case $\mathcal{l}=d/2$ , and after some simplification, we finally arrive at $i-j=n\mathrm{<mo\; stretchy="false">\; (\; </mo>}{p}^{\prime }-p_{ij}-a\mathrm{<mo>\; /\; </mo>}d\mathrm{<mo\; stretchy="false">\; )\; </mo>}+n\mathrm{<mo>\; /\; </mo>2}$ . Thus the conclusion we can draw here is $i-j=n\mathrm{<mo>\; /\; </mo>2}$ . ¨

Finally (it remains to verify that) if $n\ne 3d$ , we have,

$\begin{array}{c}{\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}=\frac{s}{2}\mathrm{<mo\; stretchy="false">\; (\; </mo>}{C^{\prime }}_i-b_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}+k{b}_i+r_i\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}\frac{nh}{d}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; \}\; </mo>}\\ \le s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>\; <mo\; stretchy="false">\; (\; </mo>2}n\mathrm{<mo>\; /\; </mo>}d-1-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d\mathrm{<mo>\; /\; </mo>2}-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}h+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}\\ =s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}+d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}-h\end{array}$ ¨

3. Generalization

In this section we will generalize the result for any circulant, i.e. we provide a way to assign the vertex labeling that satisfies the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ criteria (Algorithm (1) and (2)). Later in Theorem (3.1), we investigate the condition on the connection set S in order to have the exact value of ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ .

Algorithm (1) and Algorithm (2) together provide us the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling for circulants with any connection set S, such that $S^c={\mathbb{Z}}_n\backslash S=\mathrm{<mo>\; \{\; </mo>}{a}_1\mathrm{,}{a}_2\mathrm{,}\cdots ,a_k\mathrm{,}n-a_k\mathrm{,}n-a_{k-1}\mathrm{,}\cdots \mathrm{,}n-a_2\mathrm{,}n-a_1\mathrm{<mo>\; \}\; </mo>}$ and immediately we can figure out the upper bound for ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for those circulants. Here we denote $d_{a_1{a}_2\cdots a_k}=\gcd (a_1,a_2,\cdots ,a_k)$ . First, Algorithm (1) takes the connection set S as input, immediately calculate the non-connection set $S^c=\mathrm{<mo>\; \{\; </mo>}{b}_1\mathrm{,}{b}_2\mathrm{,}\cdots \mathrm{,}{b}_{m^{\prime }}\mathrm{<mo>\; \}\; </mo>}$ , and then finds the minimal non-connection set $S^{\prime }=\mathrm{<mo>\; \{\; </mo>}{a}_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_m\mathrm{<mo>\; \}\; </mo>}\subseteq S^c$ ; where $m\le \mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\left|S\right|\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}$ , and $\mathrm{<mo>\; \{\; </mo>}{a}_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_m\mathrm{<mo>\; \}\; </mo>}$ is the smallest set such that $\gcd (a_1,a_2,\cdots ,a_m)=\gcd (b_1,b_2,\cdots ,b_{m^{\prime }})$ . Next, Algorithm (2) assigns the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling to the circulant graph of order n. First of all, note that for any $a\in {\mathbb{Z}}_n$ , the circulant graph $\Gamma =\Gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{Z}_n\mathrm{,\; <mo>\; \{\; </mo>}a\mathrm{<mo>\; \}\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ is just $d=\gcd (n,a)$ many disconnected cycles is of order n/d. Also observe that the groups of integers modulo n; $\langle a_1\rangle$ is a cyclic subgroup of ${\mathbb{Z}}_n$ with order $n\mathrm{<mo>\; /\; </mo>}{d}_{a_1}$ , and $\langle a_1\mathrm{,}{a}_2\rangle$ is a subgroup of $Z_n$ with order $n\mathrm{<mo>\; /\; </mo>}{d}_{a_1{a}_2}$ . It is easy to verify that $\langle a_1\rangle ⊲\langle a_1\mathrm{,}{a}_2\rangle$ , and hence $\langle a_1\mathrm{,}{a}_2\rangle \mathrm{<mo>\; /\; </mo>}\langle a_1\rangle =d_{a_1}\mathrm{<mo>\; /\; </mo>}{d}_{a_1{a}_2}$ . Similarly for any $t\le m$ , $\langle a_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_t\rangle \mathrm{<mo>\; /\; </mo>}\langle a_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_{t-1}\rangle =d_{a_1{a}_2\cdots a_t}\mathrm{<mo>\; /\; </mo>}{d}_{a_1{a}_2\cdots a_{t-1}}$ . According to Algorithm (2), we first label all vertices of $\mathrm{<mo>\; \{\; </mo>}{i}_1{a}_1\mathrm{<mo>\; |\; </mo>}{i}_1\in Z_{n\mathrm{<mo>\; /\; </mo>}{d}_{a_1}}\mathrm{<mo>\; \}\; </mo>}$ $\mathrm{<mo\; stretchy="false">\; (\; </mo>}\mathrm{mod}n\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ in this fashion $\mathrm{<mo>\; \{\; </mo>0,}k\mathrm{,}s\mathrm{,}s+k\mathrm{,2}s\mathrm{,}\cdots \mathrm{<mo>\; \}\; </mo>}$ (s is defined in Lemma 2.1). Once we are done with labeling $n\mathrm{<mo>\; /\; </mo>}{d}_1$ many vertices in this manner, we label $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{a}_2-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}=f\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h$ . We continue labeling the remaining vertices $a_2+i_1{a}_1$ as $\mathrm{<mo>\; \{\; </mo>}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h+k\mathrm{,}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h+s\mathrm{,}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h+s+k\mathrm{,}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-a_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h+2s\mathrm{,}\cdots \mathrm{<mo>\; \}\; </mo>}$ , for $i_1\ge 0$ . It can be easily observed that this pattern of labeling can be repeated $d_1\mathrm{<mo>\; /\; </mo>}{d}_{a_1{a}_2}$ many times. Hence after labeling $n\mathrm{<mo>\; /\; </mo>}{d}_{a_1{a}_2}$ in this fashion, we then iterate this method for $\mathrm{<mo>\; \{\; </mo>}{a}_3\mathrm{,}{a}_4\mathrm{,}\cdots \mathrm{,}{a}_m\mathrm{<mo>\; \}\; </mo>}$ . Since according to the Algorithm (2), consecutive labels are only being used in difference of $a_1\mathrm{,}{a}_2\mathrm{,}\cdots \mathrm{,}{a}_{m-1}$ or $a_m$ , any two adjacent vertices have the difference of labeling of at least 2. Hence Algorithm (2) provides a $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling to the graph $\Gamma$ .

We now have only one more result to discuss in terms of the exact value of ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ .

Theorem 3.1 Let $S^c={\mathbb{Z}}_n\backslash S=\{a_1,a_2,\cdots ,a_m\}$ , and $d=\gcd (a_1,a_2,\cdots ,a_m)$ . Then if $a_p+a_q\ne a_r(\mathrm{mod}n)$ for all $a_p\mathrm{,}{a}_q\mathrm{,}{a}_r\in S^c$ , then

${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}=\{\begin{array}{ll}ns\mathrm{<mo>\; /\; </mo>2}+d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}-h\hfill & \text{if}n\mathrm{<mo>\; /\; </mo>}d\text{is}\text{even}\hfill \\ s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\hfill & \text{if}n\mathrm{<mo>\; /\; </mo>}d\text{is}\text{odd}\mathrm{,}\text{and}\mathrm{<mo>\; |\; </mo>}{S}^c\mathrm{<mo>\; |\; </mo>}\text{is}\text{odd}\hfill \\ ns\mathrm{<mo>\; /\; </mo>2}+d\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}-h\hfill & \text{if}n\mathrm{<mo>\; /\; </mo>}d\text{is}\text{odd}\mathrm{,}\text{and}\mathrm{<mo>\; |\; </mo>}{S}^c\mathrm{<mo>\; |\; </mo>}\text{is}\text{even}\hfill \end{array}$

Proof. First we consider the case $d=1$ . Let f be a function that assigns $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling to the graph $\Gamma$ . Rearrange the set $V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ as $\mathrm{<mo>\; \{\; </mo>}{x}_0\mathrm{,}{x}_1\mathrm{,}\cdots \mathrm{,}{x}_{n-1}\mathrm{<mo>\; \}\; </mo>}$ , such that $0=f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_0\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \cdots \le f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Now let us assume that for some $k\in {\mathbb{Z}}_{n-3}$ , $f(x_{k+1})-f(x_k)$ , $f(x_{k+2})-f(x_{k+1})$ , $f(x_{k+2})-f(x_k)$ , all are less than s, which implies that $\mathrm{<mo>\; \{\; </mo>}{x}_{k+1}-x_k\mathrm{,}{x}_{k+2}-x_{k+1}\mathrm{,}{x}_{k+2}-x_k\mathrm{<mo>\; \}\; </mo>}\in S^c$ . But this leads to a contradiction to our assumption. Hence we conclude that $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{k+2}\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_k\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge s$ . Thus

$\begin{array}{c}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-3}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+s\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-5}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+2s\\ ⋮\\ \ge (\begin{array}{ll}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_0\mathrm{<mo\; stretchy="false">\; )\; </mo>}+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}\hfill & \text{if}n\text{is}\text{odd}\hfill \\ f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}\hfill & \text{if}n\text{is}\text{even}\hfill \end{array}\end{array}$

Hence if n is odd then ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}$ . On the other hand $f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge k$ , because otherwise there exist another $x^{\mathrm{<mo>\; *\; </mo>}}\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , such that $x^{\mathrm{<mo>\; *\; </mo>}}-x_0\mathrm{,}{x}^{\mathrm{<mo>\; *\; </mo>}}-x_1\mathrm{,}{x}_1-x_0\in S^c$ , which is a contradiction to our assumption. Hence if n is even then ${\lambda }_h^1\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge s\mathrm{<mo\; stretchy="false">\; (\; </mo>}n-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>2}+k$ .

Next we are going to consider the case that $d\ge 2$ . In this case, first let us define an orbit $\mathcal{O}\subseteq V\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , so that none of vertices in an orbit is connected to every other vertex in that same orbit. Thus if $x\in \mathcal{O}$ then there exist $y\in \mathcal{O}$ such that $x-y\in S^c$ . Also note that if $\mathcal{O}$ and ${\mathcal{O}}^{\mathrm{<mo>\; *\; </mo>}}$ are two orbits, then any vertex in $\mathcal{O}$ is connected to all the vertex of ${\mathcal{O}}^{\mathrm{<mo>\; *\; </mo>}}$ , and therefore $\left|f\mathrm{<mo\; stretchy="false">\; (\; </mo>}x\mathrm{<mo\; stretchy="false">\; )\; </mo>}-f\mathrm{<mo\; stretchy="false">\; (\; </mo>}y\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right|\ge h$ if $x\in \mathcal{O}$ , and $y\in {\mathcal{O}}^{\mathrm{<mo>\; *\; </mo>}}$ . Now when $S^c$ is odd, then it is clear that the maximum possible size of an orbit n/d, and there are d many of them. Thus if n/d is odd, then

$\begin{array}{c}f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-n\mathrm{<mo>\; /\; </mo>}d}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-n\mathrm{<mo>\; /\; </mo>}d-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+h\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n-2n\mathrm{<mo>\; /\; </mo>}d-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+2\cdot s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+2\cdot h\\ ⋮\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n\mathrm{<mo>\; /\; </mo>}d}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\cdot s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}\cdot h\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_{n\mathrm{<mo>\; /\; </mo>}d-1}\mathrm{<mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\cdot s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\cdot h\\ \ge f\mathrm{<mo\; stretchy="false">\; (\; </mo>}{x}_0\mathrm{<mo\; stretchy="false">\; )\; </mo>}+d\cdot s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\cdot h\\ \ge s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n-d\mathrm{<mo\; stretchy="false">\; )\; </mo>}+h\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}\end{array}$

On the other hand if $S^c$ is even, then there are d/2 orbits of maximum possible size 2n/d, since $n\mathrm{<mo>\; /\; </mo>2}\notin S$ . Hence similar to the previous computation, one can easily check ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge ns\mathrm{<mo>\; /\; </mo>2}+d\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}-h$ . Finally when n/d is even, then clearly n is even, and d is odd. In this case, $n\mathrm{<mo>\; /\; </mo>\; <mo\; stretchy="false">\; (\; </mo>2}d\mathrm{<mo\; stretchy="false">\; )\; </mo>}=m$ for some $m\in \mathbb{N}$ , which implies that $n\mathrm{<mo>\; /\; </mo>2}=md\in \langle d\rangle$ . Thus there are d orbits of maximum possible size n/d. Hence, ${\lambda }_h^k\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge d\mathrm{<mo\; stretchy="false">\; (\; </mo>}s\mathrm{<mo>\; /\; </mo>2\; <mo\; stretchy="false">\; (\; </mo>}n\mathrm{<mo>\; /\; </mo>}d-\mathrm{2\; <mo\; stretchy="false">\; )\; </mo>}+k\mathrm{<mo\; stretchy="false">\; )\; </mo>}+\mathrm{<mo\; stretchy="false">\; (\; </mo>}d-\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>}h=ns\mathrm{<mo>\; /\; </mo>2}+d\mathrm{<mo\; stretchy="false">\; (\; </mo>}h+k-s\mathrm{<mo\; stretchy="false">\; )\; </mo>}-h$ . ¨

4. Conclusion

In this paper, we have worked on the $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -Labeling of the family of circulant graphs, which is an obvious generalization of $L\mathrm{<mo\; stretchy="false">\; (\; </mo>2,1\; <mo\; stretchy="false">\; )\; </mo>}$ -Labeling. In fact, results in [14] can be easily verified from this paper, as a particular case substituting $h=2$ , and $k=1$ . Also in this paper, the obtained $L\mathrm{<mo\; stretchy="false">\; (\; </mo>}h\mathrm{,}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ -labeling is tight, as long as $h\ge k$ . In the case of $h<k$ , the tightness is no more applicable. For instance, in contrast to the Theorem 2.1, when $\left|S\right|=n-1$ , ${\lambda }_1^2\mathrm{<mo\; stretchy="false">\; (\; </mo>}\Gamma \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ is also $n-1$ . Thus, the case $h<k$ , can be investigated in future for the same family, or even for generalized Cayley Graphs.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Griggs, J. and Yeh, R.K. (1992) Labelling Graphs with a Condition at Distance Two. SIAM J. Discrete Math., 5, 586-595. https://doi.org/10.1137/0405048
[2]	Bodlaender, H.L., Kloks, T., Tan, R.B. and Leeuwen, J.V. (2004) Approximations for Colorings of Graphs. The Computer Journal, 47, 193-204. https://doi.org/10.1093/comjnl/47.2.193
[3]	Kang, J.H. (2008) L(2,1)-Labeling of Hamiltonian Graphs with Maximum Degree 3. SIAM J. Discrete Math., 22, 213-230. https://doi.org/10.1137/050632609
[4]	Liu, D. and Zhu, X. (2006) Cicular Distance Two Labeling and the λ-Number for Outerplanar Graphs. SIAM J. Discrete Math., 19, 281-291. https://doi.org/10.1137/S0895480102414296
[5]	Sakai, D. (1994) Labelling Chordal Graphs with a Condition at Distance Two. SIAM J. Discrete Math., 7, 133-140. https://doi.org/10.1137/S0895480191223178
[6]	Calamoneri, T. (2014) The L(h,k)-Labelling Problem: An Updated Survey and Annotated Bibliography. http://wwwusers.di.uniroma1.it/calamo/PDF-FILES/survey.pdf
[7]	Chang, G.J. and Lu, C. (2003) Distance-Two Labelings of Graphs. European Journal of Combinatorics, 24, 53-58. https://doi.org/10.1016/S0195-6698(02)00134-8
[8]	Havet, F., Reed, B. and Sereni, J.S. (2008) L(2,1)-Labelling of Graphs. Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, SIAM, 621-630.
[9]	Zhao, S. (2004) Channel Assignment Problem for Optical Networks Modelled by Cayley Graphs. Theoretical Computer Science, 310, 501-511. https://doi.org/10.1016/S0304-3975(03)00394-3
[10]	Zhao, S. (2006) Labeling Cayley Graphs on Abelian Groups. SIAM J. Discrete Math., 19, 985-1003. https://doi.org/10.1137/S0895480102404458
[11]	Bahls, P. (2011) Channel Assignment on Cayley Graphs. J. Graph Theory, 67, 169-177. https://doi.org/10.1002/jgt.20523
[12]	Li, X., Mak-Hau, V. and Zhou, S. (2013) The L(2,1)-Labelling Problem for Cubic Cayley Graphs on Diehedral Groups. J. Comb. Optim., 25, 716-736. https://doi.org/10.1007/s10878-012-9525-4
[13]	Georges, J.P. and Mauro, D.W. (1995) Generalized Vertex Labeling with a Condition at Distance Two. Congressus Numerantium, 109, 141-159.
[14]	Mitra, S. and Bhoumik, S. (2019) L(2,1)-Labeling of Circulant Graphs. Discussiones Mathematicae Graph Theory, 39, 143-155. https://doi.org/10.7151/dmgt.2086
[15]	Bhoumik, S. and Mitra, S. (2022) L(3,1)-Labeling of Circulant Graphs. Discrete Mathematics, Algorithms and Applications, 4, No. 1. https://doi.org/10.1142/S1793830921500932