[3]Gopika Sharma

1]Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

2]Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

3]Department of Mathematics, Indian Institute of Technology Ropar, Rupnagar,
India

# Computation of Grundy dominating sequences in (co-)bipartite graphs

Boštjan Brešar<EMAIL_ADDRESS>Arti Pandey<EMAIL_ADDRESS><EMAIL_ADDRESS>[  [  [

###### Abstract

A sequence $S$ of vertices of a graph $G$ is called a dominating sequence of
$G$ if $(i)$ each vertex $v$ of $S$ dominates a vertex of $G$ that was not
dominated by any of the vertices preceding vertex $v$ in $S$, and $(ii)$ every
vertex of $G$ is dominated by at least one vertex of $S$. The Grundy
Domination problem is to find a longest dominating sequence for a given graph
$G$. It has been known that the decision version of the Grundy Domination
problem is NP-complete even when restricted to chordal graphs. In this paper,
we prove that the decision version of the Grundy Domination problem is NP-
complete for bipartite graphs and co-bipartite graphs. On the positive side,
we present a linear-time algorithm that solves the Grundy Domination problem
for chain graphs, which form a subclass of bipartite graphs.

###### keywords:

dominating sequence, bipartite graph, chain graphs, computational complexity,
linear-time algorithm

###### pacs:

[

Mathematics Subject Classification]05C69, 05C65, 05C85

##  1 Introduction

Graph domination is an established area of graph theory with an extremely rich
literature and a number of applications. Given a graph $G=(V,E)$ a set
$S\subseteq V$ is _dominating_ if every vertex $x\in V\setminus S$ is adjacent
to a vertex in $S$. A dominating set of $G$ with minimum cardinality is called
a _minimum dominating set_ of $G$. The cardinality of a minimum dominating set
of $G$ is the _domination number_ of $G$ and is denoted by $\gamma(G)$. The
Minimum Domination problem is to find a dominating set of cardinality
$\gamma(G)$. The Minimum Domination problem and its variations have numerous
applications in real world problems including social networks, facility
location problems, routing problems. An extensive overview on graph domination
can be found in three recent monographs [11, 12, 13].

The domination game was introduced in [2] using the approach of building a
dominating set of a graph one vertex at a time. The game is played on a graph
$G$ by two players, named Dominator and Staller, who are building a dominating
set of $G$. These two players have the opposite goals in the game: one wants
the game to end in as few moves as possible while the other one wants to
extend the length of the game. They are taking turns in which a player chooses
a vertex that has to dominate a vertex that has not been dominated by any of
the previously chosen vertices. The game ends when there is no more vertex to
choose, that is, the set of vertices chosen during the game is a dominating
set. Thus, during the game a sequence of vertices is selected. In several
papers, authors considered a sequence obtained by the same basic rule, yet
assuming that only the slow player plays the game. This leads to the following
definitions.

Let $S=(v_{1},v_{2},\ldots,v_{k})$ be a sequence of vertices of $G$, and let
$\widehat{S}=\\{v_{1},\ldots,v_{k}\\}$. A sequence
$S=(v_{1},v_{2},\ldots,v_{k})$ is a closed neighborhood sequence if
$N[v_{i}]\setminus\bigcup_{j=1}^{i-1}N[v_{j}]\neq\emptyset,$ holds for every
$i\in\\{2,3,\ldots,k\\}$. If, in addition, $\widehat{S}$ is a dominating set
of $G$, then $S$ is a _dominating sequence_ of $G$. Clearly, the length $k$ of
$S$ is bounded from below by $\gamma(G)$. A dominating sequence of maximum
length in $G$ is a _Grundy dominating sequence_ (or, GD-sequence for short) of
$G$. The cardinality of such a sequence is called the _Grundy domination
number_ of $G$ and is denoted by $\gamma_{gr}(G)$.

These concepts were introduced and studied in 2014 by Brešar, Gologranc,
Milanič, Rall and Rizzi [3], where motivation came from the domination game as
described above. In addition, Grundy domination presents the worst-case
scenario in the process of the online update of a dominating set in the
expanding network. In $2021$, domination games as well as Grundy domination
were comprehensevely surveyed in the book [7].

The optimization version of the Grundy domination problem is to find a GD-
sequence (that is, a dominating sequence of maximum length) in a graph $G$.
From the computational complexity point of view the decision version of the
problem is defined as follows:

Grundy Domination Decision (GDD) Input: A graph $G=(V,E)$ and
$k\in{\mathbb{Z}}^{+}.$ Question: Is there a dominating sequence of $G$ of
length at least $k$?

In the seminal paper [3], the authors proved that the GDD problem is NP-
complete for chordal graphs. They also proved that a GD-sequence in trees,
cographs and split graphs can be computed in polynomial time [3]. An
additional study of Grundy domination in forests was used to give a partial
confirmation of a conjecture concerning the Grundy domination number in strong
products of graphs [1]. Several combinatorial results have also been
established for the parameter and its relatives in the literature [6, 8, 9,
10, 15]. Concerning the computational complexity, it was shown that the GDD
problem can be solved in polynomial time for interval graphs and Sierpiński
graphs [4], as well as on some $X$-join products, lexicographic products and
related classes of graphs [16]. A hierarchy presenting relationships between
some classes of graphs that are relevant for this paper are shown in Fig. 1.

GeneralCographChordalCo-bipartiteBipartiteChordal BipartiteConvex
BipartiteBipartite PermutationChainIntervalSplitTrees Figure 1: Hierarchy of
selected graph classes.

A close relation between dominating sequences in graphs and certain covering
sequences in hypergraphs was found in the seminal paper [3]. Given a
hypergraph $\cal H=(X,E)$ with no isolated vertices, an _edge cover_ of $\cal
H$ is a family of (hyper)edges from ${\cal E}$ whose union is the vertex set
$\cal X$. The smallest cardinality of an edge cover of $\cal H$ is the _edge
cover number_ of $\cal H$ and is denoted by $\rho(\cal H)$.

Now, consider a sequence of edges ${\cal C}=(C_{1},\ldots,C_{r})$ of a
hypergraph $\cal H$. If for each $i$, $i\in[r]$, $C_{i}$ contains a vertex not
contained in $C_{j}$, for all $j<i$, then ${\cal C}$ is a _legal edge
sequence_ of $\cal H$. If ${\cal C}=(C_{1},C_{2},\ldots,C_{r})$ is a legal
edge sequence and the set $\widehat{\cal C}=\\{C_{1},C_{2},\ldots,C_{r}\\}$ is
an edge cover of $\cal H$, then ${\cal C}$ is an _edge covering sequence_. An
edge covering sequence of maximum length in $\cal H$ is a _Grundy covering
sequence_ of $\cal H$. The length of such a sequence is the _Grundy cover
number_ , $\rho_{gr}(\cal H)$, of $\cal H$. Given a hypergraph $\cal H=(X,E)$,
the Grundy Covering problem is to find a Grundy covering sequence, and thus
establishing the Grundy cover number, and its decision version is the Grundy
Covering Decision (GCD) problem. It was shown in [3] that the GDD problem is
NP-complete by reduction from the GCD problem, while for the NP-completeness
of the GCD problem a reduction from the classical Feedback Arc Set problem was
used.

In Section 2, we establish basic notation and mention several preliminary
results. In Section 3, we prove that the GDD problem is NP-complete even when
restricted to bipartite or co-bipartite graphs. In contrast, we present a
linear-time algorithm for determining the Grundy domination number of chain
graphs in Section 4. In the final section, we add a few comments and open
problems.

##  2 Preliminaries

Let $[n]=\\{1,\ldots,n\\}$ for any $n\in\mathbb{N}$. Given a graph $G$, the
_neighborhood_ of a vertex $x$ is $N_{G}(x)=\\{y\in V(G):\,xy\in E(G)\\}$, and
the closed neighborhood of $x$ is $N_{G}[x]=N_{G}(x)\cup\\{x\\}$. Vertices $u$
and $v$ in a graph $G$ are closed twins (respectively, open twins) if
$N_{G}[u]=N_{G}[v]$ (respectively, $N_{G}(u)=N_{G}(v)$). We may omit the
indices in the above definitions if the graph $G$ is understood from the
context. The following statement has a straightforward proof using
definitions.

######  Proposition 1.

Let $S$ be a (Grundy) dominating sequence in a graph $G$. If $u,v\in V(G)$
such that $N[u]\subseteq N[v]$ and $u,v\in\hat{S}$, then $u$ appears before
$v$ in $S$.

If $S$ is a closed neighborhood sequence, then we say that $v_{i}$
_footprints_ the vertices from $N[v_{i}]\setminus\cup_{j=1}^{i-1}N[v_{j}]$,
and that $v_{i}$ is the _footprinter_ of every vertex $u\in
N[v_{i}]\setminus\cup_{j=1}^{i-1}N[v_{j}]$. If
$S_{1}=(v_{1},v_{2},\ldots,v_{n})$ and $S_{2}=(u_{1},u_{2},\ldots,u_{m})$,
$n,m\geq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1},$
are two sequences, then the concatenation of $S_{1}$ and $S_{2}$ is the
sequence $S_{1}\oplus
S_{2}=(v_{1},v_{2},\ldots,v_{n},u_{1},u_{2},\ldots,u_{m})$.

Given a hypergraph $\cal H=(X,E)$, a _legal transversal sequence_ is a
sequence $S=(v_{1},\ldots,v_{k})$ of vertices from $\cal X$ such that for each
$i$ there exists an edge $\mathcal{E}_{i}\in\mathcal{E}$ such that
$v_{i}\in\mathcal{E}_{i}$ and $v_{j}\notin\mathcal{E}_{i}$ for all $j$, where
$j<i$. The maximum length of a legal transversal sequence in a hypergraph
$\cal H$ is denoted by $\tau_{\rm gr}({\cal H})$. The following result was
proved in [5, Proposition 8.3].

######  Proposition 2.

For any hypergraph ${\cal H}$ we have $\tau_{\rm gr}({\cal H})=\rho_{\rm
gr}({\cal H})$.

A set of vertices $A\subseteq V(G)$ is called an _independent set_ of $G$ if
no two vertices of $A$ are adjacent in $G$. A _maximum independent set_ is an
independent set of maximum cardinality. The size of a maximum independent set
in $G$ is the _independence number_ of $G$ and is denoted by $\alpha(G)$.

A _bipartite graph_ is a graph whose vertex set can be partitioned into two
independent sets. A _co-bipartite graph_ is a graph, which is the complement
of a bipartite graph. A bipartite graph $G=(X,Y,E)$ is a chain graph if the
neighborhoods of the vertices of $X$ form a chain, that is, the vertices of
$X$ can be linearly ordered, say $\\{x_{1},x_{2},\ldots,x_{n_{1}}\\}$ such
that $N(x_{1})\subseteq N(x_{2})\subseteq\cdots\subseteq N(x_{n_{1}})$, where
$n_{1}=|X|$. If $G=(X,Y,E)$ is a chain graph, then one can easily see that the
neighborhoods of the vertices of $Y$ also form a chain. If $n_{2}=|Y|$, an
ordering $\alpha=(x_{1},x_{2},\ldots,x_{n_{1}},y_{1},y_{2},\ldots,y_{n_{2}})$
is called a chain ordering if $N(x_{1})\subseteq
N(x_{2})\subseteq\cdots\subseteq N(x_{n_{1}})$ and $N(y_{1})\supseteq
N(y_{2})\supseteq\cdots\supseteq N(y_{n_{2}})$.

If a vertex $x_{i}$ appears before $x_{j}$ in chain ordering, we write
$x_{i}<x_{j}$. Given a chain graph $G$, a chain ordering of $G$ can be
computed in linear time [14]. Now, suppose
$A=\\{x_{i_{1}},x_{i_{2}},\ldots,x_{i_{r}}\\},B=\\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{r^{\prime}}}\\}$
be two disjoint subsets of $X$ such that $x_{i_{p}}<x_{i_{q}}$ and
$x_{j_{p}}<x_{j_{q}}$ for $p<q$. Then $(A)\oplus(B)$ denotes the sequence
$(x_{i_{1}},\ldots,x_{i_{r}},x_{j_{1}},\ldots,x_{j_{r^{\prime}}})$. Similar
notation can be used for vertices in $Y$.

Recall that two vertices $u,v$ are called open twins if $N(u)=N(v)$. We define
a relation $R$ on $X$ such that vertices $x,x^{\prime}\in X$ are related by
$R$ if and only if they are open twins. Clearly, $R$ is an equivalence
relation, and let $X_{1},X_{2},\ldots,X_{k}$ be the parts in $X$ that arise
from $R$. Without loss of generality, for a chain graph $G=(X,Y,E)$, we may
also assume that $N(X_{1})\subseteq
N(X_{2})\cdots{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\subseteq}N(X_{k})$.
We denote the set of vertices in $N(X_{1})$ by $Y_{1}$. For
$i\in\\{2,3,\ldots,k\\}$, let
$Y_{i}=N(X_{i})\setminus\cup_{j=1}^{i-1}N(X_{j})$. It is easy to see that
every two vertices from $Y_{j}$ are open twins for all $j\in[k]$. The
following statement follows from the construction of the sets $X_{i}$ and
$Y_{j}$.

######  Observation 1.

Let $X_{1},X_{2},\ldots,X_{k}$ and $Y_{1},Y_{2},\ldots,Y_{k}$ be the subsets
of vertices of $G$ as defined above. Then, $N(X_{i})=\bigcup_{r=1}^{i}Y_{r}$
and $N(Y_{j})=\bigcup_{r=j}^{k}X_{r}$ for each $i,j\in[k]$.

##  3 NP-completeness results

As mentioned in the introduction, the GDD problem is NP-complete for general
graphs, and also when restricted to chordal graphs. In the following
subsections, we prove that the problem remains NP-complete for bipartite and
co-bipartite graphs.

###  3.1 Bipartite graphs

In this subsection, we prove the NP-completeness of the GDD problem for
bipartite graphs. We reduce the GCD problem for hypergraphs to the GDD problem
for bipartite graphs. Given a hypergraph $\cal H=(X,E)$ with $|\mathcal{X}|=n$
and $|\mathcal{E}|=m$, $(n,m\geq 2)$, we construct an instance $G_{\cal H}$ of
the GDD problem, where $G_{\cal H}$ is a bipartite graph, as follows.

Let $V(G_{\cal H})=A\cup X^{\prime}\cup{\mathcal{E}}^{\prime}\cup B$, where
$A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ and $B=\\{b_{1},b_{2},\ldots,b_{m}\\}$. The
sets $X^{\prime}$ and ${\mathcal{E}}^{\prime}$ contain $n$ and $m$ vertices
respectively, where each vertex of $X^{\prime}$ corresponds to a vertex of
$\cal X$ in the hypergraph $\cal H$ and each vertex of
${\mathcal{E}}^{\prime}$ correspond to an edge of $\cal H$. For an edge
${\mathcal{E}}_{i}\in\mathcal{E}$, we denote the corresponding vertex in
${\mathcal{E}}^{\prime}$ by $e_{i}$. All sets
$A,X^{\prime},{\mathcal{E}}^{\prime},$ and $B$ are indepedent sets in $G_{\cal
H}$, and $A\cup X^{\prime}$ induces the complete bipartite graph $K_{n,n}$,
while ${\mathcal{E}}^{\prime}\cup B$ induces the complete bipartite graph
$K_{m,m}$. Now, a vertex $x$ of $X^{\prime}$ is adjacent to a vertex of
$e_{i}\in{\mathcal{E}}^{\prime}$ in $G_{\cal H}$ if and only if
$x\in{\mathcal{E}}_{i}$ in $\cal H$.

Clearly, $G_{\cal H}$ is a bipartite graph. See Fig. 2, which presents the
construction of the graph $G_{\cal H}$ from a hypergraph $\cal H$, which is
given by
$(\mathcal{X}=\\{x_{1},x_{2},x_{3},x_{4}\\},\mathcal{E}=\\{\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3},\mathcal{E}_{4},\mathcal{E}_{5}\\})$,
where $\mathcal{E}_{1}=\\{x_{1},x_{2},x_{4}\\}$,
$\mathcal{E}_{2}=\\{x_{2},x_{3}\\}$, $\mathcal{E}_{3}=\\{x_{1},x_{2}\\}$,
$\mathcal{E}_{4}=\\{x_{2},x_{3},x_{4}\\}$ and
$\mathcal{E}_{5}=\\{x_{1},x_{3},x_{4}\\}$.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$A$$X^{\prime}$${\cal
E}^{\prime}$$B$ Figure 2: Illustration of the construction of $G_{\cal H}$
from $\cal H$.

######  Theorem 1.

If $\cal H=(X,E)$ is a hypergraph with $|\mathcal{X}|=n$ and
$|\mathcal{E}|=m$, where $n,m\geq 2$, then ${\rho}_{gr}(\mathcal{H})\geq k$ if
and only if ${\gamma}_{gr}(G_{\cal H})\geq n+m+k$.

###### Proof.

In the proof, let $G=G_{\cal H}$. First, let
($\mathcal{E}_{1},\mathcal{E}_{2},\ldots,\mathcal{E}_{k^{\prime}})$ be an edge
covering sequence of length at least $k$ in $\cal H$. Then the sequence
$(b_{1},b_{2},\ldots,b_{m},e_{1},e_{2},\ldots,e_{k^{\prime}},a_{1},a_{2},\ldots,a_{n})$
is a dominating sequence of length at least $n+m+k$ in $G$. Hence,
${\gamma}_{gr}(G)\geq n+m+k$.

For the converse, let us assume that ${\gamma}_{gr}(G)\geq n+m+k$ for some
positive integer $k$. If $X^{\prime}\cap\hat{S}\neq\emptyset$ for some
dominating sequence $S$ of $G$, then $x_{0}$ denotes the first vertex in $S$
coming from $X^{\prime}$, and if
${\mathcal{E}}^{\prime}\cap\hat{S}\neq\emptyset$ for some dominating sequence
$S$ of $G$, then $e_{0}$ denotes the first vertex in $S$ coming from
${\mathcal{E}}^{\prime}$. First, we prove two auxiliary claims.

######  Claim 1.

There exists a dominating sequence $S$ of length at least $n+m+k$ in $G$ such
that all vertices of $A$ appear in $S$ and if
$X^{\prime}\cap\hat{S}\neq\emptyset$, then all vertices of $A$ appear before
$x_{0}$.

###### Proof.

Let $S$ be a dominating sequence of length at least $n+m+k$ in $G$ (which
exists, since ${\gamma}_{gr}(G)\geq n+m+k$). Suppose there exists a vertex
$a_{i}\in A$, which is not appearing in $S$. Then, there exists a vertex from
$X^{\prime}$ which is appearing in $S$ to footprint $a_{i}$. Hence,
$X^{\prime}\cap\hat{S}\neq\emptyset$ and $x_{0}$ footprints $a_{i}$. Let $P$
denotes the set of vertices appearing before $x_{0}$ and $Q$ be the set of
vertices appearing after $x_{0}$ in $S$. Now, two cases are possible.

Case 1: $Q\cap A=\emptyset$.
In this case, either $P\cap A=\emptyset$ or $P$ contains some vertices of $A$.
So, first assume that $P$ contains no vertex of $A$. Then, we see that no
vertex of $A$ appears in the sequence $S$. If $x_{0}$ does not footprint any
vertex in ${\mathcal{E}}^{\prime}$, then we modify $S$ by appending vertices
of $A$ in the order $(a_{1},a_{2},\ldots,a_{n})$ just before $x_{0}$ and
removing all vertices from $Q$ that footprinted a vertex of $X^{\prime}$ along
with the vertex $x_{0}$. Otherwise, if $x_{0}$ footprints some vertices of
${\mathcal{E}}^{\prime}$, we perform the same modification without removing
$x_{0}$. Note that the number of vertices of $Q$ that footprint a vertex of
$X^{\prime}$ are at most $n-1$. In either case, we removed at most $n$
vertices and we added $n$ new vertices to $S$, by which the so modified
sequence $S$ is a dominating sequence of length at least $n+m+k$ in $G$, which
satisfies the statement of the claim.

Now, if $P$ contains some vertices of $A$, then no vertex of $Q$ footprints
any vertex of $X^{\prime}$. Again, if $x_{0}$ footprints only vertices of $A$,
then we modify $S$ by appending vertices of $A\setminus P$ in any order just
before $x_{0}$ and removing the vertex $x_{0}$. Otherwise, if $x_{0}$
footprints also some vertices of ${\mathcal{E}}^{\prime}$, we perform the same
modification, but without removing $x_{0}$. In either case, we removed at most
$1$ vertex and we added at least $1$ new vertex to the sequence $S$. With
this, the so modified sequence $S$ is a dominating sequence of length at least
$n+m+k$ in $G$, which satisfies the statement of the claim.

Case 2: $|Q\cap A|=1$.
In this case, $P$ contains no vertex of $A$. Let $a_{j}$ be the vertex from
$Q\cap A$ appearing in $S$. Note that the vertices in $S$, which footprint
only vertices from $X^{\prime}$, do not appear after $a_{j}$ in $S$. Note that
there are at most $n-2$ vertices that appear in $S$ between $x_{0}$ and
$a_{j}$ and footprint a vertex of $X^{\prime}$, and denote the set of these
vertices by $Q^{\prime}$. If $x_{0}$ does not footprint any vertex in
${\mathcal{E}}^{\prime}$, then we modify $S$ by appending vertices of $A$ in
the order $(a_{1},a_{2},\ldots,a_{n})$ just before $x_{0}$ and then removing
all vertices of $Q^{\prime}\cup\\{x_{0},a_{j}\\}$. Otherwise, if $x_{0}$
footprints also some vertices of ${\mathcal{E}}^{\prime}$, we perform the same
modification without removing $x_{0}$. In either case, we removed at most
$n-1$ vertices and we added $n-1$ new vertices to $S$. Hence, the so modified
sequence $S$ is a dominating sequence of length at least $n+m+k$ in $G$, which
satisfies the statement of the claim. ∎

By the above claim, there exists a dominating sequence $S$ of length $n+m+k$
such that all vertices of $A$ appear in $S$ and they appear before $x_{0}$ if
$X^{\prime}\cap\hat{S}\neq\emptyset$. The proof of Claim 2 follows similar
lines as the proof of the Claim 1.

######  Claim 2.

There exists a dominating sequence $S$ of length at least $n+m+k$ in $G$ such
that all vertices of $B$ appear in $S$ and if
${\mathcal{E}}^{\prime}\cap\hat{S}\neq\emptyset$, then all vertices of $B$
appear before $e_{0}$.

Combining the above two claims we infer that there exists a dominating
sequence $S$ of length at least $n+m+k$ in $G$ such that
$|(X^{\prime}\cup{\mathcal{E}}^{\prime})\cap\hat{S}|\geq k$.

######  Claim 3.

Either $X^{\prime}\cap\hat{S}=\emptyset$ or
${\mathcal{E}}^{\prime}\cap\hat{S}=\emptyset$.

###### Proof.

If $X^{\prime}\cap\hat{S}=\emptyset$, we are done. So, assume that
$X^{\prime}\cap\hat{S}\neq\emptyset$ and
${\mathcal{E}}^{\prime}\cap\hat{S}\neq\emptyset$. Now, either $e_{0}$ appears
before $x_{0}$ or $e_{0}$ appears after $x_{0}$. In the former case, we see
that before the vertex $x_{0}$, all vertices of $G$ are footprinted (and thus
dominated) using Claims 1 and 2. So, $x_{0}$ does not footprint any vertex
implying that this case is not possible. Similarly, the latter case is also
not possible, which proves the claim. ∎

Now, if $X^{\prime}\cap\hat{S}=\emptyset$, then we have that
$|{\mathcal{E}}^{\prime}\cap\hat{S}|\geq k$. In addition, by Claim 2, since
all vertices of $B$ appear in $S$ before any vertex of
${\mathcal{E}}^{\prime}$ appears in $S$, the subsequence of $S$ of vertices in
${\mathcal{E}^{\prime}}$ corresponds to an edge covering sequence in the
hypergraph $\cal H$, which is of length at least $k$. Thus,
${\rho}_{gr}(\mathcal{H})\geq k$, as desired.

Otherwise, if ${\mathcal{E}}^{\prime}\cap\hat{S}=\emptyset$, then we derive
that $|X^{\prime}\cap\hat{S}|\geq k$, where the subsequence formed by vertices
of $X^{\prime}\cap\widehat{S}$ corresponds to a legal transversal sequence of
the hypergraph $\cal H$ of length at least $k$. By Proposition 2, $\tau_{\rm
gr}({\cal H})=\rho_{\rm gr}({\cal H})$, and so ${\rho}_{gr}(\mathcal{H})\geq
k$. The proof of the theorem is complete. ∎

Based on Theorem 1 and earlier discussions we immediately derive the main
result of this section.

######  Theorem 2.

The GDD problem is NP-complete for bipartite graphs.

###  3.2 Co-bipartite graphs

In this subsection, we prove the NP-completeness of the GDD problem for co-
bipartite graphs. Here, we reduce the GDD problem for general graphs to the
GDD problem for co-bipartite graphs. Given a graph $G=(V,E)$, where
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, we construct an instance
$G^{\prime}=(V_{1}\cup V_{2},E^{\prime})$ of the GDD problem, where
$G^{\prime}$ is a co-bipartite graph, as follows.

The vertex set of $G^{\prime}$ is $V_{1}\cup V_{2}$, where
$V_{1}=\\{v_{i}^{1}:v_{i}\in V\\}$ and $V_{2}=\\{v_{i}^{2}:v_{i}\in V\\}$. The
set of edges of $G^{\prime}$ is given by $\\{v_{i}^{1}v_{j}^{1}:1\leq i<j\leq
n\\}\cup\\{v_{i}^{2}v_{j}^{2}:1\leq i<j\leq
n\\}\cup\\{v_{i}^{1}v_{j}^{2}:v_{j}\in N_{G}[v_{i}],i,j\in[n]\\}$. Note that
$G^{\prime}$ is a co-bipartite graph. Fig. 3 provides an illustration of the
construction of $G^{\prime}$ from $G$.

$a$$b$$c$$a^{1}$$b^{1}$$c^{1}$$a^{2}$$b^{2}$$c^{2}$$G:$$G^{\prime}:$$V_{1}$$V_{2}$
Figure 3: Construction of a co-bipartite graph $G^{\prime}$ from a graph $G$,
where $G=P_{3}$.

######  Claim 4.

For a positive integer $k$, $\gamma_{gr}(G)\geq k$ if and only if
$\gamma_{gr}(G^{\prime})\geq k$.

###### Proof.

First, let $S=(u_{1},u_{2},\ldots,u_{t})$ be a dominating sequence of $G$ of
length $t$, where $t\geq k$. Then
$S^{\prime}=(u_{1}^{1},u_{2}^{1},\ldots,u_{t}^{1})$ is a dominating sequence
of length at least $k$ in $G^{\prime}$. Indeed, if $v_{i}$ is a vertex
footprinted by $u_{i}$ with respect to $S$, then $v_{i}^{2}$ is footprinted by
$u_{i}^{1}$ with respect to $S^{\prime}$.

Conversely, let $S=(w_{1},w_{2},\ldots,w_{t})$ be a dominating sequence of
length $t$ in $G^{\prime}$, where $t\geq k$ and $w_{i}\in V_{1}\cup V_{2}$ for
all $i\in[t]$. Without loss of generality, we may assume that $w_{1}\in
V_{1}$. Note that there can be at most one vertex from $V_{2}$ in $S$. If
there is no such vertex, then the sequence $S$ corresponds to a sequence of
vertices in $G$ of length at least $k$, which is a dominating sequence of $G$.
Now, suppose there exists a vertex from $V_{2}$ in $S$. Clearly, it has to be
the last vertex of $S$, and let $w_{t}$ be vertex $v_{i}^{2}\in V_{2}$. Note
that $v_{i}^{2}$ appears in $S$ to footprint a vertex $v_{j}^{2}\in V_{2}$ and
$v_{j}^{1}\notin\hat{S}$. We modify $S$ by replacing the vertex $v_{i}^{2}$
with the vertex $v_{j}^{1}$ and get a new sequence $S^{\prime}$, which is
again a dominating sequence of $G^{\prime}$ of length at least $k$. Since
$S^{\prime}$ contains only vertices from $V_{1}$, it corresponds to a sequence
of vertices in $G$ of length at least $k$, which is a dominating sequence of
$G$. This completes the proof of the converse direction of the statement. ∎

Now, we are ready to state the announced result.

######  Theorem 3.

The GDD problem is NP-complete for co-bipartite graphs.

##  4 Efficient algorithm for chain graphs

In this section, we give a linear-time algorithm to compute a GD-sequence of a
chain graph. Before discussing the main idea for chain graphs, we first give
the Grundy domination number of a complete bipartite graph which is a subclass
of chain graphs. The proof of this result is straightforward.

######  Proposition 3.

If $G=(X,Y,E)$ is a complete bipartite graph, then
$\gamma_{gr}(G)=max\\{|X|,|Y|\\}$.

Recall that a chain graph $G=(X,Y,E)$ has a chain ordering $\alpha$, and based
on the equivalence relation joining open twins, the sets $X$ and $Y$ partition
into subsets $X_{1},X_{2},\ldots,X_{k}$ and $Y_{1},Y_{2},\ldots,Y_{k}$,
respectively. (Also recall that $N(X_{i})=\bigcup_{r=1}^{i}Y_{r}$ and
$N(Y_{j})=\bigcup_{r=j}^{k}X_{r}$ for each $i,j\in[k]$.) Since the case $k=1$
yields a complete bipartite graph, in the rest of this section we only
consider the chain graphs with $k\geq 2$. We also assume that a chain graph
$G=(X,Y,E)$ is given along with the chain ordering $\alpha$ and the partitions
of $X$ and $Y$ into $k$ subsets.

The proof of the following observation is again easy, and hence is omitted.

######  Observation 2.

Let $A\subseteq V(G)$ be a set of open twins in an arbitrary graph $G$. Then
there exists a GD-sequence $S$ of $G$ such that all vertices of $A\cap\hat{S}$
appear together in $S$.

######  Observation 3.

Let $S$ be a GD-sequence of an arbitrary graph $G$ and $A\subseteq V(G)$ be a
set of open twins in $G$ such that $A\cap\hat{S}\neq\emptyset$. If the first
vertex of $A$ in $S$ footprints itself, then there exists a GD-sequence of $G$
in which all vertices of $A$ appear and they appear together in that sequence.

###### Proof.

If $A\cap\hat{S}=A$, we have nothing to prove. So, suppose that
$A\cap\hat{S}\neq A$. Then, there exists a vertex $a\in A$, which is not in
$S$. Thus there exists a vertex $b\in\hat{S}$, which footprints $a$. Note that
$b$ appears after all vertices of $A\cap\hat{S}$. Now, we modify $S$ by
replacing $b$ with the vertex $a$. By doing this repeatedly, we get a new GD-
sequence $S^{\prime}$ of $G$ which contains all vertices of $A$. We can
rearrange all vertices of $A$ so that all vertices of $A$ appear together in
$S^{\prime}$. ∎

In the remainder of the section we assume that $G$ is a chain graph with the
partition of its vertex set as described earlier.

######  Observation 4.

There exists a GD-sequence $S$ of $G$ such that for every $i\in[k]$, we have
$X_{i}\cap\hat{S}\neq\emptyset$ or $Y_{i}\cap\hat{S}\neq\emptyset$.

###### Proof.

Let $S$ be a GD-sequence such that $X_{i}\cap\hat{S}=\emptyset$ and
$Y_{i}\cap\hat{S}=\emptyset$. This implies that there exist vertices
$x\in\cup_{r=i+1}^{k}X_{r}$ and $y\in\cup_{r=1}^{i-1}Y_{r}$ in $S$ to
footprint the vertices of $Y_{i}$ and $X_{i}$ respectively. Note that
$i\notin\\{1,k\\}$. Now, if $x$ appears before $y$ in $S$, then modifying the
sequence $S$ by replacing $y$ by all vertices of $X_{i}$ gives another GD-
sequence of $G$, which includes some vertices from $X_{i}$. (Note that if
$y\in Y_{j}$, then $X_{j}\cap\hat{S}\neq\emptyset$. To see this, assuming that
$X_{j}\cap\hat{S}=\emptyset$ implies that $y$ footprints vertices of both
$X_{j}$ and $X_{i}$ in $S$. In this case, replacing the vertex $y$ with all
vertices of $X_{i}$ and $X_{j}$ results in a new dominating sequence of $G$ of
length bigger than $S$, a contradiction.) Similarly, if $y$ appears before $x$
in $S$, then modifying the sequence $S$ by replacing $x$ by all vertices of
$Y_{i}$ gives another GD-sequence of $G$, which includes some vertices from
$Y_{i}$. Hence, there exists a GD-sequence $S$ of $G$ such that
$X_{i}\cap\hat{S}\neq\emptyset$ or $Y_{i}\cap\hat{S}\neq\emptyset$. ∎

Let $A$ be a set of open twins in $G$. If $|A\cap\hat{S}|\geq 2$, then we see
that the first vertex of $A$ in $S$ footprints itself. Thus we can assume
that, $A\subseteq\hat{S}$, due to Observation 3. Hence, we have,
$|A\cap\hat{S}|\leq 1$ or $A\subseteq\hat{S}$ for any set of open twins $A$ in
$G$. Note that the each of the sets
$X_{1},X_{2},\ldots,X_{k},Y_{1},Y_{2},\ldots,Y_{k}$ is a set of open twins in
$G$.

Now, based on the Observations 2, 3 and 4, whenever we consider a GD-sequence
$S$ of $G$, we assume that $S$ satisfies the following, for the rest of this
section:
(1) For each $i\in[k],|X_{i}\cap\hat{S}|\leq 1$ or $X_{i}\subseteq\hat{S}$. If
$X_{i}\subseteq\hat{S}$, then all vertices of $X_{i}$ appear together in $S$.
(2) For each $i\in[k],|Y_{i}\cap\hat{S}|\leq 1$ or $Y_{i}\subseteq\hat{S}$. If
$Y_{i}\subseteq\hat{S}$, then all vertices of $Y_{i}$ appear together in $S$.
(3) For each $i\in[k],~{}X_{i}\cap\hat{S}\neq\emptyset$ or
$Y_{i}\cap\hat{S}\neq\emptyset$.

Now, let $S$ be a GD-sequence of $G$. Then $S$ is one of the following type:

$(a)$ $X\cap\hat{S}=\emptyset$, $(b)$ $Y\cap\hat{S}=\emptyset$, $(c)$
$X\cap\hat{S}\neq\emptyset$ and $Y\cap\hat{S}\neq\emptyset$.

We call the corresponding GD-sequences $S$ to be of _type (a)_ , type (b), and
_type (c)_ , respectively.

######  Lemma 1.

Let $S^{*}=(v_{1},v_{2},\ldots,v_{p})$ be a GD-sequence of $G$ of type (c).
The following statements hold:

  1. (1)

If $v_{1}\in Y_{1}$, then there exists a type (a) GD-sequence of $G$.

  2. (2)

If $v_{1}\notin Y_{1}$, then there exists a GD-sequence $S$ of $G$ such that
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$ for some $i\in[k]$.

###### Proof.

First, we assume that $v_{1}\in Y_{1}$. In this case, all vertices of $X$ are
footprinted by $v_{1}$. So, all the vertices $v_{2},\ldots,v_{p}$ appear to
footprint vertices of $Y\setminus\\{v_{1}\\}$ only. This implies that
$\gamma_{gr}(G)\leq|Y|$. So, the sequence
$S=(y_{n_{2}},y_{n_{2}-1},\ldots,y_{1})$ is also a GD-sequence of $G$ and it
is of type (a). Next, we assume that $v_{1}\notin Y_{1}$. Since $S^{*}$
contains vertices from both $X$ and $Y$, we have two cases to consider.

Case 1: $v_{1}\in X$.
Let $v_{1}\in X_{i}~{}(i\in[k])$. So, we get that $v_{1}$ footprints all
vertices of $N(X_{i})\cup\\{v_{1}\\}$. Now, let $u$ be a vertex of $X$ such
that $N(u)\subseteq N(v_{1})$. If $u$ is footprinted by some vertex from
$N(u)$, we modify the sequence $S^{*}$ as follows. We remove the footprinter
of $u$ from $S^{*}$ and include $u$ just after $v_{1}$ and get a new sequence.
But, if $u$ is footprinted by itself, then we relocate $u$ in $S$ by putting
it just after $v_{1}$. We repeat the respective modifications for each vertex
$u$ such that $N(u)\subseteq N(v_{1})$ and get a new sequence $S$ which
remains a GD-sequence of $G$. We again modify the ordering of vertices in $S$,
so that it satisfies all the properties of Observations 2, 3 and 4, if
required. Hence, we see that $\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$ for some
$i\in[k]$.

Case 2: $v_{1}\in Y$.
Let $v_{1}\in Y_{i}~{}(i\in[k])$. Note that $i>1$. Here, we may assume that
all vertices $u$ from $Y$, where $N(u)\supseteq N(v_{1})$, are in $S^{*}$ and
all vertices of $\cup_{r=i}^{k}Y_{r}\setminus\\{v_{1}\\}$ appear together just
after $v_{1}$. This is ensured because we can do modifications similar to the
case 1, if it is not true. We rename vertices of $S^{*}$ again by
$(v_{1},v_{2},\ldots,v_{p})$, if necessary. Now, let $v_{t}$ be the vertex
with the smallest index in the ordering $(v_{2},v_{3},\ldots,v_{p})$ such that
$v_{t}\in X$. Suppose that $v_{t}\in X_{t^{\prime}}$. Note that there exists
an integer $r^{\prime}\in\\{2,3,\ldots,k\\}$ such that all vertices of
$\cup_{r=r^{\prime}}^{k}(X_{r}\cup Y_{r})$ are footprinted before the vertex
$v_{t}$ appears in $S$, and all remaining vertices of $G$ are not footprinted.
If $v_{t}\in\cup_{r=1}^{r^{\prime}-1}X_{r}$, we get that $v_{t}$ footprints
all vertices of $N(v_{t})\cup\\{v_{t}\\}$. In this case, we put all vertices
$u$ of $X$ such that $N(u)\subseteq N(v_{t})$ just after $v_{t}$ in any order,
remove vertices from $N(u)\cap\widehat{S^{*}}$ which were appearing to
footprint the vertex $u$ and rearrange all vertices so that the new sequence
$S$ satisfies all the properties of Observation 2. Thus, we get that
$\cup_{r=1}^{t^{\prime}}X_{r}\subseteq\hat{S}$. But, if
$v_{t}\in\cup_{r=r^{\prime}}^{k}X_{r}$, then $v_{t}$ footprints all vertices
of $\cup_{r=1}^{r^{\prime}-1}Y_{r}$. So, we may assume that $v_{t}\in
X_{r^{\prime}}$. Again, we put all vertices
$u\in\cup_{r=1}^{r^{\prime}-1}X_{r}$ just after $v_{t}$ in any order, remove
vertices from $N(u)\cap\widehat{S^{*}}$ which were appearing to footprint the
vertex $u$ and rearrange all vertices so that the new sequence $S$ satisfies
all the properties of Observation 2. Thus, we get that
$\cup_{r=1}^{r^{\prime}-1}X_{r}\subseteq\hat{S}$.

Therefore, there exists a GD-sequence $S$ of $G$ such that
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$ for some $i\in[k]$. ∎

Analogous to Lemma 1, we give a symmetric lemma for the set $Y$ of $G$, whose
proof follows similar lines and is omitted.

######  Lemma 2.

Let $S^{*}=(v_{1},v_{2},\ldots,v_{p})$ be a GD-sequence of $G$ of type (c).
The following statements hold:

  1. (1)

If $v_{1}\in X_{k}$, then there exists a type (b) GD-sequence of $G$.

  2. (2)

If $v_{1}\notin X_{k}$, then there exists a GD-sequence $S$ of $G$ such that
$\cup_{r=j}^{k}Y_{r}\subseteq\hat{S}$ for some $j\in[k]$.

######  Lemma 3.

Let $S$ be a GD-sequence of $G$ of type (c) and let $i\in[k]$ be the largest
index such that $\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$. If $i<k$, then the
following is true:

  1. (1)

If $i\leq k-2$, then there exists a GD-sequence $S^{\prime}$ of $G$ such that
either $(\cup_{r=i+1}^{k}X_{r})\cap\hat{S^{\prime}}=\emptyset$ or
$(\cup_{r=i+2}^{k}X_{r})\cap\hat{S^{\prime}}=\emptyset$ and
$|X_{i+1}\cap\hat{S^{\prime}}|=1$.

  2. (2)

If $i=k-1$, then either $X_{k}\cap\hat{S}=\emptyset$ or
$|X_{k}\cap\hat{S}|=1$.

###### Proof.

Let $S$ be a GD-sequence of $G$ in which we have a largest index $i$ such that
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$. Now, assume that $i<k$ and so,
$X_{i+1}\nsubseteq\hat{S}$. If $i=k-1$ and $X_{k}\cap\hat{S}\neq\emptyset$
then either $|X_{k}\cap\hat{S}|=1$ or $|X_{k}\cap\hat{S}|\geq 2$. In the
latter case, we get that first vertex of $X_{k}$ in $S$ footprints itself. So,
Observation 3 ensures that $|X_{k}\cap\hat{S}|=1$.

Next, we show that if $i\leq k-2$, then
$(\cup_{r=i+2}^{k}X_{r})\cap\hat{S}=\emptyset$. So, let
$t\in\\{i+2,\ldots,k\\}$ be the minimum index such that
$X_{t}\cap\hat{S}\neq\emptyset$. This means that there are some vertices of
$\cup_{r=i+1}^{t-1}X_{r}$ which are not appearing in the sequence $S$. Let $A$
denotes the set of these vertices. Note that $A$ is not the empty set. As
$X_{t}\cap\hat{S}\neq\emptyset$, vertices of $X_{t}\cap\hat{S}$ appear to
footprint some vertices of
$N[X_{t}\cap\hat{S}]=(X_{t}\cap\hat{S})\cup(\cup_{r=1}^{t}Y_{r})$. Let $x$ be
the vertex of $X_{t}$ which appears first in $S$. We discuss two cases here.

Case 1: $x$ footprints itself.
In this case, we have that no neighbor of $X_{t}$ appears in $S$ before $x$.
So, all vertices in $S$, which footprint vertices of $A$, appear after $x$.
Now, we modify $S$ by removing all such vertices and including all vertices of
$A$ in the sequence just after all vertices of $X_{t}\cap\hat{S}$. We call the
modified sequence again by $S$ as it remains a GD-sequence of $G$. Thus, we
get a contradiction on $i$ being the largest index satisfying
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$. So, this case is not possible.

Case 2: $x$ does not footprint itself.
In this case, we get that all vertices of $X_{t}$ are footprinted by some
vertex of $Y$, which appears before $x$ in $S$. So, $x$ footprints some
vertices from the set $\cup_{r=1}^{t}Y_{r}$. Thus, $|X_{t}\cap\hat{S}|=1$ and
$X_{t}\cap\hat{S}=\\{x\\}$. Now, let $y$ be the vertex which footprints
vertices of $A\cap X_{i+1}$ in $S$. Then, there can be two subcases:

Subcase 2.1: $y$ appears after $x$.
In this subcase, we modify $S$ by removing $y$ and including all vertices of
$A\cap X_{i+1}$ in the sequence just after $x$. We call the modified sequence
again by $S$ as it remains a GD-sequence of $G$. Thus, we get a contradiction
on $i$ being the largest index satisfying
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$. So, this subcase is not possible.

Subcase 2.2: $y$ appears before $x$.
Here, all vertices of $A$ are footprinted before the appearance of $x$. Recall
that $x\in(\cup_{r=i+2}^{k}X_{r})\cap\hat{S}$. We get that all vertices of
$\cup_{r=i+1}^{k}X_{r}$ are footprinted before the appearance of $x$. Note
that the vertex $x$ itself is footprinted before the appearance of $x$. So, we
have, $x$ appears to footprint some vertices of $\cup_{r=1}^{t}Y_{r}$. This
can be further divided in two cases: (i) $x$ does not footprint the vertices
of $Y_{t}$. (ii) $x$ footprints the vertices of $Y_{t}$.

In the first case, $x$ footprints some vertices of the set
$\cup_{r=1}^{t-1}Y_{r}$. Note that $A\cap X_{t-1}\neq\emptyset$ and vertices
of $A\cap X_{t-1}$ do not appear in $S$. Now, we modify $S$ by replacing the
vertex $x$ by a vertex of $A\cap X_{t-1}$ and a get a new GD-sequence in which
no vertex of $X_{t}$ appears and one vertex of $X_{t-1}$ appears. If $t=i+2$,
then after applying the modification once, we get a GD-sequence $S^{\prime}$
such that $X_{i+2}\cap\hat{S^{\prime}}=\emptyset$ and
$|X_{i+1}\cap\hat{S^{\prime}}|=1$. Otherwise, if $t>i+2$, then after applying
the modification once, we get a GD-sequence $S^{\prime}$ such that
$X_{t}\cap\hat{S^{\prime}}=\emptyset$ and $|X_{t-1}\cap\hat{S^{\prime}}|=1$.
Thus, we have another index $t^{\prime}=t-1\in\\{i+2,\ldots,k\\}$ such that
$X_{t^{\prime}}\cap\hat{S^{\prime}}\neq\emptyset$.

In the second case, $x$ footprints vertices of $Y_{t}$ and we modify $S$ by
replacing $x$ with all vertices of $Y_{t}$. Note that no vertex of $Y_{t}$ was
appearing in the sequence prior to this modification. If $t=i+2$, then after
applying the modification once, we get a GD-sequence $S^{\prime}$ such that
$X_{i+2}\cap\hat{S^{\prime}}=\emptyset$. Otherwise, if $t>i+2$, then after
applying the modification once, we get a GD-sequence $S^{\prime}$ such that
$X_{t}\cap\hat{S^{\prime}}=\emptyset$ and
$X_{t-1}\cap\hat{S^{\prime}}=\emptyset$. Now, we have, either there is no
index $t^{\prime}$ in the set $\\{i+2,\ldots,k\\}$ such that
$X_{t^{\prime}}\cap\hat{S^{\prime}}\neq\emptyset$ or there is some
$t^{\prime}\in\\{i+2,\ldots,k\\}~{}(t^{\prime}>t)$ such that
$X_{t^{\prime}}\cap\hat{S^{\prime}}\neq\emptyset$.

In both the cases, we end up with a new GD-sequence $S^{\prime}$ of $G$. In
the former case, we get that $X_{t}\cap\hat{S^{\prime}}=\emptyset$ and
$|X_{t-1}\cap\hat{S^{\prime}}|=1$. The latter case ensures that
$X_{t}\cap\hat{S^{\prime}}=\emptyset$ and
$X_{t-1}\cap\hat{S^{\prime}}=\emptyset$ (if $t>i+2$). By repeating the above
arguments we get that, there is a GD-sequence $S$ of $G$ such that either
$(\cup_{r=i+1}^{k}X_{r})\cap\hat{S}=\emptyset$ or
$(\cup_{r=i+2}^{k}X_{r})\cap\hat{S}=\emptyset$ and $|X_{i+1}\cap\hat{S}|=1$
for some $i\in[k]$. ∎

Analogous to Lemma 3, we give a symmetric lemma for the set $Y$ of $G$, whose
proof follows similar lines, and is omitted.

######  Lemma 4.

Let $S$ be a GD-sequence of $G$ of type (c) and let $j\in[k]$ be the smallest
index such that $\cup_{r=j}^{k}Y_{r}\subseteq\hat{S}$. If $j>1$, then the
following is true:

  1. (1)

If $j\geq 3$, then there exists a GD-sequence $S^{\prime}$ of $G$ such that
either $(\cup_{r=1}^{j-1}Y_{r})\cap\hat{S^{\prime}}=\emptyset$ or
$(\cup_{r=1}^{j-2}Y_{r})\cap\hat{S^{\prime}}=\emptyset$ and
$|Y_{j-1}\cap\hat{S^{\prime}}|=1$.

  2. (2)

If $j=2$, then either $Y_{1}\cap\hat{S}=\emptyset$ or $|Y_{1}\cap\hat{S}|=1$.

######  Lemma 5.

Let $S$ be a GD-sequence of $G$ satisfying all properties of Lemmas 1, 2, 3
and 4, let $i\in[k]$ have the role as in Lemma 3, and let $j\in[k]$ have the
role as in Lemma 4. The following statements are true:

  1. (1)

$j\in\\{i,i+1\\}$;

  2. (2)

if $j=i$ then $|X_{i}|=1$ or $|Y_{i}|=1$;

  3. (3)

if $j=i+1$, then either $|X_{i+1}\cap\hat{S}|=1$ or $|Y_{i}\cap\hat{S}|=1$.

###### Proof.

Since $S$ satisfies all properties of Lemmas 1, 2, 3 and 4, there are integers
$i\in[k-1],j\in\\{2,\ldots,k\\}$ such that
$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$ and
$\cup_{r=j}^{k}Y_{r}\subseteq\hat{S}$. It also holds that either
$X_{i+1}\cap\hat{S}=\emptyset$ or $|X_{i+1}\cap\hat{S}|=1$. Similarly, either
$Y_{j-1}\cap\hat{S}=\emptyset$ or $|Y_{j-1}\cap\hat{S}|=1$. Using Lemmas 3 and
4, we can also say that if $i\leq k-2$, then
$(\cup_{r=i+2}^{k}X_{r})\cap\hat{S}=\emptyset$ and, if $j\geq 3$, then
$(\cup_{r=1}^{j-2}Y_{r})\cap\hat{S}=\emptyset$.

First, we show that $j\geq i$. To the contrary, assume that $j<i$. This
implies that $X_{i-1}\cup Y_{i-1}\cup X_{i}\cup Y_{i}\subseteq\hat{S}$. If
$X_{i}$ appears before $Y_{i}$, then $Y_{i-1}$ appears after $Y_{i}$. In this
case, we see that $X_{i-1}$ can not appear anywhere in the sequence. So, this
case is not possible. If $Y_{i}$ appears before $X_{i}$, then $X_{i-1}$
appears after $X_{i}$. Here, $Y_{i-1}$ can not appear anywhere in the
sequence. So, this case is also not possible. So, we get that $j\geq i$. Now,
either $j=i$ or $j\geq i+1$.

First, we assume $j=i$. If $X_{i}$ appears before $Y_{i}$, then an eventual
second vertex from $Y_{i}$ does not footprint any vertex, a contradiction. So,
$|Y_{i}|=1$. In the similar way, we get that $|X_{i}|=1$, when $Y_{i}$ appears
before $X_{i}$. Thus, property $(2)$ holds.

Next, assume that $j\geq i+1$. We need to show that $j=i+1$. First, we show
that $j\leq i+3$. If $j\geq i+4$, then
$X_{i+2}\cap\hat{S}=\emptyset,Y_{i+2}\cap\hat{S}=\emptyset$. This contradicts
Observation 4. So, $j\in\\{i+1,i+2,i+3\\}$. If $j=i+3,$ then we see that
$\gamma_{gr}(G)\leq\alpha+\beta+2$, where $\alpha=\sum_{r=1}^{i}|X_{r}|$ and
$\beta=\sum_{r=i+3}^{k}|Y_{r}|$. But, the sequence
$(X_{1})\oplus(X_{2})\oplus\cdots\oplus(X_{i})\oplus(X_{i+1})\oplus(Y_{k})\oplus(Y_{k-1})\oplus\cdots\oplus(Y_{i+3})\oplus(x)\oplus(X_{i+2})$,
where $x\in X_{i+3}$ is a dominating sequence of $G$ of length at least
$\alpha+\beta+3$. So, $j\neq i+3$. If $j=i+2$, then we see that
$\gamma_{gr}(G)\leq\alpha+\beta^{\prime}+2$, where
$\beta^{\prime}=\sum_{r=i+2}^{k}|Y_{r}|$. Now, consider the sequence
$S_{0}=(X_{1})\oplus(X_{2})\oplus\cdots\oplus(X_{i})\oplus(Y_{k})\oplus(Y_{k-1})\oplus\cdots\oplus(Y_{i+2})\oplus(y)\oplus(Y_{i+1})$,
where $y\in Y_{i}$. If $|Y_{i+1}|>1$, $S_{0}$ is a dominating sequence of $G$
having length at least $\alpha+\beta^{\prime}+3$. This implies that
$|Y_{i+1}|=1$ and $S_{0}$ is also a GD-sequence of $G$. So, we consider
$S_{0}$ as a GD-sequence of $G$ as it also satisfies Lemmas 1, 2, 3 and 4 and
thus, $j=i+1$. Thus, property $(1)$ holds.

For the property $(3)$, we show that either $|X_{i+1}\cap\hat{S}|=1$ or
$|Y_{i}\cap\hat{S}|=1$. So, first we assume that neither is true, that is,
$|X_{i+1}\cap\hat{S}|=0$ and $|Y_{i}\cap\hat{S}|=0$. Now, if $Y_{i+1}$ appears
before $X_{i}$, then the length of $S$ can be increased by including a vertex
of $X_{i+1}$ just before $X_{i}$, but $S$ is a dominating sequence of $G$ of
maximum length. So, $Y_{i+1}$ appears after $X_{i}$, thus length of $S$ can be
increased by including a vertex of $Y_{i}$ just before $Y_{i+1}$, but $S$ is a
dominating sequence of $G$ of maximum length. Hence, $|X_{i+1}\cap\hat{S}|=1$
or $|Y_{i}\cap\hat{S}|=1$. If $|X_{i+1}\cap\hat{S}|=1$ and
$|Y_{i}\cap\hat{S}|=1$, then suppose that $X_{i+1}\cap\hat{S}=\\{a\\}$ and
$Y_{i}\cap\hat{S}=\\{b\\}$. Clearly, vertices of the four sets
$\\{a\\},\\{b\\},X_{i}$ and $Y_{i+1}$ appear in $S$. Let
$\mathcal{K}=\\{\\{a\\},\\{b\\},X_{i},Y_{i+1}\\}$. Recall that all vertices of
$X_{i}$ appear together in $S$. Similarly, all vertices of $Y_{i+1}$ appear
together in $S$. Let $A\in\mathcal{K}$ be the set whose vertices appear after
the other three sets of $\mathcal{K}$ in the sequence $S$. Then, all vertices
of $N[A]$ are footprinted before the appearance of vertices of $A$. Therefore,
either $|X_{i+1}\cap\hat{S}|=1$ or $|Y_{i}\cap\hat{S}|=1$. Thus property $(3)$
holds. ∎

######  Lemma 6.

Let $S$ be a GD-sequence of $G$ of type (c) and satisfies all properties of
Lemmas 1, 2, 3, 4 and 5. Then the sequence $S$ satisfies the following
properties

  1. (1)

If $j=i$ then, $X_{i+1}\cap\hat{S}=\emptyset$ and
$Y_{i-1}\cap\hat{S}=\emptyset$;

  2. (2)

If $j=i+1$, then either $|X_{i+1}\cap\hat{S}|=1$ and
$Y_{i}\cap\hat{S}=\emptyset$ or $|Y_{i}\cap\hat{S}|=1$ and
$X_{i+1}\cap\hat{S}=\emptyset$.

###### Proof.

First, let $j=i$ and $X_{i+1}\cap\hat{S}\neq\emptyset$. This implies that
$|X_{i+1}\cap\hat{S}|=1$. There are two cases.

Case 1: A vertex of $X_{i+1}$ footprints itself.
In this case, both $Y_{i}$ and $Y_{i+1}$ appear after $X_{i+1}$. Note that
$Y_{i+1}$ appears before $Y_{i}$. Here, we see that $X_{i}$ can not appear
after $Y_{i}$ as all vertices in the closed neighborhood of $X_{i}$ are
footprinted before its appearance. So, $X_{i}$ appears before $Y_{i}$, but,
then all vertices in the closed neighborhood of $Y_{i}$ are footprinted before
its appearance.

Case 2: Vertices of $X_{i+1}$ are footprinted before their appearance in $S$.
Here, at least one of $Y_{i}$ and $Y_{i+1}$ appear before $X_{i+1}$. So, first
we assume that $Y_{i}$ appears before $X_{i+1}$. Let $A$ denotes the set of
vertices which appear before $Y_{i}$, $B$ denotes the set of vertices which
appear before $X_{i+1}$ and after $Y_{i}$ and $C$ denotes the set of vertices
which appear after $X_{i+1}$ in $S$. In this case, $X_{i}\nsubseteq C$, so
$X_{i}\subseteq A\cup B$. But, then one of $Y_{i+1}$ and $X_{i+1}$ does not
footprint any vertex, a contradiction. Similar arguments can be given when
$Y_{i+1}$ appears before $X_{i+1}$. Hence, $X_{i+1}\cap\hat{S}=\emptyset$. In
the similar manner, we can prove that $Y_{i-1}\cap\hat{S}=\emptyset$.

Next, we assume that $j=i+1$ and $|X_{i+1}\cap\hat{S}|=1$. We need to show
that $Y_{i}\cap\hat{S}=\emptyset$. On the contrary, suppose that
$Y_{i}\cap\hat{S}\neq\emptyset$. Here, we see that $S$ contain vertices from
all of the sets $X_{i},X_{i+1},Y_{i}$ and $Y_{i+1}$. Then there exists a
vertex $a\in X_{i}\cup X_{i+1}\cup Y_{i}\cup Y_{i+1}$ whose closed
neighborhood is footprinted before its appearance, a contradiction. In the
similar way, we can prove that if $|Y_{i}\cap\hat{S}|=1$, then
$X_{i+1}\cap\hat{S}=\emptyset$. ∎

######  Lemma 7.

Let $S=(v_{1},v_{2},\ldots,v_{p})$ be a GD-sequence of $G$, which satisfies
$X\subseteq\hat{S}$. Then one of the following statements is true.
$1.$ $\gamma_{gr}(G)=|X|$
$2.$ $\gamma_{gr}(G)=|Y|$
$3.$ $\gamma_{gr}(G)=|X|+|Y_{k}|$

###### Proof.

If $S$ is not a type (c) GD-sequence of $G$, then $Y\cap\hat{S}=\emptyset$ and
so, $\gamma_{gr}(G)=|X|$. So, assume that $S$ is a type (c) GD-sequence of
$G$.

Case 1: $v_{1}\in Y_{1}$.
In this case, all vertices of $X$ are footprinted by $v_{1}$. So, all the
vertices $v_{2},\ldots,v_{p}$ appear to footprint vertices of
$Y\setminus\\{v_{1}\\}$ only. This implies that $\gamma_{gr}(G)\leq|Y|$ and
so, $\gamma_{gr}(G)=|Y|$.

Case 2: $v_{1}\notin Y_{1}$.
Here, we see that $S$ satisfies all conditons of part (2) of Lemma 1 with
$i=k$. Using Lemma 4, we get that there exists an integer $j\in[k]$ such that
$\cup_{r=j}^{k}Y_{r}\subseteq\hat{S}$ and Lemma 5 ensures that $j=k$. Hence,
we have that $Y_{k}\subseteq\hat{S}$ and
$(\cup_{r=1}^{k-2}Y_{r})\cap\hat{S}=\emptyset$, if $k\geq 3$. Thus, we have
that $X\cup Y_{k}\subseteq\hat{S}$ and so, $\gamma_{gr}(G)\geq|X|+|Y_{k}|$.
Now, if there is no vertex of $Y$ before the vertices of $X_{k}$ in $S$, then
$\gamma_{gr}(G)\leq|X|$. So, all vertices of $Y_{k}$ appear before vertices of
$X_{k}$.

Next, we have that $Y_{k-1}\cap\widehat{S}=\emptyset$ using Lemma 6.
Therefore, $\hat{S}=X\cup Y_{k}$ which implies that
$\gamma_{gr}(G)=|X|+|Y_{k}|$. ∎

Analogous to Lemma 7, we give a symmetric lemma for the set $Y$ of $G$, whose
proof follows similar lines, and is omitted.

######  Lemma 8.

Let $S=(v_{1},v_{2},\ldots,v_{p})$ be a GD-sequence of $G$, which satisfies
$Y\subseteq\hat{S}$. Then one of the following statements is true.
$1.$ $\gamma_{gr}(G)=|Y|$
$2.$ $\gamma_{gr}(G)=|X|$
$3.$ $\gamma_{gr}(G)=|Y|+|X_{1}|$

######  Lemma 9.

If $G=(X,Y,E)$ is a chain graph such that every GD-sequence of $G$ is of type
(c), then for any GD-sequence $S$ of $G$, the following statements are true:

  1. (1)

$\cup_{r=1}^{i}X_{r}\subseteq\hat{S}$ and
$\cup_{r=j}^{k}Y_{r}\subseteq\hat{S}$ for some $i,j\in[k]$.

  2. (2)

Integers $i$ and $j$ satisfy exactly one of the following:

    1. (a)

$i<k,j>1$.

    2. (b)

$i=1,j=1$.

    3. (c)

$i=k,j=k$.

  3. (3)

If $i<k,j>1$, then
$\gamma_{gr}(G)=\begin{cases}\sum_{r=1}^{i}|X_{r}|+\sum_{r=j}^{k}|Y_{r}|&:j=i\\\
\sum_{r=1}^{i}|X_{r}|+\sum_{r=j}^{k}|Y_{r}|+1&:j=i+1\end{cases}$

  4. (4)

If $i=1,j=1$, then $\gamma_{gr}(G)=|Y|+|X_{1}|$

  5. (5)

If $i=k,j=k$, then $\gamma_{gr}(G)=|X|+|Y_{k}|$

###### Proof.

Lemmas 1 and 2 ensure property (1). To prove property (2), we need to show
that $i=k,j=1$ cannot be true. So, assume that this is true. Then, Lemma 5
yields $k=1$, a contradition proving that property (2) holds. Property (3)
follows from Lemmas 3, 4, 5 and 6. Properties (4) and (5) can be proved using
Lemmas 7 and 8. ∎

We are ready to present an algorithm for computing a GD-sequence of a chain
graph based on the above lemmas; see Algorithm 1.

Input: A chain graph $G=(X,Y,E)$ without isolated vertices along with a chain
ordering $(x_{1},\ldots,x_{n_{1}},y_{1},\ldots,y_{n_{2}})$ of $V(G)$.

Output: A GD-sequence $S$ of $G$.

1Find the parts $X_{1},X_{2},\ldots,X_{k}$ and $Y_{1},Y_{2},\ldots,Y_{k}$;

2$i=0$, $sum[$ $]=0$;

3if  _$|Y_{1}|=1$_ then

4 $sum[0]=n_{2}+|X_{1}|$;

5else

6 $sum[0]=n_{2}$;

7for  _$i=1:k-1$_ do

8 $sum[i]=\sum_{j=1}^{i}|X_{j}|+n_{2}-\sum_{j=1}^{i}|Y_{j}|+1$;

9if  _$|X_{k}|=1$_ then

10 $sum[k]=n_{1}+|Y_{k}|$;

11else

12 $sum[k]=n_{1}$;

13Find an index $i^{*}\in\\{0,1,2,\ldots,k\\}$ for which $sum[i]$ is maximum;

14if  _$i^{*}==0$ and $|Y_{1}|>1$_ then

15$S\leftarrow(Y_{k})\oplus(Y_{k-1})\oplus\cdots\oplus(Y_{1})$;

16else if  _$i^{*}==0$ and $|Y_{1}|=1$_ then

17if  _$k\geq 3$_ then

18$S\leftarrow(X_{1})\oplus(Y_{k})\oplus\cdots\oplus(Y_{3})\oplus(Y_{1})\oplus(Y_{2})$;

19else

20$S\leftarrow(X_{1})\oplus(Y_{1})\oplus(Y_{2})$;

21else if  _$i^{*}==k$ and $|X_{k}|>1$_ then

22$S\leftarrow(X_{1})\oplus(X_{2})\oplus\cdots\oplus(X_{k})$;

23else if  _$i^{*}==k$ and $|X_{k}|=1$_ then

24if  _$k\geq 3$_ then

25$S\leftarrow(X_{1})\oplus(X_{2})\oplus\cdots\oplus(X_{k-2})\oplus(Y_{k})\oplus(X_{k})\oplus(X_{k-1})$;

26else

27$S\leftarrow(Y_{2})\oplus(X_{2})\oplus(X_{1})$;

28else

29choose a vertex $x\in X_{i^{*}+1}$

30if  _$i^{*} >1$_ then

31$S\leftarrow(X_{1})\oplus(X_{2})\oplus\cdots\oplus(X_{i^{*}-1})\oplus(Y_{k})\oplus(Y_{k-1})\oplus\cdots\oplus(Y_{i^{*}+1})\oplus
x\oplus(X_{i^{*}})$;

32else

33$S\leftarrow(Y_{k})\oplus(Y_{k-1})\oplus\cdots\oplus(Y_{2})\oplus
x\oplus(X_{1})$;

34return $S$.

Algorithm 1 GD-sequence of a chain graph

By following the above discussion, note that $\gamma_{gr}(G)\in{\cal A}$,
where

${\cal
A}=\\{n_{1},n_{2},n_{1}+|Y_{k}|,n_{2}+|X_{1}|,\sum_{r=1}^{i}|X_{r}|+\sum_{l=i}^{k}|Y_{l}|,\sum_{r=1}^{i}|X_{r}|+\sum_{l=i+1}^{k}|Y_{l}|+1\\},$

for some $i\in[k-1]$. Thus, the sequence returned by Algorithm 1 is a GD-
sequence of $G$. It is easy to see that Algorithm 1 computes $S$ in linear
time, which is the time needed to compute the parts
$X_{1},\ldots,X_{k},Y_{1},\ldots,Y_{k}$. The following theorem readily
follows.

######  Theorem 4.

Algorithm 1 outputs a GD-sequence $S$ of $G$ in linear time.

There is a connection between Grundy domination number of a graph and its
independence number. Let $A$ be an independent set of size $\alpha(G)$. By
considering all vertices of $A$ in any order, we get a closed neighborhood
sequence of $G$, which yields the well known bound
$\gamma_{gr}(G)\geq\alpha(G)$. In addition, for a chain graph $G$, we prove
that Grundy domination number is either $\alpha(G)$ or $\alpha(G)+1$.

######  Theorem 5.

If $G$ is a chain graph, then $\gamma_{gr}(G)\in\\{\alpha(G),\alpha(G)+1\\}$.

###### Proof.

Let $G$ be a chain graph. By using the notation established in this section,
we claim that
$\alpha(G)\in\\{n_{1},n_{2},\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|\text{
for some }i\in[k-1]\\}$. To see this, let $A$ be a maximum independent set of
$G$. Three cases are possible. If $A\subseteq X$, then $A=X$ implying that
$\alpha(G)=n_{1}$; if $A\subseteq Y$, then $A=Y$ implying that
$\alpha(G)=n_{2}$. Now, if $A\cap X\neq\emptyset$ and $A\cap Y\neq\emptyset$,
then one can easily infer that
$A=(\cup_{j=1}^{i}X_{j})\cup(\cup_{j=i+1}^{k}Y_{j})$ for some $i\in[k-1]$
implying that $\alpha(G)=\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|$.
Letting $i_{0}\in[k-1]$ be an index such that
$\sum_{j=1}^{i_{0}}|X_{j}|+\sum_{j=i_{0}+1}^{k}|Y_{j}|\geq\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|\text{
for each }i\in[k-1]$, we may write
$\alpha(G)\in\\{n_{1},n_{2},\sum_{j=1}^{i_{0}}|X_{j}|+\sum_{j=i_{0}+1}^{k}|Y_{j}|\\}$.

Algorithm 1 computes a GD-sequence of $G$ and it turns out that
$\gamma_{gr}(G)\in\\{n_{1},n_{2},n_{1}+|Y_{k}|,n_{2}+|X_{1}|,\sum_{j=1}^{i}|X_{j}|+\sum_{j=i}^{k}|Y_{j}|,\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|+1\\}$
for some $i\in[k-1]$. Note that $\gamma_{gr}(G)=n_{1}+|Y_{k}|$ when
$|X_{k}|=1$ implying that $\gamma_{gr}(G)=\sum_{j=1}^{k-1}|X_{j}|+|Y_{k}|+1$.
Similarly, $\gamma_{gr}(G)=n_{2}+|X_{1}|$ when $|Y_{1}|=1$ implying that
$\gamma_{gr}(G)=|X_{1}|+\sum_{j=2}^{k}|Y_{k}|+1$. Now, if
$\gamma_{gr}(G)=\sum_{j=1}^{i}|X_{j}|+\sum_{j=i}^{k}|Y_{j}|$ for some
$i\in[k-1]$ then Lemma 5 ensures that $\gamma_{gr}(G)$ is either
$\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|+1$ or
$\sum_{j=1}^{i-1}|X_{j}|+\sum_{j=i}^{k}|Y_{j}|+1$. Hence,
$\gamma_{gr}(G)\in\\{n_{1},n_{2},\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|+1\text{
for some }i\in[k-1]\\}$. Since Algorithm 1 computes the GD-sequence by finding
the maximum of the set
$\\{n_{1},n_{2}\\}\cup\\{\sum_{j=1}^{i}|X_{j}|+\sum_{j=i+1}^{k}|Y_{j}|+1:i\in[k-1]\\}$,
we have,
$\gamma_{gr}(G)\in\\{n_{1},n_{2},\sum_{j=1}^{i_{0}}|X_{j}|+\sum_{j=i_{0}+1}^{k}|Y_{j}|+1\\}$.
Now, suppose $t=\sum_{j=1}^{i_{0}}|X_{j}|+\sum_{j=i_{0}+1}^{k}|Y_{j}|$, then
we can write that $\alpha(G)\in\\{n_{1},n_{2},t\\}$ and
$\gamma_{gr}(G)\in\\{n_{1},n_{2},t+1\\}$. Now, we consider three cases.

Case 1: $\gamma_{gr}(G)=n_{1}$:
In this case, $n_{1}\geq n_{2}$ and $n_{1}\geq t+1>t$. This implies that
$\alpha(G)=n_{1}$.

Case 2: $\gamma_{gr}(G)=n_{2}$:
In this case, $n_{2}\geq n_{1}$ and $n_{2}\geq t+1>t$. This implies that
$\alpha(G)=n_{2}$.

Case 3: $\gamma_{gr}(G)=t+1$:
In this case, if $\alpha(G)=n_{1}$ then $n_{1}\geq t=\gamma_{gr}(G)-1$. So,
$\gamma_{gr}(G)\leq\alpha(G)+1$. Similarly, if $\alpha(G)=n_{2}$ then
$n_{2}\geq t=\gamma_{gr}(G)-1$. So, $\gamma_{gr}(G)\leq\alpha(G)+1$.
Otherwise, $\alpha(G)=t$ implying that $\gamma_{gr}(G)=\alpha(G)+1$.

Therefore, $\gamma_{gr}(G)\in\\{\alpha(G),\alpha(G)+1\\}$. ∎

##  5 Conclusion

In this paper, we studied the GDD problem for bipartite graphs and co-
bipartite graphs. We proved that the problem is NP-complete for bipartite
graphs and efficiently solvable for chain graphs, which form a subclass of
bipartite graphs. We also proved NP-completeness of the problem in co-
bipartite graphs. To obtain a complete dichotomy, it would be interesting to
find the status of the problem in some graph classes that lie between chain
graphs and bipartite graphs.

Note that the GDD problem in the class of co-chain graphs (that is, the
complements of chain graphs) is easily solvable. Indeed, in a co-chain graph
$G=(X,Y,E)$, one can find similar partitions of $X$ and $Y$ into $k$ sets
$X_{1},\ldots,X_{k}$, and $Y_{1},\ldots,Y_{k}$, respectively, that arises from
the closed twin relation in $G$. Then, one can also immediately infer that
$\gamma_{gr}(G)=k$. It would be interesting to see if there are some other
known classes of graphs $\cal G$ whose complement class $\overline{{\cal
G}}=\\{\overline{G}:\,G\in\cal G\\}$ has similar status of the computational
complexity of the GDD problem as $\cal G$. Two nice instances (with $\cal G$
given by bipartite graphs and chain graphs) are presented in this paper.

## Declarations

Conflict of interest: The authors have no conflicts of interest to declare
that are relevant to the content of this article.

## Acknowledgments

The first author was supported by the Slovenian Research and Innovation agency
(grants P1-0297, J1-2452, J1-3002, and J1-4008).

## References

  * Bell et al [2021] Bell K, Driscoll K, Krop E, Wolff K (2021) Grundy domination of forests and the strong product conjecture. The Electronic Journal of Combinatorics P2.12
  * Brešar et al [2010] Brešar B, Klavžar S, Rall DF (2010) Domination game and an imagination strategy. SIAM Journal on Discrete Mathematics 24(3):979–991
  * Brešar et al [2014] Brešar B, Gologranc T, Milanič M, Rall DF, Rizzi R (2014) Dominating sequences in graphs. Discrete Mathematics 336:22–36
  * Brešar et al [2016a] Brešar B, Gologranc T, Kos T (2016a) Dominating sequences under atomic changes with applications in sierpinski and interval graphs. Appl Anal Discrete Math 10(2):518–531
  * Brešar et al [2016b] Brešar B, Henning MA, Rall DF (2016b) Total dominating sequences in graphs. Discrete Mathematics 339(6):1665–1676
  * Brešar et al [2017] Brešar B, Bujtás Cs, Gologranc T, Klavžar S, Košmrlj G, Patkós B, Tuza Zs, Vizer M (2017) Grundy dominating sequences and zero forcing sets. Discrete Optimization 26:66–77
  * Brešar et al [2021] Brešar B, Henning MA, Klavžar S, Rall DF (2021) Domination games played on graphs. Springer, Cham
  * Campêlo and Severín [2021] Campêlo M, Severín D (2021) An integer programming approach for solving a generalized version of the grundy domination number. Discrete Applied Mathematics 301:26–48
  * Erey [2020] Erey A (2020) Uniform length dominating sequence graphs. Graphs and Combinatorics 36(6):1819–1825
  * Haynes and Hedetniemi [2021] Haynes T, Hedetniemi S (2021) Vertex sequences in graphs. Discrete Math Lett 6:19–31
  * Haynes et al [2020] Haynes TW, Hedetniemi ST, Henning MA (eds) (2020) Topics in domination in graphs, Developments in Mathematics, vol 64. Springer, Cham
  * Haynes et al [2021] Haynes TW, Hedetniemi ST, Henning MA (eds) (2021) Structures of domination in graphs, Developments in Mathematics, vol 66. Springer, Cham
  * Haynes et al [2022] Haynes TW, Hedetniemi ST, Henning MA (2022) Domination in graphs: Core concepts. Manuscript (Springer, New York, 2020)
  * Heggernes and Kratsch [2007] Heggernes P, Kratsch D (2007) Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nord J Comput 14(1-2):87–108
  * Lin [2019] Lin JH (2019) Grundy domination number, and their variants. Linear Algebra Appl 563:240–254
  * Nasini and Torres [2020] Nasini G, Torres P (2020) Grundy dominating sequences on x-join product. Discrete Applied Mathematics 284:138–149


# Barrow black hole variable parameter model
connected to information theory

Everton M. C. Abreu<EMAIL_ADDRESS>Departamento de Física,
Universidade Federal Rural do Rio de Janeiro, 23890-971, Seropédica, RJ,
Brazil  Departamento de Física, Universidade Federal de Juiz de Fora,
36036-330, Juiz de Fora, MG, Brazil  Programa de Pós-Graduação
Interdisciplinar em Física Aplicada, Instituto de Física, Universidade Federal
do Rio de Janeiro, 21941-972, Rio de Janeiro, RJ, Brazil

###### Abstract

One of the greatest challenges of theoretical physics today is to unveil the
quantum information theory concerning what happens when one bit of information
enters the black hole (BH) horizon. The Landauer principle showed that a
certain amount of energy is generated when one-bit of information is erased as
it enters the event horizon system. In this paper we used the recently
developed Barrow BH model to calculate the addition to the area of the event
horizon of his toy model by using the Landauer concept. Besides we make this
computation considering $\Delta$ as a constant and a variable parameter. We
formulate the Barrow parameter ($\Delta$) as a function of the energy/mass,
which is new in the Barrow BH literature. We will investigate the differences
between the Bekenstein-Hawking entropy ($\Delta=0$) and the fractal
($\Delta=1$) cases concerning the addition in the area of the BH. The
asymptotical analysis is also mentioned and we will see that it affects only
the fractal case. All the results accomplished here are new concerning BHs in
general and the Barrow model literature in particular.

Black holes information theory, Landauer principle, Barrow black hole entropy

###### pacs:

03.67.-a, 04.70.Dy, 04.70.-s

##  I Introduction

Entropy is well known to be a measure of disorder, or of how much uncertainty
we have in the whole system. Its connection to information, its depository and
the analysis of what happens in each system has underlying relevance nowadays.

The Gibbs paradox explain the subjective nature of entropy. It consider a box
divided by a wall and we have two equal parts. Each part has an ideal gas at
the same temperature nd pressure. Without the wall, both parts will mix. If
both gases are different, the entropy of the system will rise. In the case of
equality, both gases are identical and the entropy does not change. So, the
entropy depends on the capacity of the observer to distinguish or not, both
gases. Hence, irreversibility is dependent of what we know about physics bf .
Hence, we can conclude that physical objects do not have an intrinsic entropy.

The so-called comoving observers have a system that is dissipationless, i.e.,
with no gain in the entropy although to the so-called tilted congruence, we
have the presence of dissipative fluxes, with entropy producing.

Let us consider a different point of view, by accounting the transitions form
the tilted congruence case to the comoving one. The Landauer principle,
landauer  also known as the Brilloin principle brilloin-varios , the erasure
of one-bit of information within a system demands the dissipation into the
environment of a minimal quantity of energy, which if written by

$\delta E\,=\,k_{{}_{B}}T\ln 2\;\;,$ (1)

where $T$ is the temperature of the environment. The $\ln 2$ term comes
directly from the information theory since $e^{S}=N=2^{n}$, where $N$ is the
dimension of the Hilbert space and $n$ is the total number of Boolean degree
of freedom in a region encompassing the BH. So, the entropy is given by $n\ln
2$.

Namely, Landauer landauer  demonstrated that reproducing classical information
can be carried out reversibly and without wasting energy. However, when
information is erased there is an energy cost greater than $k_{{}_{B}}\,T\,\ln
2$ per classical bit. This energy is ultimately converted into thermal energy
and raises the final energy of the whole system by $\delta E\geq
k_{{}_{B}}\,T\,\ln 2$.

In other words, erasure means a reset operation recovering the system to a
peculiar state, using an external agent, i.e., we can carry out work on it.
However, we have to increase the entropy of another system or the environment.

Hence, the Landauer principle is a reflection of the fact that logical
irreversibility implies thermodynamical irreversibility. It is a particular
version of the second law of thermodynamics constructed to include the
information theory. The erasure of data in a system concerns the production of
heat and therefore increasing of entropy. Throughout the erasure of one-bit of
information the framework has to generate at least $\delta
Q=k_{{}_{B}}\,T\,\ln 2$ of heat. Hence, the erasure of one-bit of information
raises the classical entropy by $\delta S\geq k_{{}_{B}}\,\ln 2$. Landauer
principle has been relevant in fathoming the thermodynamics of quantum
computation landauer2 ; Lloyd ; jwzgb  establishing a principle of information
erasure for a black hole (BH), that says that “A BH is one of the most
efficient information eraser in systems of a given temperature.” In the
information erasing procedure the infalling matter “saturates the Landauer
bound, $\delta E=k_{{}_{B}}\,T\,\ln 2$” landauer . The result is that this
saturating energy $\delta E$ is given to BH, although the system, the
intermediate region of information, is in thermal contact with BH that acts as
a thermal bath and raise its mass by, as we will see, by

$\delta(Mc^{2})\,=\delta E\,=\,k_{{}_{B}}\,T\,\ln 2\;\;,$ (2)

where $T$ is the BH temperature and it multiplies the increased entropy
$\delta S=k_{{}_{B}}\,\ln 2$. It is important the notice that the relation in
Eq. (2) does not origin form the first law of BH thermodynamics. It is
understood that the energy $k_{{}_{B}}\,T\,\ln 2$ is coming from the infalling
particle into the system erasing one-bit of information in the system and
ultimately to the BH via thermal contact. Thus, the rise of the BH mass
$\delta M$ is connected to the information erasing of the system directly.

Barrow entropy barrow  has been demonstrated to result in very relevant
cosmological phenomena meus ; saridakis . It originates from quantum
gravitational phenomena on he horizon framework barrow , parametrized by the
single exponent $\Delta$, where $\Delta=0$ means the standard Bekenstein-
Hawking bekenstein ; hawking  entropy and $\Delta=1$ means the maximal fractal
deformation. Consequently, we can realize the at early times these quantum
behavior is deeper and so $\Delta$ is closer to one. However, as time goes by,
$\Delta$ tends to its basic value which is zero. To sum up, a scenario of
Barrow entropy with a variable parameter $\Delta$111In blps  the authors
suggested a $\Delta$ being dependent of the scale factor. has a even more
reason that the usual energy scale dependence of coupling parameters blps .
But to construct a $\Delta=\Delta(M)$ as we make here is completely new in the
literature

This paper follows an organization such that in section 2 we used the Barrow
model with $\Delta=\Delta(M)$ to compute the entropy, temperature and the
addition of the area of the BH horizon where one-bit of information is erased.
In section 3, we obtained the standard expression for this area addition for
$\Delta=$constant, i.e., $\Delta=0$ and $\Delta=1$. In section 4, we analyzed
a simple form for the function $\Delta=\Delta(M)$. Finally, the final
discussions, conclusions and perspectives are depicted in section 5.

##  II The Barrow variable parameter

Barrow barrow , based in the geometry of the Covid-$19$ virus, planned a
fractal model for BHs where the entropy is given by

$S_{{}_{Ba}}\,=\,\left(\frac{k_{{}_{B}}A}{4\ell_{P}^{2}}\right)^{1+\frac{\Delta}{2}}$
(3)

Here the deformation provided by quantum gravity is given by the
$\Delta$-parameter shown in Eq. (3), where $\ell_{P}^{2}=G$ is the Planck area
where $c=\hbar=1$. From now on we will oscillate showing relativistic and non-
relativistic units in order to indicate pedagogically gravitational,
thermodynamical quantum and relativistic features of the specific equation,
but we will mention where one or the other are been used, in a very simple and
direct way, of course. The value of $\Delta$ is crucial for the understanding
what kind of geometry we are dealing with. For example, for $\Delta=0$ it is
direct to see that we have the well known Bekenstein-Hawking entropy in Eq.
(3) and for $\Delta=1$ we have he maximal deformation of the BH surface thanks
to its fractal structure as suggested by Barrow barrow .

To be more specific, the geometry visualized by Barrow was created by an
infinite minimizing hierarchy of touching spheres around the Schwarzschild
event horizon. Beginning with a Schwarzschild BH with mass $M$ and radius
$R_{g}=2GM/c^{2}$, some smaller spheres are attached to its outer area.
Moreover, further smaller spheres are also attached to the firstly mentioned
outer spheres and this sequence keeps going to provide a highly intricate
fractal structure. Hence, the boundary will encompass surfaces of
hierarchically framework induces a finite volume, but with the finite or
infinity area, which in turn provides the modification of the BH entropy given
in Eq. (3) mr .

This toy model was created basically to show that close the scale where the
quantum gravity effects rules mr  the surface area of a BH are above
$4\pi\,R^{2}_{g}$ due to the presence of complicated fractal characteristics.
Besides, this happens if we consider any external complexity having a
Hausdorff $D\geq 2$ space. Fundamentally, the $D=2$ geometrical surface
behaves like $D>2$ and tends toward a $D=3$ surface behavior in a limiting
scenario with maximal difficulties. This behavior shows that the $D=2$ surface
behaves as if it carries all the information of a $D=3$ volume, the
holographic concept. It must be noticed that this fractal nature does not
emerge from any specific quantum gravity computation, but from generalized
physical concepts and thus, it is a good proposition as an initial approach
barrow .

Considering Eq. (3) where $A=4\pi\,R^{2}_{g}$ and $R_{g}=2GM$ and so

$A\,=\,16\,\pi\,G^{2}\,M^{2}\;\;.$ (4)

Substituting Eq. (4) into Eq. (3) we have that

$S_{{}_{Ba}}\,=\,\left(\frac{4\pi
k_{{}_{B}}G^{2}M^{2}}{\ell_{P}^{2}}\right)^{1+\frac{\Delta}{2}}\;\;.$ (5)

So, Eq. (5) can now be written as

$S_{{}_{Ba}}\,=\,\Big{(}4\pi
Gk_{{}_{B}}M^{2}\Big{)}^{1+\frac{\Delta}{2}}\;\;.$ (6)

As we mentioned before, here we will use a $\Delta=\Delta(M)$ form. From Eq.
(6) the first step is to write

$\ln S_{{}_{Ba}}\,=\,\Big{(}1+\frac{\Delta}{2}\Big{)}\,\ln\Big{(}4\pi
Gk_{{}_{B}}M^{2}\Big{)}$ (7)

and differentiating this equation it yields

$\frac{\delta S_{{}_{Ba}}}{\delta M}\,=\,\Big{(}4\pi
Gk_{{}_{B}}M^{2}\Big{)}^{1+\frac{\Delta}{2}}\Big{[}\Big{(}A_{G}\,+\,\ln
M\Big{)}\,\frac{\delta\Delta}{\delta M}\,+\,\frac{(2+\Delta)}{M}\Big{]}\;\;,$
(8)

where $A_{G}\,=\,\ln\,(4\pi G\,k_{{}_{B}})/2$

Since we know that

$\frac{1}{T}\,=\,\frac{\delta S}{\delta M}\;\;,$ (9)

from Eq. (8) we can write that

$T\,=\,\frac{1}{\Big{(}4\pi
Gk_{{}_{B}}M^{2}\Big{)}^{1+\frac{\Delta}{2}}\Big{[}\Big{(}A_{G}\,+\,\ln
M\Big{)}\,\frac{\delta\Delta}{\delta M}\,+\,\frac{(2+\Delta)}{M}\Big{]}}\;\;,$
(10)

but, from Landauer’s principle, as said above,

$\delta E\,=\,k_{{}_{B}}\,T\,\ln 2$ $\Longrightarrow\delta
E\,=\,\frac{k_{{}_{B}}^{\prime}\ln
2}{M^{2+\Delta}\,\Big{[}\Big{(}A_{G}\,+\,\ln
M\Big{)}\,\frac{\delta\Delta}{\delta M}\,+\,\frac{(2+\Delta)}{M}\Big{]}}\;\;,$
(11)

where

$k_{{}_{B}}^{\prime}\,=\,\frac{1}{(4\pi
G)^{1+\frac{\Delta}{2}}k_{{}_{B}}^{\Delta/2}}$

and we also know that

$\delta M\,=\,\frac{\delta E}{c^{2}}\;\;.$ (12)

Hence, for $c=1$,

$\delta M\,=\,\frac{k_{{}_{B}}^{\prime}\ln 2}{\Big{(}A_{G}\,+\,\ln
M\Big{)}\,\frac{\delta\Delta}{\delta M}\,+\,\frac{(2+\Delta)}{M}}\;\;.$ (13)

The gravitational radius is given by $R=2GM/c^{2}$, and consequently the
variation of $R$ is $\delta R\,=\,2G(\delta M)/c^{2}$. Substituting these
values into Eq. (13) we have

$\delta R\,=\,\frac{(2G)^{3+\Delta}\ln 2}{(4\pi
G)^{1+\frac{\Delta}{2}}k_{{}_{B}}^{\Delta/2}R^{2+\Delta}\Big{\\{}\Big{[}A_{G}\,+\,\ln\Big{(}\frac{R}{2G}\Big{)}\Big{]}\,\frac{\delta\Delta}{\delta
M}\,+\,\frac{2G(2+\Delta)}{R}\Big{\\}}}\;\;.$ (14)

So, we see clearly that the variation of the radius by an absorption of one-
bit of information, in the case of Barrow model, depends directly on the form
of the $\Delta$-parameter. In the next sections we will analyze the results
for specific values of $\Delta$, considering $\Delta=$constant, and for a
simple form for $\Delta=\Delta(M)$.

##  III The Bekenstein-Hawking and fractal versions of Barrow entropy from a
$\Delta$ variable one

Let us analyze firstly the consequences of adopting a constant value for
$\Delta$. The main values for $\Delta$ are the extremities of the interval
$[0,1]$, we will use these values in Eq. (14) where, for $\Delta=$constant, we
have that $\frac{\delta\Delta}{\delta M}=0$,

$\delta R_{{}_{\Delta}=const.}\,=\,\frac{(2G)^{3+\Delta}\ln 2}{(4\pi
G)^{1+\frac{\Delta}{2}}k_{{}_{B}}^{\Delta/2}R^{1+\Delta}2G(2+\Delta)}$ (15)

and

$T_{{}_{\Delta}=const.}\,=\,\frac{1}{(4\pi
Gk_{{}_{B}})^{1+\frac{\Delta}{2}}(2+\Delta)M^{1+\Delta}}\;\;.$ (16)

Thus, we can also write that

$\displaystyle 4\pi R\,(\delta R)\,=\,\frac{(2G)^{3+\Delta}\ln 2}{2G^{2}(4\pi
Gk_{{}_{B}})^{\frac{\Delta}{2}}(2+\Delta)R^{\Delta}}$
$\displaystyle\Longrightarrow\delta A\,=\,\frac{(2G)^{3+\Delta}\ln
2}{G^{2}(4\pi Gk_{{}_{B}})^{\frac{\Delta}{2}}(2+\Delta)R^{\Delta}}\;\;,$ (17)

where $A$ means the area of the event horizon and the Hawking temperature is
given by

$T_{\Delta=0}\,=\,\frac{1}{8\pi Gk_{{}_{B}}M}\;\;,$

as it is well known in the literature.

For $\Delta=0$, we have, as mentioned before, the Bekenstein-Hawking entropy
and from Eq. (III) we see precisely that the addition of the horizon area due
to the erasing of one-bit of information is

$\delta A_{\Delta=0}\,=\,4\,\ell^{2}_{P}\,\ln 2\;\;,$ (18)

which means that the area correction given by the erasure of one-bit of
information is proportional to the value given by the Landauer principle. But
let us calculate the correction in the case of a fractal perturbation of the
geometry. As mentioned before, $\Delta=1$ represents the maximal fractal
deformation of the BH surface and
$S_{Ba}\,=\,\Big{(}\frac{A}{4G}\Big{)}^{3/2}$. So, in Eq. (10), the
temperature is

$T_{\Delta=1}\,=\,\frac{1}{3\,(4\pi Gk_{{}_{B}})^{3/2}\,M^{3}}$

and the correction in the area of the surface is given by

$\delta A_{\Delta=1}\,=\,\frac{8\ln 2}{3\sqrt{\pi
k_{{}_{B}}}}\frac{\ell^{3}_{P}}{R}\;\;.$ (19)

We see that for a large $R$, the addition in the area approximates to zero,
although from Eq. (18) we see that $\delta A_{\Delta=0}$ is a constant value
independent of $R$. On the other hand, for $R=\frac{\ell_{P}}{3\sqrt{\pi
k_{{}_{B}}}}$ we have that both cases are equal, $\delta A_{\Delta=0}=\delta
A_{\Delta=1}$. In relativistic units $R=\frac{\ell_{P}}{3\sqrt{\pi}}$ and the
addition in both zero deformation and maximal deformation are equal,
independently of the geometry.

This result can indicate a kind of spin degree of freedom (dof) on all surface
components of size $\ell_{P}^{2}$. As we said above, the Landauer theory
landauer  showed that Eq. (1) is the energy in one-bit of information. We
showed precisely that Eq. (III), besides being a kind of spin dof of the
fractal surface of Barrow BH it can be seen also as the increase of its
surface. Hence, we can say that there is a correspondence between both
concepts, the spin dof concept and the Landauer one. The first came form the
holographic principle which means that the Landauer concept can be understood
as the first step to the holographic principle.

##  IV A simple form for $\Delta=\Delta(M)$

It is very important to understand that if the environment presents a
decreasing of entropy, the system entropy must increase in order to no violate
the second law. It is known in the literature as the generalized second law of
thermodynamics of BHs bekenstein .

Since the interval of validity of $\Delta$ is $[0,1]$, let us suggest a simple
form for $\Delta=\Delta(M)$, namely,

$\Delta\,=\,a\,e^{-bM}\;\;,$ (20)

where $a$ and $b$ are real positive definite numbers and the interval of
validity of $a$ is given by

$\\{a\in\mathbb{R}_{+}/0\leq ae^{-bM}\leq 1\\}\;\;,$ (21)

which is dependent of the value of $M$. But the ratio $a/e^{bM}$ must obey the
same restriction as the $\Delta$-parameter obeys. Hence,

$\frac{\delta\Delta}{\delta M}\,=\,-\,abMe^{-bM}$ (22)

which shows a decreasing entropy behavior from Eq. (8) and an increasing
temperature as shown in Eq. (10). The $a=0$ is equivalent to the
$\Delta=$constant case and $0\leq a\leq 1$. We can be more specific concerning
the value of $a$ if we analyze Eq. (10) using Eq. (20), so,

$T_{a,b}\,=\,\frac{e^{bM}}{\Big{(}4\pi
Gk_{{}_{B}}\Big{)}^{1+\frac{\Delta}{2}}\,M^{1+\Delta}\Big{[}2e^{bM}\,+\,a\,-\,abM\Big{(}A_{G}\,+\,\ln
M\Big{)}\Big{]}}$ (23)

and for $\Delta=0$ ($a=0$) in Eq. (20), hence

$T_{{}_{a=0,b}}\,=\,\frac{1}{8\pi Gk_{{}_{B}}M}\;\;,$ (24)

the Hawking temperature, as mentioned before. For $\Delta=1$ which means that
$a=1$ and $b=0$ in Eq. (20) we have that

$T_{{}_{a=1,b=0}}\,=\,\frac{1}{3\Big{(}4\pi
Gk_{{}_{B}}\Big{)}^{3/2}\,M^{2}}\;\;,$ (25)

which shows a temperature of the event horizon for a maximal fractal
deformation of the horizon surface. Consequently, for the increasing in the
area of the BH using both Eqs. (20) and (22) we have that

$\delta A_{a,b}\,=\,\frac{2(2G)^{3+\Delta}e^{bM}\,\ln 2}{G(4\pi
Gk_{{}_{B}})^{\frac{\Delta}{2}}R^{\Delta}\Big{\\{}2G(2e^{bM}+a)\,-\,abR\Big{[}A_{G}\,+\,\ln\Big{(}\frac{R}{2G}\Big{)}\Big{]}\Big{\\}}}$
(26)

and it is direct to see that for $\Delta=0$ ($a=0$), we obtain Eq. (18) and
for $\Delta=1$ ($a=1,b=0$), we have Eq. (19).

Back to the value of $a$ and $b$, let us, for example, analyze Eq. (22). Since
the temperature is measured in Kevin units, the temperature is positive
definite and hence both parameters are connected by the relation

$\displaystyle 2e^{bM}\,+\,a>abM\Big{(}A_{G}\,+\,\ln M\Big{)}$

which means finally that, since $a$ is positive definite,

$0\leq a<\frac{2e^{bM}}{bM\Big{(}A_{G}+\ln M\Big{)}\,-\,1}\;\;,$ (27)

since $a$ is also positive definite and $b\in\mathbb{R}_{+}$. The more
specific condition in Eq. (27) complements the general conditions for $a$
given before in Eq. (21). Notice that in Eq. (22) the condition on $a$ is
directly connected to $b$. In Eq. (28) we have an isolated condition on $a$
and $b\in\mathbb{R}_{+}$. The same consideration can be written for $\Delta=1$
since the denominators in Eqs. (22)-(24), concerning $a$, are all the same.

##  V Conclusions, discussions and perspectives

As shown in thooft  the result in Eq. (19) can indicate a kind of spin degree
of freedom (dof) on all surface components of size $\ell_{P}^{2}$. As we said
above, the Landauer theory landauer  showed that Eq. (1) is the energy erasure
of one-bit of information when inside a BH. We showed precisely that Eq.
(III), besides of being a kind of spin dof of the fractal surface of Barrow BH
it can be seen also as the increase of the area of its surface. Hence, we can
say that there is a correspondence between both concepts, the spin dof and the
Landauer one. The first came form the holographic principle which means that
the Landauer concept can be understood as the first step to the holographic
principle.

Moreover, for $\Delta=0$, which recover the Bekenstein-Hawking entropy, as
shown in the basics of Barrow model, this is obviously the increasing in the
horizon area due one-bit of information shown in Eq. (19). On the other hand,
for $\Delta=1$, in Eq. (20), it clearly keeps the area dimensions for
$k_{{}_{B}}=1$, we see that the increasing of Barrow horizon area in its
maximal deformation is inversely dependent of $R$ which means that for large
$R$ the increasing of the area goes to zero. It is a completely different
situation from the $\Delta=0$ case, which is constant.

To sum up, the increasing in the area due to the erasure of one-bit of
information happens in both cases, but for $\Delta=0$ it is constant although
for $\Delta=1$ it depends on the radius of BH.

Considering $\Delta=\Delta(M)$, we suggested an exponential form for
$\Delta=\Delta(M)$, there are two parameters in this exponential form. We
computed the temperature and the area increasing concerning theses parameters
and we established the validity values for both in an independent way. This
exponential form. in the case of a decreasing one that we have chosen here,
showed also a decreasing behavior of the temperature. However, given that the
temperature is positive definite, it helped us to establish the interval of
validity of one of the parameters, as explained just above. We did not
consider Shannon entropy, which is a negative one, as it is the fundamental
entropy formulation for the information theory.

## References

  * (1) F. A. Bais and J. D. Farmer, “The physics of information,” arXiv: 0708.2837.
  * (2) R. Landauer, IBM J. Res. Dev. 5 (1961) 183; “Information is Physical,” Phys. Today 44 (1991) 23.
  * (3) L. Brilloin, J. Appl. Phys. 24 (1953) 1152; “Scientific uncertainty and iformation,” Academic Press, New York USA, 1964; “Science and information theory,” Academic Press, New York NY, USA, 1962; L. B. Kish, C. G. Granvist, “Energy requirement of control: comments on Szilards’s engine and Maxwell’s demon, arXiv: 1110.0197; L. B. Kish, Proc. IEEE 151 (2004) 190.
  * (4) R. Landauer, Phys. Lett. A 217 (1961) 1888.
  * (5) S. Lloyd Phys. Rev. A 56 (1997) 3374;
  * (6) D. Janzing, P. Wocjan, R. Zein, R. Geiss and T. Beth, Int. J. Theor. Phys. 39 (2000) 2717,
  * (7) H.-G. Kim, J.-W. Lee and J. Lee, Mod. Phys. Lett. A 25 (2010) 1581.
  * (8) J. Barrow, Phys. Lett. B 808 (2020) 135643, arXiv: 2004.09444.
  * (9) E. M. C. Abreu, J. Ananias Neto and E. M. Barboza, Europhysics Lett. 130 (2020) 40005, arXiv: 2005.11609 [gr-qc]; E. M. C. Abreu and J. Ananias Neto, Phys. Lett. B 807 (2020) 135602. E. M. C. Abreu and J. Ananias Neto, Europhysics Lett. 137 (2022) 49002; E. M.C. Abreu and J. Ananias Neto, Phys. Lett. B 810 (2020) 135805, arXiv: 2009.10133 E. M. C. Abreu and J. Ananias Neto, Eur. Phys. J. C 80 (2020) 776;
  * (10) J. D. Barrow, S. Basilakos and E. N. Saridakis, “Big Bang Nucleosynthesis constraints on Barrow entropy,” arXiv: 2010.00986 [gr-qc];
E. N. Saridakis, JCAP 07 (2020) 031, arXiv: 2006.01105;
F. K. Anagnostopoulos, S. Basilakos and E. N. Saridakis, Eur. Phys. J. C 80
(2020) 826;
E. N. Saridakis and S. Basilakos, “The generalized second law of
thermodynamics with Barrow entropy,” arXiv: 2005.08258;
E. N. Saridakis, Phys. Rev. D 102 (2020) 123525. arXiv: 2005.04115 [gr-qc].

  * (11) J. D. Bekenstein, Phys. Rev. D 7 (1973) 2333; Phys. Rev. D 9 (1974) 3292.
  * (12) S. W. Hawking, Commun. Math. Phys. 43 (1975) 199; Phys. Rev. Lett. 26 (1971) 1344.
  * (13) S. Basilakos, A. Lymperis, M. Petronikolou and E. N. Saridakis, “ Barrow holographic dark energy with varying exponent,” arXiv: 2312.15767 [gr-qc]
  * (14) S. Maity and P. Rudra, JHAP 2 (2022) 1, arXiv: 2202.08160.
  * (15) G. ’t Hooft, “The Holographic Principle,” hep-th/0003004.