# Lambda number of zero-divisor graphs of finite commutative rings

Annayat Ali1 and Rameez Raja2 ††,2 Department of Mathematics, National
Institute of Technology Srinagar, Jammu and Kashmir, India. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a simple graph, an
$L(2,1)$-labelling of $\mathcal{G}$ is assignment of labels from non-negative
integers to the vertices of $\mathcal{G}$ such that adjacent vertices gets
labels which at least differ by two and vertices which are at distance two
from each other get different labels. The $\lambda$-number of $\mathcal{G}$,
denoted by $\lambda(\mathcal{G})$ is the smallest positive integer $\ell$ such
that $\mathcal{G}$ has a $L(2,1)$-labelling with all the labels are members of
the set $\\{0,1,\cdots,\ell\\}$. The zero-divisor graph denoted by
$\Gamma(R)$, of a finite commutative ring $R$ with unity is a simple graph
with vertices as non-zero zero divisors of $R$. Two vertices $u$ and $v$ are
adjacent in $\Gamma(R)$ if and only if $uv=0$ in $R$. In this paper, we
investigate $L(2,1)$-labelling in zero-divisor graphs. We study the partite
truncation, a graph operation that reduces a $n$-partite graph of higher order
to a graph of lower order. We establish the relation between $\lambda$-numbers
of two graphs. We make use of the operation partite truncation to contract the
zero-divisor graph of a reduced ring to the zero-divisor graph of a Boolean
ring. We compute the exact value of $\lambda$-numbers of zero-divisor graphs
of some classes of local and mixed rings such as
$\mathbb{Z}_{p^{n}},\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}},$ and
$\mathbb{F}_{q}\times\mathbb{Z}_{p^{n}}.$

Keywords: Zero-divisor graph, $L(2,1)$-labelling, $\lambda$-number, partite
truncation.

2010 AMS Classification Code: 05E40, 13A99.

##  1 Introduction

Given a simple undirected finite graph $\mathcal{G}$ and two positive integers
$j,k$, an $L(j,k)$-labelling of $\mathcal{G}$ is a function
$f:V(\mathcal{G})\longrightarrow\mathbb{Z}_{\geq 0}$ such that
$|f(v_{1})-f(v_{2})|\geq j$, whenever $v_{1}$ is adjacent to $v_{2}$ and
$|f(v_{1})-f(v_{2})|\geq k$, whenever $v_{1}$ and $v_{2}$ are at distance two
apart. The difference between the maximum and minimum values of $f$ is called
its span denoted by $span(f)$. If $f$ is a $L(j,k)$-labelling of $\mathcal{G}$
with a minimum value say $\delta$, then the function $g$ defined on vertices
of $\mathcal{G}$ by $g(v)=f(v)-\delta$ is also an $L(j,k)$-labelling with a
minimum value $0$ and a maximum value $span(f)=span(g)$. As a result, we
assume that every $L(j,k)$-labelling has a minimum value of $0$ and the
maximum value its span. The minimum span over all $L(j,k)$-labellings of
$\mathcal{G}$ is called a $L(j,k)$-labelling number denoted by
$\lambda_{j,k}(\mathcal{G})$ and the corresponding $L(j,k)$ labelling is
called the minimal labelling. The $L(j,k)$-labelling problem has been studied
extensively for the case $j=2$ and $k=1$. The $L(2,1)$-labelling number of a
graph $\mathcal{G}$ is called its $\lambda$-number  denoted by
$\lambda(\mathcal{G})$.

The difficulty of assigning channel frequencies to transmitters without
interference motivates the study of $L(j,k)$-labelling problem of a graph.
Roberts [17] proposed the challenge of efficiently assigning radio channels to
transmitters at several sites using nonnegative integers to denote channels,
so that adjacent locations receive distinct channels and extremely close
locations receive channels that are at least at differ by two. As a result,
there would be no interference between these channels. In 1992 Griggs and Yeh
[7] formalised the concept of $L(j,k)$-labelling and demonstrated that the
$L(2,1)$-labelling problem is NP-complete for general graphs. The
$L(j,k)$-labelling problem and $L(2,1)$-labelling problem has been studied in
[6, 5, 10, 18].

On the other hand, the fundamental objective of associating a graph to an
algebraic structure is to investigate the relationship between algebraic
properties and combinatorial properties of the algebraic structures. The
graphs such as Cayley graph [4], power graph [8], zero-divisor graph [1],
group-annhilator graph [12], torsion graph [19], are some graphs emerging from
algebraic structures such as groups, rings and modules. Beck [3] introduced
the concept of an undirected zero-divisor graph $\Gamma^{\prime}(R)$ which is
called Beck’s zero-divisor graph of a commutative ring $R$. In his work, all
the elements of a ring $R$ are vertices of the graph $\Gamma^{\prime}(R)$ with
two vertices $u$ and $v$ adjacent in $\Gamma^{\prime}(R)$ if and only if
$uv=0$. Anderson and Livingston [1] also investigated the combinatorial
properties of a commutative ring $R$. They associated a graph $\Gamma(R)$ to
$R$ with vertices as elements of $Z^{*}(R)=Z(R)\setminus\\{0\\}$, that is, the
non-zero zero-divisors of $R$ with two vertices $a,b\in Z^{*}(R)$ are adjacent
in $\Gamma(R)$ if and only if $ab=0$. For more on zero-divisor graphs please
see [2, 13, 14, 15, 16].

Let $R$ be a finite commutative ring with unity. Then $R$ is said to be a
local ring if it has a unique maximal ideal. On the other hand, the Artinian
decomposition of $R=R_{1}\times\cdots\times R_{r}\times
F_{1}\times\cdots\times F_{s}$, where each $R_{i}$ is a commutative local ring
with unity, $F_{j}$ is a field. A ring $R$ is said to be a mixed ring if
either $r\geq 1$ and $s\geq 1$ or $r\geq 2$ and $s=0$. A ring $R$ is said to
be a reduced ring if $r=0$ and $s\geq 1$.

The research article is organised as follows. Section 2 presents preliminary
results and definitions related to $L(2,1)$-labelling. In Section 3, we study
partite truncation operation in graphs and as an application, we obtain the
exact value of the $\lambda$-number of zero-divisor graphs realized by some
classes of reduced rings. In Section 4, we compute $\lambda$-numbers of zero-
divisor graphs of a local ring of the form $\mathbb{Z}_{p^{n}}$ and of a mixed
ring of the form $\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}}$. In the
concluding Section 5, we determine the $\lambda$-number of the zero-divisor
graph of a mixed ring of the from $\mathbb{F}_{q}\times\mathbb{Z}_{p^{n}}$,
where $\mathbb{F}_{q}$ is a finite field of order $q$.

##  2 Preliminaries

In this section, we discuss some results related to $L(2,1)$-labelling of some
classes of graphs.

For a positive real number, $d$, an $L_{d}(2,1)$-labelling of a simple graph
$\mathcal{G}$ is a positive real valued function $f$ defined on
$V(\mathcal{G})$ such that for $u_{1},u_{2}\in
V(\mathcal{G}),|f(u_{1})-f(u_{2})|\geq 2d$, whenever $u_{1}$ is adjacent to
$u_{2}$ and $|f(u_{1})-f(u_{2})|\geq d$, whenever distance between $u_{1}$ and
$u_{2}$ is two. The $L_{d}(2,1)$-labelling number of $\mathcal{G}$ denoted by
$\lambda(\mathcal{G},d)$ is a smallest number $m$ such that $\mathcal{G}$ has
$L_{d}(2,1)$-labelling $f$ with $\max\limits_{v\in
V(\mathcal{G})}\\{f(v)\\}=m$. $L_{d}(2,1)$-labelling introduced by Griggs and
Yeh [7] is a natural generalisation of $L(2,1)$-labelling. Note that
$\lambda(\mathcal{G},1)=\lambda(\mathcal{G})$. The authors confirmed that to
determine $\lambda(\mathcal{G},d)$, it suffices to study the case for
$\lambda(\mathcal{G})$. They provided bounds on $\lambda$-number for a variety
of graphs, including trees, cycles, $3$-connected graphs and hypercubes. The
proved the following interesting results in which they obtain
$\lambda(\mathcal{G})$ in terms of graph invariants such as chromatic number
$\chi(\mathcal{G})$ and maximum degree $\Delta(\mathcal{G})$.

######  Theorem 1 ([7], Theorem 4.1).

If $\mathcal{G}$ is a graph with $n$ vertices, then $\lambda(\mathcal{G})\leq
n+\chi(\mathcal{G})-2$.

######  Theorem 2 ([7], Theorem 6.2).

For any graph $\mathcal{G}$,
$\lambda(\mathcal{G})\leq\Delta^{2}(\mathcal{G})+2\Delta(\mathcal{G})$.

The authors in [5] introduced the notion of holes, multiplicities and gaps of
an $L(2,1)$-labelling. Let $f$ be a $L(2,1)$-labelling of $\mathcal{G}$, and
given positive integer $h$, $0<h<span(f)$, let $f_{h}=\\{v\in
V(\mathcal{G}):f(v)=h\\}$. If $f_{h}$ is empty, then $h$ is called a hole of
$f$ and if $|f_{h}|\geq 2$, then $h$ is called multiplicity of $f$. $h$ is
called a gap of $f$ if $h$ is a hole with $|f_{h-1}|=|f_{h+1}|=1$ and
$(v^{h-1}v^{h+1})\in E(\mathcal{G})$, where $f(v^{h-1})=h-1$ and
$f(v^{h+1})=h+1$. $H(f),M(f)$ and $G(f)$ represents collection of holes,
multiplicities, and gaps of $f$, respectively. Let $h(f)$ and $g(f)$ denote
cardinalities of $H(f)$ and $G(f)$. The function $f$ is called a minimal
$L(2,1)$-labelling of $\mathcal{G}$ if it has minimum number of holes over the
set $L_{(2,1)}(\mathcal{G})$, where $L_{(2,1)}(\mathcal{G})$ denotes the set
of all $L(2,1)$-labellings of $\mathcal{G}$. The graph invariant called as
path covering number is the least number of vertex-disjoint paths required to
cover vertices of the graph. The relationship between $\lambda(\mathcal{G})$
and path covering number $c(\mathcal{G})$ of a graph $\mathcal{G}$ proved in
[5] is given as follows.

######  Lemma 3 ([5], Lemma 2.2).

Let $f$ be a minimal $L(2,1)$-labelling of $\mathcal{G}$. If $h$ is a hole of
$f$, then $|f_{h-1}|=|f_{h+1}|>0$. Furthermore, if $|f_{h-1}|=|f_{h+1}=1$,
then $h$ is a gap.

######  Lemma 4 ([5], Lemma 2.3).

If $f$ is a minimum $L(2,1)$-labelling of $\mathcal{G}$, then $G(f)$ is empty
or $M(f)$ is empty.

######  Theorem 5 ([5], Theorem 1.1).

If $\mathcal{G}$ is a simple graph of order n, then
(i) $\lambda(\mathcal{G})\leq n-1$ if and only if $c(\mathcal{G}^{c})=1$.
(ii) Let $r$ be an integer $r\geq 2$, then $\lambda(\mathcal{G})=n+r-2$ if and
only if $c(\mathcal{G}^{c})=r$.

A clique of a graph $\mathcal{G}$ is a subset of $V(\mathcal{G})$ such that
any two distinct vertices of this subset are adjacent in $\mathcal{G}$. The
maximum cardinality of a clique in $\mathcal{G}$ is known as its clique
number, which is denoted by $\omega(\mathcal{G})$ whereas an independent set
of a graph $\mathcal{G}$ is a subset of $V(\mathcal{G})$ such that no two
vertices in the subset are adjacent. The maximum cardinality of an independent
subset in $\mathcal{G}$ is called its independence number denoted by
$\alpha(\mathcal{G})$. The authors in [11] investigated the relationships
between $\lambda$-number and clique number and also between $\lambda$-number
and independence number of $\mathcal{G}$. They obtained some interesting
results which are presented below.

######  Theorem 6 ([11], Proposition 4.1).

Let $C$ be a clique of a graph $\mathcal{G}$ such that
$|C|=\omega(\mathcal{G})$. Then $\lambda(\mathcal{G})=2\omega(\mathcal{G})-2$
if there exists partitions

$\\{A_{1},A_{2},\cdots,A_{s}\\}~{}\mbox{and}~{}\\{C_{1},C_{2},\cdots,C_{s},C_{s+1}\\}$

of $V(\mathcal{G})\setminus C$, respectively, satsfying the following
conditions for each $i\in\\{1,2,\cdots,s\\}$

  1. 1.

$|A_{i}|\leq|C_{i}|-1$

  2. 2.

Every vertex in $A_{i}$ and every vertex $|C_{i}$ are non adjacent in
$\mathcal{G}$.

######  Theorem 7 ([11], Proposition 2.4).

If $\mathcal{G}$ is a graph of order $n$ then, $\lambda(\mathcal{G})\leq
2n-\alpha(\mathcal{G})-1$.

The Power Graph $\Gamma_{G}$ [CGS, 8] of a finite group $G$ is the simple
graph with vertex set $G$ and two vertices are adjacent in $\Gamma_{G}$ if and
only if one is the power of another in $G$. The exact value of
$\lambda$-number of power graphs of Dihedral group $D_{2n}$,
$\mathcal{P}$-group, and Generalised Quaternion group $Q_{4n}$ was computed in
[11]. For some certain classes of groups of order $n$, they obtained an upper
bound related to $\lambda$-number of a power graph.

######  Theorem 8 ([11], Theorem 4.1).

If $G$ is a group of order $n$ and $n$ is not a prime power, then
$\lambda(\Gamma_{G})\leq 2n-4$, The bound is achieved if and only if $G$ is
isomorphic to $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ or $\mathbb{Z}_{2q}$, where
$q$ is a prime greater than $2$.

Moreover, the $L(j,k)$-labelling of Cayley graphs has been studied in [20] and
Kelarev, Ras, and Zhou [9] revealed a relationship between a semigroup
structure and the minimum distance labelling spans of its Cayley graph.

##  3 Partite Truncation of a Graph

In this section, we study a graph operation called as partite truncation of a
graph. This operation allows us to reduce a graph with a significantly larger
order to a graph with relatively small order. As an application, we determine
$\lambda$-number of a complete $n$-partite graph.

######  Definition 9.

Let $\mathcal{G}$ be an $n$-partite graph with partite sets as
$V_{1},V_{2},\cdots,V_{n}$. We define partite truncated graph
$\hat{\mathcal{G}}$ of $\mathcal{G}$ with vertices $v_{1},v_{2},\cdots,v_{n}$
where $v_{i}$ corresponds to the whole partite set $V_{i}$, $1\leq i\leq n$
and two distinct vertices $v_{i}$ and $v_{j}$ are adjacent in
$\hat{\mathcal{G}}$ if and only if there is a vertex in $V_{i}$ adjacent to
some vertex in $V_{j}$.

Thus in partite truncation of a $n$-partite graph, each partite set is
truncated to one vertex, and edges connecting (if any) two partite sets are
truncated to a single edge. It is clear from the definition that if
$\mathcal{G}$ is connected, so is $\hat{\mathcal{G}}$ and if there is a path
between two partite sets $V_{i}$ and $V_{j}$ of $\mathcal{G}$, then there must
be a path between the two corresponding vertices $v_{i}$ and $v_{j}$ in
$\hat{\mathcal{G}}$. If $diam(\mathcal{G})=1$, then
$\mathcal{G}\cong\mathcal{K}_{n}\cong\hat{\mathcal{G}}$. Also, if the
cardinality of each partite set of $\mathcal{G}$ is equal to one, then
$\mathcal{G}\cong\hat{\mathcal{G}}$. We consider $n$-partite graphs
$\mathcal{G}$ for which $diam(\mathcal{G})>1$ and there is at least one
partite set $\mathcal{V}$ in $\mathcal{G}$ with cardinality greater than one.

Let $\bar{\mathcal{G}}$ denote the $n$-partite graph with the property that
the bipartite subgraph induced by any two distinct partite sets $V_{i}$ and
$V_{j}$ is either complete or empty and let $\hat{\bar{\mathcal{G}}}$ be its
partite truncation.

The subsequent result is about the exploration of diameters of graphs
$\bar{\mathcal{G}}$ and $\hat{\bar{\mathcal{G}}}$.

######  Lemma 10.

Let $\hat{\bar{\mathcal{G}}}$ be the partite truncation of
$\bar{\mathcal{G}}$. Then

$diam(\hat{\bar{\mathcal{G}}})\begin{cases}\leq diam(\bar{\mathcal{G}}),\text{
if }diam(\bar{\mathcal{G}})=2,\\\ =diam(\bar{\mathcal{G}}),\text{ if
}diam(\bar{\mathcal{G}})\geq 3.\end{cases}$

###### Proof.

We consider the following cases.
Case - I : $diam(\bar{\mathcal{G}})=2$,
since for any graph $\mathcal{G}$,
$diam(\bar{\mathcal{G}})=\max\limits_{u,v\in
V(\bar{\mathcal{G}})}\\{d(u,v)\\}$, therefore, for some $u,w\in
V(\bar{\mathcal{G}})$,

$d(u,w)=\max\limits_{x,y\in
V(\bar{\mathcal{G}})}\\{d(x,y)\\}=diam(\bar{\mathcal{G}})=2$

. If $u,w$ are in two different partite sets $\mathcal{V},\mathcal{W}$ of
$\bar{\mathcal{G}}$, then

$d(\hat{v},\hat{w})=\max\limits_{\hat{x},\hat{y}\in
V(\hat{\bar{\mathcal{G}}})}\\{d(\hat{x},\hat{y})\\}=diam(\hat{\bar{\mathcal{G}}})=2,$

where $\hat{v},\hat{w}$ are vertices of the graph $\hat{\bar{\mathcal{G}}}$
corresponding to partite sets $\mathcal{V}$ and $\mathcal{W}$ of
$\bar{\mathcal{G}}$. However if $u,w$ are in the same partite set say
$\mathcal{U}$ of $\bar{\mathcal{G}}$ and are unique in the sense that there
are no other two vertices in $\bar{\mathcal{G}}$ lying in two different
partite sets with the same property, then $diam(\hat{\bar{\mathcal{G}}})=1$.
Consequently, $diam(\hat{\bar{\mathcal{G}}})\leq 2=diam(\bar{\mathcal{G}})$
Case - II : $diam(\bar{\mathcal{G}})\geq 3$.
Suppose $diam(\bar{\mathcal{G}})=k\geq 3$. Then there must exist two distinct
vertices $u,w\in V(\bar{\mathcal{G}})$ lying in two different partite sets say
$\mathcal{V}$ and $\mathcal{W}$ of $\bar{\mathcal{G}}$ such that

$\displaystyle d(u,w)$ $\displaystyle=$ $\displaystyle\max\limits_{x,y\in
V(\bar{\mathcal{G}})}\\{d(x,y)\\}$ $\displaystyle=$ $\displaystyle k.$

Therefore,

$\displaystyle d(\hat{v},\hat{w})$ $\displaystyle=$
$\displaystyle\max\limits_{\hat{x},\hat{y}\in
V(\hat{\bar{\mathcal{G}}})}\\{d(\hat{x},\hat{y})\\}$ $\displaystyle=$
$\displaystyle diam(\hat{\bar{\mathcal{G}}})=k,$

where $\hat{v},\hat{w}$ are vertices of $\hat{\bar{\mathcal{G}}}$
corresponding to the partite sets $\mathcal{V},\mathcal{W}$ of
$\bar{\mathcal{G}}$ respectively. Thus,
$diam(\hat{\bar{\mathcal{G}}})=diam(\bar{\mathcal{G}})$.
∎

Let $\hat{\bar{\mathcal{G}}}$ be the partite truncation of the $n$-partite
graph $\bar{\mathcal{G}}$ with $diam(\bar{\mathcal{G}})\geq 3$. Suppose
$\lambda(\hat{\bar{\mathcal{G}}})=k$ with a corresponding minimal labelling
$\mathfrak{f}$. Define,

$\displaystyle\mathcal{F}$ $\displaystyle=$
$\displaystyle\\{\mathfrak{f}(v):v\in V(\hat{\bar{\mathcal{G}}}\\}$
$\displaystyle=$
$\displaystyle\\{i_{0}^{s_{0}},i_{1}^{s_{1}},i_{2}^{s_{2}},\cdots,i_{m}^{s_{m}}\\},$

where $0=i_{0}<i_{1}<\cdots<i_{m}=k$ and $s_{j}$ denotes the multiplicities of
$i_{j},0\leq j\leq m$. For each $j$ consider the following subset of vertices
of $\hat{\bar{\mathcal{G}}}$,

$\displaystyle\mathcal{W}_{j}=\\{v_{j_{1}},v_{j_{2}},\cdots,v_{j_{s_{j}}}\\}=\mathfrak{f}^{-1}(i_{j}).$

For each $v_{j_{l}}\in\mathcal{W}_{j},1\leq l\leq s_{j}$, let $V_{j_{l}}$ be
its corresponding partite set of $\bar{\mathcal{G}}$. We define the set
$\mathcal{C}$, a collection of all partite sets of $\bar{\mathcal{G}}$, that
is,

$\mathcal{C}=\\{V_{0},V_{1},V_{2},\cdots V_{m}\\},$

where $|V_{j}|=\max\limits_{1\leq l\leq s_{j}}\\{|V_{j_{l}}|\\}$.

Now, we prove an important result related to $\lambda$-number of graphs
$\bar{\mathcal{G}}$ and $\hat{\bar{\mathcal{G}}}$, given the $\lambda$-number
of a partite truncation $\hat{\bar{\mathcal{G}}}$, we determine the
$\lambda$-number of $\bar{\mathcal{G}}$. This result also provides an
algorithm for finding a minimal $L(2,1)$-labelling of $\bar{\mathcal{G}}$
given the minimal $L(2,1)$-labelling of $\hat{\bar{\mathcal{G}}}$.

######  Theorem 11.

If $\bar{\mathcal{G}}$ is a n-partite graph and $\hat{\bar{\mathcal{G}}}$ is
its partite truncation with $\lambda(\hat{\bar{\mathcal{G}}})=k$ then

$\lambda(\bar{\mathcal{G}})=\begin{cases}|V(\bar{\mathcal{G}})|+k-n,\text{ if
}diam(\bar{\mathcal{G}})=2,\\\
\sum\limits_{V_{j}\in\mathcal{C}}|V_{j}|+k-|\mathcal{C}|,\text{ if
}diam(\bar{\mathcal{G}})\geq 3.\end{cases}$

###### Proof.

Let $\mathfrak{f}$ be the corresponding minimal $L(2,1)$-labelling of the
graph $\hat{\bar{{\mathcal{G}}}}$. We consider the following two cases.
Case - I : $diam(\bar{\mathcal{G}})=2$
By Lemma(10), we have $diam(\hat{\bar{\mathcal{G}})}\leq 2$, therefore
$\mathfrak{f}$ is injective. For this case,

$\displaystyle\mathcal{F}$ $\displaystyle=$
$\displaystyle\\{\mathfrak{f}(v):v\in V(\hat{\bar{\mathcal{G}}})\\},$
$\displaystyle=$ $\displaystyle\\{i_{0},i_{1},i_{2},\cdots,i_{n-1}\\}.$

This implies, $|\mathcal{F}|=n$, where $0=i_{0}<i_{1}<i_{2}<\cdots<i_{n-1}=k$
Let $v_{j}$, $(0\leq j\leq n-1)$ denote the vertices in
$\hat{\bar{\mathcal{G}}}$ such that $\mathfrak{f}(v_{j})=i_{j}$.

$\Rightarrow
V(\hat{\bar{\mathcal{G}}})=\\{v_{0},v_{1},v_{2},\cdots,v_{n-1}\\}$

Let $V_{0},V_{1},V_{2},\cdots\,V_{n-1}$ with respective cardinalities
$m_{0},m_{1},m_{2},\cdots,m_{n-1}$ be the partite sets of $\bar{\mathcal{G}}$
corresponding to vertices $v_{0},v_{1},\cdots,v_{n-1}$ of
$\hat{\bar{\mathcal{G}}}$. Moreover, we denote the vertices of
$\bar{\mathcal{G}}$ lying in the partite set $V_{j}$ by $v_{l_{j}}^{j}$, where
$1\leq l_{j}\leq m_{j}$. That is,

$\displaystyle V_{0}$ $\displaystyle=$
$\displaystyle\\{v_{1}^{0},v_{2}^{0},\cdots,v_{m_{0}}^{0}\\},$
$\displaystyle\vdots$ $\displaystyle V_{n-1}$ $\displaystyle=$
$\displaystyle\\{v_{1}^{n-1},v_{2}^{n-1},\cdots,v_{m_{n}}^{n-1}\\}.$

Define $L(2,1)$-labelling
$\mathfrak{g}:V(\bar{G})\longrightarrow\mathbb{Z}_{\geq 0}$ on
$\bar{\mathcal{G}}$ by,

$\displaystyle\mathfrak{g}(v_{l_{0}}^{0})$ $\displaystyle=$ $\displaystyle
l_{0}-1,$ $\displaystyle\mathfrak{g}(v_{l_{j}}^{j})$ $\displaystyle=$
$\displaystyle l_{j}+(i_{j}-i_{(j-1)})+\max\limits_{v\in
V_{{(j-1)}}}\\{\mathfrak{g}(v)\\}-1.$
$\displaystyle\mbox{Where}~{}\max\limits_{v\in
V_{{}_{(j-1)}}}\\{\mathfrak{g}(v)\\}$ $\displaystyle=$
$\displaystyle\mathfrak{g}(v_{m_{{(j-1)}}}^{{(j-1)}})$ $\displaystyle=$
$\displaystyle m_{0}+m_{1}+\cdots+m_{{(j-1)}}+i_{(j-1)}-j$

Therefore,

$\displaystyle\mathfrak{g}(v_{m_{n-1}}^{n-1})$ $\displaystyle=$ $\displaystyle
m_{0}+m_{i_{1}}+\cdots+m_{k}-n+k$ $\displaystyle=$
$\displaystyle|V(\bar{\mathcal{G}})|+k-n$

Clearly, the map $\mathfrak{g}$ is well defined $L(2,1)$-labelling, since
$\mathfrak{f}$ is well defined $L(2,1)$-labelling, vertices of
$\bar{\mathcal{G}}$ lying in the same partite set are at distance two apart
and the distance between two vertices of $\bar{\mathcal{G}}$ lying in distinct
partite sets are same as the distance between their corresponding vertices in
$\hat{\bar{\mathcal{G}}}$. Therefore,

$\lambda(\bar{\mathcal{G}})\leq Span(\mathfrak{g})=|V(\bar{\mathcal{G}})|+k-n$

Suppose $\mathfrak{g}$ is not a minimal $L(2,1)$-labelling and let
$\mathfrak{h}$ be a minimal $L(2,1)$-labelling of $\bar{\mathcal{G}}$ with

$Span(\mathfrak{h})=\lambda(\bar{\mathcal{G}})<Span(\mathfrak{g})=|V(\bar{\mathcal{G}})|+k-n.$

The operation partite truncation contracts each partite set to one vertex and
since the vertices lying in the same partite set are at distance two from each
other, therefore, $\lambda$-number of $\hat{\bar{\mathcal{G}}}$ is given as,

$\displaystyle\lambda(\hat{\bar{\mathcal{G}}})$ $\displaystyle=$
$\displaystyle\lambda(\bar{\mathcal{G}})-\sum\limits_{0\leq j\leq
n-1}(|V_{j}|-1)$ $\displaystyle=$
$\displaystyle\lambda(\bar{\mathcal{G}})-|V(\bar{\mathcal{G}})|+n$
$\displaystyle<$
$\displaystyle|V(\bar{\mathcal{G}})|+k-n-|V(\bar{\mathcal{G}})|+n$
$\displaystyle=$ $\displaystyle k,$

a contradiction. Thus,
$\lambda(\bar{\mathcal{G}})=|V(\bar{\mathcal{G}})|+k-n$.
Case - II : $diam(\bar{\mathcal{G}})\geq 3$
By Lemma(10), $diam(\hat{\bar{\mathcal{G}}})=diam(\bar{\mathcal{G}})\geq 3$.
This implies that $\mathfrak{f}$ may not be one-one, which in turn imply that
$\mathfrak{f}$ may have multiplicities. We have,

$\displaystyle\mathcal{F}$ $\displaystyle=$
$\displaystyle\\{\mathfrak{f}(v):v\in V(\hat{\bar{\mathcal{G}}})\\}$
$\displaystyle=$
$\displaystyle\\{i_{0}^{s_{0}},i_{1}^{s_{1}},i_{2}^{s_{2}},\cdots,i_{m}^{s_{m}}\\},$

and

$\displaystyle\mathcal{C}$ $\displaystyle=$
$\displaystyle\\{V_{0},V_{1},V_{2},\cdots V_{m}\\}.$

Let $v_{j_{l}}$ denote those vertices of $\hat{\bar{\mathcal{G}}}$ for which
$\mathfrak{f}(v_{j_{l}})=i_{j},1\leq l\leq s_{j}$ and let $V_{j_{l}}$ denote
partite sets of $\bar{\mathcal{G}}$ corresponding to the vertices $v_{j_{l}}$.
Since two distinct vertices $v_{j_{l}},v_{j_{l}^{\prime}}$ are at a distance
greater or equal to three from each other. Therefore two distinct vertices
lying in two distinct corresponding partite sets $V_{j_{l}}$,
$V_{j_{l}^{\prime}}$ are also at a distance greater or equal to three from
each other. Let $v_{j}^{n}$ denote the vertices in $V_{j}$, where $1\leq
n\leq|V_{j}|$. Define $L(2,1)$-labelling $\mathfrak{g}$ on
$V(\bar{\mathcal{G}})$ as follows,

  1. 1.

Label the partite sets in $\mathcal{C}$ the same way as we we did in above
Case-I.

  2. 2.

For each $j$, provide same labels for vertices in partite sets $V_{j_{l}}$ as
given to vertices in $V_{j}\in\mathcal{C}$

As before $\mathfrak{g}$ is well defined $L(2,1)$-labelling of
$\bar{\mathcal{G}}$. Thus,

$\lambda(\bar{\mathcal{G}})\leq\sum\limits_{V_{j}\in\mathcal{C}}|V_{j}|+k-|\mathcal{C}|.$

If we assume that there exists some other $L(2,1)$-labelling $\mathfrak{h}$ of
$\bar{\mathcal{G}}$ such that
$Span(\mathfrak{h})=\lambda(\bar{\mathcal{G}})<\sum\limits_{V_{j}\in\mathcal{C}}|V_{j}|+k-|\mathcal{C}|=Span(\mathfrak{g})$,
we get a contradiction. Hence, we conclude that,

$\lambda(\bar{\mathcal{G}})=\sum\limits_{V_{j}\in\mathcal{C}}|V_{j}|+k-|\mathcal{C}|.$

∎

######  Remark 3.1.

The set $\mathcal{C}$ defined above can be also defined by defining an
equivalence relation $\sim$ on $V(\hat{\bar{\mathcal{G}}})$ as $v_{1}\sim
v_{2}$ if and only if $\mathfrak{f}(v_{1})=\mathfrak{f}(v_{2})$, where
$\mathfrak{f}$ is a minimal $L(2,1)$-labelling of $\hat{\bar{\mathcal{G}}}$.
Since there is one-one correspondence between $n$ vertices of
$\hat{\bar{\mathcal{G}}}$ and $n$ partite sets of $\bar{\mathcal{G}}$,
therefore, we have an equivalence relation on the $n$-partite sets of
$\bar{\mathcal{G}}$ as well. We choose the representatives of each equivalence
class in a way that it has maximum cardinality among other other partite sets
in its class. The collection of all such partite sets among all equivalence
classes defines $\mathcal{C}$.

The following result is the consequence of Theorem(11) in which we determine
the $\lambda-$number of a complete $n$-partite graph.

######  Corollary 12.

If $\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}}$ denotes the complete $n$-partite
graph, then

$\lambda(\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}})=\sum\limits_{i=1}^{n}m_{i}+n-2$

.

###### Proof.

Let $V_{i}$ with $|V_{i}|=m_{i},1\leq i\leq n$ be partite sets of the graph
$\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}}$. We assume that there exists at least
on $m_{i}$ such that $m_{i}>1$. This implies that
$diam(\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}})=2$. Note that the partite
truncation of $\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}}$ is isomorphic to
$\mathbb{K}_{n}$ and a bipartite subgraph induced by any two distinct partite
sets $\mathcal{V}$ and $\mathcal{W}$ induce a complete bipartite graph. It is
easy to verify that $\lambda(\mathbb{K}_{n})=2n-2$. Thus by Theorem(11) we
have,

$\lambda(\mathbb{K}_{m_{1},m_{2},\cdots,m_{n}})=\sum\limits_{i=1}^{n}m_{i}+n-2$

. ∎

For $n=2$, we have a complete bipartite graph $\mathbb{K}_{m_{1},m_{2}}$.
Therefore $\lambda(\mathbb{K}_{m_{1},m_{2}})=m_{1}+m_{2}$.

######  Corollary 13.

If $\mathbb{F}_{q}$ is a finite field of order $q$ and
$\Gamma^{\prime}(\mathbb{F}_{q})$ denotes its Beck’s zero divisor graph, then

$\lambda(\Gamma^{\prime}(\mathbb{F}_{q}))=q$

###### Proof.

It is clear that $\Gamma^{\prime}(\mathbb{F}_{q})\cong\mathbb{K}_{q-1,1}$,
where $q-1$ non-zero elements of $\mathbb{F}_{q}$ represent the number of
independent vertices in $\Gamma^{\prime}(\mathbb{F}_{q})$ and $0$ represents
the dominating vertex in $\Gamma^{\prime}(\mathbb{F}_{q})$. Therefore,

$\lambda(\Gamma^{\prime}(\mathbb{F}_{q}))=\lambda(\mathbb{K}_{q-1,1})=q.$

∎

######  Corollary 14.

If $\mathbb{F}_{p}$ and $\mathbb{F}_{q}$ are two finite fields of order $p$
and $q$ respectively and
$\mathcal{G}\cong\Gamma(\mathbb{F}_{p}\times\mathbb{F}_{q})$, then
$\lambda(\mathcal{G})=p+q-2$

###### Proof.

The set of non-zero zero-divisors of $\mathbb{F}_{p}\times\mathbb{F}_{q}$ and
hence the vertices of $\mathcal{G}$ are given as,

$\mathcal{V}_{1}=\\{(a,0):a\in\mathbb{F}_{p}~{}\mbox{and}~{}a\neq 0\\}$,

$\mathcal{V}_{2}=\\{(0,b):b\in\mathbb{F}_{q}~{}\mbox{and}~{}b\neq 0\\}$.

This implies, $|\mathcal{V}_{1}|=p-1$ and $|\mathcal{V}_{2}|=q-1$.
There are no two vertices in sets $\mathcal{V}_{1}$ or $\mathcal{V}_{2}$ that
are adjacent to each other, and each vertex in one set is adjacent to every
vertex in the other set. Thus,

$\Gamma(\mathbb{F}_{p}\times\mathbb{F}_{q})\cong\mathcal{G}\cong\mathbb{K}_{p-1,q-1}.$

It follows that $\lambda(\mathcal{G})=p+q-2$.

∎

The next result illustrates the use of partite truncation in zero-divisor
graphs, demonstrating that partite truncation of a zero-divisor graph of a
certain class of rings give rise to a zero-divisor graph of another class of
rings.

######  Theorem 15.

For $1\leq i\leq n$, let $\mathbb{F}_{q_{i}}$ be finite fields of order
$q_{i}$ and let
$\mathcal{G}\cong\Gamma(\prod\limits_{i=1}^{n}\mathbb{F}_{q_{i}})$. Then
$\mathcal{G}$ is an $(2^{n}-2)$-partite graph with

$\hat{\mathcal{G}}\cong\Gamma(\prod^{n}\mathbb{Z}_{2})$

###### Proof.

We prove the result in two parts parts. First, we show that $\mathcal{G}$ is
$(2^{n}-2)$-partite graph and then we show its partite truncation is
isomorphic to $\Gamma(\prod^{n}\mathbb{Z}_{2})$.
Part-I
Note that each non-zero zero divisor of $\prod_{i=1}^{n}\mathbb{F}_{q_{i}}$
and hence every vertex of $\mathcal{G}$ is an n-tuple which has at least one
zero and one non-zero entry in it. For $1\leq t<n$ we partition the vertices
of $\mathcal{G}$ as follows,

$\mathcal{U}_{t}=\\{v_{t}:v_{t}\mbox{~{}has ~{}exactly ~{}}t~{}\mbox{non-
zero~{} entries ~{}in~{} it}\\}.$

For each such $t$, the number of ways to choose $t$ entries out of $n$ entries
is $\binom{n}{t}$. Further, for each $t$, we partition the set
$\mathcal{U}_{t}$ into $\binom{n}{t}$ sets as follows,

$\mathcal{U}^{t}=\bigg{\\{}\mathcal{V}_{k_{t}}^{t}:1\leq
k_{t}\leq\binom{n}{t}\bigg{\\}},$

where $\mathcal{V}_{k_{t}}^{t}$ consists of those vertices of
$\mathcal{U}_{t}$ that have $t$ non-zero entries in the same position. Clearly
no two vertices of $\mathcal{V}_{k_{t}}^{t}$ are adjacent to each other. On
the other hand, if a vertex of one such set say $\mathcal{V}_{k_{r}}^{r}$ is
adjacent to a vertex of another set say
$\mathcal{V}_{k_{r^{\prime}}}^{r^{\prime}}$, where $1\leq r\leq r^{\prime}<n$,
then every vertex of $\mathcal{V}_{k_{r}}^{r}$ is adjacent to every vertex of
$\mathcal{V}_{k_{r^{\prime}}}^{r^{\prime}}$. The total number of all such sets
in $V(\mathcal{G})$ is given by,

$\sum\limits_{1\leq t<n}\binom{n}{t}=2^{n}-2.$

This implies that, $\mathcal{G}$ is $(2^{n}-2)$-partite graph.
Part-II
It is clear from Part-I that when we partition the vertex set of a Boolean
ring $\Gamma(\prod\limits^{n}\mathbb{Z}_{2})$ into the sets defined above, the
cardinality of each $\mathcal{V}_{k_{t}}^{t}$ is equal to $1$ for all $t$,
$1\leq t<n$ and for all $k_{t}$, $1\leq k_{t}\leq\binom{n}{t}$. Since there is
a one non-zero term in $\mathbb{Z}_{2}$, therefore the order of
$\Gamma(\prod\limits^{n}\mathbb{Z}_{2})$ is equal to number of partite sets in
$\Gamma(\prod\limits_{i=1}^{n}\mathbb{F}_{q_{i}})$ which by Part-I is equal to
$2^{n}-2$. Thus, if $\hat{\mathcal{G}}$ is partite truncation of
$\mathcal{G}\cong\Gamma(\prod\limits_{i=1}^{n}\mathbb{F}_{q_{i}})$, then

$\hat{\mathcal{G}}\cong\Gamma(\prod^{n}\mathbb{Z}_{2}).$

Which completes the proof. ∎

The following example illustrates the concept of partite truncation of a graph
as well as Theorems(11) and (15).

######  Example 16.

Let $\mathbb{F}_{q_{i}}$ be finite fields of order $q_{i}$, where $1\leq i\leq
4$ and $q_{1}\leq q_{2}\leq q_{3}\leq q_{4}$. We partition the non-zero zero-
divisors of $\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}}$ and hence the vertices
of $\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ as follows,

$\displaystyle V_{1}$ $\displaystyle=$ $\displaystyle\big{\\{}(x,0,0,0):x(\neq
0)\in\mathbb{F}_{q_{1}}\big{\\}}$ $\displaystyle V_{2}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,y,0,0):y(\neq 0)\in\mathbb{F}_{q_{2}}\big{\\}}$
$\displaystyle V_{3}$ $\displaystyle=$ $\displaystyle\big{\\{}(0,0,z,0):z(\neq
0)\in\mathbb{F}_{q_{3}}\big{\\}}$ $\displaystyle V_{4}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,0,0,w):w(\neq 0)\in\mathbb{F}_{q_{4}}\big{\\}}$
$\displaystyle V_{12}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,y,0,0):x(\neq 0)\in\mathbb{F}_{q_{1}}~{}and~{}y(\neq
0)\in\mathbb{F}_{q_{2}}\big{\\}}$ $\displaystyle V_{13}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,0,z,0):x(\neq 0)\in\mathbb{F}_{q_{1}}~{}and~{}z(\neq
0)\in\mathbb{F}_{q_{3}}\big{\\}}$ $\displaystyle V_{14}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,0,0,w):x(\neq 0)\in\mathbb{F}_{q_{1}}~{}and~{}w(\neq
0)\in\mathbb{F}_{q_{3}}\big{\\}}$ $\displaystyle V_{23}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,y,z,0):y(\neq 0)\in\mathbb{F}_{q_{2}}~{}and~{}z(\neq
0)\in\mathbb{F}_{q_{3}}\big{\\}}$ $\displaystyle V_{24}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,y,0,w):y(\neq 0)\in\mathbb{F}_{q_{2}}~{}and~{}w(\neq
0)\in\mathbb{F}_{q_{4}}\big{\\}}$ $\displaystyle V_{34}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,0,z,w):z(\neq 0)\in\mathbb{F}_{q_{3}}~{}and~{}w(\neq
0)\in\mathbb{F}_{q_{4}}\big{\\}}$ $\displaystyle V_{123}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,y,z,0):x(\neq 0)\in\mathbb{F}_{q_{1}},~{}y(\neq
0)\in\mathbb{F}_{q_{2}}~{}and~{}z(\neq 0)\in\mathbb{F}_{q_{3}}\big{\\}}$
$\displaystyle V_{134}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,0,z,w):x(\neq 0)\in\mathbb{F}_{q_{1}},~{}z(\neq
0)\in\mathbb{F}_{q_{3}}~{}and~{}w(\neq 0)\in\mathbb{F}_{q_{4}}\big{\\}}$
$\displaystyle V_{124}$ $\displaystyle=$
$\displaystyle\big{\\{}(x,y,0,w):x(\neq 0)\in\mathbb{F}_{q_{1}},~{}y(\neq
0)\in\mathbb{F}_{q_{2}}~{}and~{}w(\neq 0)\in\mathbb{F}_{q_{3}}\big{\\}}$
$\displaystyle V_{234}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,y,z,w):y(\neq 0)\in\mathbb{F}_{q_{2}},~{}z(\neq
0)\in\mathbb{F}_{q_{3}}~{}and~{}w(\neq 0)\in\mathbb{F}_{q_{4}}\big{\\}}$

Figure 1: A Rough Sketch of $\Gamma(\prod_{i=1}^{4}\mathbb{F}_{q_{i}})$

Thus,

$\displaystyle\mathcal{U}_{1}$ $\displaystyle=$
$\displaystyle\bigg{\\{}V_{1},V_{2},V_{3},V_{4}\bigg{\\}}$
$\displaystyle\mathcal{U}_{2}$ $\displaystyle=$
$\displaystyle\bigg{\\{}V_{12},V_{13},V_{14},V_{23},V_{24},V_{34}\bigg{\\}}$
$\displaystyle\mathcal{U}_{3}$ $\displaystyle=$
$\displaystyle\bigg{\\{}V_{123},V_{124},V_{134},V_{234}\bigg{\\}}$

Clearly, we have $2^{4}-2=14$ partition sets, and no two vertices in the same
partition set are adjacent to each other. If a vertex in one partition set is
adjacent to a vertex in another partition set, then the two partition sets
form a complete bipartite graph. Therefore,
$\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ is a $14$-partite graph. A
rough drawing of $\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ is shown
in Figure (1), where an edge between two partite sets means that each vertex
of one set is adjacent to every vertex of the other set. Truncating the
partite sets of $\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ involves
one vertex from each partite set and one edge between two partite sets. Thus,
if we replace $x,y,z$ and $w$ with $1$ in the above partite sets, we obtain
the partite truncation of the graph
$\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$, which is also the zero
divisor graph of $\prod\limits^{4}\mathbb{Z}_{2}$. Hence, the partite
truncation of $\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ and the zero
divisor graph of $\prod\limits^{4}\mathbb{Z}_{2}$ with a minimal
$L(2,1)$-labelling is shown in Figure(2). From the Figure(2), the labelling is
minimal, since any other labelling with a shorter span would imply more than
one multiplicity, which is impossible to achieve. Thus,

$\lambda(\Gamma(\prod\limits^{4}\mathbb{Z}_{2}))=10$

Figure 2: $\Gamma(\prod\limits^{4}\mathbb{Z}_{2})$

Given a minimal labelling on partite truncation of
$\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$ we can obtain the
equivalence relation shown in Remark(3.1) on the partite sets of
$\Gamma(\prod\limits_{i=1}^{4}\mathbb{F}_{q_{i}})$. The representatives of the
equivalence classes are,

$\mathcal{C}=\big{\\{}V_{1},V_{2},V_{3},V_{4},V_{12},V_{13},V_{14},V_{23},V_{24},V_{34},V_{234}\big{\\}}.$

Thus by Theorem(11) we have,

$\displaystyle\lambda(\Gamma(\prod_{i=1}^{4}\mathbb{F}_{q_{i}}))$
$\displaystyle=$
$\displaystyle\sum\limits_{V\in\mathcal{C}}|V|+\lambda(\Gamma(\prod\limits^{4}\mathbb{Z}_{2}))-|\mathcal{C}|$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{4}(q_{i}-1)+\sum\limits_{1\leq i<j\leq
4}\big{(}(q_{i}-1)(q_{j}-1)\big{)}+(q_{2}-1)(q_{3}-1)(q_{4}-1)-1.$

It would be very interesting to determine the $\lambda$-number and a
corresponding minimal $L(2,1)$-labelling of the graph
$\Gamma(\prod\limits_{i=1}^{n}\mathbb{F}_{q_{i}})$. So, we conclude this
section with the following open problem.

######  Problem 1.

Determine the $\lambda$-number of the graph
$\Gamma(\prod\limits^{n}\mathbb{Z}_{2})$ and a corresponding minimal
$L(2,1)$-labelling.

##  4 $\lambda$-number of Local Rings

In this section, we study $\lambda$-numbers of zero-divisor graphs realized by
a local ring of the form $\mathbb{Z}_{p^{n}}$ and a mixed ring of the form
$\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}}$, where $p$ and $q$ are primes and
$m,n\geq 2$. We provide an algorithm related to a minimal $L(2,1)$-labelling
of zero-divisor graphs $\Gamma(\mathbb{Z}_{p^{n}})$ and
$\Gamma(\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}})$ and consequently
determine the exact value for $\lambda$-numbers of these graphs.

######  Theorem 17.

Let $p$ be a prime number and let
$\mathcal{G}\cong\Gamma(\mathbb{Z}_{p^{n}})$. Then the following hold,

$\lambda(\mathcal{G})=\begin{cases}p^{n-1}+p-3,\text{ if }n\geq 3,\\\
2p-4,\text{ if }n=2.\end{cases}$

###### Proof.

The set of non-zero zero-divisors of $\mathbb{Z}_{p^{n}}$ are given as,

$Z^{*}(\mathbb{Z}_{p^{n}})=\big{\\{}\alpha_{i}p^{i}:\gcd(\alpha_{i},p^{n-i})=1\mbox{~{}and~{}}1\leq
i\leq n-1\big{\\}}.$

Therefore, the order of $\mathcal{G}$ is,

$|V(\mathcal{G})|=\sum\limits_{i=1}^{n-1}\phi(p^{n-i})=p^{n-1}-1,$

where $\phi$ is Euler’s totient function. The vertices corresponding to zero-
divisors $\alpha_{i}p^{i}$ are denoted by $v_{\beta_{i},i}$, where
$1\leq\beta_{i}\leq\phi(p^{n-i})$. For a fixed $i$, we denote the set of
vertices corresponding to zero divisors $\alpha_{i}p^{i}$ by $V^{i}$, that is,

$V^{i}=\\{v_{\beta_{i},i}:1\leq\beta_{i}\leq\phi(p^{n-i})\\}.$

Note that

$\alpha_{i}p^{i}.\alpha_{j}p^{j}=0$

if and only if $i+j\geq n$, that is,

$v_{\beta_{i},i}~{}adjacent~{}to~{}v_{\beta_{j},j}$ (1)

if and only if $i+j\geq n$.

Now, we consider the following cases.
Case-I: $n\geq 3$,
we first consider the even case.
Subcase - I : $n=2k$
By (1), we see that for $i\geq k$, the vertices $v_{\beta_{i},i}$ induce a
clique in $\mathcal{G}$. The order of clique is,

$\sum\limits_{i=k}^{n-1}\phi(p^{n-i})=p^{k}-1.$

For fixed $i<k$ and $j\geq k$ we have,

$\alpha_{i}p^{i}.\alpha_{j}p^{j}=0$

if and only if $j\in\\{n-1,n-2,\cdots n-i\\}$, that is, $v_{\beta_{i},i}$ is
adjacent to $v_{\beta_{j},j}$ if and only if $j\in\\{n-1,n-2,\cdots n-i\\}$.
Thus for fixed $i<k$ and $\beta_{i}$,

$deg(v_{\beta_{i},i})=\sum\limits_{j=n-i}^{n-1}\phi(p^{n-j})=p^{i}-1.$

The set of vertices $\bigcup\limits_{i=k}^{n-1}V^{i}$ induce a clique
$\mathbb{K}_{p^{k}-1}$ in $\mathcal{G}$ of order $p^{k}-1$ and for $i<k$, the
vertices in $V^{i}$ are independent and are adjacent to vertices of sets
$V^{j}$, where $j\in\\{n-1,n-2,\cdots,n-i\\}$. A rough sketch of $\mathcal{G}$
is given in Figure (3).

Figure 3: A Rough sketch of $\Gamma(\mathbb{Z}_{p^{n}})$

Define a $L(2,1)$-labelling $f:V(\mathcal{G})\longrightarrow\mathbb{Z}_{\geq
0}$ by,

$\displaystyle f(v_{\beta_{n-1},n-1})$ $\displaystyle=$ $\displaystyle
2\beta_{n-1}-2,\mbox{~{}where~{}}v_{\beta_{n-1},n-1}\in V^{n-1}$

In general for $i\leq k$ and $v_{\beta_{n-i},n-i}\in V^{n-i}$,

$\displaystyle f(v_{\beta_{n-i},n-i})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in
V^{n-(i-1)}}\big{\\{}f(v)\big{\\}}+2\beta_{n-i}$ $\displaystyle=$
$\displaystyle 2p^{i-1}+2\beta_{n-i}-4.$

Therefore for $i=k$ we have,

$\max\limits_{v\in
V^{k}}\big{\\{}f(v)\big{\\}}=f(v_{\phi(p^{k}),k})=2p^{k}-4.$

This completes the labelling of the clique $\mathbb{K}_{p^{k}-1}$. Moreover,
for $i<k$, we label the sets $V^{i}$ as follows,

$\displaystyle f(v_{\beta_{1},1})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in V^{n-1}}\big{\\{}f(v)\big{\\}}+2\beta_{1}+1$
$\displaystyle=$ $\displaystyle
2p+2\beta_{1}-3,\mbox{~{}where~{}}1\leq\beta_{1}\leq p^{k}-p.$

For $p^{k}-p<\beta_{1}\leq\phi(p^{n-1})$,

$\displaystyle f(v_{\beta_{1},1})$ $\displaystyle=$ $\displaystyle
p^{k}+\beta_{1}+p-3.$

In general for $i<k$,

$\displaystyle f(v_{\beta_{i},i})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in
V^{i-1}}\big{\\{}f(v)\big{\\}}+\beta_{i},\mbox{~{}Where~{}}v_{\beta_{i},i}\in
V^{i}$ $\displaystyle=$ $\displaystyle f(v_{\phi(p^{n-(i-1)}),i-1})+\beta_{i}$
$\displaystyle=$ $\displaystyle p^{n-1}+p^{k}+p-p^{n-i}+\beta_{i}-3.$

Therefore,

$\displaystyle f(v_{\phi(p^{k+1}),k-1})$ $\displaystyle=$ $\displaystyle
p^{n-1}+p-3.$

Clearly $f$ is a well defined labelling, since any two vertices in sets
$V^{i}$, $i\geq k$, are adjacent to each other and their labelling differs by
at least $2$, and any two vertices in $V^{i}$ with $i<k$, are at distance two
from each other and their labelling differs by at least one. Thus we have,

$\lambda(\mathcal{G})\leq p^{n-1}+p-3.$

Subcase - II : $n=2k+1$
In this case $v_{\beta_{i},i}$ is adjacent to $v_{\beta_{j},j},$ and
$v_{\beta_{i},i}$ is adjacent to $v_{\beta_{k},k}$ for all $i,j>k$ and for
distinct $\beta^{\prime}_{k},\beta_{k}$, $v_{\beta^{\prime}_{k},k}$ is not
adjacent to $v_{\beta_{k},k}$. Therefore, the vertices
$\bigcup\limits_{i=k+1}^{n-1}V^{i}\cup\\{v_{1,k}\\}$ induce a clique
$\mathbb{K}_{p^{k}}$ on $p^{k}$ vertices. For $1\leq i\leq k-1$, the set of
vertices $V^{i}$, are independent and are adjacent to vertices of sets
$V^{j}$, where $n-i\leq j\leq n-1$. The set $V^{k}\setminus\\{v_{1,k}\\}$ also
represents an independent set, the vertices of $V^{k}$ are adjacent to
vertices of $V^{i}$, $k+1\leq i\leq n-1$. For the sets $V^{i}$ with $i>k$, we
define $f$, a $L(2,1)$-labelling in the same manner as we did in Subcase-I.
Therefore,

$\displaystyle f(v_{\phi(k),k+1})$ $\displaystyle=$ $\displaystyle 2p^{k}-4$
$\displaystyle f(v_{1,k})$ $\displaystyle=$ $\displaystyle 2p^{k}-2.$

This completes the labelling of the complete part $\mathbb{K}_{p^{k}}$. Now,
we label the vertices of sets $V^{i}$, $i<k$ and $V^{k}\setminus\\{v_{1,k}\\}$
as follows,

$\displaystyle f(v_{\beta_{1},1})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in V^{n-1}}\big{\\{}f(v)\big{\\}}+2\beta_{1}+1$
$\displaystyle=$ $\displaystyle
2p+2\beta_{1}-3,\mbox{~{}Where~{}}1\leq\beta_{1}\leq p^{k}-p+1.$

For $p^{k}-p+1<\beta_{1}\leq\phi(p^{n-1})$,

$\displaystyle f(v_{\beta_{1},1})$ $\displaystyle=$ $\displaystyle
p^{k}+\beta_{1}+p-2$

The remaining vertices in sets $V^{i}$, $1\leq i\leq k-1$ are labelled in the
same manner as in Subcase-I. Thus,

$\displaystyle f(v_{\phi(p^{k})k-1})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in V^{k-1}}\\{f(v)\\}$ $\displaystyle=$
$\displaystyle p^{n-1}+p^{k}+p-p^{k+1}-2.$

For the set $V^{k}\setminus\\{v_{1,k}\\}$,

$\displaystyle f(v_{\beta_{k},k})$ $\displaystyle=$ $\displaystyle
p^{n-1}+p^{k}+p-p^{k+1}+\beta_{k}-3,\mbox{~{}where~{}}2\leq\beta_{k}\leq\phi(p^{k+1}).$

Therefore,

$\displaystyle f(v_{\phi(p^{k+1}),k})$ $\displaystyle=$ $\displaystyle
p^{n-1}+p-3.$

This completes the labelling of $\mathcal{G}$ and it is easy to verify that
$f$ is a well defined $L(2,1)$-labelling. Thus in both the subcases,

$\lambda(\Gamma(\mathbb{Z}_{p^{n}}))=\lambda(\mathcal{G})\leq p^{n-1}+p-3.$

Since $diam(\mathcal{G})=2$, any $L(2,1)$-labelling of $\mathcal{G}$ must be
one-one. Also, each vertex in $V^{i}$, $1\leq i\leq n-2$, is adjacent to every
vertex in $V^{n-1}$, and any two vertices in $V^{n-1}$ are adjacent to each
other, so that any $L(2,1)$-labelling of $\mathcal{G}$ must have $p-1$ holes.
Therefore,

$\displaystyle\lambda(\mathcal{G})$ $\displaystyle\geq$
$\displaystyle|V(\mathcal{G})|-1+(p-1)$ $\displaystyle=$ $\displaystyle
p^{n-1}+p-3$

and we have,

$\displaystyle\lambda(\mathcal{G})$ $\displaystyle=$ $\displaystyle
p^{n-1}+p-3$

Case-II : n = 2
The set of non-zero zero-divisors of $\mathbb{Z}_{p^{2}}$ is given as,

$Z^{*}(\mathbb{Z}_{p^{2}})=\\{\alpha p:(\alpha,p)=1\\}.$

Therefore the set of vertices of $\mathcal{G}$ is,

$V^{1}=\\{v_{\beta_{1},1}:1\leq\beta_{1}\leq p-1\\}.$

By (1), $\mathcal{G}\cong\mathbb{K}_{p-1}$, which implies
$\lambda(\mathcal{G})=2p-4$. ∎

Recall that the tensor product of two graphs $G$ and $H$ denoted by $G\otimes
H$ has a vertex set $V(G\otimes H)=V(G)\times V(H)$ with $(a,b)$ adjacent to
$(c,d)$ in $G\otimes H$ if and only if $a$ is adjacent to $c$ in $G$ and $b$
is adjacent to $d$ in $H$.

######  Theorem 18.

Let $R\cong\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}}$, where $p$ and $q$ are
primes and $m,n\geq 3$. Then the following hold for the zero-divisor graph
$\Gamma(R)$,

$\lambda(\Gamma(R))=p^{n-1}q^{m}+pq-3.$

###### Proof.

Let $\mathcal{R}_{p}$, $\mathcal{R}_{q}$ be the set of non-zero zero-divisors
of $\mathbb{Z}_{p^{n}}$ and $\mathbb{Z}_{q^{m}}$ respectively and
$\mathcal{U}_{p},\mathcal{U}_{q}$ be the set of units of $\mathbb{Z}_{p^{n}}$
and $\mathbb{Z}_{q^{m}}$ respectively. We partition the non-zero zero-divisors
of $R$ and hence the vertices of $\Gamma(R)$ as follows,

$\displaystyle V_{1}$ $\displaystyle=$
$\displaystyle\\{(r_{p},0):r_{p}\in\mathcal{R}_{p}\\}$ $\displaystyle V_{2}$
$\displaystyle=$ $\displaystyle\\{(0,r_{q}):r_{q}\in\mathcal{R}_{q}\\}$
$\displaystyle U_{1}$ $\displaystyle=$
$\displaystyle\\{(u_{p},0):u_{p}\in\mathcal{U}_{p}\\}$ $\displaystyle U_{2}$
$\displaystyle=$ $\displaystyle\\{(0,u_{q}):u_{q}\in\mathcal{U}_{q}\\}$
$\displaystyle W$ $\displaystyle=$
$\displaystyle\\{(r_{p},r_{q}):r_{p}\in\mathcal{R}_{p}\mbox{~{}and~{}}r_{q}\in\mathcal{R}_{q}\\}$
$\displaystyle W_{1}$ $\displaystyle=$
$\displaystyle\\{(u_{p},r_{q}):u_{p}\in\mathcal{U}_{p}\mbox{~{}and~{}}r_{q}\in\mathcal{R}_{q}\\}$
$\displaystyle W_{2}$ $\displaystyle=$
$\displaystyle\\{(r_{p},u_{q}):r_{p}\in\mathcal{R}_{p}\mbox{~{}and~{}}u_{q}\in\mathcal{U}_{q}\\}$

This implies,

$\displaystyle|V_{1}|$ $\displaystyle=$ $\displaystyle p^{n-1}-1$
$\displaystyle|V_{2}|$ $\displaystyle=$ $\displaystyle q^{m-1}-1$
$\displaystyle|U_{1}|$ $\displaystyle=$ $\displaystyle p^{n}-p^{n-1}$
$\displaystyle|U_{2}|$ $\displaystyle=$ $\displaystyle q^{m}-q^{m-1}$
$\displaystyle|W|$ $\displaystyle=$ $\displaystyle(p^{n-1}-1)(q^{m-1}-1)$
$\displaystyle|W_{1}|$ $\displaystyle=$
$\displaystyle(p^{n}-p^{n-1})(q^{m-1}-1)$ $\displaystyle|W_{2}|$
$\displaystyle=$ $\displaystyle(p^{n-1}-1)(q^{m}-q^{m-1})$

Therefore the number of non-zero zero-divisors of $R$ and hence the order of
$\Gamma(R)$ is given as,

$|V(\Gamma(R))|=p^{n}q^{m-1}+p^{n-1}q^{m}-p^{n-1}q^{m-1}-1.$

Recall that the non-zero zero-divisors of $\mathbb{Z}_{p^{n}}$ and
$\mathbb{Z}_{q^{m}}$ are of the form $\alpha_{i}p^{i}$ and $\beta_{j}q^{j}$
respectively where $1\leq i\leq n-1,1\leq j\leq
m-1\mbox{~{}and~{}}\gcd(\alpha_{i},p^{n-i})=\gcd(\beta_{j},q^{m-j})=1$. It is
easy to verify that the vertices corresponding to sets $U_{1},U_{2},W_{1}$ and
$W_{2}$ are independent. Vertices corresponding to sets $V_{1}$ and $V_{2}$
induce subgraphs $\Gamma(\mathbb{Z}_{p^{n}})$ and $\Gamma(\mathbb{Z}_{q^{m}})$
respectively in $\Gamma(R)$. The vertices corresponding to $W$ induce the
tensor product $\Gamma(\mathbb{Z}_{p^{n}})\otimes\Gamma(\mathbb{Z}_{q^{m}})$.
We further partition the set $W$ by considering the following cases.
Case-I: $n=2k$ and $m=2l$

$\displaystyle S_{1}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i}p^{i},\beta_{j}q^{j}):i\geq k,j\geq
l\big{\\}},$ $\displaystyle S_{2}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i}p^{i},\beta_{j}q^{j}):i\geq k,j<l\big{\\}},$
$\displaystyle S_{3}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i}p^{i},\beta_{j}q^{j}):i<k,j\geq l\big{\\}},$
$\displaystyle S_{4}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i}p^{i},\beta_{j}q^{j}):i<k,j<l\big{\\}}.$

Clearly any two vertices corresponding to set $S_{1}$ are adjacent to each
other and hence induce the complete graph $\mathbb{K}_{(p^{k}-1)(q^{l}-1)}$.
The vertices corresponding to set $S_{2}$, $S_{3}$ and $S_{4}$ are
independent. No vertex corresponding to set $S_{4}$ is adjacent to a vertex
corresponding to sets $S_{2}$ or $S_{3}$. However, there will be adjacencies
between the vertices corresponding to sets $S_{4}$ and $S_{1}$. For $i<k$ and
$j<l$, $(\alpha_{i}p^{i},\beta_{j}p^{j})\in S_{4}$ and the vertex
corresponding to it is adjacent to the set of vertices corresponding to the
following subset of $S_{1}$.

$\displaystyle A_{1}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i^{\prime}}p^{i^{\prime}},\beta_{j^{\prime}}q^{j^{\prime}}):n-i\leq
i^{\prime}\leq n-1\mbox{~{}and~{}}m-j\leq j^{\prime}\leq m-1\big{\\}},$
$\displaystyle\mbox{where}~{}|A_{1}|$ $\displaystyle=$
$\displaystyle\bigg{(}\sum\limits_{i^{\prime}=n-i}^{n-1}\phi(p^{n-i^{\prime}})\bigg{)}\bigg{(}\sum\limits_{j^{\prime}=m-j}^{m-1}\phi(q^{m-j^{\prime}})\bigg{)}$
$\displaystyle=$ $\displaystyle\big{(}p^{i}-1\big{)}\big{(}q^{j}-1\big{)}.$

For any $(\alpha_{i}p^{i},\beta_{j}p^{j})\in S_{2}$ the vertex corresponding
to it is adjacent to the vertices corresponding to the following subset of
$S_{1}$:

$\displaystyle A_{2}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i^{\prime}}p^{i^{\prime}},\beta_{j^{\prime}}q^{j^{\prime}}):k\leq
i^{\prime}\leq n-1\mbox{~{}and~{}}m-j\leq j^{\prime}\leq m-1\big{\\}},$
$\displaystyle\mbox{where}~{}|A_{2}|$ $\displaystyle=$
$\displaystyle\big{(}p^{k}-1\big{)}\big{(}q^{j}-1\big{)}.$

The vertex corresponding to $(\alpha_{i}p^{i},\beta_{j}p^{j})\in S_{3}$ is
adjacent to vertices corresponding to the following subset of $S_{1}$.

$\displaystyle A_{3}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i^{\prime}}p^{i^{\prime}},\beta_{j^{\prime}}q^{j^{\prime}}):n-i\leq
i^{\prime}\leq n-1\mbox{~{}and~{}}l\leq j^{\prime}\leq m-1\big{\\}},$
$\displaystyle\mbox{where}~{}|A_{3}|$ $\displaystyle=$
$\displaystyle\big{(}p^{i}-1\big{)}\big{(}q^{l}-1\big{)}.$

The vertex corresponding to $(\alpha_{i}p^{i},\beta_{j}p^{j})\in S_{2}$ is
adjacent to vertices corresponding to the following subset of $S_{3}$:

$\displaystyle A_{4}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i^{\prime}}p^{i^{\prime}},\beta_{j^{\prime}}q^{j^{\prime}}):n-i\leq
i^{\prime}\leq k-1\mbox{~{}and~{}}m-j\leq j^{\prime}\leq m-1\big{\\}},$
$\displaystyle\mbox{where}~{}|A_{4}|$ $\displaystyle=$
$\displaystyle\big{(}p^{i}-p^{k}\big{)}\big{(}q^{j}-1\big{)}.$

The vertex corresponding to $(\alpha_{i}p^{i},\beta_{j}p^{j})\in W$ is
adjacent to vertices corresponding to the following subsets $B_{1}$, $B_{2}$
of $V_{1}$ and $V_{2}$ respectively,

$\displaystyle B_{1}$ $\displaystyle=$
$\displaystyle\big{\\{}(\alpha_{i^{\prime}}p^{i^{\prime}},0):n-i\leq
i^{\prime}\leq n-1\big{\\}}\subset V_{1},$ $\displaystyle B_{2}$
$\displaystyle=$
$\displaystyle\big{\\{}(0,\beta_{j^{\prime}}q^{j^{\prime}}):m-j\leq
j^{\prime}\leq m-1\big{\\}}\subset V_{2},$

where,

$\displaystyle|B_{1}|$ $\displaystyle=$ $\displaystyle\big{(}p^{i}-1\big{)},$
$\displaystyle|B_{2}|$ $\displaystyle=$ $\displaystyle\big{(}q^{j}-1\big{)}.$

The vertices corresponding to $(\alpha_{i}p^{i},u_{q})\in W_{2}$ and
$(u_{p},\beta_{j}p^{j})\in W_{1}$ are adjacent to the set of vertices
corresponding to sets $B_{1}$ and $B_{2}$ respectively. Also, every vertex in
sets $V_{1},V_{2},S_{2},S_{3}$ and $S_{4}$ are adjacent to vertices
corresponding to the following subset $C_{1}$ of $S_{1}$.

$\displaystyle C_{1}$ $\displaystyle=$
$\displaystyle\big{\\{}\big{(}\alpha_{n-1}p^{n-1},\beta_{m-1}q^{m-1}\big{)}\big{\\}},$
$\displaystyle\mbox{where }|C_{1}|$ $\displaystyle=$
$\displaystyle(p-1)(q-1).$

Figure 4: A Rough sketch of
$\Gamma(\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}})$

Figure (4) shows a rough sketch of $\Gamma(R)$, with a solid line between two
sets of vertices implying that each vertex in one set is adjacent to every
vertex in the other set and a dotted and dashed edge imply that not every
vertex in one set is adjacent to every vertex in the other set. Let $f$ and
$g$ be minimal labellings of $\Gamma(\mathbb{Z}_{p^{n}})$ and
$\Gamma(\mathbb{Z}_{q^{m}})$ as defined in Theorem 17. Now, we define
$L(2,1)$-labelling $h:V(\Gamma(R))\longrightarrow\mathbb{Z}_{\geq 0}$ as,

$\displaystyle h(v_{2})$ $\displaystyle=$ $\displaystyle
g(v_{2}),\mbox{~{}where~{}}v_{2}\in V_{2}$ $\displaystyle h(u_{i_{2}})$
$\displaystyle=$
$\displaystyle\lambda(\Gamma(\mathbb{Z}_{q^{m}}))+i_{2},\mbox{~{}where~{}}u_{i_{2}}\in
U_{2},1\leq i_{2}\leq|U_{2}|$ $\displaystyle=$ $\displaystyle
q^{m-1}+q+i_{2}-3$ $\displaystyle h(v_{1})$ $\displaystyle=$ $\displaystyle
f(v_{1})+q^{m}+q-1,\mbox{~{}where~{}}v_{1}\in V_{1}$ $\displaystyle
h(u_{i_{1}}^{\prime})$ $\displaystyle=$ $\displaystyle
p^{n-1}+q^{m}+p+q+i_{1}-4,\mbox{~{}where~{}}u_{i_{1}}^{\prime}\in U_{1},1\leq
i_{1}\leq|U_{1}|$ $\displaystyle h(s_{j_{1}}^{1})$ $\displaystyle=$
$\displaystyle p^{n}+q^{m}+p+q+2j_{1}-5,\mbox{~{}where~{}}s_{j_{1}}^{1}\in
S_{1},1\leq j_{1}\leq|S_{1}|$

While labelling the set of vertices corresponding to $S_{1}$, we first label
the subset of vertices corresponding to $C_{1}\subset S_{1}$. Thus,

$\max\limits_{s\in C_{1}}\\{h(s)\\}=p^{n}+q^{m}+p+q+2(p-1)(q-1)-5.$

Consider the following subset $C_{2}$ of $S_{4}$.

$\displaystyle C_{2}$ $\displaystyle=$
$\displaystyle\\{(\alpha_{1}p,\beta_{1}q)\\}\subset S_{4},$
$\displaystyle\mbox{where}~{}|C_{2}|$ $\displaystyle=$
$\displaystyle(p^{n-1}-p^{n-2})(q^{m-1}-q^{m-2})$

For $s_{j_{4}}^{4}\in C_{2},1\leq j_{4}\leq(p^{k}-1)(q^{l}-1)-(p-1)(q-1)$

$\displaystyle h(s_{j_{4}}^{4})$ $\displaystyle=$ $\displaystyle
p^{n}+q^{m}+p+q+2(p-1)(q-1)+2j_{4}-4,$

and for $s_{j_{4}}^{4}\in C_{2}$ with
$(p^{k}-1)(q^{l}-1)-(p-1)(q-1)<j_{4}\leq|C_{2}|$

$\displaystyle h(s_{j_{4}}^{4})$ $\displaystyle=$ $\displaystyle
p^{n}+q^{m}+p+q+2(p^{k}-1)(q^{l}-1)+j_{4}-\big{(}(p^{k}-1)(q^{l}-1)-(p-1)(q-1)\big{)}-4$
$\displaystyle=$ $\displaystyle p^{n}+q^{m}+pq+(p^{k}-1)(q^{l}-1)+j_{4}-3.$

Therefore,

$\displaystyle\max\limits_{v\in C_{2}}\\{h(v)\\}$ $\displaystyle=$
$\displaystyle h(s_{|C_{2}|}^{4})$ $\displaystyle=$ $\displaystyle
p^{n}+q^{m}+pq+(p^{k}-1)(q^{l}-1)+(p^{n-1}-p^{n-2})(q^{m-1}-q^{m-2})-3$
$\displaystyle=$ $\displaystyle\Delta_{1}(\mbox{say}).$

For $s_{j_{3}}^{3}\in S_{3}$, $1\leq j_{3}\leq|S_{3}|$

$\displaystyle h(s_{j_{3}}^{3})$ $\displaystyle=$
$\displaystyle\Delta_{1}+j_{3}$
$\displaystyle\mbox{Therefore~{}}\max\limits_{v\in S_{3}}\\{h(v)\\}$
$\displaystyle=$ $\displaystyle h(s_{|S_{3}|}^{3})$ $\displaystyle=$
$\displaystyle p^{n}+q^{m}+pq-q^{l}+p^{n-2}q^{m-2}(pq-
p-q+1)+p^{n-1}(q^{l}-1)-2$ $\displaystyle=$
$\displaystyle\Delta_{2}(\mbox{say}).$

For $s_{j_{4}}^{4}\in S_{4}\setminus C_{2},|C_{2}|<j_{4}\leq|S_{4}|$

$\displaystyle h(s_{j_{4}}^{4})$ $\displaystyle=$
$\displaystyle\Delta_{2}+j_{4}-|C_{2}|.$

Therefore,

$\displaystyle\max\limits_{v\in S_{4}}\\{h(v)\\}$ $\displaystyle=$
$\displaystyle h(s_{|S_{4}|}^{4})$ $\displaystyle=$ $\displaystyle
p^{n}+q^{m}+pq+q^{l}(p^{k}-1)+q^{m-1}(p^{n-1}-p^{k})-p^{n-1}-2$
$\displaystyle=$ $\displaystyle\Delta_{3}(\mbox{say}).$

For $s_{j_{2}}^{2}\in S_{2},1\leq j_{2}\leq|S_{2}|$

$\displaystyle h(s_{i_{2}}^{2})$ $\displaystyle=$
$\displaystyle\Delta_{3}+i_{2}.$

Therefore,

$\displaystyle\max\limits_{v\in S_{2}}\\{h(v)\\}$ $\displaystyle=$
$\displaystyle h(s_{|S_{2}|}^{2})$ $\displaystyle=$ $\displaystyle
p^{n}+q^{m}+pq+q^{m-1}p^{n-1}-p^{n-1}-q^{m-1}-2$ $\displaystyle=$
$\displaystyle\Delta_{4}(\mbox{say}).$

Note that,

$d(w_{t_{1}},u_{i_{2}})=d(w_{t_{2}}^{\prime},u_{i_{1}}^{\prime})=d(w_{t_{1}},w_{t_{2}}^{\prime})=3,$

where $w_{t_{1}}\in W_{1},u_{i_{2}}\in U_{2},w_{t_{2}}^{\prime}\in W_{2}$ and
$u_{i_{1}}^{\prime}\in U_{1}$. Furthermore, we define,

$\displaystyle h(w_{t_{2}}^{\prime})$ $\displaystyle=$ $\displaystyle
h(u_{i_{1}}^{\prime}),\mbox{~{}where~{}}1\leq i_{1}\leq|U_{1}|$ $\displaystyle
h(w_{(|U_{1}|+1)}^{\prime})$ $\displaystyle=$ $\displaystyle q^{m}+q-2$
$\displaystyle h(w_{t_{2}}^{\prime})$ $\displaystyle=$
$\displaystyle\Delta_{4}+t_{2}-|U_{1}|-1,\mbox{~{}where~{}}|U_{1}|+1<t_{2}\leq|W_{2}|.$

Therefore,

$\displaystyle\max\limits_{v\in W_{2}}\\{h(v)\\}$ $\displaystyle=$
$\displaystyle h(w_{|W_{2}|}^{\prime})$ $\displaystyle=$ $\displaystyle
p^{n-1}q^{m}+pq-3.$

Also,

$\displaystyle h(w_{t_{1}})$ $\displaystyle=$ $\displaystyle
h(u_{i_{2}}),\mbox{~{}where~{}}1\leq t_{1}\leq|U_{2}|.$

Since $p^{n}\leq q^{m}$, therefore, $|W_{1}|\leq|W_{2}|$. The remaining
vertices of $W_{1}$ are labelled same as the vertices $w_{t_{2}}^{\prime}$ of
$W_{2}$, where $|U_{1}|+1<t_{2}\leq|W_{2}|$. This concludes the labelling of
all the vertices of $\Gamma(R)$. It is evident form the structure of
$\Gamma(R)$ that $h$ is a well-defined $L(2,1)$-labelling. Therefore,

$\lambda(\Gamma(R))\leq p^{n-1}q^{m}+pq-3.$

We claim that $h$ is a minimal labelling. Since the vertices corresponding to
sets $\\{(\alpha_{n-1}p^{n-1},0)\\},\\\ \\{(0,\beta_{m-1}q^{m-1})\\}$ and
$\\{(\alpha_{n-1}p^{n-1},\beta_{m-1}q^{m-1})\\}$ induce a complete subgraph in
$\Gamma(R)$. Therefore any minimal labelling of $\Gamma(R)$ must have same
number of holes as $h$ admits. Thus $h$ is a required minimal labelling as
claimed. Therefore,

$\lambda(\Gamma(R))=p^{n-1}q^{m}+pq-3.$

For the remaining Cases: $n=2k,m=2l+1;n=2k+1,m=2l+1;n=2k+1,m=2l$, we follow
the same approach as in Case-I with the exception that zero-divisors in $W$
are classified in such a way that $S_{1}$ has the maximum cardinality with the
property that the vertices corresponding to $S_{1}$ induce a complete graph in
$\Gamma(R)$. ∎

######  Remark 4.1.

For cases: $m=2=n;m\geq 3,n=2;m=2,n\geq 3$, the $\lambda$-number of the graph
$\Gamma(\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}})$ is $pq^{2}+pq-5$;
$pq^{m}+pq-4$; $p^{n-1}q^{2}+pq-4$ respectively. These values can be obtained
by classifying the vertex set of
$\Gamma(\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{q^{m}})$ in the same manner as we
did in Theorem(18) and using Case-II of Theorem(17).

##  5 $\lambda$-number of Mixed Rings

This section is devoted to study the $\lambda$-number of zero-divisor graphs
of a class of mixed rings. We prove an interesting result which allows to
determine the $\lambda$-number and the corresponding minimal labelling of
Beck’s zero-divisor graph $\Gamma^{\prime}(R)$ from the zero-divisor graph
$\Gamma(R)$ of a ring R, provided $diam(\Gamma(R))<3$.

######  Theorem 19.

Let $n>1$ be a positive integer and let
$R\cong\mathbb{F}_{q}\times\mathbb{Z}_{p^{n}}$, where $\mathbb{F}_{q}$ is a
finite field of order $q$ and $p$ is a prime number. Then the following hold
for the graph $\Gamma(\mathbb{F}_{q}\times\mathbb{Z}_{p^{n}})$.

$\lambda(\Gamma(R))=\begin{cases}qp^{n-1}+p-3\text{ if }n\geq
3,~{}q>\frac{p^{n}-1}{p^{n-1}-1},\\\ p^{n}+p+q-3\text{ if }n\geq
3,~{}q\leq\frac{p^{n}-1}{p^{n-1}-1},\\\ p^{2}+p+q-4\text{ if }n=2,~{}q<p+1,\\\
2pq-2q-1~{}\text{ if }n=2,~{}q\geq p+1.\end{cases}$

###### Proof.

Recall that the non-zero zero-divisors of $\mathbb{Z}_{p^{n}}$ are given by,

$Z^{*}(\mathbb{Z}_{p^{n}})=\big{\\{}\alpha_{i}p^{i}:1\leq i\leq n-1\mbox{ and
}\gcd(\alpha_{i},p^{n-i})=1\big{\\}}$

. We classify the non-zero zero-divisors of $\Gamma(R)$ as follows,

$\displaystyle V^{1}$ $\displaystyle=$ $\displaystyle\big{\\{}(a,0):a(\neq
0)\in\mathbb{F}_{q}\big{\\}},$ $\displaystyle V^{2}$ $\displaystyle=$
$\displaystyle\big{\\{}(0,b):b(\neq 0)\in\mathbb{Z}_{p^{n}}\big{\\}},$
$\displaystyle V^{3}$ $\displaystyle=$
$\displaystyle\big{\\{}(a,\alpha_{i}p^{i}):a(\neq 0)\in\mathbb{F}_{q}\mbox{
and }\alpha_{i}p^{i}\in Z^{*}(\mathbb{Z}_{p^{n}})\big{\\}},$

where,

$\displaystyle|V^{1}|$ $\displaystyle=$ $\displaystyle q-1,$
$\displaystyle|V^{2}|$ $\displaystyle=$ $\displaystyle p^{n}-1,$
$\displaystyle|V^{3}|$ $\displaystyle=$ $\displaystyle(q-1)(p^{n-1}-1).$

Therefore, the order of $\Gamma(R)$ is $p^{n-1}(p+q-2)$. Clearly there are no
adjacencies between the vertices in $V^{1}$ and $V^{3}$, implying that
$V^{1}\cup V^{3}$ are independent set vertices of $\Gamma(R)$. However, the
vertex set $W=\\{(0,\alpha_{i}p^{i})\\}\subset V^{2}$, induces the subgraph
$\Gamma(\mathbb{Z}_{p^{n}})$ in $\Gamma(R)$. In addition, each vertex of
$V^{1}$ is adjacent to every vertex of $V^{2}$, and each vertex of $V^{3}$ is
adjacent to some vertex in $V^{2}$. Figure (5) shows a rough sketch of
$\Gamma(R)$, where the dashed lines connecting $\Gamma(\mathbb{Z}_{p^{n}})$
and $V^{3}$ indicate that not each vertex of $\Gamma(\mathbb{Z}_{p^{n}})$ is
adjacent to every vertex of $V^{3}$. We consider the following cases.
Case-1: $n\geq 3$
By Case-I of Theorem(17), we have
$\lambda(\Gamma(\mathbb{Z}_{p^{n}}))=p^{n-1}+p-3$. Let $f$ be its
corresponding minimal labelling. Define a $L(2,1)$-labelling
$g:\longrightarrow V(\Gamma{R})$ of $\Gamma(R)$ as,

$\displaystyle g(v)$ $\displaystyle=$ $\displaystyle f(v),\mbox{ where }v\in
W.$

Note that, $d(u,v)=3$, where $u\in V^{3}$ and $v\in V^{2}\setminus W$. This
implies that the vertices in $V^{3}$ can be labelled the same as the vertices
in $V^{2}\setminus W$. In addition, while labelling the vertices in $V^{3}$ we
start with vertices of the form $(a,\alpha p).$

$\displaystyle g(v_{i_{3}}^{3})$ $\displaystyle=$
$\displaystyle\max\limits_{v\in W}\\{f(v)\\}+i_{3}$ $\displaystyle=$
$\displaystyle\lambda(\Gamma(\mathbb{Z}_{p^{n}}))+i_{3},\mbox{where}~{}v_{i_{3}}^{3}\in
V^{3},1\leq i_{3}\leq|V^{3}|.$

Therefore,

$\displaystyle\max\limits_{v\in V^{3}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{3}|}^{3})$ $\displaystyle=$ $\displaystyle
p^{n-1}+p-3+(q-1)(p^{n-1}-1)$ $\displaystyle=$ $\displaystyle qp^{n-1}+p-q-2.$

For the vertices $v_{i_{2}}^{2}\in V^{2}\setminus W,1\leq
i_{2}\leq|V^{2}\setminus W|$, we define,

$\displaystyle g(v_{i_{2}}^{2})$ $\displaystyle=$
$\displaystyle\lambda(\Gamma(\mathbb{Z}_{p^{n}}))+i_{2}.$

This implies,

$\displaystyle\max\limits_{v\in V^{2}\setminus W}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{2}\setminus W|}^{2})$ $\displaystyle=$ $\displaystyle
p^{n}+p-3.$

Figure 5: A Rough sketch of $\Gamma(\mathbb{F}_{q}\times\mathbb{Z}_{p^{n}})$

The following subcases are considered for labelling the vertices in $V^{1}$.
Subcase-1.1: $q>\frac{p^{n}-1}{p^{n-1}-1}$
In this case $|V^{3}|>|V^{2}\setminus W|$, we label the vertices in $V^{1}$
as,

$\displaystyle
g(v_{i_{1}}^{1})=qp^{n-1}+p+i_{1}-q-2,\mbox{where}~{}v_{i_{1}}^{1}\in
V^{1},1\leq i_{1}\leq|V^{1}|.$

This implies,

$\displaystyle\max\limits_{v\in V^{1}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{1}|}^{1})$ $\displaystyle=$ $\displaystyle
qp^{n-1}+p-3.$

It is easy to verify that $g$ is well defined $L(2,1)$-labelling. Thus,

$\lambda(\Gamma(R))\leq qp^{n-1}+p-3.$

Subcase-1.2: $q\leq\frac{p^{n}-1}{p^{n-1}-1}$
Here $|V^{3}|\leq|V^{2}\setminus W|$, so we define $g$ as,

$\displaystyle g(v_{i_{1}}^{1})$ $\displaystyle=$ $\displaystyle
p^{n}+p+i_{1}-2,\mbox{ where }v_{i_{1}}^{1}\in V^{1},1\leq i_{1}\leq|V^{1}|.$

This implies,

$\displaystyle\max\limits_{v\in V^{1}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{1}|}^{1})$ $\displaystyle=$ $\displaystyle
p^{n}+p+q-3.$

As before $g$ is well defined $L(2,1)$-labelling. Therefore,

$\lambda(\Gamma(R))\leq p^{n}+p+q-3.$

Case-2: $n=2$
The subgraph induced by $W$ a complete in $\Gamma(R)$ and each vertex of
$V^{3}$ is adjacent to every vertex in $W$. Also, by Case-II of Theorem (17) ,
we have, $\lambda(\Gamma(\mathbb{Z}_{p^{2}}))=2p-4$. let $f$ be its
corresponding minimal labelling. Define $L(2,1)$-labelling $g:\longrightarrow
V(\Gamma(R))$ of $\Gamma(R)$ as,

$\displaystyle g(v)$ $\displaystyle=$ $\displaystyle f(v),\mbox{ where }v\in
W.$ $\displaystyle g(v_{i_{2}}^{2})$ $\displaystyle=$
$\displaystyle\lambda(\Gamma(\mathbb{Z}_{p^{2}}))+i_{2},\mbox{ where
}v_{i_{2}}^{2}\in V^{2}\setminus W,1\leq i_{2}\leq|V^{2}\setminus W|.$

This implies,

$\displaystyle\max\limits_{v\in V^{2}\setminus W}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{2}\setminus W|}^{2})$ $\displaystyle=$ $\displaystyle
p^{2}+p-4.$ $\displaystyle g(v_{i_{3}}^{3})$ $\displaystyle=$
$\displaystyle\lambda(\Gamma(\mathbb{Z}_{p^{2}}))+i_{3}+1,\mbox{ where
}v_{i_{3}}^{3}\in V^{3},1\leq i_{3}\leq|V^{3}|$

This implies,

$\displaystyle\max\limits_{v\in V^{3}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{3}|}^{3})$ $\displaystyle=$ $\displaystyle p+qp-q-2.$

To label the vertices in $V^{1}$, we consider the following subcases:
Subcase-2.1: $q<p+1$.
Then $|V^{3}|<|V^{2}\setminus W|$, we label vertices in $V^{1}$ as,

$\displaystyle g(v_{i_{1}}^{1})$ $\displaystyle=$ $\displaystyle
p^{2}+p+i_{1}-3,\mbox{ Where }v_{i_{1}}^{1}\in V^{1},1\leq i_{1}\leq|V^{1}|$

This implies,

$\displaystyle\max\limits_{v\in V^{1}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{1}|}^{1})$ $\displaystyle=$ $\displaystyle
p^{2}+p+q-4$

This completes the labelling of all the vertices of $\Gamma(R)$ and it is
Clear that $g$ is a well defined $L(2,1)$-labelling. Therefore,

$\lambda(\Gamma(R))\leq p^{2}+p+q-4$

Subcase-2.1:$q\geq p+1$
Here $|V^{3}|\geq|V^{2}\setminus W|$, we label the vertices in $V^{1}$ as,

$\displaystyle g(v_{i_{1}}^{1})$ $\displaystyle=$ $\displaystyle
p+qp+i_{1}-q-2\mbox{ Where }v_{i_{1}}^{1}\in V^{1},1\leq i_{1}\leq|V^{1}|$

This implies,

$\displaystyle\max\limits_{v\in V^{1}}\\{g(v)\\}$ $\displaystyle=$
$\displaystyle g(v_{|V^{1}|}^{1})$ $\displaystyle=$ $\displaystyle 2pq-2q-1$

This completes the labelling of all vertices of $\Gamma(R)$ and as before $g$
is a well defined $L(2,1)$-labelling. Therefore,

$\lambda(\Gamma(R))\leq 2pq-2q-1.$

The map $g$ is a minimal $L(2,1)$-labelling in all of the cases discussed
above, since $g$ admits the maximum number of multiplicities and the least
number of holes. ∎

The following result investigates the shift in the $\lambda$-number of the
graph with diameter less than 3, when a particular number of isolated vertices
and a dominant vertex are added to it. This subsequently aids in determining
the $\lambda$-number of Beck’s zero-divisor graph $\Gamma^{\prime}(R)$ of a
ring $R$.

######  Theorem 20.

Let $\mathcal{G}$ be a graph with diameter less than $3$ and
$\lambda(\mathcal{G})=k$. If $\mathcal{G}_{m+1}$ is the resultant graph when
$\mathcal{G}$ is added with $m$ isolated vertices and a dominating vertex,
then

$\lambda(\mathcal{G}_{m+1})=k+m+2.$

###### Proof.

let $f$ be a minimum labelling of $\mathcal{G}$ and let $u_{0}$ denote the
dominating vertex and $u_{1},u_{2},\cdots,u_{m}$ the isolated vertices. We
define $L(2,1)$-labelling $g$ on $\mathcal{G}_{m}$ as follows.

$\displaystyle g(u_{0})$ $\displaystyle=$ $\displaystyle 0.$ $\displaystyle
g(u_{i})$ $\displaystyle=$ $\displaystyle i+1,\mbox{where }1\leq i\leq m.$
$\displaystyle g(v)$ $\displaystyle=$ $\displaystyle f(v)+m+2,\mbox{ where
}v\in V(\mathcal{G}).$ $\displaystyle\mbox{Therefore},\max\limits_{v\in
V(\mathcal{G}_{m+1)}}\\{g(v)\\}$ $\displaystyle=$ $\displaystyle k+m+2.$

Since the diameter of $\mathcal{G}$ is less than 3, $f$ must be one to one,
which implies that g is well defined $L(2,1)$-labelling of
$\mathcal{G}_{m+1}$. Thus, $\lambda(\mathcal{G}_{m+1})\leq k+m+2$. However, if
we suppose that $\lambda(\mathcal{G}_{m+1})<k+m+2$, then $f$ is not a minimal
labelling of $\mathcal{G}$, a contradiction. ∎

The following result follows immediately from the preceding theorem.

######  Corollary 21.

If $R$ is a finite ring of order $n$ such that diameter of $\Gamma(R)$ is less
than $3$ with $\lambda(\Gamma(R))=k$, then
$\lambda(\Gamma^{\prime}(R))=k+n-m+1$, where $m$ is the order of $\Gamma(R)$.

###### Proof.

Since the set of vertices of $\Gamma^{\prime}(R)$ is $R$ and two vertices
$x,y\in R$ are adjacent in $\Gamma^{\prime}(R)$ if and only if $xy=0$.
Therefore from the structure of $\Gamma^{\prime}(R)$, it is clear that $0$ is
the dominating vertex in it and the set of $n-m-1$ units of $R$ represent the
independent set in $\Gamma^{\prime}(R)$. Therefore by Theorem (20),

$\lambda(\Gamma^{\prime}(R))=k+n-m+1.$

∎

The following example illustrates the preceding result and provides the
$\lambda$-number of the graph $\Gamma^{\prime}(\mathbb{Z}_{p^{n}})$.

######  Example 22.

Let $R\cong\mathbb{Z}_{p^{n}}$. Then $diam(\Gamma(\mathbb{Z}_{p^{n}})<3$ and
$|\mathbb{Z}_{p^{n}}|=p^{n}$. The order of $\Gamma(\mathbb{Z}_{p^{n}})$ is
$p^{n-1}-1$. Thus by Theorem (17),

$\lambda(\Gamma^{\prime}(\mathbb{Z}_{p^{n}}))=\begin{cases}p^{n}+p-1\text{ if
}n\geq 3,\\\ p^{2}+p-2\text{ if }n=2.\end{cases}$

##  6 Conclusion

In this research article, we studied partite truncation, a graph operation
that reduces a larger order $n$-partite graph to a graph with smaller order.
This contraction of the order allow us to determine the $\lambda$-number and
the corresponding minimal labelling of the $n$-partite graph from the
contracted graph. We exhibited that the zero-divisor graph realized by a
Boolean ring is a partite truncated graph of the zero-divisor graph realized
by a reduced ring. We determined the exact values of the $\lambda$-number and
the corresponding minimal labelling of zero-divisor graphs realized by some
classes of local and mixed rings. Finally, we proved an interesting result
that illustrates the deduction of $\lambda$-number of Beck’s zero divisor
graph $\Gamma^{\prime}(R)$ from the $\lambda$-number of the zero-divisor graph
$\Gamma(R)$.

## References

  * [1] D.F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999) 434 - 447.
  * [2] D. F. Anderson, R. Levy and J. Shapiro, Zero-divisor graphs, von Neumann regular rings, and Boolean algebras. J. Pure Appl. Algebra 180 (2003) 221 - 241.
  * [3] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988) 208 - 226.
  * [4] A. Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, American J. Math. 1(2) (1878) 174 - 176.
  * [5] J.P. Georges, D.W. Mauro and M.A. Whittlesey, Relating path covering to vertex labelings with a condition at distance two, Disc. Math 135 (1994) 103 - 111.
  * [6] J.P. Georges and D.W. Mauro, On regular graphs optimally labeled with a condition at distance two, SIAM J. Disc. Math (2003) 320 - 331.
  * [7] J. Griggs and R. Yeh, Labelling graphs with a condition at distance two, SIAM J. Disc. Math, 5 (1992) 586 - 595.
  * [8] A.V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, Contr. to gen. algebra 12(58) (2000) 3 - 6.
  * [9] A. Kelarev, C. Ras and S. Zhou, Distance labellings of Cayley graphs of semigroups, Semigroup Forum 91 (2015) 611 – 624.
  * [10] B.M. Kim, Y. Rho and B.C. Song, Lambda number for the direct product of some family of graphs, J. Comb. Optim. 33 (2017) 1257 - 1265.
  * [11] X. Ma, M. Feng and K. Wang, Lambda number of the power graph of a finite group, J. Algebra Comb. 53 (3) (2021) 743 - 754.
  * [12] E. Mazumdar and R. Raja, Group-annihilator graphs realised by finite abelian groups and its properties, Graphs and Combinatorics 38 (1) (2022) 1 - 24.
  * [13] F. D. Meyer and L. D. Meyer, Zero-divisor graphs of semigroups, J. Algebra 283 (2005) 190 - 198.
  * [14] K. Mönius, Eigenvalues of zero-divisor graphs of finite commutative rings, J. Algebra Comb. 54 (2021) 787 – 802
  * [15] R. Raja, Total perfect codes in graphs realized by commutative rings, Transactions of Comb. (2021) doi: 10.22108/toc.2021.122946.1727.
  * [16] S. P. Redmond, An ideal-based zero-divisor graph of a commutative ring, Commun. Algebra 31 (2003) 4425 - 4443.
  * [17] F.S. Roberts, T-colorings of graphs: recent results and open problems, Disc. Math. 93 (1991) 229 - 245.
  * [18] M. Whittlesey, J. Georges and D.W. Mauro, On the $\lambda$-number of $Q_{n}$ and related graphs, SIAM J. Discrete Math. 8 (1995) 499 - 506.
  * [19] S. Zahirović, The power graph of a torsion-free group determines the directed power graph, Disc. App. Math 305 (2021) 109 - 118.
  * [20] S. Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Disc. Math. 19 (2006) 985 - 1003.


# Tail bounds for sums of independent two-sided exponential random variables

Jiawei Li  (J.L.) Carnegie Mellon University; Pittsburgh, PA 15213, USA.
<EMAIL_ADDRESS>and  Tomasz Tkocz  (T.T.) Carnegie Mellon University;
Pittsburgh, PA 15213, USA<EMAIL_ADDRESS>
###### Abstract.

We establish upper and lower bounds with matching leading terms for tails of
weighted sums of two-sided exponential random variables. This extends Janson’s
recent results for one-sided exponentials.

TT’s research supported in part by NSF grant DMS-1955175.

2010 Mathematics Subject Classification. Primary 60E15; Secondary 60G50.

Key words. exponential distribution, gamma distribution, concentration, tail
bounds, sums of independent random variables.

##  1\. Introduction

Concentration inequalities establish conditions under which random variables
are _close_ to their _typical values_ (such as the expectation or median) and
provide quantitative probabilistic bounds. Their significance cannot be
overestimated, both across probability theory and in applications in related
areas (see [1, 2]). Particularly, such inequalities often concern sums of
independent random variables.

Let $X_{1},\ldots,X_{n}$ be independent exponential random variables, each
with mean $1$. Consider their weighted sum $S=\sum_{i=1}^{n}a_{i}X_{i}$ with
some positive weights $a_{1},\ldots,a_{n}$. Janson in [11] showed the
following concentration inequality: for every $t>1$,

(1) $\frac{1}{2e\alpha}\exp\big{(}-\alpha(t-1)\big{)}\leq\mathbb{P}\left(S\geq
t\mathbb{E}S\right)\leq\frac{1}{t}\exp\big{(}-\alpha(t-1-\log t)\big{)},$

where $\alpha=\frac{\mathbb{E}S}{\max_{i\leq n}a_{i}}$ (in fact, he derived
(1) from its analogue for the geometric distribution). Note that as
$t\to\infty$, the lower and upper bounds are of the same order $e^{-\alpha
t+o(t)}$. Moreover, $e^{-\alpha
t}=\mathbb{P}\left(X_{1}>t\frac{\mathbb{E}S}{\max_{i\leq n}a_{i}}\right)$. In
words, the asymptotic behaviour of the tail of the sum $S$ is the same as that
of one summand carrying the largest weight.

The goal of this short note is to exhibit that the same behaviour holds for
sums of two-sided exponentials (Laplace). Our main result reads as follows.

######  Theorem 1.

Let $X_{1},\ldots,X_{n}$ be independent standard two-sided exponential random
variables (i.e. with density $\frac{1}{2}e^{-|x|}$, $x\in\mathbb{R}$). Let
$S=\sum_{i=1}^{n}a_{i}X_{i}$ with $a_{1},\ldots,a_{n}$ positive. For every
$t>1$,

(2) $\frac{1}{57}\frac{1}{\sqrt{\alpha t}}\exp\big{(}-\alpha
t\big{)}\leq\mathbb{P}\left(S>t\sqrt{\operatorname{Var}(S)}\right)\leq\exp\left(-\frac{\alpha^{2}}{2}h\left(\frac{2t}{\alpha}\right)\right),$

where $\alpha=\frac{\sqrt{\operatorname{Var}(S)}}{\max_{i\leq
n}a_{i}}=\frac{\sqrt{2\sum_{i=1}^{n}a_{i}^{2}}}{\max_{i\leq n}a_{i}}$,
$h(u)=\sqrt{1+u^{2}}-1-\log\frac{1+\sqrt{1+u^{2}}}{2}$, $u>0$.

In (2), as $t\to\infty$, the lower and the upper bounds are of the same order,
$e^{-\alpha t+o(t)}$ (plainly, $h(u)=u+o(u)$).

Our proof of Theorem 1 presented in Section 2 is based on an observation that
two-sided exponentials are Gaussian mixtures, allowing to leverage (1) (this
idea has recently found numerous uses in convex geometry, see [4, 5, 15]). In
Section 3, we provide further generalisations of Janson’s inequality (1) to
certain nonnegative distributions, which also allows to extend Theorem 1 to a
more general framework. We finish in Section 4 with several remarks (for
instance, we deduce from (2) a formula for moments of $S$).

### Acknowledgements

We are indebted to an anonymous referee for many valuable comments, leading in
particular to the remarks in Sections 4.2 and 4.3.

##  2\. Proof of Theorem 1

For the upper bound, we begin with a standard Chernoff-type calculation.
Denote $\sigma=\sqrt{\operatorname{Var}(S)}=\sqrt{2\sum a_{i}^{2}}$. For
$\theta>0$, we have

$\mathbb{P}\left(S\geq t\sigma\right)\leq e^{-\theta
t\sigma}\mathbb{E}e^{\theta S}$

and

$\mathbb{E}e^{\theta S}=\prod\mathbb{E}e^{\theta
a_{i}X_{i}}=\prod\frac{1}{1-\theta^{2}a_{i}^{2}}=\exp\left\\{-\sum\log(1-\theta^{2}a_{i}^{2})\right\\},$

for $\theta<\frac{1}{a_{*}}$, $a_{*}=\max_{i\leq n}a_{i}$. By convexity,

$-\sum\log(1-\theta^{2}a_{i}^{2})\leq-\sum\frac{a_{i}^{2}}{a_{*}^{2}}\log(1-\theta^{2}a_{*}^{2}),$

so changing $\theta$ to $\theta/a_{*}$, for every $0<\theta<1$, we have

$\mathbb{P}\left(S\geq t\sigma\right)\leq\exp\left\\{-\theta
t\alpha-\frac{\alpha^{2}}{2}\log(1-\theta^{2})\right\\}=\exp\left\\{-\frac{\alpha^{2}}{2}\left(\frac{2t}{\alpha}\theta+\log(1-\theta^{2}\right)\right\\},$

where $\alpha=\frac{\sigma}{a_{*}}$. Optimising over $\theta$ and using

$\sup_{\theta\in(0,1)}\Big{(}\theta
u+\log(1-\theta^{2})\Big{)}=\sqrt{1+u^{2}}-1-\log\frac{1+\sqrt{1+u^{2}}}{2},\qquad
u>0$

gives the upper bound in (2) and thus finishes the argument.

For the lower bound, we shall use that a standard two-sided exponential random
variable with density $\frac{1}{2}e^{-|x|}$, $x\in\mathbb{R}$, has the same
distribution as $\sqrt{2Y}G$, where $Y$ is an exponential random variable with
mean $1$ and $G$ is a standard Gaussian random variable independent of $Y$
(this follows for instance by checking that the characteristic functions are
the same; see also a remark following Lemma 23 in [5]). This and the fact that
sums of independent Gaussians are Gaussian justify the following claim,
central to our argument.

######  Proposition 2.

The sum $S=\sum_{i=1}^{n}a_{i}X_{i}$ has the same distribution as
$(2\sum_{i=1}^{n}a_{i}^{2}Y_{i})^{1/2}G$ with $Y_{1},\ldots,Y_{n}$ being
independent mean $1$ exponential random variables, independent of the standard
Gaussian $G$.

Recall $\alpha=\frac{\sigma}{\max a_{i}}$. Fix $t>1$. By Proposition 2, for
$\theta>0$, we have

$\displaystyle\mathbb{P}\left(S\geq t\sigma\right)=\mathbb{P}\left(\sqrt{2\sum
a_{i}^{2}Y_{i}}G\geq t\sigma\right)$
$\displaystyle\geq\mathbb{P}\left(\sqrt{2\sum a_{i}^{2}Y_{i}}\geq\sqrt{\theta
t\sigma^{2}},\ G\geq\sqrt{\theta^{-1}t}\right)$
$\displaystyle=\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\frac{1}{2}\theta
t\sigma^{2}\right)\mathbb{P}\left(G\geq\sqrt{\theta^{-1}t}\right).$

_Case 1._ $t\geq\alpha$. With hindsight, choose $\theta=\frac{1}{\alpha}$.
Applying (1) to the first term yields

$\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\frac{1}{2}\theta
t\sigma^{2}\right)=\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\frac{t}{\alpha}\sum
a_{i}^{2}\right)\geq\frac{1}{e\alpha^{2}}\exp\left\\{-\frac{\alpha^{2}}{2}\left(\frac{t}{\alpha}-1\right)\right\\}.$

For the second term we use a standard bound on the Gaussian tail,

$\displaystyle\mathbb{P}\left(G>u\right)$
$\displaystyle\geq\frac{1}{\sqrt{2\pi}}\frac{u}{u^{2}+1}e^{-u^{2}/2},\qquad\
u>0,$ (3)
$\displaystyle\geq\frac{1}{2\sqrt{2\pi}}\frac{1}{u}e^{-u^{2}/2},\qquad\qquad
u\geq 1.$

and as $\theta^{-1}t=\alpha t\geq\sqrt{2}$, (3) applies in our case. Combining
the above estimates gives

$\displaystyle\mathbb{P}\left(S\geq
t\sigma\right)\geq\frac{\exp(\alpha^{2}/2)}{2\sqrt{2\pi}e\alpha^{2}}\frac{1}{\sqrt{\alpha
t}}\exp\big{(}-\alpha t\big{)}\geq\frac{1}{4\sqrt{2\pi}}\frac{1}{\sqrt{\alpha
t}}\exp\big{(}-\alpha t\big{)},$

where in the last inequality we use that
$\inf_{x>1}\frac{1}{x}e^{x/2}=\frac{e}{2}$.

_Case 2._ $t\leq\alpha$. With hindsight, choose $\theta=\frac{1}{t}$. Then

$\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\frac{1}{2}\theta
t\sigma^{2}\right)=\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\sum
a_{i}^{2}\right).$

To further lower-bound the last expresion, we use a standard Paley-Zygmund
type inequality (see, e.g. Lemma 3.2 in [17]).

######  Lemma 3.

Let $Z_{1},\ldots,Z_{n}$ be independent mean $0$ random variables such that
$\mathbb{E}Z_{i}^{4}\leq C(\mathbb{E}Z_{i}^{2})^{2}$ for all $1\leq i\leq n$
for some constant $C\geq 1$. Then for $Z=Z_{1}+\dots+Z_{n}$,

$\mathbb{P}\left(Z\geq 0\right)\geq\frac{1}{16^{1/3}\max\\{C,3\\}}.$

###### Proof.

We can assume that $\mathbb{P}\left(Z=0\right)<1$. Since $Z$ has mean $0$,

$\mathbb{E}|Z|=2\mathbb{E}Z\textbf{1}_{Z\geq 0}\leq
2(\mathbb{E}Z^{4})^{1/4}\mathbb{P}\left(Z\geq 0\right)^{3/4}.$

Moreover, by Hölder’s inequality,
$\mathbb{E}|Z|\geq\frac{(\mathbb{E}Z^{2})^{3/2}}{(\mathbb{E}Z^{4})^{1/2}}$, so

$\mathbb{P}\left(Z\geq 0\right)\geq
16^{-1/3}\frac{(\mathbb{E}Z^{2})^{2}}{\mathbb{E}Z^{4}}.$

Using independence, $\mathbb{E}Z_{i}=0$ and the assumption
$\mathbb{E}Z_{i}^{4}\leq C(\mathbb{E}Z_{i}^{2})^{2}$, we have

$\displaystyle\mathbb{E}Z^{4}=\sum_{i=1}^{n}\mathbb{E}Z_{i}^{4}+6\sum_{i<j}\mathbb{E}Z_{i}^{2}\mathbb{E}Z_{j}^{2}$
$\displaystyle\leq\max\\{C,3\\}\left(\sum_{i=1}^{n}(\mathbb{E}Z_{i}^{2})^{2}+2\sum_{i<j}\mathbb{E}Z_{i}^{2}\mathbb{E}Z_{j}^{2}\right)$
$\displaystyle=\max\\{C,3\\}(\mathbb{E}Z^{2})^{2}.$

∎

Take $Z_{i}=a_{i}(Y_{i}-1)$. We have, $\mathbb{E}(Y_{i}-1)^{2}=1$,
$\mathbb{E}(X_{i}-\gamma)^{4}=9$. Thus we can apply Lemma 3 with $C=9$ and
obtain

(4) $\mathbb{P}\left(\sum a_{i}^{2}Y_{i}\geq\sum
a_{i}^{2}\right)\geq\frac{1}{9\cdot 16^{1/3}}.$

By (3),

$\mathbb{P}\left(G\geq\sqrt{\theta^{-1}t}\right)=\mathbb{P}\left(G\geq
t\right)\geq\frac{1}{2\sqrt{2\pi}}\frac{1}{t}e^{-t^{2}/2}\geq\frac{1}{2\sqrt{2\pi}}\frac{1}{\sqrt{\alpha
t}}e^{-\alpha t/2},$

where in the last inequality we use that in this case $t\leq\sqrt{\alpha t}$.
Moreover, since $\alpha t\geq\sqrt{2}$, $e^{-\alpha t/2}\geq
e^{1/\sqrt{2}}e^{-\alpha t}$. Thus,

$\mathbb{P}\left(S\geq t\sigma\right)\geq\frac{e^{1/\sqrt{2}}}{18\cdot
16^{1/3}\sqrt{2\pi}}\frac{1}{\sqrt{\alpha t}}\exp\big{(}-\alpha
t\big{)}>\frac{1}{57}\frac{1}{\sqrt{\alpha t}}\exp\big{(}-\alpha t\big{)}.$

Combining Case 1 and 2 finishes the proof of the lower bound in (2) and thus
the proof proof of Theorem 1 is complete. $\square$

##  3\. Generalisations

In this section, we provide general tail bounds for weighted sums of
nonnegative random variables which for certain distributions allow to capture
the same bahaviour as featured in Janson’s inequality (1), viz. asymptotically
the sum has the same tail as the summand carrying the largest weight.

######  Theorem 4.

Let $X_{1},\ldots,X_{n}$ be i.i.d. nonnegative random variables,
$\mu=\mathbb{E}X_{1}$. Let $S=\sum_{i=1}^{n}a_{i}X_{i}$ with
$a_{1},\ldots,a_{n}$ positive. For every $t>1$,

(5)
$\mathbb{P}\left(S\geq\mathbb{E}S\right)r((t-1)\alpha\mu)\leq\mathbb{P}\left(S>t\mathbb{E}S\right)\leq\exp\left\\{-\alpha
I(\mu t)\right\\},$

where $\alpha=\frac{\sum_{i=1}^{n}a_{i}}{\max_{i\leq n}a_{i}}$, for $v>0$,

(6)
$r(v)=\inf_{u>0}\frac{\mathbb{P}\left(X_{1}>u+v\right)}{\mathbb{P}\left(X_{1}>u\right)}$

and for $t>0$,

(7) $I(t)=\sup_{\theta>0}\left(t\theta-\log\mathbb{E}e^{\theta X_{1}}\right).$

Before presenting the proof, we look at the example of the exponential and
gamma distribution.

###  3.1. Examples

When the $X_{i}$ are exponential rate $1$ random variables, $I(t)=t-1-\log t$,
$r(v)=e^{-v}$, $\mathbb{P}\left(S\geq\mathbb{E}S\right)\geq\frac{1}{9\cdot
16^{1/3}}$ (see (4)) and we obtain

$\frac{1}{9\cdot
16^{1/3}}e^{-\alpha(t-1)}\leq\mathbb{P}\left(S>t\mathbb{E}S\right)\leq
e^{-\alpha(t-1-\log t)}.$

Comparing with (1), the extra factor $\frac{1}{t}$ in the upper bound was
obtained in [11] through rather delicate computations for the moment
generating function specific for the exponential distribution. Since
$\alpha\geq 1$, our lower bound up to a universal constant recovers the one
from (1) (improves on it as long as $\alpha>9\cdot 16^{1/3}/(2e)$ and is worse
otherwise). Along the same lines, for the gamma distribution with parameter
$\gamma>0$ (i.e. with density $\Gamma(\gamma)^{-1}x^{\gamma-1}e^{-x}$, $x>0$),
we have $\mu=\gamma$, $I(t\mu)=\gamma(t-1-\log t)$ and with some extra work,

$r_{\gamma}(v)=\begin{cases}\frac{1}{2\Gamma(\gamma)}\min\\{v^{\gamma-1},1\\}e^{-v},&0<\gamma<1,\\\
e^{-v},&\gamma\geq 1.\end{cases}$

Moreover, via Lemma 3,
$\mathbb{P}\left(S\geq\mathbb{E}S\right)>\frac{1}{3\cdot
16^{1/3}(1+2\gamma^{-1})}$. Then (5) yields

(8) $\frac{1}{3\cdot
16^{1/3}(1+2\gamma^{-1})}r_{\gamma}\big{(}\alpha\gamma(t-1)\big{)}\leq\mathbb{P}\left(S>t\mathbb{E}S\right)\leq\exp\big{(}-\alpha\gamma(t-1-\log
t)\big{)}.$

In particular, $\mathbb{P}\left(S>t\mathbb{E}S\right)=\exp\\{-\alpha\gamma
t+o(t)\\}$ as $t\to\infty$. It would perhaps be interesting to find a larger
class of distributions for which the upper and lower bounds from (5) are
asymptotically tight. For more precise results involving the variance of $S$
for weighted sums of independent Gamma random variables (not necessarily with
the same parameter), we refer to Theorem 2.57 in [1].

###  3.2. Proof of Theorem 4: the upper bound

For the log-moment generating function
$\psi\colon\mathbb{R}\to(-\infty,\infty]$,

$\psi(u)=\log\mathbb{E}e^{uX_{1}},\qquad u\in\mathbb{R},$

we have $\psi(0)=0$, $\psi$ is convex (by Hölder’s inequality). Thus, by the
monotonicity of slopes of convex functions,

(9) $\mathbb{R}\ni u\mapsto\frac{\psi(u)}{u}\ \ \text{is nondecreasing}.$

This is what Janson’s proof specified to the case of exponentials relies on.
We turn to estimating the tails (using of course Chernoff-type bounds). Fix
$t>1$. For $\theta>0$, we have

$\displaystyle\mathbb{P}\left(S\geq
t\mathbb{E}S\right)=\mathbb{P}\left(e^{\theta S}\geq e^{\theta
t\mathbb{E}S}\right)\leq e^{-\theta t\mathbb{E}S}\mathbb{E}e^{\theta S}$
$\displaystyle=e^{-\theta t\mathbb{E}S}\prod_{i=1}^{n}\mathbb{E}e^{\theta
a_{i}X_{i}}$ $\displaystyle=\exp\left\\{-\theta
t\mathbb{E}S+\sum_{i=1}^{n}\psi(\theta a_{i})\right\\}.$

Let $a_{*}=\max_{i\leq n}a_{i}$. Thanks to (9),

$\sum_{i=1}^{n}\psi(\theta a_{i})=\sum_{i=1}^{n}(\theta
a_{i})\frac{\psi(\theta a_{i})}{\theta a_{i}}\leq\sum_{i=1}^{n}(\theta
a_{i})\frac{\psi(\theta a_{*})}{\theta
a_{*}}=\frac{\sum_{i=1}^{n}a_{i}}{a_{*}}\psi(\theta a_{*})=\alpha\psi(\theta
a_{*}),$

where we set $\alpha=\frac{\sum_{i=1}^{n}a_{i}}{a_{*}}$. Note
$\mathbb{E}S=\mu\sum a_{i}=\mu\alpha a_{*}$. We obtain,

$\mathbb{P}\left(S\geq t\mathbb{E}S\right)\leq\exp\left\\{-\theta
t\mathbb{E}S+\alpha\psi(\theta
a_{*})\right\\}=\exp\left\\{-\alpha\left(t\mu\theta a_{*}-\psi(\theta
a_{*})\right)\right\\},$

so optimising over $\theta$ gives the upper bound of (5). $\square$

###  3.3. Proof of Theorem 4: the lower bound

We follow a general idea from [11]. The whole argument is based on the
following simple lemma.

######  Lemma 5.

Suppose $X$ and $Y$ are independent random variables and $Y$ is such that
$\mathbb{P}\left(Y\geq u+v\right)\geq r(v)\mathbb{P}\left(Y\geq u\right)$ for
all $u\in\mathbb{R}$ and $v>0$, for some function $r(v)$. Then
$\mathbb{P}\left(X+Y\geq u+v\right)\geq r(v)\mathbb{P}\left(X+Y\geq u\right)$
for all $u\in\mathbb{R}$ and $v>0$.

###### Proof.

By independence, conditioning on $X$, we get

$\displaystyle\mathbb{P}\left(X+Y\geq
u+v\right)=\mathbb{E}_{X}\mathbb{P}_{Y}(Y\geq u-X+v)$ $\displaystyle\geq
r(v)\mathbb{E}_{X}\mathbb{P}_{Y}(Y\geq u-X)$
$\displaystyle=r(v)\mathbb{P}\left(X+Y\geq u\right).$

∎

Let $S=\sum_{i=1}^{n}a_{i}X_{i}$ be the weighted sum of i.i.d. random
variables and without loss of generality let us assume $a_{1}=\max_{i\leq
n}a_{i}$. Fix $t>1$. We write $S=S^{\prime}+a_{1}X_{1}$, with
$S^{\prime}=\sum_{i=2}^{n}a_{i}X_{i}$. Note that the definition of function
$r$ from (6) remains unchanged if the infimum is taken over all
$u\in\mathbb{R}$ (since $X_{1}$ is nonnegative). Thus Lemma 5 gives

$\displaystyle\mathbb{P}\left(S\geq t\mathbb{E}S\right)$
$\displaystyle=\mathbb{P}\left(S\geq\mathbb{E}S+(t-1)\mathbb{E}S\right)\geq
r\left((t-1)\frac{\mathbb{E}S}{a_{1}}\right)\mathbb{P}\left(S\geq\mathbb{E}S\right),$

as desired. $\square$

##  4\. Further remarks

###  4.1. Moments

The upper bound from (2) allows us to recover precise estimates for moments (a
special case of Gluskin and Kwapień results from [8]), with a straightforward
proof. Here and throughout, $\|a\|_{p}=(\sum_{i=1}^{n}|a_{i}|^{p})^{1/p}$
denotes the $p$-norm of a sequence $a=(a_{1},\ldots,a_{n})$, $p>0$, and
$\|a\|_{\infty}=\max_{i\leq n}|a_{i}|$.

######  Theorem 6 (Gluskin and Kwapień, [8]).

Under the assumptions of Theorem 1, for every $p\geq 2$,

(10)
$\frac{\sqrt{2e}}{\sqrt{2e}+1}\big{(}p\|a\|_{\infty}+\sqrt{p}\|a\|_{2}\big{)}\leq\left(\mathbb{E}\left|S\right|^{p}\right)^{1/p}\leq
4\sqrt{2}\big{(}p\|a\|_{\infty}+\sqrt{p}\|a\|_{2}\big{)}.$

###### Proof.

For the upper bound, letting
$\tilde{S}=\frac{S}{\sqrt{\operatorname{Var}(S)}}$ and using (2), we get

$\displaystyle\mathbb{E}|\tilde{S}|^{p}=\int_{0}^{\infty}pt^{p-1}\mathbb{P}\left(|\tilde{S}|>t\right)\mathrm{d}t\leq\int_{0}^{1}pt^{p-1}\mathrm{d}t+2\int_{1}^{\infty}pt^{p-1}\exp\left(-\frac{\alpha^{2}}{2}h\left(\frac{2t}{\alpha}\right)\right)\mathrm{d}t.$

We check that as $u$ increases, $h(u)$ behaves first quadratically, then
linearly. More precisely,

(11) $h(u)\geq\frac{1}{5}u^{2},\quad u\in(0,\sqrt{2}),\qquad
h(u)\geq\frac{1}{4}u,\quad u\in(\sqrt{2},\infty).$

Thus the second integral $\int_{1}^{\infty}\ldots\mathrm{d}t$ can be upper
bounded by (recall that $\operatorname{Var}(S)=2\|a\|_{2}^{2}$,
$\frac{\alpha}{\sqrt{2}}=\frac{\|a\|_{2}}{\|a\|_{\infty}}>1$),

$\displaystyle\int_{1}^{\alpha/\sqrt{2}}pt^{p-1}\exp\left(-\frac{\alpha^{2}}{2}\frac{1}{5}\left(\frac{2t}{\alpha}\right)^{2}\right)\mathrm{d}t+\int_{\alpha/\sqrt{2}}^{\infty}pt^{p-1}\exp\left(-\frac{\alpha^{2}}{2}\frac{1}{4}\frac{2t}{\alpha}\right)\mathrm{d}t$
$\displaystyle\leq\int_{0}^{\infty}pt^{p-1}\exp\left(-\frac{2}{5}t^{2}\right)\mathrm{d}t+\int_{0}^{\infty}pt^{p-1}\exp\left(-\frac{1}{4}\alpha
t\right)\mathrm{d}t$
$\displaystyle=\left(\frac{5}{2}\right)^{p/2}\Gamma\left(\frac{p}{2}+1\right)+\left(\frac{4}{\alpha}\right)^{p}\Gamma(p+1).$

Using $\Gamma(x+1)\leq x^{x}$, $x\geq 1$, yields

$\displaystyle\left(\mathbb{E}|S|^{p}\right)^{1/p}=\sqrt{2}\|a\|_{2}\left(\mathbb{E}|\tilde{S}|^{p}\right)^{1/p}$
$\displaystyle\leq\sqrt{2}\|a\|_{2}\left(1+2\left(\frac{5p}{4}\right)^{p/2}+2\left(\frac{4p}{\alpha}\right)^{p}\right)^{1/p}$
$\displaystyle\leq 4\sqrt{2}(p\|a\|_{\infty}+\sqrt{p}\|a\|_{2}).$

For the lower bound, suppose $a_{1}=\|a\|_{\infty}$. Then, by independence and
Jensen’s inequality,

$\mathbb{E}|S|^{p}\geq\mathbb{E}\big{|}a_{1}X_{1}+\mathbb{E}(a_{2}X_{2}+\dots+a_{n}X_{n})\big{|}^{p}=a_{1}^{p}\mathbb{E}|X_{1}|^{p}=a_{1}^{p}\Gamma(p+1).$

Using $\Gamma(x+1)^{1/x}\geq x/e$, $x>0$ (Stirling’s formula, [10]), this
gives

$(\mathbb{E}|S|^{p})^{1/p}\geq\frac{p}{e}\|a\|_{\infty}.$

On the other hand, by Proposition 2, and Jensen’s inequality,

$\mathbb{E}|S|^{p}=\mathbb{E}\left(2\sum
a_{i}^{2}Y_{i}\right)^{p/2}\mathbb{E}|G|^{p}\geq\left(2\sum
a_{i}^{2}\right)^{p/2}\mathbb{E}|G|^{p}.$

Using $\mathbb{E}|G|^{p}\geq(p/e)^{p/2}$, $p\geq 1$ (again, by e.g. Stirling’s
approximation), we obtain

$(\mathbb{E}|S|^{p})^{1/p}\geq\sqrt{\frac{2}{e}}\sqrt{p}\|a\|_{2}.$

Combining gives

$(\mathbb{E}|S|^{p})^{1/p}\geq\max\left\\{\frac{1}{e}p\|a\|_{\infty},\sqrt{\frac{2}{e}}\sqrt{p}\|a\|_{2}\right\\}\geq\frac{\sqrt{2e}}{\sqrt{2e}+1}\left(p\|a\|_{\infty}+\sqrt{p}\|a\|_{2}\right),$

which finishes the proof. ∎

######  Remark 7.

Using Markov and Payley-Zygmund type inequalities, it is possible to recover
two-sided tail bounds from moment estimates (like (10)), but incurring loss of
(universal) constants in the exponents, as it is done in e.g. [8], or [9].

###  4.2. Upper bounds on upper tails from S-inequalities

Let $S$ be as in (1). The upper bound in (1) for $t=1$ is trivial, whereas as
a result of Lemma 3, viz. (4), we obtain
$\mathbb{P}\left(S\geq\mathbb{E}S\right)\in(\frac{1}{24},\frac{23}{24})$,
where the upper bound $\frac{23}{24}$ is obtained by applying Lemma 3 to $-Z$.
Letting $a>0$ be such that
$\mathbb{P}\left(S\geq\mathbb{E}S\right)=\mathbb{P}\left(X_{1}\geq
a\right)=e^{-a}$, by the S-inequality for the two-sided product exponential
measure and the set $\\{x\in\mathbb{R}^{n},\ \sum
a_{i}|x_{i}|\leq\mathbb{E}S\\}$ (Theorem 2 in [13]), we obtain that for every
$t\geq 1$,

(12) $\mathbb{P}\left(S\geq t\mathbb{E}S\right)\leq\mathbb{P}\left(X_{1}\geq
ta\right)=e^{-at}\leq\left(\frac{23}{24}\right)^{t}.$

This provides an improvement of (1) for small enough $t$ (of course the point
of (1) is that it is optimal for large $t$). The same can be said about the
upper bound in (8) for $\gamma\geq 1$ (in view of (4) and the results from
[14] for gamma distributions with parameter $\gamma\geq 1$). Complimentary to
such concentration bounds are small ball probability estimates and anti-
concentration phenomena, typically treating however the regime of
$t=O(1/\mathbb{E}S)$ (under our normalisation). We refer for instance to the
comprehensive survey [16] of Nguyen and Vu, as well as the recent work [12] of
Li and Madiman for further results and references. Specific reversals of (12)
concerning the exponential measure can be found e.g. in [5] (Corollary 15),
[18] (Proposition 3.4), [19] ((5.5) and Theorem 5.7).

###  4.3. Heavy-tailed distributions

Janson’s as well as this paper’s techniques strongly rely on Chernoff-type
bounds involving exponential moments to establish the _largest-weight_ summand
tail asymptotics from (1) or (2). Interestingly, when the exponential moments
do _not_ exist, i.e. for heavy-tailed distributions, under some natural
additional assumptions (subexponential distributions), a different phenomenon
occurs: in the simplest case of i.i.d. summands, we have

$\mathbb{P}\left(X_{1}+\dots+X_{n}>t\right)=(1+o(1))\mathbb{P}\left(\max_{i\leq
n}X_{i}>t\right)\qquad\text{as }t\to\infty,$

often called the single big jump or catastrophe principle. We refer to the
monograph [7] (Chapters 3.1 and 5.1), as well as the papers [3] and [6] for
extensions including weighted sums and continuous time respectively.

###  4.4. Theorem 1 in a more general framework

A careful inspection of the proof of Theorem 1 shows that thanks to Theorem
2.57 from [1] (or the simpler but weaker bound (8)), the former can be
extended to the case where the $X_{i}$ have the same distribution as
$\sqrt{Y_{i}}G_{i}$ with the $Y_{i}$ being i.i.d. gamma random variables and
the $G_{i}$ independent standard Gaussian. For simplicity, we have decided to
present it for the symmetric exponentials.

## References

  * [1] Bercu, B., Delyon, B., Rio, E., Concentration inequalities for sums and martingales. SpringerBriefs in Mathematics. Springer, Cham, 2015.
  * [2] Boucheron, S., Lugosi, G., Massart, P., Concentration inequalities. A nonasymptotic theory of independence. With a foreword by Michel Ledoux. Oxford University Press, Oxford, 2013.
  * [3] Chen, Y., Ng, K. W., Tang, Q., Weighted sums of subexponential random variables and their maxima. Adv. in Appl. Probab. 37 (2005), no. 2, 510–522.
  * [4] Eskenazis, A. On Extremal Sections of Subspaces of $L_{p}$. Discrete Comput. Geom. (2019).
  * [5] Eskenazis, A., Nayar, P., Tkocz, T., Gaussian mixtures: entropy and geometric inequalities, Ann. Probab. 46 (2018), no. 5, 2908–2945.
  * [6] Foss, S., Konstantopoulos, T., Zachary, S., Discrete and continuous time modulated random walks with heavy-tailed increments. J. Theoret. Probab. 20 (2007), no. 3, 581–612.
  * [7] Foss, S., Korshunov, D., Zachary, S., An introduction to heavy-tailed and subexponential distributions. Second edition. Springer Series in Operations Research and Financial Engineering. Springer, New York, 2013.
  * [8] Gluskin, E. D., Kwapień, S., Tail and moment estimates for sums of independent random variables with logarithmically concave tails. Studia Math. 114 (1995), no. 3, 303–309.
  * [9] Hitczenko, P., Montgomery-Smith, S., A note on sums of independent random variables. Advances in stochastic inequalities (Atlanta, GA, 1997), 69–73,
  * [10] Jameson, G., A simple proof of Stirling’s formula for the gamma function. Math. Gaz. 99 (2015), no. 544, 68–74.
  * [11] Janson, S., Tail bounds for sums of geometric and exponential variables. Statist. Probab. Lett. 135 (2018), 1–6.
  * [12] Li, J., Madiman, M., A combinatorial approach to small ball inequalities for sums and differences. Combin. Probab. Comput. 28 (2019), no. 1, 100–129.
  * [13] Nayar, P., Tkocz, T., The unconditional case of the complex S-inequality. Israel J. Math. 197 (2013), no. 1, 99–106.
  * [14] Nayar, P., Tkocz, T., S-inequality for certain product measures. Math. Nachr. 287 (2014), no. 4, 398–404.
  * [15] Nayar, P., Tkocz, T., On a convexity property of sections of the cross-polytope. Proc. Amer. Math. Soc. 148 (2020), no. 3, 1271–1278.
  * [16] Nguyen, H. H., Vu, V. H., Small ball probability, inverse theorems, and applications. Erdös centennial, 409–463, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013.
  * [17] Oleszkiewicz, K., Precise moment and tail bounds for Rademacher sums in terms of weak parameters. Israel J. Math. 203 (2014), no. 1, 429–443.
  * [18] Paouris, G., Valettas, P., A Gaussian small deviation inequality for convex functions. Ann. Probab. 46 (2018), no. 3, 1441–1454.
  * [19] Paouris, G., Valettas, P., Variance estimates and almost Euclidean structure. Adv. Geom. 19 (2019), no. 2, 165–189.