# Some invariants related to threshold and chain graphs

Rameez Raja1 and Samir Ahmad Wagay2††,2Department of Mathematics, National
Institute of Technology Srinagar, Jammu and Kashmir, India. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author:1

###### Abstract

Let $G=(V,E)$ be a finite simple connected graph. We say a graph $G$ realizes
a code of the type $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots
0^{s_{k}}1^{t_{k}}$ if and only if $G$ can obtained from the code by some
rule. Some classes of graphs such as threshold and chain graphs realizes a
code of the above mentioned type. In this paper, we develop some
computationally feasible methods to determine some interesting graph
theoretical invariants. We present an efficient algorithm to determine the
metric dimension of threshold and chain graphs. We compute threshold dimension
and restricted threshold dimension of threshold graphs. We discuss
$L(2,1)$-coloring of threshold and chain graphs. In fact, for every threshold
graph $G$, we establish a formula by which we can obtain the
$\lambda$-chromatic number of $G$. Finally, we provide an algorithm to compute
the $\lambda$-chromatic number of chain graphs.

Keywords: Threshold graph, chain graph, metric dimension, threshold dimension,
$\lambda$-chromatic number.
2020 AMS Classification Code: 05C12, 05C15, 05C85.

##  1 Introduction

This paper is concerned with threshold and chain graphs. Recall that a graph
$G$ is called a chain graph if it is bipartite and the neighbourhoods of
vertices in each partite set form a chain with respect to set inclusion. The
color classes $U$, $V$ of a chain graph $G$ can be partitioned into $h$ non-
empty cells $U_{1},\cdots,U_{h}$ and $V_{1},\cdots,V_{h}$ such that
$N(u)=V_{1}\cup\cdots\cup V_{h-i+1}$ for any vertex $u\in U_{i}$ with $1\leq
i\leq h$, $N(u)$ denotes the neighbourhood of a vertex $u$ of $G$.
Equivalently, chain graphs are $\\{2K_{2},C_{3},C_{5}\\}$-free graphs. Chain
graphs present a broad class of graphical models for description of
conditional independence structures, including computer networks, social
networks, communication networks, information networks, software designs and
Bayesian networks.

On the other hand, threshold graphs are $\\{P_{4},C_{4},2K_{2}\\}$-free
graphs. The concept of threshold graphs was first established by the authors
Chvátal and Hammer [3] and Henderson and Zalcstein [9]. Threshold graphs play
an important role in graph theory as well as in several applied areas such as
psychology, computer science, scheduling theory, etc. These graphs can be used
to control the flow of information between processors, much like the traffic
lights used in controlling the flow of the traffic. These graphs can be viewed
as special cases of some wider classes of graphs like cographs, split graphs
and interval graphs.

It is important to mention here that threshold and chain graphs can be
generated by some binary code. In fact, given a binary code of the type
$0^{s_{1}}1^{t_{1}}\cdots 0^{s_{k}}1^{t_{k}}$, where $s_{i}$ and $t_{i}$ are
positive integers with $1\leq i\leq k$, we can construct these graphs. A
formal definition is presented in section 2. In this paper, we are mainly
interested to determine some graph theoretical invariants such as metric
dimension, threshold dimension, restricted threshold dimension and
$\lambda$-chromatic number from a binary generating code
$0^{s_{1}}1^{t_{1}}\cdots 0^{s_{k}}1^{t_{k}}$. We focus on developing some
computationally feasible methods to determine the invariants discussed in the
succeeding sections.

We have organized the theory and the results involved in this investigation as
follows. In section $2$, we present some preliminary information related to
threshold and chain graphs. We discuss some results regarding metric dimension
of threshold and chain graphs. We present an algorithm for computing the
metric dimension of a threshold graph and a chain graph from their respective
binary generating code. In section $3$, we provide bounds for the threshold
dimension and describe the method (Algorithm-(a)) for computing the restricted
threshold dimension of a threshold graph. Finally, we discuss the
$\lambda$-chromatic number of a threshold graph and introduce an algorithm
(Algorithm-(b)) to determine the $\lambda$-chromatic number of chain graphs.

##  2 Metric dimension

A threshold graph can be defined in several different ways as can be seen in
[13]. We follow the definition through binary generating codes, that is, a
threshold graph $G(b)$ is obtained from a binary code of the form
$b=(b_{1}b_{2}\cdots b_{n})$ in the following way,

  * (i)

Assume $G_{1}=G(b_{1})=K_{1}$, a single isolated vertex.

  * (ii)

For $i\geq 2$, let $G_{i-1}=G(b_{1}b_{2}...b_{i-1})$. Then the graph
$G_{i}=G(b_{1}b_{2}...b_{i-1}b_{i})$ is obtained by adding $b_{i}$ vertices to
$G_{i-1}$ (already constructed). Note that $b_{i}=0$ if the vertex $v_{i}$ is
added as an isolated vertex to $G_{i-1}$, and $b_{i}=1$ if $v_{i}$ is added as
a dominating vertex to $G_{i-1}$. This representation is called a binary
generating code for the threshold graph and is written as,

$b~{}=~{}(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})\cdots(0^{s_{k}}1^{t_{k}}),\mbox{where}~{}s_{i},t_{i}>0~{}\mbox{for}~{}1\leq
i\leq k.$

We restrict ourselves with connected graphs only, so $b_{k}=1$. A simplified
illustration of threshold graph is shown in Figure 1-(a).
Chain graphs are analogues to threshold graphs in the class of all connected
bipartite graphs of specified order and size. By deleting all the edges that
belong to the complete part of a threshold graph, we obtain the chain graph.
Accordingly, a chain graph can also be generated by a binary code in the
following way,

  * (i)

Assume $G_{1}=G(b_{1})=K_{1}$, a single isolated vertex.

  * (ii)

For $i\geq 2$, let $G_{i-1}=G(b_{1}b_{2}...b_{i-1})$. Then the graph
$G_{i}=G(b_{1}b_{2}...b_{i-1}b_{i})$ is obtained by adding $b_{i}$ vertices to
$G_{i-1}$ (already constructed). Note that $b_{i}=0$ if the vertex $v_{i}$ is
added as an isolated vertex to $G_{i-1}$ and $b_{i}=1$ if $v_{i}$ is added as
a dominating vertex to the only previously added isolated vertices of
$G_{i-1}$. A representation of the chain graph is shown in Figure 1-(b).

$U_{5}$$U_{4}$$U_{3}$$U_{2}$$U_{1}$$V_{5}$$V_{4}$$V_{3}$$V_{2}$$V_{1}$

(a) $U_{5}$$U_{4}$$U_{3}$$U_{2}$$U_{1}$$V_{5}$$V_{4}$$V_{3}$$V_{2}$$V_{1}$ (b)

Figure 1: Representation of threshold and chain graphs generated by a code
$0101010101$

Note that, we call a part $0^{s}1^{t}$ of a binary generating code as a
string. The power bit $0^{s}$ represents the independent part (white class)
and $1^{t}$ represents the complete part (black class) of vertices of the
graph $G$ realized by $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots
0^{s_{k}}1^{t_{k}}$.

Let $\mathcal{W}=\\{v_{1},v_{2},\cdots,v_{k}\\}$ be an ordered set of vertices
of $G$ and let $w\in V(G)$. The representation of $w$ with respect to
$\mathcal{W}$ is the ordered $k$-tuple
$d(w|\mathcal{W})=\big{(}d(w,v_{1}),d(w,v_{2}),\cdots,d(w,v_{k})\big{)}$,
where $d(w,v_{i})$ represents distance between the vertex $w$ and vertices
$v_{i}$, where $1\leq i\leq k$. If every two vertices of $G$ have distinct
representations with respect to $\mathcal{W}$, then the set $\mathcal{W}$ is
called a resolving set (locating set) for $G$. The metric dimension of $G$ is
the minimum cardinality of a resolving set of $G$ denoted by $\beta(G)$. A
resolving set containing a minimum number of vertices is called a basis
(reference set) for $G$.

Resolving sets for graphs were introduced independently by Slater [16] and
Harary and Melter[8], while the concept of a resolving set and that of metric
dimension were defined much earlier in the more general context of metric
spaces by Blumenthal in his monograph theory and applications of distance
geometry. Graphs are special examples of metric spaces with their intrinsic
path metric. The metric dimension has appeared in various applications in
graph theory as diverse as pharmaceutical chemistry, combinatorial
optimization [15], mastermind game tactics [4], network discovery and
verification [1], robot navigation [11] and so on. According to the authors
[5], the problem of determining the metric dimension of an arbitrary graph is
NP-complete. The following interesting results have appeared in [2].

######  Theorem 2.1.

If $G$ is a connected graph of order $n\geq 2$ and diameter $d$, then
$f(n,d)\leq\beta(G)\leq n-d$, where $f(n,d)$ is the least positive integer $k$
for which $k+d^{k}\geq n$.

######  Theorem 2.2.

Let $G$ be a connected graph of order $n\geq 2$. Then the following hold,

  * (i)

$\beta(G)=1$ if and only if $G$ is a path and,

  * (ii)

$\beta(G)=n-1$ if and only if $G$ is a complete graph.

In the following result, we determine the metric dimension of a threshold
graph realized by a string of type $0^{s}1^{t}$.

######  Lemma 2.3.

If $G$ is a graph of order $s+t$ realized by the string $0^{s}1^{t}$, then
$\beta(G)=s+t-2$, where $s>1$.

######  Proof 1.

We partition the vertex of $G$ as, $V(G)=U\cup V$, where
$U~{}=\\{u_{1},u_{2},\cdots,u_{s}\\}$ and $V=\\{v_{1},v_{2},\cdots,v_{t}\\}$
represents the independent and complete parts of $G$. Since $G$ is threshold,
therefore $d(u_{i},u_{k})=2$, for all $i\neq k$ and
$d(u_{i},v_{j})=d(v_{j},v_{l})=1$, for all $j\neq l$. It follows that there
are only two vertices in $G$ (one from each $U$ and $V$) whose distances are
uniquely determined by the vertex set of $G$. Therefore the resolving set of
$G$ contains exactly $s-1$ vertices of $U$ and $t-1$ vertices of $V$, that is,
$\mathcal{W}=\\{u_{1},u_{2},\cdots,u_{s-1},v_{1},v_{2},\cdots,v_{t-1}\\}$
contains all but two vertices of $G$ and the result follows.

######  Proposition 2.1.

Let $G_{1}$ be a graph realized by $0^{s_{1}}1^{t_{1}}$ with
$\beta(G_{1})=\alpha$ and let $G_{2}$ be a graph realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}$. Then the metric dimension of $G_{2}$
is one of the following.

  * (i)

If $s_{2}>1,t_{2}>1$ and $G_{1}$ is not a star graph, then
$\beta(G_{2})=\alpha+(s_{2}+t_{2}-2)$, otherwise it is
$\alpha+(s_{2}+t_{2}-1)$.

  * (ii)

If $s_{2}>1,t_{2}=1$ and $G_{1}$ is not a star graph, then
$\beta(G_{2})=\alpha+(s_{2}-1)$, otherwise it is $\alpha~{}+~{}s_{2}$.

  * (iii)

If $s_{2}=1,t_{2}>1$, then $\beta(G_{2})=\alpha+t_{2}$.

  * (iv)

If $s_{2}=1,t_{2}=1$, then $\beta(G_{2})=\alpha+1$.

######  Proof 2.

As before, we partition the vertex set of $G_{2}$ as, $V(G_{2})=U\cup V$,
where
$U=\\{(x_{1},x_{2},\cdots,x_{s_{1}})\cup(z_{1},z_{2},\cdots,z_{s_{2}})\\}=\\{I_{1}\cup
I_{2}\\}$ and
$V=\\{(y_{1},y_{2},\cdots,y_{t_{1}})\cup(u_{1},u_{2},\cdots,u_{t_{2}})\\}=\\{J_{1}\cup
J_{2}\\}$. The sets $I_{1},I_{2}$ and $J_{1},J_{2}$ respectively represents
the independent and complete parts of $G_{2}$. For all $i,j,k$ and $l$,
$d(x_{i},y_{j})=d(x_{i},u_{l})=d(z_{k},u_{l})=1$ and
$d(x_{i},z_{k})=d(y_{j},z_{k})=2$.

To prove (i), assume $G_{1}$ is not a star graph. Then the distance vector of
all vertices of $I_{1}$ is of the form
$(2,2,\cdots,2,1,1,\cdots,1,~{}2,2,\cdots,2,1,1,\cdots,1)$, where as the
distance vectors of all vertices of $J_{1}$, $I_{2}$ and $J_{2}$ are of the
forms $(1,1,\cdots,1,1,1,\cdots,1,2,2,\cdots,2,1,1,\cdots,1)$,
$(2,2,\cdots,2,2,2,\cdots,2\\\ ,2,2,\cdots,2,1,1,\cdots,1)$ and
$(1,1,\cdots,1,1,1,\cdots,1,1,1,\cdots,1,1,1,\cdots,1)$ respectively.
Therefore,
$\mathcal{W}=\\{x_{1},x_{2},\cdots,x_{s_{1}-1},y_{1},y_{2},\cdots,y_{t_{1}-1},z_{1},z_{2},\cdots,z_{s_{2}-1},u_{1},u_{2},\cdots,u_{t_{2}-1}\\}$
is the required resolving set and consequently,
$\beta(G_{2})=s_{1}-1+t_{1}-1+s_{2}-1+t_{2}-1=\alpha+(s_{2}+t_{2}-2)$.
If $G_{1}$ is a star graph, then
$V(G_{2})=\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1}\\}\cup\\{z_{1},z_{2},\cdots,z_{s_{2}}\\}\cup\\{u_{1},u_{2},\cdots,u_{t_{2}}\\}$.
By Lemma (1), the resolving set of $G_{1}$ contain all but one vertices of
$I_{1}$. Taking this into consideration, $d(z_{k},x_{i})=2$ for all $i,k$ and
$d(u_{l},x_{i})=1$ for all $i,l$. Thus,
$\mathcal{W}=\\{x_{1},x_{2},\cdots,x_{s_{1}-1},z_{1},z_{2},\cdots,z_{s_{2}},u_{1}\\\
,u_{2},\cdots,u_{t_{2}-1}\\}$ and therefore,
$\beta(G_{2})=s_{1}-1+s_{2}+t_{2}-1=\alpha+(s_{2}+t_{2}-1)$.

To prove (ii), we first assume that $G_{1}$ is not a star graph. Then by Lemma
(1), the resolving set of $G_{1}$ is
$\\{x_{1},x_{2},\cdots,x_{s_{1}-1},y_{1},y_{2},\cdots,y_{t_{1}-1}\\}$. By
adding $s_{2}$ number of isolated vertices and a single dominating vertex
$u_{1}$ to $G_{1}$, the new graph $G_{2}$ obtained from $G_{1}$ has a vertex
set of the form
$\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1},y_{2},\cdots,y_{t_{1}}\\}\cup\\{z_{1},z_{2},\cdots,z_{s_{2}}\\}\cup\\{u_{1}\\}$.
However, $d(z_{k},x_{i})=d(z_{k},y_{j})=2~{}~{}\mbox{for all}~{}~{}i,j,k$ and
the vertex $u_{1}$ is adjacent to every vertex of $G_{2}$. Therefore, the
resolving set of $G_{2}$ contains the resolving set of $G_{1}$ and all but one
vertices of $I_{2}$. Thus,
$\mathcal{W}=\\{x_{1},x_{2},\cdots,x_{s_{1}-1},y_{1},y_{2},\cdots,y_{t_{1}-1}\\\
,z_{1},z_{2},\cdots,z_{s_{2}-1}\\}$ and
$\beta(G_{2})=s_{1}-1+t_{1}-1+s_{2}-1=\alpha+(s_{2}-1)$.
If $G_{1}$ is a star graph, then
$V(G_{2})=\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1}\\}\cup\\{z_{1},z_{2},\cdots,z_{s_{2}}\\}\cup\\{u_{1}\\}$.
For each $i$ and $k$, we have $d(z_{k},x_{i})=d(z_{k},y_{1})=2$, and
therefore, the resolving set contains all but one independent vertices of
$G_{2}$. This implies,
$\mathcal{W}=\\{x_{1},x_{2},\cdots,x_{s_{1}-1},z_{1},z_{2},\cdots,z_{s_{2}}\\}$
and $\beta(G_{2})=s_{1}-1+s_{2}=\alpha+s_{2}$.

For (iii), we consider the graph $G_{2}$ obtained from $G_{1}$ by adding a
single isolated vertex $z_{1}$ and $t_{2}$ number of dominating vertices. Then
the vertex set of $G_{2}$ is of the form
$\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1},y_{2},\cdots,y_{t_{1}}\\}\cup\\{z_{1}\\}\cup\\{u_{1},u_{2},\cdots,u_{t_{2}}\\}$.
For each $i,j$ and $l$, $d(z_{1},x_{i})=d(z_{1},y_{j})=2$ and
$d(u_{l},x_{i})=d(u_{l},y_{j})=d(u_{l},z_{1})=1$. Therefore, the resolving set
of $G_{2}$ contains the resolving set of $G_{1}$ and all the newly added
dominating vertices of $G_{2}$. Thus,
$\mathcal{W}=\\{x_{1},\cdots,x_{s_{1}-1},y_{1},\cdots,y_{t_{1}-1},u_{1},u_{2},\cdots,u_{t_{2}}\\}$
and $\beta(G_{2})=s_{1}-1+t_{1}-1+t_{2}=\alpha+t_{2}$.

Finally for (iv), let
$V(G_{2})=\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1},y_{2},\cdots,y_{t_{1}}\\}\cup\\{z_{1}\\}\cup\\{u_{1}\\}$.
Then the resolving set of $G_{2}$ contains the resolving set of $G_{1}$ along
with one of the vertex from $\\{z_{1},u_{1}\\}$ and therefore,
$\beta(G_{2})=\alpha+1$.

######  Theorem 2.4.

For each $s_{i}>1$, $t_{i}>1$ with $1\leq i\leq k$, the metric dimension of a
graph $G$ realized by a code of the type
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$ is
$\sum\limits_{i=1}^{k}(s_{i}~{}+~{}t_{i}~{}-~{}2)$.

######  Proof 3.

Apply Proposition (2) to each string of the form $(0^{s_{3}}1^{t_{3}})$,
$(0^{s_{4}}1^{t_{4}})$, $\cdots$, $(0^{s_{k}}1^{t_{k}})$. Then the resolving
set of $G$ contains exactly $s_{i}~{}-1+~{}t_{i}~{}-~{}1$ number of vertices.
Thus, $\beta(G)~{}=~{}\sum\limits_{i=1}^{k}(s_{i}~{}+~{}t_{i}~{}-~{}2)$.

Next, we provide bounds for the metric dimensions of a graph $G$ realized by
any code of the type $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots
0^{s_{k}}1^{t_{k}}$. We also present families of graphs for which the bounds
are attained.

######  Theorem 2.5.

Let $G$ be a graph realized by a code
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$. Then the
following hold,

$\sum\limits_{i=1}^{k}(s_{i}+t_{i}-2)\leq\beta(G)\leq\sum\limits_{i=1}^{k}(s_{i}+t_{i}-1).$

If $s_{i}>1$ and $t_{i}>1$ with $1\leq i\leq k$, then the lower bound is
attained and the upper bound is attained if and only if $s_{i}=1$ and
$t_{i}\geq 1$.

######  Proof 4.

By Lemma (1), the resolving set of every graph realized by a string
$(0^{s_{i}}1^{t_{i}})$ contains atleast $(s_{i}+t_{i}-2)$ vertices. Therefore,
$\beta(G)\geq\sum\limits_{i=1}^{k}(s_{i}~{}+~{}t_{i}~{}-~{}2)$ and the
equality follows from Theorem (3).
By Lemma (1), we see that for each $i$, $1\leq i\leq k$ there are at most two
vertices in each string $(0^{s_{i}}1^{t_{i}})$ (one from each partite set)
which does not belong to $\mathcal{W}$ of $G$. If $s_{i}=1$ for all $i$, then
by Theorem (3), the set $\mathcal{W}$ does not contain any vertex from the
independent part of the string $(0^{s_{i}}1^{t_{i}})$. This implies that
$\mathcal{W}$ contains all vertices of the complete part. However, if
$s_{i}\geq 2$, then $\mathcal{W}$ contains atleast one vertex from the
independent part of the string $(0^{s_{i}}1^{t_{i}})$, which resolves any pair
of vertices from two consecutive complete parts say $J_{i}$ and $J_{i+1}$ of
$G$. Note that if $s_{i}=1$ for each $i$, then $|\mathcal{W}|$ is maximum
(that is, when every string in the graph $G$ is of the form $01^{t_{i}}$,
where $t_{i}\geq 2$), that is,
$|\mathcal{W}|\leq\sum\limits_{i=1}^{k}(s_{i}+t_{i}-2+1)=\sum\limits_{i=1}^{k}(s_{i}+t_{i}-1)$.
Moreover, if for each $i$, $s_{i}=1$ and $t_{i}\geq 1$, then the equality
follows directly from Theorem (3) and consequently,
$\beta(G)=\sum\limits_{i=1}^{k}(1+t_{i}-1)=\sum\limits_{i=1}^{k}t_{i}$.
Conversely, suppose that there is atleast one $s_{i}>1$. Without loss of
generality say it is $s_{1}$. Then the graph $G$ realizes a code
$0^{s_{1}}1^{t_{1}}01^{t_{2}}\cdots 01^{t_{k}}$. By Lemma (1), we have seen
that if the cardinality of the independent part in any string
$0^{s_{i}}1^{t_{i}}$ is greater than $1$, then the resolving set contains
exactly $s_{i}+t_{i}-2$ vertices. Using this argument, the metric dimension of
$G$ is
$(s_{1}+t_{1}-2)+(s_{2}+t_{2}-1)+\cdots+(s_{k}+t_{k}-1)=\sum\limits_{i=1}^{k}(s_{i}+t_{i}-1)-1<\beta(G)$,
a contradiction.

It is pertinent to mention that from preceding results, the metric dimension
$\beta(G)$ of a graph $G$ realized by any code of the type
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$ is dependent
on the powers of bits $0$ and $1$ of strings $(0^{s_{i}}1^{t_{i}})$, that is,
by varying the powers of bits in the code, $\beta(G)$ also varies. In fact
$\beta(G)$ gets effected if and only if $s_{i}=1$ or $t_{i}=1$. As seen above
in Theorem (4), the upper bound for $\beta(G)$ is attained if and only if
$s_{i}=1$ and $t_{i}\geq 1$ for each $i$ and the lower bound is attained if
for each $i$, $s_{i}>1$ and $t_{i}>1$. Below, we present an algorithm to
determine the metric dimension of any graph $G$ realized by a code of the type
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$. The input is
a binary code of length $k\geq 3$, and in return we obtain $\beta(G)$ .

Algorithm-(a) (method to compute the metric dimension of threshold graphs)

INPUT: $(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})\cdots(0^{s_{k}}1^{t_{k}}).$
OUTPUT: $\beta(G)$.
Step-1. If $i=2$, $1\leq i\leq k$, then $\beta(G)=\alpha_{1}$ (computed in
Proposition (2)). For $i=3$, go to Step-2.
Step-2. If $s_{3}>1$ and $t_{3}\geq 1$, then
$\beta(G)=\alpha_{1}+(s_{3}+t_{3}-1)=\alpha_{2}$, only if $s_{2}>1,~{}t_{2}=1$
or $s_{2}>1$ and $t_{1}=s_{1}=t_{2}=1$, otherwise, apply Proposition (2). For
$i=4$, go to Step-3.
Step-3. If $s_{4}>1$ and $t_{4}\geq 1$, then
$\beta(G)=\alpha_{2}+(s_{3}+t_{3}-1)=\alpha_{3}$, only if $s_{3}>1,~{}t_{3}=1$
or $s_{2}>1$ and $t_{2}=s_{3}=t_{3}=1$ or $s_{1}>1$ and
$t_{1}=t_{2}=t_{3}=s_{2}=s_{3}=1$, otherwise, apply Proposition (2). For
$i=5$, go to Step-4.
Step-4. Follow the same iteration for $i=5,6,\cdots,k-1$ and suppose that for
$i=k-1$, $\beta(G)=\alpha_{k-2}$. Finally, for $i=k$ go to Step-5.
Step-5. If $s_{k}>1$ and $t_{k}\geq 1$, then
$\beta(G)=\alpha_{k-2}+(s_{k}+t_{k}-1)=\alpha_{k-1}$, only if $s_{k-1}>1$ and
$t_{k-1}=1$ or for any $i$, $1\leq i\leq k-2$, $s_{i}>1$, $t_{i}=1$ and
$s_{i+1}=s_{i+2}=\cdots=s_{k-1}=t_{i+1}=t_{i+2}=\cdots=t_{k-1}=1$, otherwise,
apply Proposition (2).
Step-6. END.

It is not difficult to see that the algorithm-(a) is linear. Indeed for each
$i$, $1\leq i\leq k$, $\beta(G)$ is computed on the basis of previous
iteration and we have at most $n$ iterations such that each one is performed
with $O(1)$ operations, which gives $O(n)$ for these steps.

We notice that by removing all the edges in the complete part of a threshold
graph, the resultant graph is a chain graph. As discussed above, chain graphs
can also be generated by a binary code of the type
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$. The metric
dimension of a threshold graph $0^{s}1^{t}$ is either $s+t-2$ or $s+t-1$.
However, the metric dimension of its corresponding chain graph of order
greater or equal to three is always $s+t-2$.

In the following result, we determine the metric dimension of a chain graph
realized by a code $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}$.

######  Lemma 2.6.

Let $H_{1}$ be a chain graph realized by $0^{s_{1}}1^{t_{1}}$ with
$\beta(H_{1})=\alpha^{\prime}$ and let $H_{2}$ be a chain graph realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}$. Then the following hold.
(i) For each $s_{2}>1$ and $t_{2}>1$,

$\beta(H_{2})=\begin{cases}\alpha^{\prime}+(s_{2}+t_{2}-1)&if~{}s_{1}>1~{}\mbox{and}~{}t_{1}=1\\\
\alpha^{\prime}+(s_{2}+t_{2}-2)&otherwise.\end{cases}$

(ii) For $s_{2}>1$ and $t_{2}=1$,

$\displaystyle\beta(H_{2})=\begin{cases}\alpha^{\prime}+s_{2}&if~{}s_{1}>1~{}\mbox{and}~{}t_{1}=1\\\
\alpha^{\prime}+(s_{2}-1)&otherwise.\end{cases}$

(iii) For $s_{2}=1$ and $t_{2}>1$, $\beta(H_{2})=\alpha^{\prime}+t_{2}$.
(iv) For each $s_{2}=t_{2}=1$,

$\beta(H_{2})=\begin{cases}1&if~{}s_{1}=t_{1}=1\\\
\alpha^{\prime}+1&otherwise.\end{cases}$

######  Proof 5.

We partition the vertex set of $H_{2}$ as, $V(H_{2})=U\cup
V=\\{{u_{1},u_{2},\cdots,u_{s_{1}}\\}}\cup\\{{v_{1},v_{2},\cdots,v_{t_{1}}\\}}\cup\\{{u^{\prime}_{1},u^{\prime}_{2},\cdots,u^{\prime}_{s_{2}}\\}}\cup\\{{v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{t_{2}}\\}}=U_{1}\cup
V_{1}\cup U_{2}\cup V_{2}$, where $U_{1},U_{2}$ represents classes of white
vertices and $V_{1},V_{2}$ represents classes of black vertices in $H_{2}$.
Then for every $i,j,k$ and $l$,
$d(u_{i},u^{\prime}_{k})=d(v_{j},v^{\prime}_{l})=2$,
$d(u_{i},v_{j})=d(u_{i},v^{\prime}_{l})=d(u^{\prime}_{k},v^{\prime}_{l})=1$
and $d(v_{j},u^{\prime}_{k})=3$.

To prove (i), suppose $s_{1}>1$ and $t_{1}=1$. Then,
$V(H_{2})=\\{{u_{1},\cdots,u_{s_{1}}\\}}\cup\\{{v_{1}\\}}\cup\\{{u^{\prime}_{1},\cdots,u^{\prime}_{s_{2}}\\}}\cup\\{{v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{t_{2}}\\}}$.
From the structure of the graph $H_{2}$, we see that there are vertices $x\in
U_{1}\cup U_{2}$, $y\in V_{2}$ and $z\in V_{1}$ such that
$d(x|\mathcal{W})\neq d(y|\mathcal{W})\neq d(z|\mathcal{W})$, where
$\mathcal{W}=V(H_{2})\setminus\\{x,y,z\\}$. Therefore,
$\beta(H_{2})=s_{1}-1+s_{2}+t_{2}-1=\alpha^{\prime}+(s_{2}+t_{2}-1)$, where
$\alpha^{\prime}=\beta(H_{1})$.
If $s_{1}=1$ and $t_{1}>1$ , then
$V(H)=\\{{u_{1}\\}}\cup\\{{v_{1},\cdots,v_{t_{1}}\\}}\cup\\{{u^{\prime}_{1},\cdots,u^{\prime}_{s_{2}}\\}}\cup\\{{v^{\prime}_{1},\cdots,v^{\prime}_{t_{2}}\\}}$.
Using the same argument as above, the resolving set of $H_{2}$ is given as,
$\mathcal{W}=\\{{v_{1},\cdots,v_{t_{1}-1},u^{\prime}_{1},\cdots,u^{\prime}_{s_{2}-1},v^{\prime}_{1},\cdots,v^{\prime}_{t_{2}-1}\\}}$.
Thus, $\beta(H)=t_{1}-1+s_{2}-1+t_{2}-1=\alpha^{\prime}+(s_{2}+t_{2}-2)$.

For (ii), it is given that $s_{2}>1$ and $t_{2}=1$. Then for $s_{1}>1$ and
$t_{1}=1$,
$V(H_{2})=\\{{u_{1},u_{2},\cdots,u_{s_{1}}\\}}\cup\\{{v_{1}\\}}\cup\\{{u^{\prime}_{1},u^{\prime}_{2},\cdots,u^{\prime}_{s_{2}}\\}}\cup\\{{v^{\prime}_{1}\\}}$.
There are vertices $x\in U_{1}\cup U_{2}$, $y\in V_{2}$ and $z\in V_{1}$ such
that $d(x|\mathcal{W})\neq d(y|\mathcal{W})\neq d(z|\mathcal{W})$, where
$\mathcal{W}=V(H_{2})\setminus\\{x,y,z\\}$. Therefore,
$\beta(H)=|U_{1}|+|U_{2}|-1=s_{1}-1+s_{2}=\alpha^{\prime}+s_{2}$.
If $s_{1}=1$ and $t_{1}>1$, then using the same argument as above, the
resolving set of $H_{2}$ is,
$\mathcal{W}=\\{{v_{1},v_{2},\cdots,v_{t_{1}-1},u^{\prime}_{1},u^{\prime}_{2},\cdots,u^{\prime}_{s_{2}-1}\\}}$
and consequently, $\beta(H_{2})=t_{1}-1+s_{2}-1=\alpha^{\prime}+s_{2}-1$.

To prove (iii), let $s_{1}>1$ and $t_{1}=1$. Then,
$V(H_{2})=\\{{u_{1},u_{2},\cdots,u_{s_{1}}\\}}\cup\\{{v_{1}\\}}\cup\\{{u^{\prime}_{1}\\}}\cup\\{{v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{t_{2}}\\}}$.
The proof follows from (ii).

For (iv), it is given that $s_{2}=t_{2}=1$, suppose that $s_{1}=t_{1}=1$. Then
the graph $H_{2}$ is a path on four vertices and therefore, $\beta(H_{2})=1$.
If $s_{1}>1$ and $t_{1}=1$, then the basis of $H_{2}$ contains all vertices of
$H_{2}$ except one vertex of $U_{1}$. Thus,
$\beta(H_{2})=s_{1}-1+1=\alpha^{\prime}+1$.

######  Remark 2.2.

By Lemma (5), the metric dimension of any chain graph $H$ realized by
$(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})\\\ \cdots(0^{s_{i}}1^{t_{i}})$ can
be obtained iteratively for each $i\geq 3$. In fact, for $3\leq i\leq k$, the
Algorithm-(a) can be applied to determine the metric dimension of $H$, note
that for $i=2$, $\beta(H)=\alpha_{2}$ (Lemma (5)). The Algorithm-(a)
establishes a relationship between $\beta(H)$ and $\beta(G)$ and the equality
$\beta(H)=\beta(G)-1$ or $\beta(H)=\beta(G)$ follows, where $G$ is threshold
graph.

Now, we provide an example which illustrates the above theory and
Algorithm-(a) related to $\beta(H)$ and $\beta(G)$.

######  Example 2.7.

Let $G$ be a threshold graph and $H$ be a chain graph generated by a code of
the type $01^{2}0^{3}10^{2}1^{2}0^{3}1^{4}010^{3}1^{4}$. By Algorithm-(a), we
see that $\beta(G)=18$ whereas $\beta(H)=17$. Moreover, for $s_{1}\geq 2$, if
$G$ and $H$ are realized by
$0^{s_{1}}10^{s_{2}}10^{s_{3}}10^{s_{4}}10^{s_{5}}10^{s_{6}}10^{s_{7}}10^{s_{8}}1$,
then $\beta(H)=\beta(G)=\big{(}\sum\limits_{i=1}^{8}s_{i}\big{)}-1$.

##  3 Threshold dimension, restricted threshold dimension of a threshold graph

The metric basis determines the location of landmarks in a graph with a fixed
number of vertices. Chartrand et. al [2] and Khuller et. al [10] previously
posed a question that how the metric dimension of a graph is related to its
subgraphs? However, in [14], the authors have asked that how much the metric
dimension of a graph can be reduced by adding edges? Equivalently, for a given
graph $G$, what is the smallest metric dimension among all graphs that contain
$G$ as a spanning subgraph? Recall that the threshold dimension of a graph
$G$, denoted by $\tau(G)$, is defined as,

$\tau(G)=min\\{\beta(H):\mbox{H contaning G as a spanning subgraph}\\}$.

A graph $G$ is called irreducible if $\beta(G)=\tau(G)$, otherwise it is
reducible. In this section, a graph of order less or equal to $4$ is always
irreducible.

######  Lemma 3.1.

For $s\geq 3$, let $G$ be a graph realized by $0^{s}1^{t}$. If $s\leq
2^{k}-1+k,$ then $\tau(G)=t-1+k$, where $k\geq 2$ is the minimum number of
isolated vertices taken from the independent part of $G$.

######  Proof 6.

Let $V(G)=I\cup J$, where $I$ and $J$ represents the independent and complete
parts of $G$ with cardinalities $s$ and $t$ respectively. The only way to add
edges in $G$ is to add edges between the isolated vertices in $I$. Choose
$W\subset I$, a proper subset of $I$ with cardinality $k\geq 2$. Then it can
be verified that there are $2^{k}-1$ vertices of $I$ such that their distance
vectors are distinct with respect to $W$. In fact, the distance vectors are of
the form
$(1,1,\cdots,1,2),\cdots,(1,2,2,\cdots,2,1),\cdots,(2,1,\cdots,1),\cdots,(2,2,\cdots,2)$.
Therefore the resolving set of $G$ contains $|J|-1$ and $|W|$ vertices. Thus,
$\tau(G)=t-1+k$.

######  Example 3.2.

Let $G$ be a graph realized by $0^{2359}1^{15}$. Then for $k=11$,
$\tau(G)=15-1+11=25$ and $2359-11\leq 2^{11}-1$. However, if $k=10$, then it
can be verified that for $G$, Lemma (6) does not hold.

######  Theorem 3.3.

Let $G$ be a threshold graph realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}$. Then one of the following holds.
(i) If $s_{1}+t_{1}+s_{2}-k_{1}\leq 2^{k_{1}}-1$, then
$\tau(G)=(t_{2}-1)+k_{1}$.
(ii) If $t_{1}\geq 2^{s_{2}}-1$ and $s_{1}-k_{2}\leq
2^{s_{2}+k_{2}}-2^{s_{2}}$, then $\tau(G)=(t_{2}-1)+s_{2}+m_{1}+k_{2}$.
(iii) If $t_{1}<2^{s_{2}}-1$ and $s_{1}-m_{2}-k_{2}\leq
2^{s_{2}+k_{2}}-2^{s_{2}}$, then $\tau(G)=(t_{2}-1)+s_{2}+k_{2}$,
$~{}~{}~{}~{}~{}~{}~{}\mbox{where},m_{1}=t_{1}-2^{s_{2}}+1$,
$m_{2}=2^{s_{2}}-1-t_{1}$ and $k_{1}$, $k_{2}$ are positive integers.

######  Proof 7.

Let $V(G)=U\cup V$, where $U=U_{1}\cup U_{2}$ and $V=V_{1}\cup V_{2}$
represents the independent and complete parts of $G$ with cardinalities
$s_{1}+s_{2}$ and $t_{1}+t_{2}$. Clearly, from the structure of $G$, the
resolving set of $G$ contains atleast $|V_{2}|-1$ vertices.
To prove (i), choose $W\subseteq U_{2}$, a proper subset with cardinality
$k_{1}\geq 2$. Then by the similar argument as in Lemma (6), we have the
required result.

If $|V_{1}|\geq 2^{|U_{2}|}-1$, then $t_{1}-2^{s_{2}}+1\geq 0$. Note that
$m_{1}=t_{1}-2^{s_{2}}+1$ vertices from $V_{1}$ have same distance vectors
with respect to $U_{2}$ after adding $s_{2}(2^{s_{2}-1}-1)$ edges between
$V_{1}$ and $U_{2}$. Further adding of edges between vertices of $V_{1}$ is
not possible, since $V_{1}$ is complete. It remains to add edges between the
vertices of partite sets $U_{1}$ and $U_{2}$. As before, choose $W\subseteq
U_{1}$, a proper subset with cardinality $k_{2}$. Then the resolving set of
$G$ contains exactly $|V_{2}|-1+|U_{2}|+|V_{1}|-2^{|U_{2}|}+1+k_{2}$ vertices,
provided $|U_{1}|-k_{2}\leq 2^{|U_{2}|+k_{2}}-2^{|U_{2}|}$. Thus,
$\tau(G)=(t_{2}-1)+s_{2}+m_{1}+k_{2}$, whenever $s_{1}-k_{2}\leq
2^{s_{2}+k_{2}}-2^{s_{2}}$. Therefore, (ii) follows.

If $|V_{1}|<2^{|U_{2}|}-1$, then $m_{2}=t_{1}-2^{s_{2}}+1<0$ and there is
nothing to prove. Suppose $|U_{1}|\leq|m_{2}|$, then it gets reduced to (i)
proven above. If $|U_{1}|>|m_{2}|$, then as in (ii), we take a smallest subset
of $U_{1}$ with cardinality as $k_{2}$ satisfying $m_{2}-k_{2}\leq
2^{s_{2}+k_{2}}-2^{s_{2}}$. Therefore resolving set of $G$ contains
$(t_{2})-1+s_{2}+k_{2}$ vertices, whenever $m_{2}-k_{2}\leq
2^{s_{2}+k_{2}}-2^{s_{2}}$. Thus, (iii) follows.

######  Theorem 3.4.

Let $G$ be a threshold graph realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}0^{s_{3}}1^{t_{3}}$. Then one of the
following holds.
(i) If $\sum\limits_{i=1}^{3}(s_{i}~{}+~{}t_{3-i})-k_{1}\leq 2^{k_{1}}-1$,
then $\tau(G)=(t_{3}-1)+k_{1}$.
(ii) If $t_{2}\geq 2^{s_{3}}-1$ and $s_{1}+t_{1}+s_{2}-k_{2}\leq
2^{s_{3}+k_{2}}-2^{s_{3}}$, then
$\tau(G)=(t_{3}-1)+s_{3}+\big{(}t_{2}-(2^{s_{3}}-1)\big{)}+k_{2}$.
(iii) If $t_{2}<2^{s_{3}}-1$,
$\big{(}t_{1}-(2^{s_{3}}-1-t_{2})\big{)}\geq(2^{s_{2}+s_{3}}-2^{s_{3}})$ and
$s_{1}+s_{2}-k_{3}\leq 2^{s_{3}+k_{3}}-2^{s_{3}}$, then
$~{}~{}~{}~{}~{}~{}~{}\tau(G)=(t_{3}-1)+s_{3}+(t_{1}+t_{2}+1-2^{s_{2}+s_{3}})+k_{3}$.
(iv) If $t_{1}+t_{2}<2^{s_{3}}-1$,
$\sum\limits_{i=1}^{2}(s_{i}~{}+~{}t_{i})\geq 2^{s_{3}}-1$ and
$\sum\limits_{i=1}^{2}(s_{i}~{}+~{}t_{i})-k_{3}\leq
2^{s_{3}+k_{3}}-2^{s_{3}}$, then
$~{}~{}~{}~{}~{}~{}~{}\tau(G)=(t_{3}-1)+s_{3}+k_{3}$.
The numbers $k_{3},k_{2}$ and $k_{1}$ are any positive integers.

######  Proof 8.

The inequalities of the above type are extensions of the inequalities given in
Theorem (3.3), therefore the result can be proven by the similar approach.

######  Remark 3.1.

By Theorems {(3.3), (3.4)}, we can determine the threshold dimension of any
threshold graph $G$ realized by a code of the type
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$. Suppose for
each $i$, $s_{i}\geq t_{i}$ and
$\sum\limits_{i=1}^{k}(s_{i}~{}+~{}t_{k-i})-k_{1}\leq 2^{k_{1}}-1$, where
$1\leq i\leq k$ and $k_{1}$ a positive integer. Then
$\tau(G)=(t_{k}-1)+k_{1}$. Moreover, if $\sum\limits_{i=1}^{k-1}<2^{s_{k}}-1$,
$\sum\limits_{i=1}^{k-1}(s_{i}~{}+~{}t_{i})\geq 2^{s_{k}}-1$ and
$\sum\limits_{i=1}^{k-1}(s_{i}~{}+~{}t_{i})-r\leq 2^{s_{k}+r}-2^{s_{k}}$, then
$\tau(G)=(t_{k}-1)+s_{k}+r$, $r$ is some positive integer. Therefore, based on
the conditions of the powers of bits $0$ and $1$ of the code we can establish
the threshold dimension of any threshold graph.

###  3.1 Restricted threshold dimension

As defined in the preceding section, the threshold dimension of a threshold
graph $G$ is the minimum metric dimension among all graphs that contain $G$ as
a spanning subgraph. However, the resulting graph with the least metric
dimension may or may not be threshold. Related to the threshold dimension of
$G$, there is another graph theoretical invariant called as the restricted
threshold dimension of $G$, denoted by $\tau_{r}(G)$, which is defined as the
smallest metric dimension among all threshold graphs which contains $G$ as a
spanning subgraph, that is,

$\tau_{r}(G)=min\\{\beta(H):\mbox{H is a threshold graph contaning G as a
spanning subgraph}\\}.$

This section is devoted to study the restricted threshold dimension of the
threshold graph.

######  Proposition 3.2.

Let $G$ be a threshold graph realized by $0^{s}1^{t}$. Then the following
hold,

$\tau_{r}(G)=\lceil\frac{s}{2}\rceil+(t-1),$

where $s\geq 4$.

######  Proof 9.

We partition the vertex of $G$ as, $V(G)~{}=~{}U\cup V$. The set
$U~{}=\\{u_{1},u_{2},\cdots,u_{s}\\}$, represents the independent part of $G$
and $V~{}=\\{v_{1},v_{2},\cdots,v_{t}\\}$, represents the complete part of
$G$. By Lemma (1), $\beta(G)=s+t-2$. The only way to add edges in $G$ such
that $G$ continues to remain a threshold is to add edges between the vertices
in $U$. Suppose $u_{1}\sim\\{u_{2},u_{3},\cdots,u_{s}\\}$, that is $u_{1}$ is
adjacent to each of the vertex from $\\{u_{2},u_{3},\cdots,u_{s}\\}$. Then the
resulting graph $H$ is the threshold graph realized by$0^{s-1}1^{t+1}$ with
$\beta(G)=\beta(H)$. Now, suppose $u_{1}\sim u_{2}$ and
$\\{u_{1},u_{2}\\}\sim\\{u_{3},u_{4},\cdots,u_{s}\\}$. Then the resulting
threshold graph is some $H$ realized by $0^{s-2}1^{t+2}$ with
$\beta(G)=\beta(H)$. We continue the same process of adding edges till the
power of a bit $0$ is reduced to two and the resulting graph is a threshold
graph realized by $0^{2}1^{s+t-2}$. The total number of such graphs realized
by strings of length $1$ are ${{s}\choose{1}}-2$. Further, let $H$ be a
threshold graph realized by $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t}$ containing $G$
as a spanning subgraph. Note that $H$ is obtained from $G$ by making $t_{1}$
dominating vertices in $U$ and partition $s$ isolated vertices of $U$ into
$s_{1}$ and $s_{2}$ isolated vertices. The total number of such graphs is
${{s}\choose{3}}$. Using the same procedure, it can be verified that if $s$ is
even, then there are exactly
${{s}\choose{1}}-2+{{s}\choose{3}}+{{s}\choose{5}}+\cdots+{{s}\choose{s-1}}$
different threshold graphs with strings of lengths $1,2,\cdots,\frac{s}{2}$.
If $s$ is odd, there are
${{s}\choose{1}}-2+{{s}\choose{3}}+{{s}\choose{5}}+\cdots+{{s}\choose{s-2}}+1$
different threshold graphs with lengths $1,2,\cdots,\lceil\frac{s}{2}\rceil$.
By Theorem (4), among all $2^{s-1}-2$ threshold graphs with strings of lengths
less or equal to $\lfloor\frac{s}{4}\rfloor$, the metric dimension is greater
than $\lceil\frac{s}{2}\rceil$. Using the Algorithm-(a), the metric dimension
of all these $2^{s-1}-2$ threshold graphs with $G$ as a spanning subgraph lies
in $[\lceil\frac{s}{2}\rceil,s+t-2]$, where the maximum is attained for graphs
with strings of length $1$ and the minimum is attained if the graph with
string is of length atleast $\lfloor\frac{s}{4}\rfloor+1$. Furthermore, the
graphs obtained by adding the maximum number of edges with smaller metric
dimension are clearly dependent on the cardinality of $U$ alone. So, we
consider the following cases.
Case - I. $s\in\\{4k:k\geq 1\\}\cup\\{4k+2:k\geq 1\\}$, then following the
above computations, there is a unique graph $H$ realized by $0^{2}10101\cdots
0101^{t}$ with strings of length $\frac{s}{2}$. In fact $H$ is obtained by
adding $2k(2k-1)$ or $2k(2k+1)$ edges with metric dimension
$\underbrace{1+1+\cdots+1}_{\frac{s}{2}-1}+t=\frac{s}{2}+t-1$
Case - II. $s\in\\{4k+1:k\geq 1\\}\cup\\{4k-1:k\geq 2\\}$, then there is a
unique graph $H=0^{2}10101\cdots 0101^{t+1}$ with strings of length
$\frac{s-1}{2}$. The graph $H$ is obtained by adding $2k(2k+1)$ or $2k(2k-1)$
edges with metric dimension
$\underbrace{1+1+\cdots+1}_{\frac{s-1}{2}-1}+(t+1)=\frac{s-1}{2}+t=\lceil\frac{s}{2}\rceil+t-1$.
Thus, $\tau_{r}(G)=\beta(H)=\lceil\frac{s}{2}\rceil+t-1$.

######  Theorem 3.5.

Let $G$ a threshold graph realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$. Then for each
$i$,
$\tau_{r}(G)=\sum\limits_{i=1}^{k}\big{(}\lceil\frac{s_{i}}{2}\rceil+(t_{i}-1)\big{)}$,
where $1\leq i\leq k$, $s_{i}\geq 4$ and $t_{i}\geq 2$.

######  Proof 10.

By Proposition (9), the string $0^{s_{1}}1^{t_{1}}$ can be expressed in two
ways only. If $s_{1}$ is even, then the string can be uniquely written as
$0^{2}10101\cdots 0101^{t_{1}}$. On the other hand, if $s_{1}$ is odd, then it
can be written as $0^{2}10101\cdots 0101^{t_{1}+1}$. Using this approach to
each string $0^{s_{i}}1^{t_{i}}$, $2\leq i\leq k$ of the graph $G$. Since $G$
has $k$ strings, therefore, the metric dimension of $H$ is
$\big{(}\lceil\frac{s_{1}}{2}\rceil+(t_{1}-1)\big{)}+\big{(}\lceil\frac{s_{2}}{2}\rceil+(t_{2}-1)\big{)}+\cdots+\big{(}\lceil\frac{s_{n}}{2}\rceil+(t_{n}-1)\big{)}=\sum\limits_{i=1}^{n}\big{(}\lceil\frac{s_{i}}{2}\rceil+(t_{i}-1)\big{)}=\tau_{r}(G)$.

######  Remark 3.3.

For any threshold graph $G$ realized by
$0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$,
$\beta(G)=\tau_{r}(G)$, where $1\leq i\leq k$, $s_{i}\leq 3$ and $t_{i}\geq
2$. If $s_{i}\geq 4$ and $t_{i}=1$, then
$\tau_{r}(G)=\lceil\frac{s_{1}}{2}\rceil+(\lceil\frac{s_{2}}{2}\rceil+1)+\lceil\frac{s_{3}}{2}\rceil+(\lceil\frac{s_{4}}{2}\rceil+1)+\cdots+\big{(}(\lceil\frac{s_{k}}{2}\rceil+1)$
or $\lceil\frac{s_{k}}{2}\rceil\big{)}$ (depending on the length of the binary
generating code). If $s_{i}\leq 3$ and $t_{i}=1$, then
$\tau_{r}(G)=\sum\limits_{i=1}^{k}\lceil\frac{s_{i}}{2}\rceil$. Summing up all
the theory related to the restricted threshold dimension of a threshold graph
$G$ realized by $0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots
0^{s_{k}}1^{t_{k}}$, $\tau_{r}(G)$ can be obtained by the following procedure.
(i) If $s_{i}\in\\{4k:k\geq 1\\}\cup\\{4k+2:k\geq 1\\}$, then write each of
the strings $0^{s_{i}}1^{t_{i}}$ of $G$ as $0^{2}10101\cdots 0101^{t_{i}}$. If
$s_{i}\in\\{4k+1:k\geq 1\\}\cup\\{4k-1:k\geq 2\\}$, then write $G$ as
$0^{2}10101\cdots 0101^{t_{i}+1}$. In each case the strings of $G$ are of the
form $(0^{3}1^{t_{i}})$, we write it as $0101^{t_{i}}$, and continue the
process untill the power of a bit $0$ in the resulting graph is reduced to not
more than $2$.
(ii) If the code of the resulting graph $H$ is free from the string
$0^{s}1^{t}$, $t\geq 2$ and strings $(0^{2}1)$ are repeated $n$ number of
times, then replace $0^{2}1\longrightarrow(01^{2})$ at even places of the
code. If in the code of $H$, the string $(0^{2}1)$ is repeated $n$ number of
times between strings $0^{s}1^{t}$, $t\geq 2$, then again replace
$(0^{2}1)\longrightarrow(01^{2})$ at even places of the code. Finally, if the
string $(0^{2}1)$ is repeated $n$ number of times before or after the string
$0^{s}1^{t}$, $t\geq 2$, then follow the same process as mentioned. Therefore,
by the Algorithm-(a), $\beta(H)=\tau_{r}(G)$.

The following example illustrates Proposition (9) and Remark (3.3).

######  Example 3.6.

Let $G$ be a threshold graph realized by
$0^{3}1^{2}0^{8}1^{2}0^{5}10^{6}1^{4}0^{7}1^{2}$. Then by Algorithm-(a),
$\beta(G)=29$. Further, by applying Proposition(9) to each of the strings of
$G$, the code of the resulting threshold graph $H$ is
$(0101^{2})(0^{2}1010101^{2})(0^{2}101^{2})(0^{2}10101^{4})(0^{2}10101^{3})$
and $H$ contains $G$ as a spanning subgraph. Therefore, again by the
Algorithm-(a), $\tau_{r}(G)=22=\beta(H)$. However, if
$G=0^{2}10^{4}10^{6}10^{8}1$, then $\beta(G)=19$ and the code of the resulting
graph $H$ is $(0^{2}1)(0^{2}101)(0^{2}10101)(0^{2}1010101)$. Note that the
code of $H$ contains the string $0^{2}1$ four times. Therefore, by Remark
(3.3) replace $0^{2}1\longrightarrow 01^{2}$ at even places. Consequently,
$\tau_{r}(G)=12=\beta(H)$.

##  4 $\lambda$-chromatic number

Let $j$ and $k$ be two positive integers, an $L(j,k)$-coloring of a graph $G$
is a function from $V(G)$ to the set of non-negative integers such that
$|f(x)-f(y)|\geq j$, whenever $x,y\in V(G)$ are adjacent and $|f(x)-f(y)|\geq
k$, whenever $x,y\in V(G)$ 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)$-coloring of $G$ with a minimum value $\delta$ (say), then
the function $\mathfrak{g}$ defined on $V(G)$ by $\mathfrak{g}(v)=f(v)$ is
also an $L(j,k)$-coloring with a minimum value of $0$ and a maximum value of
$span(f)=span(\mathfrak{g})$. An $L(j,k)$-chromatic number, denoted by
$L_{j,k}(G)$, is the minimum span over all $L(j,k)$-colorings of $G$, and the
minimal coloring is the $L(j,k)$ coloring that corresponds to it. For the
cases $j=2$ and $k=1$, an $L(2,1)$-coloring problem was first studied by
Griggs and Yeh [7]. An $L(2,1)$\- coloring that uses colors from the set
$\\{1,2,\cdots,s\\}$ (not necessarily all) is called an $s$-coloring. The
minimum $s$, so that $G$ has a $s$-coloring is called the $\lambda$\-
chromatic number of $G$ and is denoted by $\lambda(G)$. If the color $h$,
$0<h<s$, is not used in an $s$-coloring of $G$, then $h$ is called the hole of
the coloring. The $L(j,k)$-coloring problem and $L(2,1)$-coloring problem have
been extensively studied in [6, 12].

In this section, we study the $\lambda$-chromatic number of threshold and
chain graphs. In the following result, we exactly determine the $\lambda$\-
chromatic number of a graph with diameter two.

######  Lemma 4.1.

Let $G$ be a diameter two graph with $\lambda(G)=s$. Then the following hold,

$\lambda(\mathcal{G}_{m,n})=s+\frac{|m-k|+(m-k)}{2}+2n,$

where $\mathcal{G}_{m,n}$ is the graph obtained from $G$ by adding $m$
isolated and $n$ dominating vertices, and $k$ is the number of holes in the
$s$-coloring of $G$.

######  Proof 11.

Let $f$ be the minimum $L(2,1)$-coloring of $G$ with $\lambda(G)=s$ and let
$\\{h_{1},h_{2},\cdots,h_{k}\\}$ be its holes. We obtain $\mathcal{G}_{m,n}$
from $G$ by adding $\\{x_{1},x_{2},\cdots,x_{m}\\}$ isolated vertices and
$\\{y_{1},y_{2},\cdots,y_{n}\\}$ dominating vertices. Define the
$L(2,1)$-coloring $g$ on $\mathcal{G}_{m,n}$ as follows,

$\displaystyle g(y_{i})$ $\displaystyle=$ $\displaystyle
2i-2,~{}~{}~{}~{}1\leq i\leq n,$ $\displaystyle g(v)$ $\displaystyle=$
$\displaystyle f(v)+2n,~{}~{}v\in V(G),$ $\displaystyle g(x_{i})$
$\displaystyle=$ $\displaystyle h_{i}+2n,~{}~{}~{}~{}1\leq i\leq m.$

If $m>k$ and $1\leq j\leq m-k$, then we define, $g(x_{k+j})=s+j+2n$.

$\mbox{Therefore},\max\limits_{v\in
V(G_{m,n})}{g(v)}=s+\frac{|m-k|+(m-k)}{2}+2n.$

Since the diameter of $G$ is two, therefore $f$ must be one-one and this
implies $g$ is well defined $L(2,1)$-coloring of $\mathcal{G}_{m,n}$. Further,
$f$ is minimum, therefore,
$\lambda(\mathcal{G}_{m,n})<s+\frac{|m-k|+(m-k)}{2}+2n$ is not possible and we
conclude $\lambda(\mathcal{G}_{m,n})=s+\frac{|m-k|+(m-k)}{2}+2n$.

The following result is an immediate consequence of Lemma (11).

######  Theorem 4.2.

Let $G$ be any threshold graph realized by
$(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})\cdots(0^{s_{k}}1^{t_{k}})$. Then

$\lambda(G)=2\sum\limits_{i=1}^{k}t_{i}+(s_{1}-1)+\frac{1}{2}{\sum\limits_{i=1}^{k-1}\big{(}|s_{i+1}-h_{i}|+(s_{i+1}-h_{i})\big{)}}$

where $h_{i}=t_{i}+\frac{1}{2}\big{(}|t_{i-1}-s_{i}|+(t_{i-1}-s_{i})\big{)}$,
$1\leq i\leq k$, denotes the number of holes in the minimum coloring of $G$.

######  Proof 12.

To prove the result, we use an iterative procedure on $k$. For $k=1$, let
$\mathcal{G}$ be a graph realized by $(0^{s_{1}}1^{t_{1}})$ with
$V(\mathcal{G})=X\cup
Y=\\{x_{1},x_{2},\cdots,x_{s_{1}}\\}\cup\\{y_{1},y_{2},\cdots,y_{t_{1}}\\}$.
Define the $L(2,1)$-coloring $f$ on $V(\mathcal{G})$ as follows,

$\displaystyle f(y_{i})$ $\displaystyle=$ $\displaystyle
2i-2,~{}~{}~{}~{}~{}~{}~{}~{}1\leq i\leq t_{1},$ $\displaystyle f(x_{i})$
$\displaystyle=$ $\displaystyle 2t_{1}+(i-1),~{}~{}~{}1\leq i\leq s_{1}.$

Since $\mathcal{G}$ is threshold with diameter less than three, this implies
that $f$ is one-one. Moreover, the clique number of $\mathcal{G}$ is
$t_{1}+1$, therefore $f$ has $t_{1}$ number of holes. Thus, $f$ is minimal and
$\lambda(\mathcal{G})=2t_{1}+s_{1}-1$. Let $\mathcal{G}_{s_{2},t_{2}}$ be a
graph realized by $(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})$, obtained from
$\mathcal{G}$ by adding $s_{2}$ isolated and $t_{2}$ dominating vertices. Then
by Lemma (11),

$\lambda(\mathcal{G}_{s_{2},t_{2}})=2\sum\limits_{i=1}^{2}t_{i}+(s_{1}-1)+\frac{1}{2}\big{(}|s_{2}-h_{1}|+(s_{2}-h_{1})\big{)},$

where $h_{1}=t_{1}$. We iterate further and finally, we obtain
$\mathcal{G}_{s_{k},t_{k}}=G$ realized by
$(0^{s_{1}}1^{t_{1}})(0^{s_{2}}1^{t_{2}})\cdots(0^{s_{k}}1^{t_{k}})$. Again,
by Lemma (11),

$\lambda(G)=2\sum\limits_{i=1}^{k}t_{i}+(s_{1}-1)+\frac{1}{2}{\sum\limits_{i=1}^{k-1}\big{(}|s_{i+1}-h_{i}|+(s_{i+1}-h_{i})\big{)}}.$

For $1\leq i\leq k$, the equality
$h_{i}=t_{i}+\frac{1}{2}\big{(}|t_{i-1}-s_{i}|+(t_{i-1}-s_{i})\big{)}$ follows
directly from the definition of minimal coloring $f$ of $G$.

Recall that a chain graph satisfy the nesting property, that is, there exists
a partition of $U=U_{1}\cup U_{2}\cup\cdots\cup U_{l}$ and $V=V_{1}\cup
V_{2}\cup\cdots\cup V_{l}$ such that for each $i$, $1\leq i\leq l$, the
neighbourhood of each vertex in $U_{i}$ is $V_{1}\cup V_{2}\cup\cdots\cup
V_{l+1-i}$. If $|U_{i}|=m_{i}$ and $|V_{i}|=n_{i}$, where $i=1,2,\cdots,l$,
then the another representation of $G$ is
$G(m_{1},\cdots,m_{l};~{}n_{1},\cdots,n_{l})$. Below, we present an algorithm
for determining the $\lambda$-chromatic number of chain graphs.

Algorithm-(b) (method for computing the $\lambda$-chromatic number of chain
graph)

INPUT: Chain graph $G(m_{1},\cdots,m_{l};~{}n_{1},\cdots,n_{l})$
Output: $\lambda(G)$
Step-1. For each vertices of the type $u_{i_{1}}\in U_{1}$, $u_{i_{2}}\in
U_{2},\cdots,u_{i_{l}}\in U_{l}$, where $1\leq i_{1}\leq m_{1}$, $1\leq
i_{1}\leq m_{2},\cdots,1\leq i_{l}\leq m_{l}$. Define $L(2,1)$-coloring on
$V(G)$ as,

$\displaystyle f(u_{i_{1}})$ $\displaystyle=$ $\displaystyle
i_{1}-1,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}1\leq i_{1}\leq m_{1},$ $\displaystyle
f(u_{i_{2}})$ $\displaystyle=$ $\displaystyle m_{1}-1+i_{2},~{}~{}~{}1\leq
i_{2}\leq m_{2},$ $\displaystyle\vdots$ $\displaystyle f(u_{i_{l}})$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l-1}(m_{i})-1+i_{l}~{}~{}~{}1\leq i_{l}\leq
m_{l}.$

and for vertices of type $v_{i_{1}}\in V_{1},v_{1_{2}}\in V_{2},$ where $1\leq
i_{1}\leq n_{1}$, define $L(2,1)$-coloring as,

$f(v_{i_{1}})=\sum\limits_{i=1}^{l}m_{i}+i_{1},~{}~{}1\leq i_{1}\leq
n_{1}~{}\mbox{and}~{}f(v_{1_{2}})=\sum\limits_{i=1}^{l}m_{i}.$

The sum $\sum\limits_{i=1}^{l}m_{i}$ is the hole of $f$. To color the
remaining vertices of the graph $G$, we go to Step-2 (note that by definition
of the graph, coloring of vertices of $v_{i_{2}}\in V_{2}$, $2\leq i_{2}\leq
n_{2}$, depends on the colors of vertices of $U_{l}$).
Step-2. Compute $|V_{2}|-|U_{l}|$, if $s_{1}=|V_{2}|-|U_{l}|\leq 0$, then go
to Step-3.
Step-3. If $r_{1}=|V_{2}|-|U_{l}|>0$, define,

$\displaystyle f({v_{{i_{2}}^{{}^{\prime}}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+{i_{2}^{{}^{\prime}}}~{}~{}~{}~{}1\leq{i_{2}^{{}^{\prime}}}\leq
r_{1}.$

Step-4. Compute $|V_{3}|-|U_{l-1}|$, if $s_{2}=|V_{3}|-|U_{l-1}|\leq 0$, then
go to Step-5.
Step-5. If $r_{2}=|V_{3}|-|U_{l-1}|>0$, then compute $r_{2}+s_{1}$. If
$s_{3}=r_{2}+s_{1}\leq 0$, then go to Step-6.
Step-6. If $r_{3}=r_{2}+s_{1}>0$, define,

$\displaystyle f({v_{{i_{3}}^{{}^{\prime}}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+{i_{3}^{{}^{\prime}}},~{}~{}1\leq{i_{3}^{{}^{\prime}}}\leq
r_{3},$

otherwise go to Step-7.
Step-7. If no such $s_{1}$ exists, then define,

$\displaystyle f({v_{{i_{3}}^{{}^{\prime}}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+r_{1}+{i_{3}^{{}^{\prime}}},~{}~{}~{}1\leq{i_{3}^{{}^{\prime}}}\leq
r_{3}.$

Step-8. Continue the same iterations.
Step-9. End.

Next, we provide extreme values (bounds) for $\lambda$-chromatic number of
chain graphs.

######  Theorem 4.3.

Let $G(m_{1},\cdots,m_{l};~{}n_{1},\cdots,n_{l})$ be a chain graph. Then the
following hold,

$\sum\limits_{i=1}^{l}m_{i}+n_{1}\leq\lambda(G)\leq\sum\limits_{i=1}^{l}m_{i}+n_{1}+\sum\limits_{i=1}^{l-1}(n_{i+1}-m_{l+1-i}).$

If $n_{i+1}>m_{l+1-i}$, then the maximum is attained and if $n_{i+1}\leq
m_{l+1-i}$, then the minimum is attained, where $1\leq i\leq{l-1}$.

######  Proof 13.

Since $G$ is a bipartite graph with partite sets $U$ and $V$, where $U$ is
partitioned into disjoint sets $U_{1},U_{2},\cdots,U_{l}$ and $V$ is
partitioned into $V_{1},V_{2},\cdots.,V_{l}$ with cardinalities $m_{i}$ and
$n_{i}$, respectively for $1\leq i\leq l$. We specify the vertices of
$U_{1},\cdots,U_{l}$ and $V_{1},\cdots,V_{l}$ as follows,

$\displaystyle U_{1}$ $\displaystyle=$
$\displaystyle\\{u_{1_{1}},u_{2_{1}},\cdots,u_{m_{1}}\\},$ $\displaystyle
U_{2}$ $\displaystyle=$
$\displaystyle\\{u_{1_{2}},u_{2_{2}},\cdots,u_{m_{2}}\\},$
$\displaystyle\vdots$ $\displaystyle U_{l}$ $\displaystyle=$
$\displaystyle\\{u_{1_{l}},u_{2_{l}},\cdots,u_{m_{l}}\\},$ $\displaystyle
V_{1}$ $\displaystyle=$
$\displaystyle\\{v_{1_{1}},v_{2_{1}},\cdots,v_{n_{1}}\\},$ $\displaystyle
V_{2}$ $\displaystyle=$
$\displaystyle\\{v_{1_{2}},v_{2_{2}},\cdots,v_{n_{2}}\\},$
$\displaystyle\vdots$ $\displaystyle V_{l}$ $\displaystyle=$
$\displaystyle\\{v_{1_{l}},v_{2_{l}},\cdots,v_{n_{l}}\\}.$

We define $L(2,1)$-coloring $f:V(G)\rightarrow[0,\infty)$ of $G$ as,

$\displaystyle f(u_{i_{1}})$ $\displaystyle=$ $\displaystyle
i_{1}-1,~{}~{}~{}~{}~{}1\leq i_{1}\leq m_{1},$ $\displaystyle f(u_{i_{2}})$
$\displaystyle=$ $\displaystyle m_{1}+i_{2},~{}~{}~{}1\leq i_{2}\leq m_{2},$
$\displaystyle\vdots$ $\displaystyle f(u_{i_{l}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l-1}(m_{i})-1+i_{l},~{}~{}1\leq i_{l}\leq
m_{l},$ $\displaystyle f(v_{i_{1}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+i_{1},~{}~{}~{}1\leq i_{1}\leq
n_{1},$ $\displaystyle f(v_{1_{2}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}m_{i}.$

Note that the vertex $v_{1_{2}}$ is colored by the hole
$\sum\limits_{i=1}^{l}m_{i}$. The coloring for rest of the vertices of $V_{2}$
depends on the cardinality of $U_{l}$, since $d(u_{i_{l}},v_{i_{2}})=3$ for
each $u_{i_{l}}$ and $v_{i_{2}}$. Similarly, coloring of vertices of $V_{3}$
depends on the cardinalities of $U_{l}$ and $U_{l-1}$ and in general, the
coloring of vertices of $V_{l}$ depends on the cardinalities of sets
$U_{2},\cdots,U_{l}$. Suppose, $|V_{2}|\leq|U_{l}|$. Then color all but one
($v_{1_{2}}$) vertices of $V_{2}$ by the existing colors of vertices of
$U_{l}$. In fact, if for each $i$, $3\leq i\leq l$, $|V_{i}|\leq|U_{l+2-i}|$,
then color the vertices of $V_{i}$ by the existing colors of $U_{l+2-i}$.
Therefore by the definition, $f$ is well-defined minimal coloring. Thus,
$span(f)=\sum\limits_{i=1}^{l}(m_{i})+n_{1}$ and consequently,
$\lambda(G)=\sum\limits_{i=1}^{l}(m_{i})+n_{1}$.
For each $2\leq i\leq l$, suppose $|V_{i}|>|U_{l+2-i}|$. Then,
$|V_{2}|-|U_{l}|=r_{1},|V_{3}|-|U_{l-1}|=r_{2},\cdots,|V_{l}|-|U_{2}|=r_{k}$.
By Algorithm-(b), we define $L(2,1)$-colors of $r_{1},\cdots,r_{k}$ vertices
as,

$\displaystyle f({v_{{i_{2}}^{{}^{\prime}}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+{i_{2}^{{}^{\prime}}},~{}~{}~{}~{}1\leq{i_{2}^{{}^{\prime}}}\leq
r_{1},$ $\displaystyle f({v_{{i_{3}}^{{}^{\prime}}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+r_{1}+{i_{3}^{{}^{\prime}}},~{}~{}~{}~{}1\leq{i_{3}^{{}^{\prime}}}\leq
r_{2},$ $\displaystyle\vdots$ $\displaystyle f({v_{{i_{l}}^{{}^{\prime}}}})$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{l}(m_{i})+n_{1}+r_{1}+\cdots+r_{k-1}+{i_{l}^{{}^{\prime}}},~{}~{}~{}~{}1\leq{i_{l}^{{}^{\prime}}}\leq
r_{k}.$

Again, by the definition, $f$ is the well-defined minimal coloring of $G$ and
therefore,
$\lambda(G)=span(f)=\sum\limits_{i=1}^{l}(m_{i})+n_{1}+r_{1}+\cdots+r_{k}=\sum\limits_{i=1}^{l}(m_{i})+n_{1}+(n_{2}-m_{l})+\cdots+(n_{l}-m_{2})=\sum\limits_{i=1}^{l}m_{i}+n_{1}+\sum\limits_{i=1}^{l-1}(n_{i+1}-m_{l+1-i})$.

We conclude this paper with the following example which illustrates
Algorithm-(b) and Theorem (4.3).

######  Example 4.4.

Let $G(5,2,3,2,4,3,3;2,2,5,3,6,2,5)$ be a chain graph. Define the
$L(2,1)$-coloring $f:V(G)\rightarrow[0,\infty)$ of $G$ as,

$\displaystyle f(u_{i_{1}})$ $\displaystyle=$ $\displaystyle
i_{1}-1,~{}~{}~{}~{}1\leq i_{1}\leq 5,$ $\displaystyle f(u_{i_{2}})$
$\displaystyle=$ $\displaystyle 4+i_{2},~{}~{}~{}~{}1\leq i_{2}\leq 2,$
$\displaystyle f(u_{i_{j}})$ $\displaystyle=$ $\displaystyle
4+\sum\limits_{j=3}^{7}(m_{j-1})+i_{j},~{}~{}~{}~{}1\leq i_{j}\leq
m_{j}~{}~{}and~{}~{}3\leq j\leq 7,$ $\displaystyle f(v_{i_{1}})$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})+i_{1}=22+i_{1},~{}~{}~{}~{}1\leq
i_{1}\leq 2.$

We compute $|V_{2}|-|U_{7}|=-1=s_{1}$ (say), it follows that the vertices of
$V_{2}$ can be colored by already existing colors of vertices of $U_{7}$.
Therefore by Algorithm-(b), we define the colors of vertices of $V_{2}$ as,

$\displaystyle f(v_{1_{2}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})=22,$ $\displaystyle f(v_{2_{2}})$
$\displaystyle=$ $\displaystyle\sum\limits_{i=1}^{7}(m_{i})-1=21.$

Next, we compute $|V_{3}|-|U_{6}|=2=r_{1}$ and $r_{1}+s_{1}=1$. Then by
Algorithim-(b), we define the coloring of vertices of $V_{3}$ as,

$\displaystyle f(v_{i_{3}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})-(i_{3}+1)=22,~{}~{}~{}1\leq
i_{3}\leq 4$ $\displaystyle~{}~{}~{}~{}~{}f(v_{5_{3}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})+n_{1}+1=25.$

The coloring for rest of the vertices of $V$ can be defined as,

$\displaystyle f(v_{i_{4}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})-|V_{3}|-i_{4},~{}~{}~{}~{}1\leq
i_{4}\leq 3,$ $\displaystyle f(v_{i_{5}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})-|V_{3}|-|V_{4}|-i_{5},~{}~{}~{}~{}1\leq
i_{5}\leq 3,$ $\displaystyle f(v_{i_{5}^{{}^{\prime}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})+n_{1}+1+{i_{5}^{{}^{\prime}}},~{}~{}~{}~{}1\leq{i_{5}^{{}^{\prime}}}\leq
3,$ $\displaystyle f(v_{i_{6}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})-|V_{3}|-|V_{4}|-|V_{5}-3|-i_{6},~{}~{}~{}~{}1\leq
i_{6}\leq 2,$ $\displaystyle f(v_{i_{7}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})-|V_{3}|-|V_{4}|-|V_{5}-3|-|V_{6}|-i_{7},~{}~{}~{}~{}1\leq
i_{7}\leq 3,$ $\displaystyle f(v_{i_{7}^{{}^{\prime}}})$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{7}(m_{i})+n_{1}+1+3+{i_{7}^{{}^{\prime}}},~{}~{}~{}~{}1\leq{i_{7}^{{}^{\prime}}}\leq
2.$

Therefore, $\lambda(G)=span(f)=\sum\limits_{i=1}^{7}(m_{i})+n_{1}+1+3+2=30$.

## References

  * [1] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak and L. S. Ram Network discovery and verification, IEEE J. On Sel. Areas in Comm. 24 (2006) 2168 - 2181.
  * [2] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Disc. Applied Math. 105 (1-3) (2000) 99 - 113.
  * [3] V. Chvátal, P. L. Hammer, Aggregation of Inequalities in Integer Programming, Ann. Disc. Math. 1 (1977) 145 - 162.
  * [4] V. Chvatal, Mastermind, Combinatorica 3 (1983) 325 - 329.
  * [5] L. Epstein and P. Ferragina, Algorithms – ESA Ann. Eur. Symp. Ljub. Slovenia. (2012) 10 - 12.
  * [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] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191 – 195.
  * [9] P. B. Henderson and Y. Zalcstein, Synchronization problems solvable by generalized pv systems. J. ACM., 27 (1) (1980) 60 - 71.
  * [10] S. Khuller, B. Radhavachari, and A. Rosenfeld, Landmarks in graphs, Disc. Appl. Math. 70 (1996) 200 – 207.
  * [11] S. Khuller, B. Raghavachari and A. Rosenfeld, Localization in graphs (1988).
  * [12] 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.
  * [13] N. V. R. Mahadev, U.N. Peled, Threshold Graphs and Related Topics. Ann. Disc. Math. 56 (1996).
  * [14] L. Mol, M. J. Murphy and O. R. Oellermann, The threshold dimension of a graph, Disc. Appl. Math. 287 (2020) 118 – 133.
  * [15] A. Sebo and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383 - 393.
  * [16] P. J. Slater, Leaves of trees, Cong. Numer. 14 (1975) 549 – 559.