# Optimal radio labelings of the Cartesian product of the generalized Peterson
graph and tree

Payal Vasoya
Gujarat Technological University, Ahmedabad - 383 824, Gujarat (India)
E-mail<EMAIL_ADDRESS>

Devsi Bantva
Lukhdhirji Engineering College, Morvi - 363 642, Gujarat (India)
E-mail<EMAIL_ADDRESS>
###### Abstract

A radio labeling of a graph $G$ is a function
$f:V(G)\rightarrow\\{0,1,2,\ldots\\}$ such that $|f(u)-f(v)|\geq{\rm
diam}(G)+1-d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio
number of $G$, denoted by ${\rm rn}(G)$, is the smallest number $k$ such that
$G$ has radio labeling $f$ with max$\\{f(v):v\in V(G)\\}$ = $k$. In this
paper, we give a lower bound for the radio number for the Cartesian product of
the generalized Petersen graph and tree. We present two necessary and
sufficient conditions, and three other sufficient conditions to achieve the
lower bound. Using these results, we determine the radio number for the
Cartesian product of the Peterson graph and stars.

Keywords: Radio labeling, radio number, Cartesian product of graphs,
Generalized Petersen graph, tree.

##  1 Introduction

The channel assignment problem, introduced by Hale in [11], deals with the
task of assigning channels to the radio transmitters so that the interference
constraints between two transmitters is satisfied and the span of channels
used is kept to a minimum. The interference between two transmitters is
primarily dependent on the proximity of transmitters. The closer the two
transmitters are, higher the interference is and vice-versa. Initially, only
two levels of interference were considered, namely minor and major, and
accordingly two transmitters are classified as close and very close
transmitters.

The problem of assignment of channels to transmitters is studied using a graph
model in which transmitters are represented by vertices of a graph such that
two vertices are adjacent if major interference occurs and at distance two if
minor interference occurs between those two corresponding transmitters. It is
assumed that there is no interference if the vertices are distance two apart
in the graph model. Roberts[16] suggested that a pair of transmitters having
minor interference must receive different channels and a pair of transmitters
having major interference must receive channels that are at least two apart.
Motivated through this, Griggs and Yeh[10] introduced $L(2,1)$-labeling which
is also known as distance two labeling as follows: An _$L(2,1)$ -labeling_ (or
distance two labeling) of a graph $G=(V(G),E(G))$ is a function
$f:V(G)\rightarrow\\{0,1,2,...\\}$ such that for each pair of distinct
vertices $u$ and $v$ satisfies the following conditions:

$|f(u)-f(v)|\geq\left\\{\begin{array}[]{ll}2,&\mbox{if }d(u,v)=1,\\\
1,&\mbox{if }d(u,v)=2.\end{array}\right.$

where $d(u,v)$ is the distance between $u$ and $v$ in $G$. The span of $f$ is
defined as ${\rm span}(f)=\max\\{|f(u)-f(v)|:u,v\in V(G)\\}$ and the
_$\lambda$ -number_ (or the $\lambda_{2,1}$-number) of $G$, denoted by
$\lambda(G)$ (or $\lambda_{2,1}(G)$), is the minimum span of an
$L(2,1)$-labeling of $G$. An $L(2,1)$-labeling $f$ of $G$ is called optimal if
${\rm span}(f)=\lambda(G)$. The readers can refer the survey article [6] and
[20] for recent results on $L(2,1)$-labeling of graph $G$.

It is observed that the interference among transmitters might go beyond two
levels. A radio labeling extends the level of interference considered in
$L(2,1)$-labeling from two to the largest possible - the diameter of G.
Motivated through this, Chartrand et al.[7, 8] introduced the concept of radio
labeling of a graph as follows:

######  Definition 1.1.

A _radio labeling_ of a graph $G$ is a mapping
$f:V(G)\rightarrow\\{0,1,2,\ldots\\}$ such that for every pair of distinct
vertices $u,v$ of $G$,

$|f(u)-f(v)|\geq{\rm diam}(G)+1-d(u,v).$

The integer $f(u)$ is called the _label_ of $u$ under $f$, and the _span_ of
$f$ is defined as

${\rm span}(f)=\max\\{|f(u)-f(v)|:u,v\in V(G)\\}.$

The _radio number_ of $G$ is defined as

${\rm rn}(G)=\min_{f}{\rm span}(f)$

with minimum taken over all radio labelings $f$ of $G$. A radio labeling $f$
of $G$ is called _optimal_ if ${\rm span}(f)={\rm rn}(G)$. If ${\rm
diam}(G)=2$ then radio labeling of $G$ is same as $L(2,1)$-labeling of $G$.

A radio labeling always assign label $0$ to some vertex then the maximum label
used is a ${\rm span}(f)$. It is an interesting and challenging task to find
radio number for the graph. The radio labeling problem is well studied for
trees by several authors; refer [3, 12, 13, 14, 15]. The radio labeling is
studied only for handful graph families other than trees. The radio number for
all graphs of order $n$ and diameter $n-2$ is determined by Benson et al. in
[4]. Cada et al. studied the radio number of distance graph in [5]. Saha and
Panigrahi studied the radio number for toroidal grids and square of graphs in
[17] and [18], respectively. Bantva and Liu gave a lower bound for the radio
number of block graphs and presented three necessary and sufficient condition
to achieve the lower bound in [1]. The same authors also discussed the radio
number of line graph of trees which are block graphs. Das et al. gave a
technique to find a lower bound for the radio number of graphs in [9]. In
[21], Zhou discussed the problem of radio channel assignment for the network
modelled by Cayley graphs. Bantva and Liu discussed the radio number of
Cartesian product of two trees in [2].

The paper is structured as follows. In Section 2, we define necessary terms
and notations required for the present work. In Section 3, we give a lower
bound for the radio number of the Cartesian product of the generalized
Peterson graph and a tree. We present two necessary and sufficient conditions
and, three other sufficient conditions for a lower bound to be tight. Finally,
using these results, we determine the radio number for the Cartesian product
of the Peterson graph and stars.

##  2 Preliminaries

In this section, we define necessary terms and notations which will be used in
the present work. We follow [19] for standard graph theoretic definitions and
notations. The distance between two vertices $u$ and $v$ in a graph $G$,
denoted by $d(u,v)$, is the length of the shortest path joining $u$ and $v$ in
a graph $G$. The diameter of a graph $G$ is ${\rm
diam}(G)=\max\\{d(u,v):u,v\in G\\}$. The _weight_ of a graph $G$ from a vertex
$u\in V(G)$ is defined as $w_{G}(u)=\sum_{v\in V(G)}d(u,v)$. A vertex $c\in
V(G)$ is said to be _weight center_ of $G$ if $w_{G}(c)=\min\\{w_{G}(u):u\in
V(G)\\}$. The weight of graph $G$, denoted by $w(G)$, is defined as
$w(G)=w_{G}(c)$, where $c$ is the weight center of the graph $G$. Denote the
set of all weight centers of graph $G$ by $W(G)$. A tree $T$ is a simple
connected acyclic graph. The following is known about weight center(s) of a
tree $T$.

######  Lemma 2.1.

[15] If $w$ is a weight center of a tree $T$. Then each component of $T-w$
contains at most $|V(T)|/2$ vertices.

######  Lemma 2.2.

[15] Every tree $T$ has one or two weight centers, and $T$ has two weight
centers, say, $W(T)=\\{w,w^{\prime}\\}$ if and only if $ww^{\prime}$ is an
edge of $T$ and $T-ww^{\prime}$ consists of two equal sized components.

For a tree $T$ rooted at $r$, if $x$ is on the $r-y$ path then $x$ is called
ancestor of $y$ and $y$ is called descendant of $x$. Note that the root of the
tree $T$ is an ancestor of every vertex and every vertex is its own ancestor
and descendant.

If $W(T)=\\{w\\}$ then we view a tree T rooted at $w$ and if
$W(T)=\\{w,w^{\prime}\\}$ then we view a tree $T$ rooted at both $w$ and
$w^{\prime}$. Let $u$ be any vertex adjacent to the weight center of $T$, then
the subtree induced by $u$ with all its descendants is called a branch of a
tree $T$. Two branches are called different if they induced by different
vertices adjacent to the same weight center and opposite if they induced by
different vertices adjacent to different weight centers. Two vertices $u$ and
$v$ are said to be in different branches if either $u$ and $v$ are in
different branches or one of them is a weight center of $T$ and other is in
the branch of $T$ induced by the vertex adjacent to it. If
$W(T)=\\{w,w^{\prime}\\}$ then $u$ and $v$ are said to be in opposite branches
if they belong to different components of $T-ww^{\prime}$. Define a level
function $L_{T}:V(T)\rightarrow\\{0,1,2,\ldots\\}$ by

$L_{T}(x):=\min\\{d(x,w):w\in W(T)\\}.$

The value of $L_{T}(x)$ is called level of the vertex $x$ in $T$. The total
level of $T$, denoted by $L(T)$, is defined as

$L(T):=\sum_{x\in V(T)}L_{T}(x).$

For any two vertices $x,y\in V(T)$, define

$\phi_{T}(x,y)=\max\\{L_{T}(z):z\mbox{ is a common ancestor of }x\mbox{ and
}y\\},$ $\delta_{T}(x,y)=\left\\{\begin{array}[]{ll}1,&\mbox{if $|W(T)|=2$
and, $x$ and $y$ are in opposite branches},\\\
0,&\mbox{otherwise}.\end{array}\right.$

Define

$\varepsilon(T)=\left\\{\begin{array}[]{ll}1,&\mbox{if
$|W(T)|=1$},\\\\[5.69046pt] 0,&\mbox{if $|W(T)|=2$}.\end{array}\right.$

######  Observation 2.3.

Let $T$ be a tree and $x,y\in V(T)$, then

  1. (1)

$0\leq\phi_{T}(x,y)<\max\\{L_{T}(v):v\in V(T)\\}$,

  2. (2)

$\phi_{T}(x,y)=0$ if and only if $x$ and $y$ are in opposite or different
branches,

  3. (3)

$d_{T}(x,y)=L_{T}(x)+L_{T}(y)+\delta_{T}(x,y)-2\phi_{T}(x,y)$.

######  Definition 2.4.

For integers $m\geq 3$ and $k\geq 1$, the generalized Petersen graph $P_{m,k}$
is the graph with vertex set $V(P_{m,k})=\\{u_{i},v_{i}:i\in Z_{m}\\}$ and
edge set $E(P_{m,k})=\\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}:i\in Z_{m}\\}$.

######  Definition 2.5.

Let $G$ and $H$ be any two simple connected graphs. The Cartesian product of
$G$ and $H$ is denoted by $G\Box H$ with vertex set $V(G)\times V(H)$, where
two vertices $(g,h)$ and $(g^{\prime},h^{\prime})$ are adjacent in $G\Box H$
if and only if $g$ and $g^{\prime}$ are adjacent in $G$ and $h=h^{\prime}$ in
$H$; or $h$ and $h^{\prime}$ are adjacent in $H$ and $g=g^{\prime}$ in $G$.

######  Observation 2.6.

Let $G$ be any graph of order $m$ with diameter $d_{1}$ and $H$ be any graph
of order $n$ with diameter $d_{2}$, then

  1. (1)

$|V(G\Box H)|=mn$,

  2. (2)

${\rm diam}(G\Box H)=d_{1}+d_{2}$,

  3. (3)

For any two vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$ in $G\Box H$,

$d_{G\Box
H}((g_{1},h_{1}),(g_{2},h_{2}))=d_{G}(g_{1},g_{2})+d_{H}(h_{1},h_{2}).$

##  3 Main results

In this section, we continue to use terms and notations defined in previous
section. Note that a radio labeling $f$ of graph $G$ induced an ordering
$O(V(G)):=z_{0},z_{1},\ldots,z_{|V(G)|-1}$ of $V(G)$ such that

$0=f(z_{0})<f(z_{1})<\ldots<f(z_{p-1})={\rm span}(f).$

######  Theorem 3.1.

Let $P_{m,k}$ be a generalized Petersen graph of order $2m$ and $T$ be a tree
of order $n$. Denote ${\rm diam}(P_{m,k}\Box T)=d_{G}$, ${\rm
diam}(P_{m,k})=d_{p}$, ${\rm diam}(T)=d_{t}$ and $\varepsilon(T)=\varepsilon$.
Then

${\rm rn}(P_{m,k}\Box T)\geq(2mn-1)(d_{t}+\varepsilon)-4mL(T).$ (1)

Moreover, the equality holds in (1) if and only if there exist an ordering
$O(V(P_{m,k}\Box T)):=z_{0},z_{1},\ldots,z_{2mn-1}$ of $V(P_{m,k}\Box T)$,
where $z_{t}=(x_{i_{t}},y_{j_{t}})$ such that the following all holds for all
$0\leq t\leq 2mn-2$:

  1. (a)

$d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})=d_{p}$,

  2. (b)

$L_{T}(y_{j_{0}})+L_{T}(y_{j_{2mn-1}})=0$,

  3. (c)

$y_{j_{t}}$ and $y_{j_{t+1}}$ are in different branches when $|W(T)|=1$ and in
opposite branches when $|W(T)|=2$,

  4. (d)

the mapping $f$ defined on $O(V(P_{m,k}\Box T))$ by $f(z_{0})=0$ and
$f(z_{t+1})=f(z_{t})+d_{t}+\varepsilon-L_{T}(y_{j_{t}})-L_{T}(y_{j_{t+1}})$ is
a radio labeling of $P_{m,k}\Box T$.

###### Proof.

Denote $G=P_{m,k}\Box T$. It is suffices to prove that the span of any radio
labeling $f$ of $G$ is no less than the right-hand side of (1). Let $f$ be any
radio labeling of $P_{m,k}\Box T$ with
$0=f(z_{0})<f(z_{1})<\ldots<f(z_{2mn-1})={\rm span}(f)$. Since $f$ is a radio
labeling, we have $f(z_{i+1})-f(z_{i})\geq
d_{G}+1-d_{G}(z_{i},z_{i+1})=d_{p}+d_{t}+1-d_{G}(z_{i},z_{i+1})$ for $0\leq
i\leq 2mn-2$. Summing up these $2mn-1$ inequalities, we obtain

${\rm
span}(f)=f(z_{2mn-1})\geq(2mn-1)(d_{p}+d_{t}+1)-\sum_{i=0}^{2mn-2}d_{G}(z_{i},z_{i+1})$
(2)

Denote $z_{t}=(x_{i_{t}},y_{j_{t}})$ for $0\leq t\leq 2mn-1$, where
$x_{i_{t}}\in V(P_{m,k})$ and $y_{j_{t}}\in V(T)$. By Observations 2.3 and
2.6, we have

$\displaystyle\sum_{t=0}^{2mn-2}d_{G}(z_{t},z_{t+1})$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{2mn-2}[d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})+d_{T}(y_{j_{t}},y_{j_{t+1}})]$
(3) $\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2mn-2}[d_{p}+L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})+\delta_{T}(y_{j_{t}},y_{j_{t+1}})-2\phi_{T}(y_{j_{t}},y_{j_{t+1}})]$
$\displaystyle=$
$\displaystyle(2mn-1)d_{p}+2\sum_{t=0}^{2mn-1}L_{T}(y_{j_{t}})-L_{T}(y_{j_{0}})-L_{T}(y_{j_{2mn-1}})$
$\displaystyle\hskip
113.81102pt+\sum_{t=0}^{2mn-2}[\delta_{T}(y_{j_{t}},y_{j_{t+1}})-2\phi_{T}(y_{j_{t}},y_{j_{t+1}})]$
$\displaystyle=$
$\displaystyle(2mn-1)d_{p}+4mL(T)-L_{T}(y_{j_{0}})-L_{T}(y_{j_{2mn-1}})$
$\displaystyle\hskip
113.81102pt+\sum_{t=0}^{2mn-2}[\delta_{T}(y_{j_{t}},y_{j_{t+1}})-2\phi_{T}(y_{j_{t}},y_{j_{t+1}})].$

We consider the following two cases.

Case-1: $|W(T)|=1$.

In this case, $\delta_{T}(y_{j_{t}},y_{j_{t+1}})=0$,
$\phi_{T}(y_{j_{t}},y_{j_{t+1}})\geq 0$ for all $0\leq t\leq 2mn-2$ and
$L_{T}(y_{j_{0}})+L_{T}(y_{j_{2mn-1}})\geq 0$. Substituting these all in (3),
we get

$\sum_{t=0}^{2mn-2}d_{G}(z_{t},z_{t+1})\leq(2mn-1)d_{p}+4mL(T).$ (4)

Substituting (4) in (2), we obtain

${\rm span}(f)=f(z_{2mn-1})\geq(2mn-1)(d_{t}+1)-4mL(T).$

Case-2: $|W(T)|=2$.

In this case, $0\leq\delta_{T}(y_{j_{t}},y_{j_{t+1}})\leq 1$,
$\phi_{T}(y_{j_{t}},y_{j_{t+1}})\geq 0$ for all $0\leq t\leq 2mn-2$ and
$L_{T}(y_{j_{0}})+L_{T}(y_{j_{2mn-1}})\geq 0$. Substituting these all in (3),
we get

$\sum_{t=0}^{2mn-2}d_{G}(z_{t},z_{t+1})\leq(2mn-1)d_{p}+4mL(T)+(2mn-1).$ (5)

Substituting (5) in (3), we obtain

${\rm span}(f)=f(z_{2mn-1})\geq(2mn-1)d_{t}-4mL(T).$

It is easy to see from above Cases 1 and 2 that the equality hold in (1) if
and only if the conditions in moreover part hold which completes the proof. ∎

######  Theorem 3.2.

Let $P_{m,k}$ be a generalized Petersen graph of order $2m$ and $T$ be a tree
of order $n$. Denote $P_{m,k}\Box T=G$, ${\rm diam}(P_{m,k}\Box T)=d_{G}$,
${\rm diam}(P_{m,k})=d_{p}$, ${\rm diam}(T)=d_{t}$ and
$\varepsilon(T)=\varepsilon$. Then

${\rm rn}(P_{m,k}\Box T)=(2mn-1)(d_{t}+\varepsilon)-4mL(T)$ (6)

if and only if there exist an ordering $O(V(P_{m,k}\Box
T)):=z_{0},z_{1},\ldots,z_{2mn-1}$ of $V(P_{m,k}\Box T)$, where
$z_{t}=(x_{i_{t}},y_{j_{t}})$ such that the following all holds for all $0\leq
t\leq 2mn-2$:

  1. (a)

$d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})=d_{p}$,

  2. (b)

$L_{T}(y_{j_{0}})+L_{T}(y_{j_{2mn-1}})=0$,

  3. (c)

For any $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}}),0\leq
a<b\leq 2mn-1$; the distance $d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})$ and
$d_{T}(y_{j_{a}},y_{j_{b}})$ satisfies

$d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})\geq\sum_{t=a}^{b-1}(L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})-d_{t}-\varepsilon)+d_{t}+d_{p}+1.$
(7)

###### Proof.

Necessity: Suppose (6) holds. By Theorem 3.1, there exist a radio labeling $f$
of $P_{m,k}\Box T$ with $0=f(z_{0})<f(z_{1})<\ldots<f(z_{2mn-1})={\rm
rn}(P_{m,k}\Box T)$, where $z_{t}=(x_{i_{t}},y_{j_{t}}),x_{i_{t}}\in
V(P_{m,k})$ and $y_{j_{t}}\in V(T)$ such that the conditions (a)-(d) in
Theorem 3.1 hold. Hence, the conditions (a) and (b) are satisfied. For any two
vertices $z_{a}$ and $z_{b}\;(0\leq a<b\leq 2mn-1)$, by the condition (d) of
Theorem 3.1, we have

$f(z_{b})-f(z_{a})=\sum_{t=a}^{b-1}(d_{t}+\varepsilon-
L_{T}(y_{j_{t}})-L_{T}(y_{j_{t+1}})).$

Since $f$ is a radio labeling, $f(z_{b})-f(z_{a})\geq
d_{G}+1-d_{G}(z_{a},z_{b})=d_{p}+d_{t}+1-d_{T}(y_{j_{a}},y_{j_{b}})-d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})$.
Substituting this in above equation, we obtain

$\sum_{t=a}^{b-1}(d_{t}+\varepsilon-
L_{T}(y_{j_{t}})-L_{T}(y_{j_{t+1}}))=f(z_{b})-f(z_{a})\geq
d_{p}+d_{t}+1-d_{T}(y_{j_{a}},y_{j_{b}})-d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

Hence, the condition (c) is satisfied.

Sufficiency: Let an ordering $O(V(P_{m,k}\Box
T)):=z_{0},z_{1},\ldots,z_{2mn-1}$ of $V(P_{m,k}\Box T)$ satisfying the
conditions (a)-(c) of hypothesis. We prove that (6) holds and for this
purpose, it is enough to show that the conditions (c) and (d) in Theorem 3.1
hold. Take $a=t$ and $b=t+1$ in (7), we have $d_{T}(y_{j_{t}},y_{j_{t+1}})\geq
L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})+1-\varepsilon$ which implies that
$y_{j_{t}}$ and $y_{j_{t+1}}$ are in different branches when $|W(T)|=1$ and
opposite branches when $|W(T)|=2$. Hence, the condition (c) in Theorem 3.1 is
satisfied. Let $f$ is defined by $f(z_{0})=0$ and
$f(z_{t+1})=f(z_{t})+d_{t}+\varepsilon-L_{T}(y_{j_{t}})-L_{T}(y_{j_{t+1}})$
for $0\leq t\leq 2mn-2$. We prove that $f$ is a radio labeling. Let $z_{a}$
and $z_{b}\;(0\leq a<b\leq 2mn-1)$ be two arbitrary vertices. Then

$\displaystyle f(z_{b})-f(z_{a})$ $\displaystyle=$
$\displaystyle\sum_{t=a}^{b-1}(d_{t}+\varepsilon-
L_{T}(y_{j_{t}})-L_{T}(y_{j_{t+1}}))$ $\displaystyle\geq$ $\displaystyle
d_{p}+d_{t}+1-d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})-d_{T}(y_{j_{a}},y_{j_{b}})$
$\displaystyle=$ $\displaystyle d_{G}+1-d_{G}(z_{a},z_{b}).$

Hence $f$ is a radio labeling. Thus the condition (d) of Theorem 3.1 is
satisfied. The proof is complete. ∎

In the next result, we give three sufficient conditions to achieve the lower
bound for the radio number for the Cartesian product of the generalized
Peterson graph $P_{m,k}$ and a tree.

######  Theorem 3.3.

Let $P_{m,k}$ be a generalized Peterson graph of order $2m$ and $T$ be a tree
of order $n$. Denote ${\rm diam}(P_{m,k})=d_{p}$, ${\rm diam}(T)=d_{t}$ and
$\varepsilon(T)=\varepsilon$. Then

${\rm rn}(P_{m,k}\Box T)=(2mn-1)(d_{t}+\varepsilon)-4mL(T)$ (8)

if there exist an ordering $O(V(P_{m,k}\Box T)):=z_{0},z_{1},\ldots,z_{2mn-1}$
of $V(P_{m,k}\Box T)$, where $z_{t}=(x_{i_{t}},y_{j_{t}})$ such that the
following holds for all $0\leq t\leq 2mn-2$.

  1. (a)

$d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})=d_{p}$ and for $b\geq a+2$,

$d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})\geq\left\\{\begin{array}[]{ll}d_{p}-(b-a-1),&\mbox{if
$|W(T)|=1$};\\\\[5.69046pt] d_{p}-(b-a-2),&\mbox{if
$|W(T)|=2$}.\end{array}\right.$

  2. (b)

$L_{T}(y_{j_{0}})+L_{T}(y_{j_{2mn-1}})=0$,

  3. (c)

$y_{j_{t}}$ and $y_{j_{t+1}}$ are in different branches when $|W(T)|=1$ and in
opposite branches when $|W(T)|=2$,

and one of the following holds.

  1. (d)

$\min\\{d_{T}(y_{j_{t}},y_{j_{t+1}}),d_{T}(y_{j_{t+1}},y_{j_{t+2}})\\}\leq(d_{t}+1-\varepsilon)/2$
for all $0\leq t\leq 2mn-3$,

  2. (e)

$d_{T}(y_{j_{t}},y_{j_{t+1}})\leq(d_{t}+1+\varepsilon)/2$ for all $0\leq t\leq
2mn-2$,

  3. (f)

For all $0\leq t\leq 2mn-1$, $L_{T}(y_{j_{t}})\leq(d_{t}+1)/2$ when $|W(T)|=1$
and $L_{T}(y_{j_{t}})\leq(d_{t}-1)/2$ when $|W(T)|=2$ and for
$z_{a}=(x_{i_{a}},y_{j_{a}})$, $z_{b}=(x_{i_{b}},y_{j_{b}})\;(0\leq a<b\leq
2mn-1)$, if $y_{j_{a}}$ and $y_{j_{b}}$ are in the same branch of $T$ then
$b-a\geq d_{t}+d_{p}$.

###### Proof.

We show that if (a)-(c) and one of (d)-(f) holds for an ordering
$O(V(P_{m,k}\Box T)):=z_{0},z_{1},\ldots,z_{2mn-1}$ of $V(P_{m,k}\Box T)$,
where $z_{t}=(x_{i_{t}},y_{j_{t}});0\leq t\leq 2mn-1$ then (a)-(c) of Theorem
3.2 satisfies. Since the conditions (a) and (b) are identical in both Theorems
3.2 and 3.3, we verify the condition (c) of Theorem 3.2 only. Let
$z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}}),0\leq a<b\leq
2mn-1$ be two arbitrary vertices. Denote the right-hand side of (7) by
$E(a,b)$. We consider the following two cases.

Case-1: $|W(T)|=1$. In this case, recall that $\varepsilon(T)=1$ and
$\delta_{T}(y_{j_{t}},y_{j_{t+1}})=0$ for all $0\leq t\leq 2mn-2$ by the
definition of $\delta$.

Subcase-1.1: Suppose (a)-(d) holds. By (b) and (d), we have
$L_{T}(y_{j_{0}})=L_{T}(y_{j_{2mn-1}})=0<d_{t}/2$ and for all $1\leq t\leq
2mn-2$,
$L_{T}(y_{j_{t}})\leq\min\\{L_{T}(y_{j_{t-1}})+L_{T}(y_{j_{t}}),L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})\\}=\min\\{d_{T}(y_{j_{t-1}},y_{j_{t}}),d_{T}(y_{j_{t}},y_{j_{t+1}})\\}\leq
d_{t}/2$. If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$
such that $y_{j_{a}}$ and $y_{j_{b}}$ are in different branches then note that
$d_{T}(y_{j_{a}},y_{j_{b}})=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})$. Hence, we have

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)d_{t}-(b-a)+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(b-a-1)(d_{t}/2)-(b-a-1)d_{t}+(d_{p}-b+a+1)$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+(d_{p}-b+a+1)\leq
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in the same branch of $T$ then note that
$b-a\geq 2$. If $b-a\geq 4$ then
$\min\\{L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}}),L_{T}(y_{j_{t+1}})+L_{T}(y_{j_{t+2}})\\}\leq
d_{t}/2$ as
$\min\\{d_{T}(y_{j_{t}},y_{j_{t+1}}),d_{T}(y_{j_{t+1}},y_{j_{t+2}})\\}\leq
d_{t}/2$ and
$\max\\{L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}}),L_{T}(y_{j_{t+1}})+L_{T}(y_{j_{t+2}})\\}\leq
d_{t}$. Hence, we have

$\displaystyle E(a,b)$ $\displaystyle\leq$
$\displaystyle(2(d_{t}/2)+2d_{t})-3d_{t}-4+d_{p}+1=d_{p}-3=d_{p}-b+a+1$
$\displaystyle\leq$ $\displaystyle d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})\leq
d_{P_{m,k}}(x_{i_{t}},x_{i_{t+1}})+d_{T}(y_{j_{t}},y_{j_{t+1}}).$

If $b=a+3$ then there are two possibilities: (i)
$d_{T}(y_{j_{a}},y_{j_{a+1}})\leq
d_{t}/2,d_{T}(y_{j_{a+1}},y_{j_{a+2}})>d_{t}/2$ and
$d_{T}(y_{j_{a+2}},y_{j_{a+3}})\leq d_{t}/2$, (ii)
$d_{T}(y_{j_{a}},y_{j_{a+1}})>d_{t}/2,d_{T}(y_{j_{a+1}},y_{j_{a+2}})\leq
d_{t}/2$ and $d_{T}(y_{j_{a+2}},y_{j_{a+3}})>d_{t}/2$. In case of (i),
$L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq
d_{t}/2,L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq d_{t}$ and
$L_{T}(y_{j_{a+2}})+L_{T}(y_{j_{a+3}})\leq d_{t}/2$. Hence,

$\displaystyle E(a,b)$ $\displaystyle\leq$
$\displaystyle(d_{t}/2+d_{t}+d_{t}/2)-2d_{t}-3+d_{p}+1=d_{p}-2$
$\displaystyle\leq$ $\displaystyle d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}}).$

In case of (ii), we have $d_{t}/2<L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq
d_{t},L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq d_{t}/2$ and
$d_{t}/2<L_{T}(y_{j_{a+2}})+L_{T}(y_{j_{a+3}})\leq d_{t}$. Hence,

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+3}})+2(L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}}))-2d_{t}-3+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+3}})+2(d_{t}/2)-2d_{t}+d_{p}-2$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+3}})-2(d_{t}/2)+d_{p}-2$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+3}})-2\phi_{T}(y_{j_{a}},y_{j_{a+3}})+d_{p}-2$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $b=a+2$ then either (i) $d_{T}(y_{j_{a}},y_{j_{a+1}})\leq d_{t}/2$ and
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})\leq d_{t}/2$ or (ii)
$d_{T}(y_{j_{a}},y_{j_{a+1}})\leq d_{t}/2$ and
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})>d_{t}/2$. In case of (i),
$L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq d_{t}/2$ and
$L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq d_{t}/2$ and hence,
$E(a,b)\leq(d_{t}/2+d_{t}/2)-d_{t}-2+d_{p}+1=d_{p}-1\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{a+2}})\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{a+2}})+d_{T}(y_{j_{a}},y_{j_{a+2}})$. In case of
(ii), $L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq d_{t}/2$ and
$L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})>d_{t}/2$, that is
$L_{T}(y_{j_{a+1}})\leq d_{t}/2-L_{T}(y_{j_{a}})$. Hence,

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+2L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})-d_{t}-2+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+2(d_{t}/2-L_{T}(y_{j_{a}}))+L_{T}(y_{j_{a+2}})-d_{t}+d_{p}-1$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+2}})-2L_{T}(y_{j_{a}})+d_{p}-1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+2}})-2\phi_{T}(y_{j_{a}},y_{j_{a+2}})+d_{p}-1$
$\displaystyle=$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{a+2}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{i+2}}).$

Subcase-1.2: Suppose (a)-(c) and (e) hold. Then for all $0\leq t\leq 2mn-2$,
$L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})\leq(d_{t}+2)/2$ as
$d_{T}(y_{j_{t}},y_{j_{t+1}})\leq(d_{t}+2)/2$ and, $y_{j_{t}}$ and
$y_{j_{t+1}}$ are in different branches. If $b=a+1$ then
$E(a,b)=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}=d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})$.
If $b=a+2$ then

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+2L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{b}})-d_{t}-1+d_{p}$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2((d_{t}+2)/2-L_{T}(y_{j_{a}}))-d_{t}-1+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2(L_{T}(y_{j_{a}})-1)+d_{p}-1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})+d_{p}-1$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $b-a\geq 3$ then

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a)(d_{t}+1)+d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(b-a-1)((d_{t}+2)/2)-(b-a-1)(d_{t}+1)+d_{p}$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2((d_{t}+2)/2)-2d_{t}-2+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2((d_{t}-2)/2)+d_{p}-2$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})+d_{p}-2$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

Subcase-1.3: Suppose (a)-(c) and (f) hold. If $z_{a}=(x_{i_{a}},y_{j_{a}})$
and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that $y_{j_{a}}$ and $y_{j_{b}}$ are in
different branches. Assume $d_{t}$ is even then $L_{T}(y_{j_{t}})\leq d_{t}/2$
for all $0\leq t\leq 2mn-1$. Hence, we obtain

$\displaystyle E(a,b)$ $\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)(d_{t}+1)+d_{p}$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}(d_{t}/2)-(b-a-1)(d_{t}+1)+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-1)$ $\displaystyle\leq$
$\displaystyle d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

Assume $d_{t}$ is odd then note that for any $(d_{t}+d_{p})$ consecutive
vertices in ordering $O(V(P_{m,k}\Box T)):=z_{0},z_{1},\ldots,z_{2mn-1}$, at
most one $L(y_{j_{q}})=(d_{t}+1)/2$ and for all other vertices
$L(y_{j_{t}})\leq(d_{t}-1)/2$. Hence, we have

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)(d_{t}+1)+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(b-a-1)\left(\frac{d_{t}-1}{2}\right)+2\left(\frac{b-a-1}{d_{t}+d_{p}}\right)-(b-a-1)(d_{t}+1)+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-(b-a-1)((d_{t}+d_{p}-2)/(d_{t}+d_{p}))+d_{p}-(b-a-1)$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{y_{j_{a}}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-1)$ $\displaystyle\leq$
$\displaystyle d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in the same branch of $T$ then note that
$b-a\geq d_{t}+d_{p}$. Hence, $E(a,b)\leq
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-1)\leq
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(d_{t}+d_{p}-1)=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2((d_{t}-1)/2)\leq
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})\leq
d_{T}(y_{j_{a}},y_{j_{b}})\leq
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})$.

Case-2: $|W(T)|=2$. In this case, recall that $\varepsilon(T)=0$ and
$\delta_{T}(y_{j_{t}},y_{j_{t+1}})=1$ for all $0\leq t\leq 2mn-2$ by the
definition of $\delta$.

Subcase-2.1: Suppose (a)-(d) holds. By (b) and (d), we have
$L_{T}(y_{j_{0}})=L_{T}(y_{j_{2mn-1}})=0<(d_{t}-1)/2$ and for all $1\leq t\leq
2mn-2$,
$L_{T}(y_{j_{t}})\leq\min\\{L_{T}(y_{j_{t-1}})+L_{T}(y_{j_{t}}),L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})\\}=\min\\{d_{T}(y_{j_{t-1}},y_{j_{t}})-1,d_{T}(y_{j_{t}},y_{j_{t+1}})-1\\}\leq(d_{t}-1)/2$.
If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in opposite branches of $T$ then
$d_{T}(y_{j_{a}},y_{j_{b}})=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+1$ and
$y_{j_{a}}$ and $y_{j_{b}}$ are in different branches then
$d_{T}(y_{j_{a}},y_{j_{b}})=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})$. Hence, in both
these cases, we have

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(b-a-1)((d_{t}-1)/2)-(b-a-1)d_{t}+d_{p}+1$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-2)$ $\displaystyle\leq$
$\displaystyle d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in the same branch of $T$ then note that
$b-a\geq 2$. If $b-a\geq 4$ then
$\min\\{L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}}),L_{T}(y_{j_{t+1}})+L_{T}(y_{j_{t+2}})\\}\leq(d_{t}-1)/2$
as
$\min\\{d_{T}(y_{j_{t}},y_{j_{t+1}})-1,d_{T}(y_{j_{t+1}},y_{j_{t+2}})-1\\}\leq(d_{t}-1)/2$
and
$\max\\{L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}}),L_{T}(y_{j_{t+1}})+L_{T}(y_{j_{t+2}})\\}\leq
d_{t}-1$. Hence, we have

$\displaystyle E(a,b)$ $\displaystyle\leq$
$\displaystyle(2((d_{t}-1)/2)+2(d_{t}-1))-3d_{t}+d_{p}+1$ $\displaystyle=$
$\displaystyle d_{p}-2\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}}).$

If $b=a+3$ then there are two possibilities: (i)
$d_{T}(y_{j_{a}},y_{j_{a+1}})\leq(d_{t}+1)/2$,
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})>(d_{t}+1)/2$ and
$d_{T}(y_{j_{a+2}},y_{j_{a+3}})\leq(d_{t}+1)/2$, (ii)
$d_{T}(y_{j_{a}},y_{j_{a+1}})>(d_{t}+1)/2$,
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})\leq(d_{t}+1)/2$ and
$d_{T}(y_{j_{a+2}},y_{j_{a+3}})>(d_{t}+1)/2$. In case of (i), note that
$L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq(d_{t}-1)/2$,
$(d_{t}-1)/2<L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq d_{t}-1$ and
$L_{T}(y_{j_{a+2}})+L_{T}(y_{j_{a+3}})\leq(d_{t}-1)/2$. Hence,
$E(a,b)\leq((d_{t}-1)/2+(d_{t}-1)+(d_{t}-1)/2)-2d_{t}+d_{p}+1=d_{p}-1\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$. In case of (ii),
note that $(d_{t}-1)/2<L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq d_{t}-1$,
$L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq(d_{t}-1)/2$ and
$(d_{t}-1)/2<L_{T}(y_{j_{a+2}})+L_{T}(y_{j_{a+3}})\leq d_{t}-1$. Hence,

$\displaystyle E(a,b)$ $\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}}))-2d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2((d_{t}-1)/2)-2d_{t}+d_{p}+1$
$\displaystyle=$ $\displaystyle L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-d_{t}+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2((d_{t}-1)/2)+d_{p}-1$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})+d_{p}-1$
$\displaystyle\leq$ $\displaystyle
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}}).$

If $b=a+2$ then either (i) $d_{T}(y_{j_{a}},y_{j_{a+1}})\leq(d_{t}+1)/2$ and
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})\leq(d_{t}+1)/2$, or (ii)
$d_{T}(y_{j_{a}},y_{j_{a+1}})\leq(d_{t}+1)/2$ and
$d_{T}(y_{j_{a+1}},y_{j_{a+2}})>(d_{t}+1)/2$. In case of (i),
$L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq(d_{t}-1)/2$ and
$L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq(d_{t}-1)/2$. Hence, we have
$E(a,b)\leq((d_{t}-1)/2+(d_{t}-1)/2)-d_{t}+d_{p}+1=d_{p}\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$. In case of (ii),
$L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+1}})\leq(d_{t}-1)/2$ and
$(d_{t}-1)/2<L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})\leq d_{t}-1$, that is
$L_{T}(y_{j_{a+1}})\leq(d_{t}-1)/2-L_{T}(y_{j_{a}})$. Hence, $E(a,b)\leq
L_{T}(y_{j_{a}})+2L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{a+2}})-d_{t}+d_{p}+1\leq
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+2}})+2((d_{t}-1)/2-L_{T}(y_{j_{a}}))-d_{t}+d_{p}+1=L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+2}})-2L_{T}(y_{j_{a}})+d_{p}\leq
L_{T}(y_{j_{a}})+L_{T}(y_{j_{a+2}})-2\phi_{T}(y_{j_{a}},y_{j_{a+2}})+d_{p}\leq
d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$.

Subcase-2.2: Suppose (a)-(c) and (e) holds. Then for all $0\leq t\leq 2mn-2$,
$L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})\leq(d_{t}-1)/2$ as
$d_{T}(y_{j_{t}},y_{j_{t+1}})\leq(d_{t}+1)/2$ and, $y_{j_{t}}$ and
$y_{j_{t+1}}$ are in the opposite branches. If $b=a+1$ then
$E(a,b)=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+1+d_{p}=d_{P_{m,k}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$.
If $b=a+2$ then

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+2L_{T}(y_{j_{a+1}})+L_{T}(y_{j_{b}})-d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2((d_{t}-1)/2-L_{T}(y_{j_{a}}))+L_{T}(y_{j_{b}})-d_{t}+d_{p}+1$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2L_{T}(y_{j_{a}})+d_{p}$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})+d_{p}$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{T}(x_{i_{a}},x_{i_{b}}).$

If $b-a\geq 3$ then

$\displaystyle E(a,b)$ $\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2((d_{t}-1)/2)-2d_{t}+d_{p}+1$
$\displaystyle=$ $\displaystyle L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-d_{t}+d_{p}$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2((d_{t}-1)/2)+d_{p}-1$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})+d_{p}-1$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

Subcase-2.3: Suppose (a)-(c) and (f) holds. In this case, recall that
$L_{T}(y_{j_{t}})\leq(d_{t}-1)/2$ for all $0\leq t\leq 2mn-1$. If
$z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in opposite branches or in different branches
of $T$ then

$\displaystyle E(a,b)$ $\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2\sum_{t=a+1}^{b-1}L_{T}(y_{j_{t}})-(b-a-1)d_{t}+d_{p}+1$
$\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2(b-a-1)((d_{t}-1)/2)-(b-a-1)d_{t}+d_{p}+1$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-2)$ $\displaystyle\leq$
$\displaystyle d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

If $z_{a}=(x_{i_{a}},y_{j_{a}})$ and $z_{b}=(x_{i_{b}},y_{j_{b}})$ such that
$y_{j_{a}}$ and $y_{j_{b}}$ are in the same branch of $T$ then recall that
$b-a\geq d_{t}+d_{p}$. Hence, as above, we have

$\displaystyle E(a,b)$ $\displaystyle\leq$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(b-a-2)$ $\displaystyle\leq$
$\displaystyle L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+d_{p}-(d_{t}+d_{p}-2)$
$\displaystyle=$ $\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2((d_{t}-2)/2)$ $\displaystyle\leq$
$\displaystyle
L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-2\phi_{T}(y_{j_{a}},y_{j_{b}})$
$\displaystyle\leq$ $\displaystyle
d_{T}(y_{j_{a}},y_{j_{b}})+d_{P_{m,k}}(x_{i_{a}},x_{i_{b}}).$

∎

We now determine the radio number for the Cartesian product of the Petersen
graph and star using our results.

The famous Petersen graph is the generalized Petersen graph $P_{5,2}$ as shown
in figure 1. We denote $V(P_{5,2})=\\{x_{1},x_{2},\ldots,x_{10}\\}$ with
$E(P_{5,2})=\\{x_{i}x_{i+2},x_{j}x_{j+3},x_{1}x_{10},x_{2}x_{7},x_{3}x_{9}:i=1,2,3,4,6,7,8;j=1,2,5,6,7\\}$.
An $n$-star is a tree consisting of $n$ leaves and another vertex joined to
all leaves by edges denoted by $K_{1,n}$. Denote
$V(K_{1,n})=\\{y_{j}:j=0,1,2,\ldots,n\\}$ with
$E(K_{1,n})=\\{y_{0}y_{j}:j=1,2,\ldots,n\\}$.

Figure 1: The Peterson graph $P_{5,2}$.

######  Theorem 3.4.

Let $P_{5,2}$ be the Petersen graph and $K_{1,n}$ be a star graph with $n\geq
3$. Then

${\rm rn}(P_{5,2}\Box K_{1,n})=10n+27.$ (9)

###### Proof.

The order, diameter and the total level of $K_{1,n}$ are given by $n+1$, $2$
and $n$, respectively. Substituting all these in the right-hand side of (1),
we obtain the right-hand side of (9) which is a lower bound for ${\rm
rn}(P_{5,2}\Box K_{1,n})$. Now we prove that this lower bound is tight. The
result is easy to verify for $n=3,4$ and $5$. Hence, we consider $n\geq 6$ and
for these cases, it suffices to give an ordering $O(V(P_{5,2}\Box
K_{1,n})):=z_{0},z_{1},\ldots,z_{10n+9}$ of vertices of $P_{5,2}\Box K_{1,n}$
satisfying the conditions (a)-(c) of Theorem 3.2. We use three permutations
$\alpha=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\\ 1&5&9&3&7&2&4&6&8&10\\\
\end{pmatrix}$, $\beta=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\\
1&4&2&5&3&6&9&7&10&8\\\ \end{pmatrix}$ and
$\tau=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\\ 5&1&2&3&4&10&6&7&8&9\\\
\end{pmatrix}$ to defined such ordering of $V(P_{5,2}\Box K_{1,n})$. We
consider the following two cases.

Case-1: $n\equiv 0$ (mod $5$).

In this case, we first rename $(x_{i},y_{j})\;(1\leq i\leq 10,0\leq j\leq n)$
as $(a_{r},b_{s})$ as follows:

$(a_{r},b_{s})=\left\\{\begin{array}[]{ll}(x_{i},y_{j}),&\mbox{if $1\leq i\leq
10$ and $j=0$},\\\ (x_{\alpha\tau^{j-1}(i)},y_{j}),&\mbox{if $1\leq i\leq 10$
and $1\leq j\leq n$}.\end{array}\right.$

We now define an ordering $O(V(P_{5,2}\Box
K_{1,n})):=z_{0},z_{1},\ldots,z_{10n+9}$ as follows: Let $z_{0}=(a_{5},b_{0})$
and for $1\leq t\leq 10n+9$, let $z_{t}=(a_{r},b_{s})$, where

$t:=\left\\{\begin{array}[]{ll}(r-1)n+s,&\mbox{if $1\leq r\leq 10$ and $1\leq
s\leq n$},\\\ 10n+r,&\mbox{if $1\leq r\leq 4$ and $s=0$},\\\ 10n+r-2,&\mbox{if
$7\leq r\leq 10$ and $s=0$},\\\ 10n+9,&\mbox{if $r=6$ and
$s=0$}.\end{array}\right.$

Case-2: $n\not\equiv 0$ (mod $5$).

In this case, we first rename $(x_{i},y_{j})\;(1\leq i\leq 10,0\leq j\leq n)$
as $(a_{r},b_{s})$ as follows:

$(a_{r},b_{s})=\left\\{\begin{array}[]{ll}(x_{i},y_{j}),&\mbox{if $1\leq i\leq
10$ and $j=0$},\\\ (x_{\tau^{j-1}(i)},y_{j}),&\mbox{if $1\leq i\leq 10,1\leq
j\leq n$ and $n\equiv 1$ (mod $5$)},\\\
(x_{\beta\tau^{j-1}(i)},y_{j}),&\mbox{if $1\leq i\leq 10,1\leq j\leq n$ and
$n\equiv 2$ (mod $5$)},\\\ (x_{\beta^{3}\tau^{j-1}(i)},y_{j}),&\mbox{if $1\leq
i\leq 10,1\leq j\leq n$ and $n\equiv 3$ (mod $5$)},\\\
(x_{\beta^{2}\tau^{j-1}(i)},y_{j}),&\mbox{if $1\leq i\leq 10,1\leq j\leq n$
and $n\equiv 4$ (mod $5$)},\\\ \end{array}\right.$

We now define an ordering $O(V(P_{5,2}\Box
K_{1,n})):=z_{0},z_{1},\ldots,z_{10n+9}$ as follows: Let $z_{0}=(a_{5},b_{0})$
and for $1\leq t\leq 10n+9$, let $z_{t}=(a_{r},b_{s})$, where

$t:=\left\\{\begin{array}[]{ll}(r-1)n+s,&\mbox{if $1\leq r\leq 10$ and $1\leq
s\leq n$},\\\ 10n+5-r,&\mbox{if $1\leq r\leq 4$ and $s=0$},\\\
10n+r-1,&\mbox{if $6\leq r\leq 10$ and $s=0$}.\end{array}\right.$

Then, in both the cases above, note that
$d_{P_{5,2}}(x_{i_{t}},x_{i_{t+1}})=2$ and
$L_{T}(y_{j_{0}})+L_{T}(y_{j_{10n+9}})=0$, where $z_{t}=(x_{i_{t}},y_{j_{t}})$
for $0\leq t\leq 10n+9$. Hence, the conditions (a)-(b) of Theorem 3.2 is
satisfied.

Claim: The above defined ordering $O(V(P_{5,2}\Box
K_{1,n})):=z_{0},z_{1},\ldots,z_{10n+9}$ satisfies (7).

Let $z_{a}=(x_{i_{a}},y_{j_{a}}),z_{b}=(x_{i_{b}},y_{j_{b}});0\leq a<b\leq
10n+9$ be two vertices. Denote the right-hand side of (7) by $E(a,b)$. If
$b-a=1$ then
$E(a,b)=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})-3+5=L_{T}(y_{j_{a}})+L_{T}(y_{j_{b}})+2=d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$.
Assume $b-a\geq 2$. If $a=0$ and $b=2$ then
$d_{P_{m,k}}(x_{i_{0}},x_{i_{2}})=d_{T}(y_{j_{0}},y_{j_{2}})=1$ and hence
$E(a,b)=L_{T}(y_{j_{0}})+2L_{T}(y_{j_{1}})+L_{T}(y_{j_{2}})-d_{t}-1=2=d_{P_{m,k}(x_{i_{0}},x_{i_{2}})}+d_{T}(y_{j_{0}},y_{j_{2}})$.
If $a=0$ and $b\geq 3$ then $E(a,b)\leq 1\leq
d_{P_{m,k}}(x_{i_{0}},x_{i_{b}})+d_{T}(y_{j_{0}},y_{j_{b}})$ as
$z_{0}=(x_{i_{0}},y_{j_{0}})\neq z_{b}=(x_{i_{b}},y_{j_{b}})$. Hence, the (7)
is satisfied. If $1\leq a<b\leq 10n$ then observe that $L_{T}(y_{t})=1$ for
all $1\leq t\leq 10n$ and hence we have

$\displaystyle E(a,b)$ $\displaystyle=$
$\displaystyle\sum_{t=a}^{b-1}[L_{T}(y_{j_{t}})+L_{T}(y_{j_{t+1}})-2-1]+2+2+1$
$\displaystyle\leq$ $\displaystyle 2(b-a)-3(b-a)+5$ $\displaystyle=$
$\displaystyle 5-(b-a).$

If $b-a=2$ then note that $d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})\geq 1$ and
$d_{T}(y_{j_{a}},y_{j_{b}})=2$ and hence $E(a,b)\leq 3\leq
d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$. If $b-a=3$ then
observe that $d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})\geq 1$ and
$d_{T}(y_{j_{a}},y_{j_{b}})\geq 2$ and hence $E(a,b)\leq 2\leq
d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$. If $b-a\geq 4$
then as $z_{a}\neq z_{b}$, we have
$d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})\geq 1$ and hence
$E(a,b)\leq 1\leq
d_{P_{5,2}}(x_{i_{a}},x_{i_{b}})+d_{T}(y_{j_{a}},y_{j_{b}})$. Again if
$10n<b\leq 10n+9$ then it is easy to verify that (7) is satisfied. Therefore,
the condition (c) of Theorem 3.2 is satisfied. ∎

######  Example 3.5.

In the following Table 1, a vertex ordering $O(V(P_{5,2}\Box
K_{1,6})):=z_{0},z_{1},\ldots,z_{69}$ and an optimal radio labeling of
$P_{5,2}\Box K_{1,6}$ obtained from the proof of Theorem 3.4 is shown.

Table 1: ${\rm rn}(P_{5,2}\Box K_{1,6})=87$. $(x_{i},y_{j})$ | $y_{0}$ | $y_{1}$ | $y_{2}$ | $y_{3}$ | $y_{4}$ | $y_{5}$ | $y_{6}$
---|---|---|---|---|---|---|---
$x_{1}$ | $z_{64}\rightarrow 72$ | $z_{1}\rightarrow 2$ | $z_{26}\rightarrow 27$ | $z_{21}\rightarrow 22$ | $z_{16}\rightarrow 17$ | $z_{11}\rightarrow 12$ | $z_{6}\rightarrow 7$
$x_{2}$ | $z_{63}\rightarrow 69$ | $z_{7}\rightarrow 8$ | $z_{2}\rightarrow 3$ | $z_{27}\rightarrow 28$ | $z_{22}\rightarrow 23$ | $z_{17}\rightarrow 18$ | $z_{12}\rightarrow 13$
$x_{3}$ | $z_{62}\rightarrow 66$ | $z_{13}\rightarrow 14$ | $z_{8}\rightarrow 9$ | $z_{3}\rightarrow 4$ | $z_{28}\rightarrow 29$ | $z_{23}\rightarrow 24$ | $z_{18}\rightarrow 19$
$x_{4}$ | $z_{61}\rightarrow 63$ | $z_{19}\rightarrow 20$ | $z_{14}\rightarrow 15$ | $z_{9}\rightarrow 10$ | $z_{4}\rightarrow 5$ | $z_{29}\rightarrow 30$ | $z_{24}\rightarrow 25$
$x_{5}$ | $z_{0}\rightarrow 0$ | $z_{25}\rightarrow 26$ | $z_{20}\rightarrow 21$ | $z_{15}\rightarrow 16$ | $z_{10}\rightarrow 11$ | $z_{5}\rightarrow 6$ | $z_{30}\rightarrow 31$
$x_{6}$ | $z_{65}\rightarrow 75$ | $z_{31}\rightarrow 32$ | $z_{56}\rightarrow 57$ | $z_{51}\rightarrow 52$ | $z_{46}\rightarrow 47$ | $z_{41}\rightarrow 42$ | $z_{36}\rightarrow 37$
$x_{7}$ | $z_{66}\rightarrow 78$ | $z_{37}\rightarrow 38$ | $z_{32}\rightarrow 33$ | $z_{57}\rightarrow 58$ | $z_{52}\rightarrow 53$ | $z_{47}\rightarrow 48$ | $z_{42}\rightarrow 43$
$x_{8}$ | $z_{67}\rightarrow 81$ | $z_{43}\rightarrow 44$ | $z_{38}\rightarrow 39$ | $z_{33}\rightarrow 34$ | $z_{58}\rightarrow 59$ | $z_{53}\rightarrow 54$ | $z_{48}\rightarrow 49$
$x_{9}$ | $z_{68}\rightarrow 84$ | $z_{49}\rightarrow 50$ | $z_{44}\rightarrow 45$ | $z_{39}\rightarrow 40$ | $z_{34}\rightarrow 35$ | $z_{59}\rightarrow 60$ | $z_{54}\rightarrow 55$
$x_{10}$ | $z_{69}\rightarrow 87$ | $z_{55}\rightarrow 56$ | $z_{50}\rightarrow 51$ | $z_{45}\rightarrow 46$ | $z_{40}\rightarrow 41$ | $z_{35}\rightarrow 36$ | $z_{60}\rightarrow 61$

## References

  * [1] D. Bantva and D. Liu, Optimal radio labelings of block graphs and line graphs of trees, _Theoretical. Compu. Sci._ , 891 (2021), 90–104.
  * [2] D. Bantva and D. Liu, Radio number for the Cartesian product of two trees, Submitted.
  * [3] D. Bantva, S. Vaidya and S. Zhou, Radio number of trees, _Discrete Appl. Math._ , 217 (2017), 110–122.
  * [4] K. F. Benson, M. Porter and M. Tomova, The radio number of all graphs of order $n$ and diameter $n-2$, _Le Mathematiche_ , 68 (2013), 167–190.
  * [5] R. C$\check{\mbox{a}}$da, J. Ekstein, P. Holub and O. Togni, Radio labeling of distance graphs, _Discrete Appl. Math._ , 161(18) (2013), 2876–2884.
  * [6] T. Calamoneri, The $L(h,k)$-labeling problem: An updated survey and annotated bibliography, _The Comput. J._ , 54(8) (2011), 1344–-1371.
  * [7] G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, _Bull. Inst. Combin. Appl._ , 33 (2001), 77–85 .
  * [8] G. Chartrand, D. Erwin and P. Zhang, A graph labeling suggested by FM channel restrictions, _Bull. Inst. Combin. Appl._ , 43 (2005), 43–57.
  * [9] S. Das, S. Ghosh, S. Nandi and S. Sen, A lower bound technique for radio k-coloring, _Discrete Math._ , 340 (2017), 855–861.
  * [10] J. R. Griggs and R. K. Yeh, Labeling graphs with condition at distance 2, _SIAM J. Discrete Math._ , 5 (1992), 586–-595.
  * [11] W.K. Hale, Frequency assignment: theory and application, _Proc IEEE_ , 68(12) (1980), 1497–1514.
  * [12] V. Halász and Z. Tuza, Distance-constrained labeling of complete trees, _Discrete Math._ , 338 (2015), 1398–1406.
  * [13] X. Li, V. Mak and S. Zhou, Optimal radio labelings of complete $m$-ary trees, _Discrete Applied Math._ , 158 (2010), 507–515.
  * [14] D. Liu, Radio numbers for trees, _Discrete Math._ , 308 (2008), 1153–1164.
  * [15] D. Liu and X. Zhu, Multi-level distance labelings for paths and cycles, _SIAM J. Discrete Math._ , 19 (2005), 610–621.
  * [16] F. S. Roberts, T-coloring of graphs: recent results and open problems, _Discrete Math._ , 93 (1991), 229-245.
  * [17] L. Saha and P. Panigrahi, On the radio number of toroidal grids, _Australas. J Comb._ , 55 (2013), 273–288.
  * [18] L. Saha and P. Panigrahi, On the Radio Number of Square of Graphs, _Electron. Notes Discret. Math._ , 48 (2015), 205–212.
  * [19] D. B. West, Introduction to Graph Theory, Prentice-Hall of India, 2001.
  * [20] R. K. Yeh, A survey on labeling graphs with a condition at distance two, _Discrete Math._ , 306 (2006), 1217–-1231.
  * [21] S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, _Theoretical Comput. Sci._ , 310 (2004), 501–511.


11institutetext: International Institute of Information Technology, Hyderabad,
India
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Michigan State University, East Lansing, USA
22email<EMAIL_ADDRESS>
# Can GAN-induced Attribute Manipulations Impact Face Recognition?

Sudipta Banerjee Corresponding author11 0000-0003-1623-7697 Aditi Aggarwal 11
Arun Ross 22 0000-0001-8850-3013

###### Abstract

Impact due to demographic factors such as age, sex, race, etc., has been
studied extensively in automated face recognition systems. However, the impact
of digitally modified demographic and facial attributes on face recognition is
relatively under-explored. In this work, we study the effect of attribute
manipulations induced via generative adversarial networks (GANs) on face
recognition performance. We conduct experiments on the CelebA dataset by
intentionally modifying thirteen attributes using AttGAN and STGAN and
evaluating their impact on two deep learning-based face verification methods,
ArcFace and VGGFace. Our findings indicate that some attribute manipulations
involving eyeglasses and digital alteration of sex cues can significantly
impair face recognition by up to 73% and need further analysis.

###### Keywords:

Face recognition Generative adversarial network (GAN) Attribute manipulation.

##  1 Introduction

Demographic attributes (race, age and sex) [14, 9], face and hair accessories
or attributes (glasses, makeup, hairstyle, beard and hair color) [28], and
data acquisition factors (environment and sensors) [24, 22] play an important
role in the performance of automated face recognition systems. Demographic
factors can potentially introduce biases in face recognition systems and are
well studied in the literature [21, 15, 1]. Work to mitigate biases due to
demographic factors are currently being investigated [20, 8]. Typically, some
of these attributes can be modified physically, e.g., by applying hair dye or
undergoing surgery. But what if these attributes are digitally modified?
Individuals can alter their facial features in photos using image editors for
cheekbone highlighting, forehead reduction, etc. The modified images, with
revised features, may be posted in social media websites. But do such
manipulations affect the biometric utility of these images? Assessing the
impact of digital retouching on biometric identification accuracy was done in
[4]. With the arrival of generative adversarial networks (GANs), the
possibilities of automated attribute editing have exploded [11, 17, 16, 18].
GANs can be used to change the direction of hair bangs, remove facial hair,
change the intensity of tinted eyeglasses and even add facial expressions to
face images. With GANs for facial age progression [29], a person’s appearance
can seamlessly transit from looking decades younger to appearing as an elderly
individual. Note that the user does not have to be a deep learning expert to
edit attributes in face images. Several smartphone-based applications have
such attribute modifications in the form of filters, e.g., FaceApp [7]. Open-
source applications make it easy to modify an image by uploading the image,
selecting the attribute to be edited, using a slider to regulate the magnitude
of the change, and downloading the edited photo. The entire process can be
easily accomplished in under five minutes [5]. Recently, mask-aware face
editing methods have emerged [26].

Motivation: Although the intent of using image editing routines stems from
personal preferences, they can be misused for obscuring an identity or
impersonating another identity. The style transfer networks are typically
evaluated from the perspective of visual realism, i.e., how realistic do the
generated images look? However, we rarely investigate the impact of such
digital manipulations on biometric face recognition. Work has been done to
localize the manipulations [13], estimate the generative model responsible for
producing the effects [30], and gauge the robustness of face recognition
networks with respect to pose and expression [10]. But we need to investigate
GAN-based attribute manipulations from the perspective of biometric
recognition. Studying the influence of digital manipulations of both
demographic and facial attributes on face images is pivotal because an
individual can use the edited images in identification documents. Therefore,
it is imperative to assess the impact of GAN-based attribute manipulations on
biometric recognition to evaluate the robustness of existing open-source deep
learning-based face recognition systems [23]. Our objective is to conduct an
investigative study that examines the impact of attribute editing (thirteen
attributes) of face images by AttGAN [11] and STGAN [17] on two popular open-
source face matchers, namely, ArcFace [6] and VGGFace [27].

The remainder of the paper is organized as follows. Section 2 describes image
attribute editing GANs and open-source face recognition networks analyzed in
the work. Section 3 describes the experimental protocols followed in this
work. Section 4 reports and analyzes the findings. Section 5 concludes the
paper.

(a) Male subject

(b) Female subject

Figure 1: Examples of attribute-manipulated images using AttGAN and STGAN for
a (a) male subject and a (b) female subject. To demonstrate the ability of the
GAN as a faithful autoencoder, ‘Reconstruction’ images are also displayed.

##  2 Proposed Study

In this work, we investigate how GAN-induced attribute manipulations affect
face recognition. In the process, we will review the following research
questions through our study.

  1. 1.

Does GAN-based attribute editing only produce perceptual changes in face
images?

  2. 2.

Are there certain attribute manipulations that are more detrimental than
others on face verification performance?

  3. 3.

Is the impact of GAN-based manipulations consistent across different face
recognition networks?

To answer the above questions, we used two GAN-based image editing deep
networks, viz., AttGAN and STGAN to modify thirteen attributes on a set of
face images from the CelebA dataset. The edited images are then compared with
the original face images in terms of biometric utility using two deep
learning-based face recognition networks, namely, ArcFace and VGGFace. We
hypothesize that digital manipulations induced using GANs can alter the visual
perceptibility of the images, but more importantly, affect the biometric
utility of the images. Note that these attributes are not originally present
in the images: they are artificially induced. Although such manipulations may
seem innocuous, they can produce unexpected changes in the face recognition
performance and should be handled cautiously. We now discuss the GANs used for
attribute manipulation and the deep face networks considered in this work.

AttGAN [11]: It can perform binary facial attribute manipulation by modeling
the relationship between the attributes and the latent representation of the
face. It consists of an encoder, a decoder, an attribute classification
network and a discriminator. The attribute classifier imposes an attribute
classification constraint to ensure that the generated image possesses the
desired attribute. Reconstruction learning is introduced such that the
generated image mimics the original image, i.e., only the desired attribute
should change without compromising the integrity of the remaining details in
the image. Finally, adversarial learning maintains the overall visual realism
of the generated images. The network allows high quality facial attribute
editing with control over the attribute intensity and accommodates changes in
the attribute style.

STGAN [17]: AttGAN employs an encoder-decoder structure with spatial pooling
or downsampling that results in reduction in the resolution and irrecoverable
loss of fine details. Therefore, the generated images are susceptible to loss
of features and look blurred. Skip connections are introduced in AttGAN that
directly concatenate encoder and decoder features and can improve the
reconstruction image quality but at the expense of reduced attribute
manipulation ability. In contrast, STGAN adopts selective transfer units that
can adaptively transform the encoder features supervised by the attributes to
be edited. STGAN accepts the difference between the target and source
attribute vector, known as the difference attribute vector, as input unlike
the AttGAN that takes the entire target attribute vector as input. Taking the
difference vector results in more controlled manipulation of the attribute and
simplifies the training process.

VGGFace [27]: “Very deep” convolutional neural networks are bootstrapped to
learn a N-way face classifier to recognize N subjects. It is designed such
that the network associates each training image to a score vector by using the
final fully connected layer that comprises N linear predictors. Each image is
mapped to one of the N identities present during training. The score vector
needs fine-tuning to perform verification by comparing face descriptors
learned in the Euclidean space. To that end, triplet-loss is employed during
training to learn a compact face representation (projection) that is well
separated across disjoint identities.

ArcFace [6]: Existing face recognition methods attempt to directly learn the
face embedding using a softmax loss function or a triplet loss function.
However, each of these embedding approaches suffer from drawbacks. Although
softmax loss is effective on closed-set face recognition, the face
representations are not discriminative enough for open-set face recognition.
Triplet loss can cause a huge number of face triplets for large datasets, and
semi-hard triplet mining is challenging for effective training. In contrast,
additive angular margin loss (ArcFace) optimises the geodesic distance margin
by establishing correspondence between the angle and arc in normalized
hypersphere. Due to its concise geometric interpretation, ArcFace can provide
highly discriminative features for face recognition, and has become one of the
most widely-used open-source deep face recognition networks.

(a) STGAN-VGGFace

(b) STGAN-ArcFace

(c) AttGAN-VGGFace

(d) AttGAN-ArcFace

Figure 2: DET curves obtained for all pairs of GANs (for attribute editing)
and deep face recognition networks (for biometric matching). (a) STGAN-
VGGFace, (b) STGAN-ArcFace, (c) AttGAN-VGGFace and (d) AttGAN-ArcFace.

##  3 Experiments

We used 2,641 images belonging to 853 unique individuals with an average of
$\sim$3 images per subject from the CelebA [19] dataset for conducting the
investigative study in this work. Next, we edited each of these images to
alter 13 attributes, one at a time, using AttGAN and STGAN to generate 2,641
$\times$ 13 $\times$ 2 = 68,666 manipulated images. We used the codes and pre-
trained models provided by the original authors of AttGAN [3] and STGAN [25]
in our work. The list of attributes edited are as follows: Bald, Bangs,
Black_Hair, Blond_Hair, Brown_Hair, Bushy_Eyebrows, Eyeglasses, Male,
Mouth_Slightly_Open, Mustache, No_Beard, Pale_Skin, and Young. We selected
these thirteen attributes as they were modified using the original AttGAN and
STGAN models. Examples of GAN edited images are presented in Figures 1(a) and
1(b). Note that the attributes are applied in a toggle fashion. For example,
the Male attribute changes the face image of the male individual by inducing
makeup to impart a feminine appearance (see Figure 1(a) ninth image from the
left), while the same attribute induces facial hair in the face image of the
female subject to impart a masculine appearance (see Figure 1(b) ninth image
from the left). We can also observe that the manipulations are not identical
across the two GANs and can manifest differently across different sexes. For
example, attribute Bald is more effectively induced by STGAN compared to
AttGAN and has a more pronounced effect on male images than female images (see
Figures 1(a) and (b) second image from the left). To perform quantitative
evaluation, we compared an original image ($\bm{I_{i}}$) with its respective
attribute manipulated image ($\bm{O_{j}}$) using a biometric comparator,
$\mathcal{B}(\bm{I_{i}},\bm{O_{j}})$, where $\mathcal{B}(\cdot,\cdot)$
extracts face representations from each image and computes the vector distance
between them. We used cosine distance in this work. The distance value is
termed as the biometric match score between a pair of face images. The
subscripts indicate the subject identifier. If $i=j$, then
$(\bm{I_{i}},\bm{O_{j}})$ forms a genuine pair (images belong to the same
individual). If $i\neq j$, then $(\bm{I_{i}},\bm{O_{j}})$ constitutes an
impostor pair (images belong to different individuals). We used the genuine
and impostor scores to compute the detection error trade-off (DET) curve, and
compared the face recognition performance between the original images and the
corresponding attribute manipulated images. In the DET curve, we plot False
Non-Match Rate (FNMR) vs. False Match Rate (FMR) at various thresholds. We
repeated this process to obtain fourteen curves, viz., one curve corresponding
to the original images (original-original comparison) and the remaining
thirteen curves corresponding to the thirteen attributes manipulated by the
GAN (original-attribute edited comparison). We used an open-source library for
the implementation of ArcFace and VGGFace [2].

(a) 50K impostor scores

(b) 100K impostor scores

(c) 500K impostor scores

(d) 1M impostor scores

Figure 3: DET curves of AttGAN-ArcFace obtained after varying the number of
impostor scores (a) 50K, (b) 100K, (c) 500K and (d) 1M. We varied the number
of impostor scores with respect to the number of genuine scores ($\sim$10K) in
factors of 5X, 10X, 50X and 100X, respectively. Note the DET curves show
minimal variations.

##  4 Findings

We present the DET curves for four different combinations of attribute
manipulating GANs and face comparators used in this work, namely, STGAN-
VGGFace, STGAN-ArcFace, AttGAN-VGGFace and AttGAN-ArcFace in Figure 2. We also
tabulated the results from the DET curves at FMR=0.01 in Table 1 and at
FMR=0.1 in Table 2.

Additionally, we performed an experiment to determine how the number of
impostor scores affect the overall biometric recognition performance for GAN-
edited images. The number of scores corresponding to genuine pairs was
$\sim$10K, and the number of scores corresponding to impostor pairs was
$\sim$7M. Due to memory constraints, we selected a subset of impostor scores
for plotting the DET curves. We randomly selected impostor scores, without
replacement, in factors of 5X, 10X, 50X and 100X of the total number of
genuine scores (10K). This resulted in 50K, 100K, 500K and 1M impostor scores,
respectively. We observed that the DET curves obtained by varying the number
of impostor scores from the AttGAN-ArcFace combination are almost identical.
See Figure 3. Therefore, for the remaining three combinations, we used the
entire set of genuine scores but restricted to utilizing one million impostor
scores.

Table 1: Face recognition performance: False Non-Match Rate (FNMR) at a False
Match Rate (FMR) = 0.01 for attribute manipulated images. The red colored
cells correspond to the maximum degradation (if any) in the biometric
recognition performance compared to the original in each column. The green
colored cells correspond to the maximum improvement (if any) in the biometric
recognition performance compared to the original in each column. Identical
performance results in multiple colored cells within a column. Note majority
of the attributes resulted in degradation. The attribute ‘Eyeglasses’ caused
the worst degradation in biometric recognition performance followed by the
‘Male’ attribute.

|  | STGAN-
---
VGGFace
| STGAN-
---
ArcFace
| AttGAN-
---
VGGFace
| AttGAN-
---
ArcFace
Original | 0.32 | 0.25 | 0.32 | 0.25
Bald | 0.34 | 0.22 | 0.35 | 0.40
Bangs | 0.28 | 0.23 | 0.35 | 0.57
Black_Hair | 0.29 | 0.20 | 0.33 | 0.35
Blond_Hair | 0.30 | 0.21 | 0.33 | 0.39
Brown_hair | 0.26 | 0.19 | 0.31 | 0.34
Bushy_Eyebrows | 0.30 | 0.22 | 0.35 | 0.40
Eyeglasses | 0.39 | 0.31 | 0.52 | 0.98
Male | 0.42 | 0.30 | 0.43 | 0.47
Mouth_Slightly_Open | 0.26 | 0.21 | 0.32 | 0.38
Mustache | 0.28 | 0.20 | 0.34 | 0.45
No_Beard | 0.28 | 0.20 | 0.33 | 0.41
Pale_Skin | 0.27 | 0.18 | 0.34 | 0.40
Young | 0.31 | 0.22 | 0.37 | 0.40

Table 2: Face recognition performance: False Non-Match Rate (FNMR) at a False
Match Rate (FMR) = 0.1 for attribute manipulated images. The red colored cells
correspond to the maximum degradation (if any) in the biometric recognition
performance compared to the original in each column. The green colored cells
correspond to the maximum improvement (if any) in the biometric recognition
performance compared to the original in each column. Identical performance
results in multiple colored cells within a column. Note @FMR=0.1, STGAN-
ArcFace (attribute editing using STGAN and face matching using ArcFace) caused
the least degradation in face recognition.

|  | STGAN-
---
VGGFace
| STGAN-
---
ArcFace
| AttGAN-
---
VGGFace
| AttGAN-
---
ArcFace
Original | 0.10 | 0.14 | 0.10 | 0.14
Bald | 0.12 | 0.12 | 0.11 | 0.16
Bangs | 0.09 | 0.11 | 0.11 | 0.17
Black_Hair | 0.09 | 0.10 | 0.11 | 0.14
Blond_Hair | 0.10 | 0.11 | 0.10 | 0.15
Brown_hair | 0.08 | 0.10 | 0.10 | 0.14
Bushy_Eyebrows | 0.09 | 0.11 | 0.11 | 0.16
Eyeglasses | 0.13 | 0.13 | 0.19 | 0.28
Male | 0.17 | 0.14 | 0.16 | 0.18
Mouth_Slightly_Open | 0.08 | 0.10 | 0.10 | 0.15
Mustache | 0.09 | 0.10 | 0.10 | 0.16
No_Beard | 0.08 | 0.10 | 0.10 | 0.16
Pale_Skin | 0.08 | 0.10 | 0.10 | 0.16
Young | 0.10 | 0.11 | 0.13 | 0.16

Analysis: In Table 1, we reported the results @FMR=0.01. We observed that the
attribute ‘Eyeglasses’, a facial attribute produced the highest degradation in
the biometric recognition performance (see the red colored cells). AttGAN-
ArcFace achieved FNMR=0.98 compared to the original performance of FNMR=0.25
@FMR=0.01 (reduction in performance by 73%). Note that we reported the
reduction as the difference between the FNMR obtained for modified images and
the original images. The DET curve indicated as Original in Figure 2 denotes
the face recognition performance computed using only the unmodified images.
AttGAN-VGGFace achieved FNMR=0.52 compared to the original performance of
FNMR=0.32 @FMR=0.01 (reduction in performance by 20%). STGAN-ArcFace achieved
FNMR=0.31 compared to the original performance of FNMR=0.25 @FMR=0.01
(reduction in performance by 6%). STGAN-VGGFace achieved FNMR=0.39 compared to
the original performance of FNMR=0.32 @FMR=0.01 (reduction in performance by
7%). The second highest degradation was caused due to the change in ‘Male’, a
demographic attribute. AttGAN-ArcFace achieved FNMR=0.47 compared to the
original performance of FNMR=0.25 @FMR=0.01 (reduction in performance by 22%).
AttGAN-VGGFace achieved FNMR=0.43 compared to the original performance of
FNMR=0.32 @FMR=0.01 (reduction in performance by 11%). STGAN-ArcFace achieved
FNMR=0.30 compared to the original performance of FNMR=0.25 @FMR=0.01
(reduction in performance by 5%). STGAN-VGGFace achieved FNMR=0.42 compared to
the original performance of FNMR=0.32 @FMR=0.01 (reduction in performance by
10%). STGAN-ArcFace achieved FNMR=0.18 compared to the original performance of
FNMR=0.25 @FMR=0.01 (improvement in performance by 7%) for the attribute
‘Pale_Skin’. In Table 2, we reported the results @FMR=0.1. We observed that
the attributes seem to improve the recognition performance by up to 4% in FNMR
for STGAN-ArcFace. On the contrary, for the remaining three sets, viz., STGAN-
VGGFace, AttGAN-ArcFace and AttGAN-VGGFace, we continued to observe a drop in
recognition performance with ‘Eyeglasses’ resulting in the worst drop in
performance by 14%, followed by ‘Male’ resulting in the second highest drop in
performance by 7%. Now, let us review the questions posited at the beginning
of the paper.

Question #1: Does GAN-based attribute editing only produce perceptual changes
in face images?
Observation: No. GAN-based attribute editing not only alters the perceptual
quality of the images but also significantly impacts the biometric recognition
performance. See Tables 1 and 2, where a majority of the attributes strongly
degraded the face recognition performance.

Question #2: Are there certain attribute manipulations that are more
detrimental than others on face verification performance?
Observation: Yes. Editing of ‘Eyeglasses’ attribute caused a significant
degradation in FNMR by up to 73% @FMR=0.01 for AttGAN-ArcFace. It was followed
by the the ‘Male’ attribute that caused the second highest degradation in FNMR
by up to 22% @FMR=0.01 for AttGAN-ArcFace. Surprisingly, a facial attribute,
‘Eyeglasses’ and a demographic attribute, ‘Male’, when edited separately, were
responsible for significant degradation in the biometric recognition
performance in a majority of the scenarios.

Question #3: Is the impact of GAN-based manipulations consistent across
different face recognition networks?
Observation: No. The impact of GAN-based attribute manipulations on face
recognition depends on two factors, firstly, which GAN was used to perform the
attribute editing operation, and secondly, which face recognition network was
used to measure the biometric recognition performance. For example, the ‘Bald’
attribute caused degradation in the performance for AttGAN, irrespective of
which face matcher was used. However, the same attribute caused improvement in
the face recognition accuracy for STGAN when ArcFace was used as the face
matcher, but caused reduction in the recognition performance when VGGFace was
used as the face comparator. Similar findings were observed for the ‘Bangs’
attribute.

Figure 4: Examples depicting ‘Male’ attribute edited using STGAN and AttGAN,
respectively, in male (top row) and female (bottom row) individuals. AttGAN
output images appear to contain more visual artifacts compared to STGAN
outputs.

(a) Without Eyeglasses

(b) With Eyeglasses

Figure 5: Examples depicting ‘Eyeglasses’ attribute edited using STGAN and
AttGAN, respectively, in original images (a) Without Eyeglasses and (b) With
Eyeglasses. Note in images containing eyeglasses, the GANs fail to remove the
glasses completely, instead they lighten the shades of the eyeglasses or the
glass rims. STGAN outputs appear better for images with and without
eyeglasses. Table 3: Face recognition performance: False Non-Match Rate (FNMR)
at a False Match Rate (FMR) = 0.01/0.1 for attribute manipulated images on the
LFW dataset. The red colored cells correspond to the maximum degradation (if
any) in the biometric recognition performance compared to the original in each
column. Note all of the attributes resulted in degradation. ‘Eyeglasses’
caused the worst degradation in biometric recognition performance.

|  | AttGAN-
---
ArcFace
| AttGAN-
---
VGGFace
Original | 0.17/0.11 | 0.39/0.17
Bald | 0.39/0.16 | 0.57/0.27
Bangs | 0.86/0.26 | 0.71/0.39
Black_Hair | 0.33/0.14 | 0.56/0.27
Blond_Hair | 0.36/0.14 | 0.59/0.27
Brown_hair | 0.33/0.14 | 0.59/0.31
Bushy_Eyebrows | 0.50/0.20 | 0.68/0.35
Eyeglasses | 0.99/0.43 | 0.77/0.49
Male | 0.26/0.11 | 0.47/0.23
Mouth_Slightly_Open | 0.30/0.12 | 0.51/0.23
Mustache | 0.36/0.16 | 0.56/0.28
No_Beard | 0.33/0.14 | 0.55/0.26
Pale_Skin | 0.33/0.14 | 0.56/0.26
Young | 0.32/0.13 | 0.55/0.26

To investigate the possibility of dataset-specific bias, we selected 495
images from the Labeled Faces in-the-Wild (LFW) dataset [12] belonging to 100
individuals, and applied attribute editing using AttGAN. AttGAN resulted in
the worst drop in performance on the CelebA dataset, so we employed it for
this experiment. This is done to examine whether the impact of attribute
editing on face recognition performance manifests across datasets. Next, we
computed the face recognition performance between the original and the
attribute-edited images using ArcFace and VGGFace comparators and observed the
following results. ‘Eyeglasses’ attribute editing resulted in the worst
degradation in the performance by 83% while using ArcFace and by 37% while
using VGGFace in terms of FNMR at FMR=0.01. It was followed by ‘Bangs’
attribute resulting in second-highest degradation in the performance by 69%
while using ArcFace and by 32% while using VGGFace in terms of FNMR at
FMR=0.01. See Table 3.

To investigate the possibility of GAN-specific artifacts, we compared the
‘Reconstructed’ images with the attribute edited images, specifically, the
‘Eyeglasses’ and ‘Male’ attribute edited images, to evaluate the face
recognition performance. This is done to assess whether face recognition
performance is affected solely by attribute editing or influenced by GAN-
specific artifacts. Note that ‘Reconstructed’ images are faithful
reconstruction of ‘Original’ images that demonstrate the fidelity of the GAN
as an effective autoencoder. See Table 4 for FNMR at FMR=0.01 and 0.1 for
Reconstructed-Reconstructed, Reconstructed-Eyeglasses and Reconstructed-Male
comparisons. We observed similar degradation in performance when comparing
attribute edited images with GAN-reconstructed images by up to 47% for
‘Eyeglasses’ attribute and by up to 12% for ‘Male’ attribute in terms of FNMR
at FMR=0.01. The results indicate that AttGAN has an overall weaker
reconstruction and attribute editing capability than STGAN.

Table 4: Face recognition performance: False Non-Match Rate (FNMR) at a False Match Rate (FMR) = 0.01/0.1 for attribute manipulated images. We report the face recognition performance by comparing ‘Reconstructed’ images with ‘Eyeglasses’ attribute and ‘Male’ attribute edited images. |  | STGAN-
---
VGGFace
| STGAN-
---
ArcFace
| AttGAN-
---
VGGFace
| AttGAN-
---
ArcFace
Reconstructed | 0.30/0.08 | 0.21/0.10 | 0.42/0.12 | 0.49/0.20
Eyeglasses | 0.38/0.12 | 0.27/0.11 | 0.50/0.19 | 0.96/0.29
Male | 0.42/0.16 | 0.28/0.12 | 0.47/0.20 | 0.46/0.19

The implications of our findings are as follows. Bias due to naturally
prevalent demographic factors in automated face recognition systems can be
further aggravated when attributes are digitally modified. Digitally altering
the sex cues (denoted by ‘Male’ attribute) can be considered as manipulating a
demographic attribute. It involves adding facial hair to images of female
individuals and adding makeup to impart feminine appearance to images of male
individuals. See Figure 4. These artificial manipulations affect face
recognition performance. Surprisingly, altering a facial attribute like
‘Eyeglasses’ caused an excessive degradation in face recognition performance.
Modifying the ‘Eyeglasses’ attribute involves adding glasses to individual
face images where no eyeglasses are present and removing eyeglasses in the
images where the individual is wearing one. See Figure 5. AttGAN struggles
with addition as well as removal of eyeglasses from the images, and, instead,
produces visually apparent artifacts that might be responsible for significant
degradation in the biometric recognition performance. Removal of glasses is
particularly hard: the GANs are only able to lighten the lens shades or the
color of the eyeglass frames, but not completely remove the glasses. To check
for any statistical variation between the results produced by AttGAN for the
‘Eyeglasses’ attribute, we repeated the experiment with the original images
five times. Each time, we followed the same procedure and executed basic
attribute editing and not attribute sliding (sliding regulates the intensity
of attribute modification). We obtained exactly identical results for each of
the five runs, i.e., a decrease by 73% in FNMR @FMR=0.01. On the LFW dataset,
‘Eyeglasses’ attribute resulted in a decrease by up to 83% in FNMR @FMR=0.01,
while ‘Bangs’, also a type of facial attribute, reduced the biometric
recognition performance by up to 69%. Therefore, we observed that ‘Eyeglasses’
attribute editing reduced the biometric recognition performance considerably
on both CelebA and LFW datasets. Although the exact reason responsible for
significant degradation in face recognition performance caused by ‘Eyeglasses’
attribute editing is unknown, we speculate that the attribute manipulations
may produce severe changes in texture around the facial landmarks resulting in
the drop in face recognition performance.

Therefore, our findings indicate that digitally modified attributes, both
demographic and facial, can have a major impact on automated face recognition
systems and can potentially introduce new biases that require further
examination.

##  5 Conclusion

In this paper, we examined the impact of GAN-based attribute editing on face
images in terms of face recognition performance. GAN-generated images are
typically evaluated with respect to visual realism but their influence on
biometric recognition is rarely analyzed. Therefore, we studied face
recognition performance obtained using ArcFace and VGGFace after modifying
thirteen attributes via AttGAN and STGAN on a total of $\sim$68,000 images
belonging to 853 individuals from the CelebA dataset. Our findings indicated
some interesting aspects: (i) Insertion or deletion of eyeglasses from a face
image can significantly impair biometric recognition performance by up to 73%.
Digitally modifying the sex cues caused the second highest degradation in the
performance by up to 22%. (ii) There can be an artificial boost in the
recognition accuracy by up to 7% depending on the GAN used to modify the
attributes and the deep learning-based face recognition network used to
evaluate the biometric performance. Similar observations were reported when
tested on a different dataset. Our findings indicate that attribute
manipulations accomplished via GANs can significantly affect automated face
recognition performance and need extensive analysis. Future work will focus on
examining the effect of editing multiple attributes simultaneously, in a
single face image, on face recognition.

## References

  * [1] Albiero, V., Zhang, K., King, M.C., Bowyer, K.W.: Gendered differences in face recognition accuracy explained by hairstyles, makeup, and facial morphology. IEEE Transactions on Information Forensics and Security 17, 127–137 (2022)
  * [2] ArcFace and VGGFace implementation: https://pypi.org/project/deepface/, [Online accessed: 18th May, 2022]
  * [3] AttGAN implementation: https://github.com/LynnHo/AttGAN-Tensorflow, [Online accessed: 18th May, 2022]
  * [4] Bharati, A., Singh, R., Vatsa, M., Bowyer, K.W.: Detecting facial retouching using supervised deep learning. IEEE Transactions on Information Forensics and Security 11(9), 1903–1913 (2016)
  * [5] Chen, H.J., Hui, K.M., Wang, S.Y., Tsao, L.W., Shuai, H.H., Cheng, W.H.: BeautyGlow: On-Demand Makeup Transfer Framework With Reversible Generative Network. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 10034–10042 (2019)
  * [6] Deng, J., Guo, J., Xue, N., Zafeiriou, S.: ArcFace: Additive Angular Margin Loss for Deep Face Recognition. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 4685–4694 (2019)
  * [7] FaceApp: https://www.faceapp.com/, [Online accessed: 17th May, 2022]
  * [8] Gong, S., Liu, X., Jain, A.K.: Jointly De-Biasing Face Recognition and Demographic Attribute Estimation. In: 16th European Conference on Computer Vision (ECCV). p. 330–347 (2020)
  * [9] Grother, P., Ngan, M., Hanaoka, K.: Face Recognition Vendor Test (FRVT) Part 3: Demographic Effects. NIST IR 8280 https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8280.pdf (2019)
  * [10] Gutierrez, N.R., Theobald, B., Ranjan, A., Abdelaziz, A.H., Apostoloff, N.: MorphGAN: Controllable One-Shot Face Synthesis. British Machine Vision Conference (BMVC) (2021)
  * [11] He, Z., Zuo, W., Kan, M., Shan, S., Chen, X.: AttGAN: Facial Attribute Editing by Only Changing What You Want. IEEE Transactions on Image Processing 28(11), 5464–5478 (2019)
  * [12] Huang, G.B., Ramesh, M., Berg, T., Learned-Miller, E.: Labeled faces in the wild: A database for studying face recognition in unconstrained environments. Tech. Rep. 07-49, University of Massachusetts, Amherst (October 2007)
  * [13] Huang, Y., Juefei-Xu, F., Wang, R., Xie, X., Ma, L., Li, J., Miao, W., Liu, Y., Pu, G.: FakeLocator: Robust Localization of GAN-Based Face Manipulations via Semantic Segmentation Networks with Bells and Whistles. ArXiv (2022)
  * [14] Klare, B.F., Burge, M.J., Klontz, J.C., Vorder Bruegge, R.W., Jain, A.K.: Face recognition performance: Role of demographic information. IEEE Transactions on Information Forensics and Security 7(6), 1789–1801 (2012)
  * [15] Krishnan, A., Almadan, A., Rattani, A.: Understanding fairness of gender classification algorithms across gender-race groups. In: 19th IEEE International Conference on Machine Learning and Applications (ICMLA). pp. 1028–1035 (2020)
  * [16] Kwak, J., Han, D.K., Ko, H.: CAFE-GAN: Arbitrary Face Attribute Editing with Complementary Attention Feature. In: European Conference on Computer Vision (ECCV) (2020)
  * [17] Liu, M., Ding, Y., Xia, M., Liu, X., Ding, E., Zuo, W., Wen, S.: STGAN: A Unified Selective Transfer Network for Arbitrary Image Attribute Editing. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 3668–3677 (2019)
  * [18] Liu, S., Li, D., Cao, T., Sun, Y., Hu, Y., Ji, J.: GAN-Based Face Attribute Editing. IEEE Access 8, 34854–34867 (2020)
  * [19] Liu, Z., Luo, P., Wang, X., Tang, X.: Deep Learning Face Attributes in the Wild. In: Proceedings of International Conference on Computer Vision (December 2015)
  * [20] Mirjalili, V., Raschka, S., Ross, A.: PrivacyNet: Semi-Adversarial Networks for Multi-Attribute Face Privacy. IEEE Transactions on Image Processing 29, 9400–9412 (2020)
  * [21] NIST Study Evaluates Effects of Race, Age, Sex on Face Recognition Software: https://www.nist.gov/news-events/news/2019/12/nist-study-evaluates-effects-race-age-sex-face-recognition-software, [Online accessed: 4th May, 2022]
  * [22] Phillips, P.J., Flynn, P.J., Bowyer, K.W.: Lessons from collecting a million biometric samples. Image and Vision Computing 58, 96–107 (2017)
  * [23] Ross, A., Banerjee, S., Chen, C., Chowdhury, A., Mirjalili, V., Sharma, R., Swearingen, T., Yadav, S.: Some research problems in biometrics: The future beckons. In: International Conference on Biometrics (ICB). pp. 1–8 (2019)
  * [24] Sgroi, A., Garvey, H., Bowyer, K., Flynn, P.: Location matters: A study of the effects of environment on facial recognition for biometric security. In: 11th IEEE International Conference and Workshops on Automatic Face and Gesture Recognition. vol. 02, pp. 1–7 (2015)
  * [25] STGAN implementation: https://github.com/csmliu/STGAN, [Online accessed: 18th May, 2022]
  * [26] Sun, R., Huang, C., Zhu, H., Ma, L.: Mask-aware photorealistic facial attribute manipulation. In: Computational Visual Media. vol. 7, pp. 363–374 (2021)
  * [27] Taigman, Y., Yang, M., Ranzato, M., Wolf, L.: DeepFace: Closing the Gap to Human-Level Performance in Face Verification. In: IEEE Conference on Computer Vision and Pattern Recognition. pp. 1701–1708 (2014)
  * [28] Terhörst, P., Kolf, J.N., Huber, M., Kirchbuchner, F., Damer, N., Moreno, A.M., Fierrez, J., Kuijper, A.: A Comprehensive Study on Face Recognition Biases Beyond Demographics. IEEE Transactions on Technology and Society 3(1), 16–30 (2022)
  * [29] Yang, H., Huang, D., Wang, Y., Jain, A.K.: Learning Face Age Progression: A Pyramid Architecture of GANs. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 31–39 (2018)
  * [30] Yu, N., Davis, L., Fritz, M.: Attributing Fake Images to GANs: Learning and Analyzing GAN Fingerprints. In: IEEE/CVF International Conference on Computer Vision. pp. 7555–7565 (2019)