# Optimal Locating-Paired-Dominating Sets in King Grids

Yuxuan Yang  Department of Science, Beijing University of Posts and
Telecommunications, Beijing, China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we continue the study of locating-paired-dominating set,
abbreviated LPDS, in graphs introduced by McCoy and Henning. Given a finite or
infinite graph $G=(V,E)$, a set $S\subset V$ is paired-dominating if the
induced subgraph $G[S]$ has a perfect matching and every vertex in $V$ is
adjacent to a vertex in $S$. The other condition for LPDS requires that for
any distinct vertices $u,v\in V\backslash S$, we have $N(u)\cap S\neq N(v)\cap
S$. Motivated by the conjecture of Kinawi, Hussain and Niepel, we prove the
minimal density of LPDS in the king grid is between $8/37$ and $2/9$, and we
find uncountable many different LPDS with density $2/9$ in the king grid.
These results partially solve their conjecture.

###### Key words and phrases:

locating-paired-dominating sets, king grids, domination, discharge method

###### 2010 Mathematics Subject Classification:

05C69

##  1\. Introduction

The concept of locating-paired-dominating sets was introduced by McCoy and
Henning [8] as an extension of paired-dominating sets [3, 4]. The problem of
locating monitoring devices in a system when every monitor is paired with a
backup monitor serves as the motivation for this concept.

Here are some basic definitions and notations. Let $G=(V,E)$ be an undirected
graph. For a subset $S\subset V$, $G[S]$ is a subgraph of $G$ induced by $S$.
For a vertex $v$ in $G$, the set $N_{G}(v)=\\{u\in V|uv\in E\\}$ is called the
open neighborhood of $v$ and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ is the closed
neighborhood of $v$. We may use $N(v)$ and $N[v]$ for short if there is no
ambiguity of the base graph $G$. And a set $S$ of vertices is called
dominating set of $G$ if for any $v\in V$, $N[v]\cap S\neq\emptyset$. A
dominating set is called locating-dominating set if for any pair of distinct
vertices $v,u\in V\setminus S$, $N[u]\cap S\neq N[v]\cap S$. A set $M$ of
edges is called matching if they do not share vertices for each two. A
matching $M$ is a perfect matching if every vertex is incident to an edge of
$M$. A paired-dominating set of $G$ is a dominating set $S$ whose induced
subgraph $G[S]$ contains a perfect matching (not necessarily induced). The set
$S$ is said to be a locating-paired-dominating set, abbreviated LPDS, if $S$
is both a paired-dominating set and a locating-dominating set.

It is optimal to make the size of the dominating set as small as possible. The
problem of finding an optimal locating-dominating set in an arbitrary graph is
known to be NP-complete [1]. Particular interest was dedicated to infinite
grids as many processor networks have a grid topology [2] [5] [6] [10]. There
was also the corresponding study for LPDS. For instance, LPDS in infinite
square grids was discussed in [9], and LPDS in infinite triangular and king
grids was discussed in [7]. Especially, Hussain, Niepel, and Kinawi guessed
the density of an optimal LPDS in the king grid is equal to $2/9$ in [7], and
they proved this number is between $3/14$ and $2/9$. Our results partially
solve this conjecture. For example, we use the Discharge Method to improve the
lower bound to $8/37$. See Section 3 for other main results.

##  2\. preliminaries

In this section, we list several notations and backgrounds for this paper.
Some of them come from [7].

######  Definition (king grid).

An infinite graph $G=(V,E)$ is called king grid, where $V=Z\times Z$. Two
vertices are adjacent if and only if their Euclidean distance is less or equal
to $\sqrt{2}$.

Each vertex $v$ in the king grid has $8$ neighbors, and four of its neighbors
are with Euclidean distance $\sqrt{2}$ from $v$. We call them
$\sqrt{2}$-neighbors of $v$. If two $\sqrt{2}$-neighbors of $v$ have distance
$2\sqrt{2}$, we call them in the opposite position of each other. The distance
of two vertices $u,v$ of a graph is the number of the edges in the shortest
path connecting $u$ and $v$, which is denoted by $d(u,v)$.

######  Definition (k-neighborhood).

The k-neighborhood of vertex $u$ in graph $G$ is defined as
$N_{G}^{k}[u]=\\{x\in V(G)|d(u,x)\leq k\\}$.

To avoid unnecessary complexity, in this paper when we consider infinite
graphs, we always assume there is a universal upper bound $M\in\mathbb{Z}_{+}$
of the degree, which means for all $v\in V$, $|N_{G}(v)|\leqslant M$. The king
grid satisfies this condition for sure.

######  Definition (density).

Given a graph $G=(V,E)$, which can be finite or infinite, and a set $S\subset
V$, the density of $S$ in $G$ is defined as

$D(S)=\limsup_{k\rightarrow\infty}\frac{|S\cap
N_{G}^{k}[u]|}{|N_{G}^{k}[u]|},$ (2.1)

where $u$ is a vertex of G.

Note that the density $D(S)$ is independent of the choice of the vertex $u$.

Hussain, Niepel, and Kinawi have proved the following result for the density
of an optimal LPDS in the king grid [7]. Here, the term “optimal” means the
LPDS has minimal density.

######  Theorem A.

If $S$ is an optimal LPDS in the king grid and $D(S)$ is the density of $S$,
then we have $3/14\leqslant D(S)\leqslant 2/9$.

Also, they gave a conjecture for this density [7].

######  Conjecture A.

If $S$ is an optimal LPDS in the king grid and $D(S)$ is the density of $S$,
then we have $D(S)=2/9$.

In this paper, we always assume $G=(V,E)$ is the king grid and $S$ is a LPDS
of $G$. For convenience, we use the following notations. Fix an arbitrary
perfect matching $M$ on the induced subgraph $G[S]$. Denote

$m:S\rightarrow S$ (2.2)

to be a map that sends each vertex to its partner in $M$. In other words, we
have $N_{M}(v)=\\{m(v)\\}$. Because of the lack of edge-transitivity in the
king grids, we have two different types of pairs in $M$. We define

$\displaystyle S_{1}:=\\{v\in S|\lvert N(v)\cap N(m(v))\rvert=2\\},$ (2.3)
$\displaystyle S_{2}:=\\{v\in S|\lvert N(v)\cap N(m(v))\rvert=4\\}.$

Remark that each pair in $S_{1}$ has Euclidean distance $\sqrt{2}$ and each
pair in $S_{2}$ has Euclidean distance $1$, so we call them far pairs and
close pairs, respectively. It’s trivial to find $S=S_{1}\cup S_{2}$ and
$S_{1}\cap S_{2}=\emptyset$.

##  3\. main results

Suppose $S$ is a LPDS of the king grid $G$, under the notation (2.3) in the
last section we have the following observation for the density of $S_{1}$ and
$S_{2}$.

######  Theorem 1.

Suppose $S_{1}$ and $S_{2}$ have density $D(S_{1})$ and $D(S_{2})$ in $G$,
then

$\frac{14}{3}D(S_{1})+\frac{9}{2}D(S_{2})\geqslant 1.$ (3.1)

######  Theorem 2.

Suppose $S_{1}$ and $S_{2}$ have density $D(S_{1})$ and $D(S_{2})$ in $G$,
then

$\frac{9}{2}D(S_{1})+5D(S_{2})\geqslant 1.$ (3.2)

Remark that Theorem 1 has almost been indicated in [7], in which the idea
called “share” was used. We prove both Theorem 1 and Theorem 2 by using
Discharge Method. The latter one is the main work of this paper.

From these two theorems, we can easily improve the lower bound in Theorem A.

######  Corollary 1.

The density of an optimal LPDS in the king grid is at least 8/37.

###### Proof.

Suppose $S$ is a LPDS in $G$, then we have

$\displaystyle D(S)$ $\displaystyle=D(S_{1})+D(S_{2})$
$\displaystyle=\frac{3[\frac{14}{3}D(S_{1})+\frac{9}{2}D(S_{2})]+[\frac{9}{2}D(S_{1})+5D(S_{2})]}{37/2}$
$\displaystyle\geqslant\frac{3+1}{37/2}$ $\displaystyle=\frac{8}{37}.$

∎

Moreover, if we have a counterexample for Conjecture A, the fair pairs and
close pairs must both have positive density.

######  Corollary 2.

Suppose $S$ is a LPDS in $G$ and $D(S)<2/9$, then $D(S_{1})>0$ and
$D(S_{2})>0$.

###### Proof.

$\displaystyle 1$
$\displaystyle\leqslant\frac{14}{3}D(S_{1})+\frac{9}{2}D(S_{2})$
$\displaystyle=\frac{14}{3}D(S_{1})+\frac{9}{2}(D(S)-D(S_{1}))$
$\displaystyle=\frac{9}{2}D(S)+\frac{1}{6}D(S_{1})$
$\displaystyle<\frac{9}{2}\cdot\frac{2}{9}+\frac{1}{6}D(S_{1}).$
$\displaystyle 1$ $\displaystyle\leqslant\frac{9}{2}D(S_{1})+5D(S_{2})$
$\displaystyle=\frac{9}{2}(D(S)-D(S_{2}))+5D(S_{2})$
$\displaystyle=\frac{9}{2}D(S)+\frac{1}{2}D(S_{2})$
$\displaystyle<\frac{9}{2}\cdot\frac{2}{9}+\frac{1}{2}D(S_{2}).$

∎

In other words, a LPDS in the king grid has density at least $9/2$, if the
pairs in this LPDS are either all far pairs or all close pairs.

All the results above are for the lower bound of the density of an optimal
LPDS in the king grid. For the upper bound, after a lot of attempts, we
believe that Conjecture A is true, which means the upper bound cannot be
improved. However, we find the LPDS with density 2/9 given by Hussain, Niepel,
and Kinawi [7] is not the only pattern.

######  Theorem 3.

There are uncountable many different LPDS with density 2/9 in the king grid.

We leave the construction of those patterns in Section 5.

##  4\. Discharge Methods

In this section, we prove Theorems 1 and 2 using Discharge Method. Suppose $S$
is a LPDS of the king grid $G=(V,E)$, we follow the notation (2.3) about
$S_{1},S_{2}$. For each $v\in S$, we define its pendent neighbors and interval
neighbors as

$\displaystyle P(v):=N(v)\backslash N[m(v)],$ (4.1) $\displaystyle
I(v):=N(v)\cap N(m(v)).$

It is trivial to see that when $v\in S_{1}$, we have $\lvert P(v)\rvert=5$ and
$\lvert I(v)\rvert=2$. Also, when $v\in S_{2}$, we have $\lvert P(v)\rvert=3$
and $\lvert I(v)\rvert=4$.

For each $v\in V\backslash S$, we assign it to one of the following sets
according to the size of the set $N(v)\cap S$.

$\displaystyle T_{1}:=\\{v\in V\backslash S|\lvert N(v)\cap S\rvert=1\\},$
(4.2) $\displaystyle T_{2}:=\\{v\in V\backslash S|\lvert N(v)\cap
S\rvert=2\\},$ $\displaystyle T_{3}:=\\{v\in V\backslash S|\lvert N(v)\cap
S\rvert\geqslant 3\\}.$

We have $V=T_{1}\cup T_{2}\cup T_{3}\cup S$, since $S$ is dominating. At
first, we investigate the neighbors for each dominating vertex $v\in S$.

######  Lemma 1.

We have the following observations.

(1) $\forall v\in S,\lvert P(v)\cap T_{1}\rvert\leqslant 1$,

(2) $\forall v\in S,\lvert I(v)\cap T_{2}\rvert\leqslant 1,I(v)\cap
T_{1}=\emptyset$,

(3) $\forall v\in S_{1},\lvert P(v)\cap(T_{3}\cup S)\rvert\geqslant 1$.

###### Proof.

(1) Suppose $v$ is the only neighbor of two vertices in $P(v)\backslash S$,
then it contradicts the locating property for LPDS.

(2) Suppose $v$ and $m(v)$ are the only neighbors of two vertices in
$I(v)\backslash S$, then it contradicts the locating property for LPDS. Also
the vertex in $I(v)$ has at least two neighbors, $v$ and $m(v)$, in $S$.

(3) We assume $P(v)\cap(T_{3}\cup S)=\emptyset$ and $v\in S_{1}$. From the
symmetry, it is safe to assume $v=(0,0)$ and $m(v)=(-1,-1)$. From (1), we know
either $(1,0)$ or $(0,1)$ is not in $T_{1}$. From the symmetry, it is safe to
assume $u=(0,1)$ is not in $T_{1}$. Then $u$ has another neighbor in $S$, say
$v^{\prime}$. It is not hard to find that $N(v)\cap N(v^{\prime})$ has at
least two members. These two members have to be in $T_{2}$, which contradicts
the locating property for LPDS. ∎

Remark that Lemma 1 have been covered by [7].

###### Proof of Theorem 1.

The initial charge $\operatorname{ch}_{0}$ on $G$ is given by

$\displaystyle\forall v\in V\backslash S,\operatorname{ch}_{0}(v)=0,$
$\displaystyle\forall v\in S_{1},\operatorname{ch}_{0}(v)=14/3,$
$\displaystyle\forall v\in S_{2},\operatorname{ch}_{0}(v)=9/2.$

Then we apply the following local discharge rules.

$\displaystyle\forall i\in\\{1,2,3\\},\forall v\in S,\forall u\in T_{i}\cap
N(v),f(v,u)=1/i,$

where $f$ is a function from $V\times V$ to $[0,+\infty)$ and the function
value $f(v,u)$ means the charge that sends from $v$ to $u$. Remark that
$f(v,u)=0$ if it is not mentioned above.

The new charge is given by

$\operatorname{ch}_{1}(v)=\operatorname{ch}_{0}(v)+\sum_{u\in
N(v)}f(u,v)-\sum_{u\in N(v)}f(v,u),\forall v\in V.$

We claim that the new charge is at least one everywhere in the king grid.

######  Claim 1.

Under the discharge rules $f$, for each $v\in V$, we have
$\operatorname{ch}_{1}(v)\geqslant 1$.

###### Proof of Claim 1.

We have $V=T_{1}\cup T_{2}\cup T_{3}\cup S_{1}\cup S_{2}$. For each
$i\in\\{1,2,3\\}$, if $v\in T_{i}$, then $v$ get $1/i$ for each of its at
least $i$ neighbors in $S$, which makes

$\operatorname{ch}_{1}(v)\geqslant 0+i\cdot 1/i=1.$

If $v\in S_{1}$, then from Lemma 1(1),(2),(3), we have

$\displaystyle\operatorname{ch}_{1}(v)$ $\displaystyle=\frac{14}{3}-\sum_{u\in
P(v)}f(v,u)-\sum_{u\in I(v)}f(v,u)$
$\displaystyle\geqslant\frac{14}{3}-(1+\frac{1}{3}+3\cdot\frac{1}{2})-(\frac{1}{2}+\frac{1}{3})$
$\displaystyle=1.$

If $v\in S_{2}$, then from Lemma 1(1),(2), we have

$\displaystyle\operatorname{ch}_{1}(v)$ $\displaystyle=\frac{9}{2}-\sum_{u\in
P(v)}f(v,u)-\sum_{u\in I(v)}f(v,u)$
$\displaystyle\geqslant\frac{9}{2}-(1+2\cdot\frac{1}{2})-(\frac{1}{2}+3\cdot\frac{1}{3})$
$\displaystyle=1.$

∎

Under the definition of density on an infinite graph, it is not hard to find
that the average charge for $\operatorname{ch}_{0}$ is the left side of (3.1)
and the average charge for $\operatorname{ch}_{1}$ is at least 1. The average
charge is fixed under the discharge rule, so Theorem 1 holds. ∎

###### Proof of Theorem 2.

The new initial charge $\operatorname{ch}_{2}$ on $G$ is given by

$\displaystyle\forall v\in V\backslash S,\operatorname{ch}_{2}(v)=0,$
$\displaystyle\forall v\in S_{1},\operatorname{ch}_{2}(v)=9/2,$
$\displaystyle\forall v\in S_{2},\operatorname{ch}_{2}(v)=5.$

Similarly, it suffices to give several local discharge rules to make the
charge at least 1 everywhere. We will manage it in three steps.

$\operatorname{ch}_{2}\xrightarrow{g_{1}}\operatorname{ch}_{3}\xrightarrow{g_{2}}\operatorname{ch}_{4}\xrightarrow{g_{3}}\operatorname{ch}_{5}.$
(4.3)

For convenience, we would like to add more notations before the discharge. We
collect all the interval neighbors as $I$ and define the redundant pendent
neighbors of $v$ denoted by $P_{0}(v)$.

$I:=\cup_{v\in S}I(v),\qquad P_{0}(v):=P(v)\cap(S\cup I).$

The remaining pendent neighbors of $v$ belong to one of the following sets.

$\displaystyle P_{i}(v):=(P(v)\backslash P_{0}(v))\cap T_{i},\quad
i\in\\{1,2,3\\}.$

The size of these sets is denoted by

$p_{i}(v):=|P_{i}(v)|\quad\forall i\in\\{0,1,2,3\\}.$

The members in $I(v)$ which is also in $S$ form the set $I_{0}(v)$ and its
size is denoted by $i_{0}(v)$.

$I_{0}(v):=I(v)\cap S,\quad i_{0}(v)=|I_{0}(v)|.$

Here comes the first-step discharge rule $g_{1}(v,u)$.

$\displaystyle\forall v\in S,\forall u\in I(v)\backslash S,g_{1}(v,u)=1/2,$
$\displaystyle\forall i\in\\{1,2\\},\forall v\in S,\forall u\in
P_{i}(v),g_{1}(v,u)=1/i.$

Under the discharge $g_{1}$, we make sure that the vertices in $S\cup I\cup
T_{1}\cup T_{2}$ have enough charge.

######  Claim 2.

Under the discharge rules $g_{1}$, for each $v\in S\cup I\cup T_{1}\cup
T_{2}$, $\operatorname{ch}_{3}(v)\geqslant 1$.

###### Proof of Claim 2.

For each $u\in I\backslash S$, there exists at least two different
$v_{1},v_{2}\in S$ such that $u\in I(v_{1})$ and $u\in I(v_{2})$, then

$ch_{3}(u)\geqslant 0+2\cdot 1/2=1.$

For each $u\in T_{1}\backslash I$, there exists a unique $v\in S$ such that
$u\in P_{1}(v)$, then $\operatorname{ch}_{3}(u)\geqslant 1$. For each $u\in
T_{2}\backslash I$, there exist two different $v_{1},v_{2}\in S$ such that
$u\in P_{2}(v_{1})$ and $u\in P_{2}(v_{2})$, then
$\operatorname{ch}_{3}(u)\geqslant 1$. For each $v\in S_{1}$, from Lemma
1(1),(2),(3), we have

$\displaystyle\operatorname{ch}_{3}(v)$ $\displaystyle=\frac{9}{2}-\sum_{u\in
P(v)}g_{1}(v,u)-\sum_{u\in I(v)}g_{1}(v,u)$
$\displaystyle\geqslant\frac{9}{2}-(1+3\cdot\frac{1}{2})-(2\cdot\frac{1}{2})$
$\displaystyle=1.$

For each $v\in S_{2}$, from Lemma 1(1),(2), we have

$\displaystyle\operatorname{ch}_{3}(v)$ $\displaystyle=5-\sum_{u\in
P(v)}g_{1}(v,u)-\sum_{u\in I(v)}g_{1}(v,u)$ $\displaystyle\geqslant
5-(1+2\cdot\frac{1}{2})-(4\cdot\frac{1}{2})$ $\displaystyle=1.$

∎

The remaining task for discharge $g_{2}$ and $g_{3}$ is to sends proper charge
to $T_{3}\backslash I=\cup_{v\in S}P_{3}(v)$. We need to make sure the charge
is at least one everywhere on the infinite kind grid.

A natural idea is to send the redundant charge of $S$ to its neighbors
$P_{3}(v)$ uniformly, but we would like to add an upper bound for it manually.
For each $v\in S$, let

$r(v):=\min\\{\frac{\operatorname{ch}_{3}(v)-1}{p_{3}(v)},\frac{1}{2}\\}.$

Note that $r(v)\geqslant 0$ since $\operatorname{ch}_{3}(v)\geqslant 1$ when
$v\in S$. Next, the second-step discharge rule $g_{2}(v,u)$ is given by

$\forall v\in S,\forall u\in P_{3}(v),g_{2}(v,u)=r(v).$ (4.4)

From the discharge rule, its trivial to see that
$\operatorname{ch}_{4}(v)\geqslant 1$ for each $v\in S$. Also, we have the
following observations.

######  Claim 3.

If one of the following conditions holds, then $r(v)=1/2$.

(1) $v\in S_{2}$, (2) $p_{0}(v)+i_{0}(v)\geqslant 1$, (3) $p_{1}(v)=0$.

###### Proof of Claim 3.

If $v\in S_{2}$, from Lemma 1(1) and
$p_{1}(v)+p_{2}(v)+p_{3}(v)\leqslant|P(v)|=3$, we have

$\displaystyle\operatorname{ch}_{3}(v)$ $\displaystyle\geqslant
5-\frac{1}{2}|I(v)\backslash S|-1\cdot p_{1}(v)-\frac{1}{2}p_{2}(v)$
$\displaystyle\geqslant 5-\frac{1}{2}\cdot
4-\frac{1}{2}-\frac{1}{2}(3-p_{3}(v))$ $\displaystyle=1+\frac{1}{2}p_{3}(v),$

which implies $r(v)=1/2$.

If $v\in S_{1}$ and $p_{0}(v)+i_{0}(v)\geqslant 1$, from Lemma 1(1) and

$p_{1}(v)+p_{2}(v)+p_{3}(v)\leqslant|P(v)|-p_{0}(v)\leqslant 5-p_{0}(v),$

we have

$\displaystyle\operatorname{ch}_{3}(v)$
$\displaystyle\geqslant\frac{9}{2}-\frac{1}{2}|I(v)\backslash S|-1\cdot
p_{1}(v)-\frac{1}{2}p_{2}(v)$
$\displaystyle\geqslant\frac{9}{2}-\frac{1}{2}(2-i_{0}(v))-\frac{1}{2}-\frac{1}{2}(5-p_{0}(v)-p_{3}(v))$
$\displaystyle=1+\frac{1}{2}p_{3}(v),$

which implies $r(v)=1/2$.

Similarly, if $v\in S_{1}$ and $p_{1}(v)=0$, then

$\displaystyle\operatorname{ch}_{3}(v)$
$\displaystyle\geqslant\frac{9}{2}-\frac{1}{2}|I(v)\backslash
S|-\frac{1}{2}p_{2}(v)$ $\displaystyle\geqslant\frac{9}{2}-\frac{1}{2}\cdot
2-\frac{1}{2}(5-p_{3}(v))$ $\displaystyle=1+\frac{1}{2}p_{3}(v),$

which implies $r(v)=1/2$. ∎

######  Claim 4.

For each $v\in S$, we have

$\displaystyle r(v)\geqslant\frac{p_{3}(v)-1}{2p_{3}(v)}$

###### Proof of Claim 4.

According to Claim 3, in those cases
$r(v)\geqslant\frac{1}{2}\geqslant\frac{p_{3}(v)-1}{2p_{3}(v)}$. It suffices
to check the case that satisfies $v\in S_{1}$, $p_{0}(v)=0$ and $p_{1}(v)=1$.
From these three conditions and Lemma 1(3), we know that
$5=p_{1}(v)+p_{2}(v)+p_{3}(v)$, $p_{3}(v)\geqslant 1$. Then, we have

$\displaystyle\operatorname{ch}_{3}(v)$
$\displaystyle=\frac{9}{2}-\frac{1}{2}|I(v)\backslash S|-1\cdot
p_{1}(v)-\frac{1}{2}p_{2}(v)$
$\displaystyle\geqslant\frac{9}{2}-\frac{1}{2}\cdot
2-1-\frac{1}{2}(4-p_{3}(v))$
$\displaystyle\geqslant\frac{1}{2}+\frac{1}{2}p_{3}(v),$

which implies the claim. ∎

Note that

$\frac{p_{3}(v)-1}{2p_{3}(v)}=\frac{1}{2}-\frac{1}{2p_{3}(v)}$

is increasing as a function of $p_{3}(v)$, so we can say that $r(v)$ is at
least $\frac{1}{4}$ or $\frac{1}{3}$ when $p_{3}(v)$ is at least $2$ or $3$,
respectively.

######  Claim 5.

Suppose $v_{1}=(a+1,b),v_{2}=(a-1,b)\in S$, then

$r(v_{1})+r(v_{2})\geqslant\frac{1}{2}.$

###### Proof of Claim 5.

Suppose $r(v_{1})+r(v_{2})<\frac{1}{2}$, then from Claim 3, we know that
$v_{1},v_{2}\in S_{1}$ and

$N(v_{i})\cap S=\\{m(v_{i})\\}\quad\mbox{for}\quad i\in\\{1,2\\}.$

It indicates that $m(v_{1})$ is either $(a+2,b+1)$ or $(a+2,b-1)$, so

$u_{1}=(a,b-1),u_{2}=(a,b),u_{3}=(a,b+1)$

are in $P(v_{1})\backslash S$. From Claim 3, we also know $u_{1},u_{2},u_{3}$
are not in $I$. Since $v_{1}$ and $v_{2}$ are in the neighborhood of $u_{j}$
for each $j\in\\{1,2,3\\}$, to locate $u_{1},u_{2}$ and $u_{3}$, at least two
of them has another neighbor in $S$. We conclude that at least two of
$u_{1},u_{2},u_{3}$ are in $T_{3}\backslash I$. That means
$p_{3}(v_{1})\geqslant 2$ and $r(v_{1})\geqslant\frac{1}{4}$. Similarly, we
have $r(v_{2})\geqslant\frac{1}{4}$. Here is a contradiction, since

$r(v_{1})+r(v_{2})\geqslant\frac{1}{4}+\frac{1}{4}=\frac{1}{2}.$

∎

Remark that from the symmetry of the king grid, this claim also works for the
case when $v_{1}=(a,b+1),v_{2}=(a,b-1)$.

Now, we are ready to investigate the charge $\operatorname{ch}_{4}$ on
$T_{3}\backslash I$. Suppose $u_{0}=(a,b)\in T_{3}\backslash I$, then it has
at least 3 neighbors in $S$, and for each $v\in S\cap N(u_{0})$, we have
$u_{0}\in P_{3}(v)$. We separate it into three cases to check if
$\operatorname{ch}_{4}(u_{0})\geqslant 1$. Because of the symmetry of the king
grid, each $u_{0}\in T_{3}\backslash I$ is symmetric to one of these three
cases.

######  Case 1.

$N(u_{0})\cap S$ is not an independent set in the king grid $G$.

Suppose $v_{1},v_{2}$ are adjacent and $v_{1},v_{2}\in S\cap N(u_{0})$, then
since $u_{0}\notin I$, $v_{1},v_{2}$ are not partner of each other. $v_{1}$ is
in either $I_{0}(v_{2})$ or $P_{0}(v_{2})$. From Claim 3, we know that
$r(v_{2})=1/2$. Similarly, we have $r(v_{1})=1/2$. Therefore, we can say

$\operatorname{ch}_{4}(u_{0})\geqslant
g_{2}(v_{1},u_{0})+g_{2}(v_{2},u_{0})=r(v_{2})+r(v_{1})=1.$

######  Case 2.

$N(u_{0})\cap S$ is an independent set in the king grid $G$ and
$v_{1}=(a+1,b+1),v_{2}=(a+1,b-1),v_{3}=(a-1,b+1)\in N(u_{0})\cap S$. See
Figure 1.

Remark that in Case 2, the vertex $(a-1,b-1)$ can either be in $S$ or not.

Figure 1. Case 2 of the vertex $u_{0}$ in $T_{3}\backslash I$

######  Claim 6.

In Case 2, we have $\operatorname{ch}_{4}(u_{0})\geqslant 1$.

###### Proof of Claim 6.

Suppose $\operatorname{ch}_{4}(u_{0})<1$, then

$r(v_{1})+r(v_{2})+r(v_{3})\leqslant ch_{4}(u_{0})<1.$

From Claim 5, we have $r(v_{1})+r(v_{2})\geqslant\frac{1}{2}$ and
$r(v_{1})+r(v_{3})\geqslant\frac{1}{2}$. Then, we know $r(v_{2})<\frac{1}{2}$
and $r(v_{3})<\frac{1}{2}$, which means they violate the conditions for Claim
3. This makes sure

$m(v_{1})\notin\\{(a,b+2),(a+2,b)\\},$

which means either $m(v_{1})\in\\{(a+1,b+2),(a+2,b+1)\\}$ or
$m(v_{1})=(a+2,b+2)$. The former one gives $v_{1}\in S_{2}$ and the latter one
gives $p_{1}(v_{1})\leqslant|T_{1}\cap P(v_{1})|=0$. The conclusion is
$r(v_{1})=\frac{1}{2}$.

Let’s move back to $v_{2}$. Since $r(v_{2})<\frac{1}{2}$, we know
$p_{0}(v_{2})=0,p_{1}(v_{2})=1$ and $v_{2}\in S_{1}$. Either
$m(v_{2})\in\\{(a+2,b-2),(a,b-2)\\}$ or $m(v_{2})=(a+2,b)$. If
$m(v_{2})\in\\{(a+2,b-2),(a,b-2)\\}$, then $(a+2,b)$ is not in $S$. Consider

$U=\\{(a,b),(a+1,b),(a+2,b)\\}.$

Since $U$ is in the neighborhood of both $v_{1}$ and $v_{2}$, to locate these
three vertices in $U$, at least two of them are in $T_{3}$. Therefore, we have
$p_{3}(v_{2})\geqslant 2$ in this case. For the other case $m(v_{2})=(a+2,b)$,
we can say

$\\{(a,b),(a,b-1),(a,b-2),(a+1,b-2),(a+2,b-2)\\}=P_{1}(v_{2})\cup
P_{2}(v_{2})\cup P_{3}(v_{2}).$

We claim that we also have $p_{3}(v_{2})\geqslant 2$ in this case. If not,
then $P_{3}(v_{2})=\\{(a,b)\\}$ and

$\\{(a,b-1),(a,b-2),(a+1,b-2),(a+2,b-2)\\}=P_{1}(v_{2})\cup P_{2}(v_{2}).$

When $P_{1}(v_{2})=\\{(a,b-1)\\}$, $(a,b-2),(a+1,b-2)$ and $(a+2,b-2)$ are all
in $P_{2}(v_{2})$. That means there are three distinct vertices
$v_{4},v_{5},v_{6}$ in $S$ such that

$\displaystyle\\{v_{4},v_{2}\\}=N((a,b-2))\cap S,$
$\displaystyle\\{v_{5},v_{2}\\}=N((a+1,b-2))\cap S,$
$\displaystyle\\{v_{6},v_{2}\\}=N((a+2,b-2))\cap S.$

However, this is impossible since the first and the last one cover the middle
one for those locations that can be in $S$.

When $P_{1}(v_{2})\neq\\{(a,b-1)\\}$, we have $(a,b-1)\in P_{2}(v_{2})$. The
other neighbor of $(a,b-1)$ in $S$ is either $(a-1,b-1)$ or $(a-1,b-2)$. In
either way, it violates $(a,b-2)\in P_{2}(v_{2})\cup P_{1}(v_{2})$, since

$N((a,b-2))\cap S\neq N((a,b-1))\cap S.$

The claim $p_{3}(v_{2})\geqslant 2$ has been proved by contradiction. Then, in
both cases, we have shown $p_{3}(v_{2})\geqslant 2$, which means
$r(v_{2})\geqslant\frac{1}{4}$ by Claim 4.

Similarly, we have the same argument that says $r(v_{3})\geqslant\frac{1}{4}$.
We conclude that

$\operatorname{ch}_{4}(u_{0})\geqslant
r(v_{1})+r(v_{2})+r(v_{3})\geqslant\frac{1}{2}+\frac{1}{4}+\frac{1}{4}=1.$

∎

######  Case 3.

$N(u_{0})\cap S$ is an independent set in the king grid $G$ and
$v_{1}=(a,b+1),v_{2}=(a+1,b-1),v_{3}=(a-1,b-1)\in N(u_{0})\cap S$. See Figure
2.

Figure 2. Case 3 of the vertex $u_{0}$ in $T_{3}\backslash I$

Firstly, It is easy to find that $\\{v_{1},v_{2},v_{3}\\}=N(u_{0})\cap S$.
This case is rather complicated. For those $u_{0}$ whose charge
$\operatorname{ch}_{4}(u_{0})$ is less than 1, we call them deficient vertices
and we need to find a rich friend for each of them and give the discharge rule
$g_{3}$ between the deficient vertices and their rich friends. Now, we assume
$u_{0}$ is deficient, then

$\operatorname{ch}_{4}(u_{0})=r(v_{1})+r(v_{2})+r(v_{3})<1.$

From Claim 5, we have $r(v_{2})+r(v_{3})\geqslant\frac{1}{2}$, then
$r(v_{1})<\frac{1}{2}$. From Claim 3, we know that

$p_{0}(v_{1})=0,m(v_{1})\in\\{(a-1,b+2),(a+1,b+2)\\}.$

Since $(a+1,b)\notin I$, we know

$m(v_{2})\in\\{(a,b-2),(a+1,b-2),(a+2,b-2)\\}.$

Similarly,

$m(v_{3})\in\\{(a,b-2),(a-1,b-2),(a-2,b-2)\\}.$

There are 9 cases for the positions of $m(v_{2})$ and $m(v_{3})$, but we can
kill one case since $m(v_{2})\neq m(v_{3})$ and kill three other cases by
symmetry, so we only need to consider the following five cases.

######  Case 3.1.

$m(v_{2})=(a+1,b-2),m(v_{3})=(a-1,b-2)$.

In this case, $v_{2},v_{3}\in S_{2}$. From Claim 3, we have
$r(v_{2})+r(v_{3})\geqslant\frac{1}{2}+\frac{1}{2}=1$, which means $u_{0}$ is
not deficient. Contradiction.

######  Case 3.2.

$m(v_{2})=(a+1,b-2),m(v_{3})=(a-2,b-2)$.

In this case, $v_{2}\in S_{2}$ and $(a,b-1)\in I(v_{2})\cap P(v_{3})$. From
Claim 3, we have $r(v_{2})+r(v_{3})\geqslant\frac{1}{2}+\frac{1}{2}=1$, which
means $u_{0}$ is not deficient. Contradiction.

######  Case 3.3.

$m(v_{2})=(a,b-2),m(v_{3})=(a-1,b-2)$.

In this case, $u_{0}$ is possibly deficient. We assign the rich friend
$(a,b-1)$ to it. Let

$g_{3}((a,b-1),u_{0})=1,$ (4.5)

then since $(a,b-1)\in I(v_{2})\cap I(v_{3})$,
$\operatorname{ch}_{4}((a,b-1))\geqslant 2$ makes sure that $(a,b-1)$ and
$u_{0}$ both have charge $\operatorname{ch}_{5}$ at least 1. It is trivial to
check that one vertex cannot be a rich friend of two different $u_{0}$ in this
case by investigating the neighborhood of the rich friend.

######  Case 3.4.

$m(v_{2})=(a,b-2),m(v_{3})=(a-2,b-2)$.

In this case, $u_{0}$ is possibly deficient. When $u_{0}$ is deficient, we
assign the rich friend $v_{3}$ to it. Let

$g_{3}(v_{3},u_{0})=\frac{1}{2}.$ (4.6)

We can see that $(a,b-1)\in I\cap P(v_{3})$ and $(a,b-2)\in S\cap P(v_{3})$.
We have $p_{0}(v_{3})\geqslant 2$, which means

$\displaystyle\operatorname{ch}_{4}(v_{3})$
$\displaystyle\geqslant\frac{9}{2}-2\cdot\frac{1}{2}-p_{1}(v_{3})-\frac{1}{2}p_{3}(v_{3})-\frac{1}{2}p_{3}(v_{3})$
(4.7) $\displaystyle\geqslant 3-\frac{1}{2}(5-p_{0}(v_{3}))$
$\displaystyle=\frac{3}{2}.$

The charge $\operatorname{ch}_{5}$ for this case will be discussed after we
define $g_{3}$ completely. For the discussion later, we would like to
investigate the rich friend in this case now. Consider those four
$\sqrt{2}$-neighbors of the rich friend $v_{3}$. One is a deficient vertex in
Case 3. The opposite vertex of it is the partner $m(v_{3})$ of the rich
friend. A third one is a vertex in $S$.

######  Case 3.5.

$m(v_{2})=(a+2,b-2),m(v_{3})=(a-2,b-2)$.

In this case, $(a,b-2)\in P(v_{2})\cap P(v_{3})$. If $(a,b-2)\in I\cup S$,
then from Claim 3, we have $r(v_{2})+r(v_{3})=1$, which contradicts that
$u_{0}$ is deficient. Also, since $(a,b-1)$ and $(a,b-2)$ are not in $S$ and

$N((a,b-1))\cap S=\\{v_{2},v_{3}\\}\subset N(a,b-2)\cap S,$

to locate them, there exists

$v_{4}\in\\{(a-1,b-3),(a,b-3),(a+1,b-3)\\}\cap S.$ (4.8)

$u_{0}$ is also possibly deficient here. When $u_{0}$ is deficient, we assign
the rich friend $v_{4}$ to it. Let

$g_{3}(v_{4},u_{0})=\frac{1}{2}.$ (4.9)

According to (4.8), we need to consider the following two cases by symmetry.

######  Case 3.5.1.

$v_{4}=(a-1,b-3)$.

One useful fact is that

$m(v_{4})\in\\{(a-2,b-3),(a-2,b-4),(a-1,b-4),(a,b-4)\\},$ (4.10)

since $(a,b-2)\notin I$. Consider those four $\sqrt{2}$-neighbor of the rich
friend $v_{4}$. One vertex $s_{1}$ is in $T_{3}\backslash(I\cup S)$ in Case 2.
Another non-opposite vertex $s_{2}$ is in $S$ and is not the partner
$m(v_{4})$,

Another useful fact is that

$I(s_{2})\cap N(v_{4})=N(s_{2})\cap N(s_{1})\cap N(v_{4}).$ (4.11)

######  Case 3.5.2.

$v_{4}=(a,b-3)$.

One useful fact is that

$m(v_{4})\in\\{(a-1,b-4),(a,b-4),(a+1,b-4)\\}.$ (4.12)

since $(a,b-2)\notin I$. Consider those four $\sqrt{2}$-neighbors of the rich
friend $v_{4}$. Two of them are vertices in $T_{3}\cap I$. They are not in the
opposite position of each other.

Now, we have finished the definition of $g_{3}$, which is given by (4.5),
(4.6) and (4.9). If $\operatorname{ch}_{5}$ is at least $1$ everywhere in the
kind grid. Under the definition of density on an infinite graph, it is not
hard to find that the average charge for $\operatorname{ch}_{2}$ is the left
side of (3.2) and the average charge for $\operatorname{ch}_{5}$ is at least
1. The average charge is fixed under the discharge rule, so Theorem 3.2 holds.
The remaining part of this section is to prove the following claim.

######  Claim 7.

Under the discharge rule $g_{3}$, the charge $\operatorname{ch}_{5}$ is at
least one everywhere.

###### Proof of Claim 7.

We have shown that $\operatorname{ch}_{4}$ is at least 1 for all vertices
except for the deficient vertices in Case 3.3, Case 3.4, and Case 3.5. It
suffices to prove that $\operatorname{ch}_{5}$ is at least one for those
related vertices, which are all deficient vertices and their rich friends. In
Case 3, by Claim 5 we have

$\operatorname{ch}_{4}(u_{0})\geqslant r(v_{2})+r(v_{3})\geqslant\frac{1}{2}.$

From (4.5), (4.6) and (4.9), we know

$\operatorname{ch}_{5}(u_{0})\geqslant ch_{4}(u_{0})+\frac{1}{2}\geqslant 1,$

which means all deficient vertices have charge $\operatorname{ch}_{5}$ at
least one.

The rich friend in Case 3.3 is not in $S$, so it cannot be a rich friend in
any other case at the same time. We have shown its charge is at least one.
Consider other rich friends. For convenience, we call the rich friends in Case
3.4 type A rich friend, call the rich friends in Case 3.5.1 type B rich
friend, and call the rich friends in Case 3.5.2 type C rich friend. We have
given the observations on the four $\sqrt{2}$-neighbors for these three types
of rich friends.

Suppose $v_{0}$ is a rich friend of type A, then the observations about those
three $\sqrt{2}$-neighbors in Case 3.3 prevent $v_{0}$ from being a rich
friend of type B or C and prevent $v_{0}$ from being a rich friend of type A
for two different deficient vertices. It means type A rich friends have charge
$\operatorname{ch}_{5}$ at least one because of (4.7) and (4.6).

Type B rich friend has one $\sqrt{2}$-neighbor in $S$ and one
$\sqrt{2}$-neighbor in $T_{3}\backslash(S\cup I)$. They are not in the
opposite position of each other and the deficient vertex is determined by
these two $\sqrt{2}$-neighbors. Type C rich friend has two
$\sqrt{2}$-neighbors in $I\backslash S$. They are not in the opposite position
of each other and the deficient vertex is determined by these two
$\sqrt{2}$-neighbors. Suppose $v_{0}$ is a rich friend of type B, then it is
in one of the following three cases.

If $v_{0}$ is a rich friend of type B and also a rich friend of type C, then
from the facts (4.10)(4.12), we have no valid position for the partner
$m(v_{0})$, which gives a contradiction.

If $v_{0}$ is a rich friend of type B for deficient vertex $u_{1}^{\prime}$
and $v_{0}$ is also a rich friend of type B for another deficient vertex
$u_{2}^{\prime}$, then from the facts (4.10)(4.11), it is not hard to find
that $v_{0}\in S_{2}$ and $v_{0}$ is not a rich friend for another deficient
vertex different from $u_{1}^{\prime},u_{2}^{\prime}$. Also,

$|S\cap N(v_{0})|\geqslant 3$

indicates $i_{0}(v_{0})+p_{0}(v_{0})\geqslant 2$. Then,

$\displaystyle\operatorname{ch}_{5}(v_{0})$
$\displaystyle\geqslant-g(v_{0},u_{1}^{\prime})-g(v_{0},u_{2}^{\prime})+\operatorname{ch}_{4}(v_{0})$
$\displaystyle\geqslant-1+5-\frac{1}{2}|I(v_{0})\backslash
S|-p_{1}(v_{0})-\frac{1}{2}p_{2}(v_{0})-\frac{1}{2}p_{3}(v_{0})$
$\displaystyle\geqslant
4-\frac{1}{2}(4-i_{0}(v_{0}))-\frac{1}{2}p_{1}(v_{0})-\frac{1}{2}(3-p_{0}(v_{0}))$
$\displaystyle\geqslant 0+\frac{1}{2}(i_{0}(v_{0})+p_{0}(v_{0}))$
$\displaystyle\geqslant 1.$

If $v_{0}$ is only a rich friend of type B for deficient vertex
$u_{1}^{\prime}$ and not a rich friend for another deficient vertex different
from $u_{1}^{\prime}$, then the non-partner $S$ neighbor indicates
$i_{0}(v_{0})+p_{0}(v_{0})\geqslant 1$. Then,

$\displaystyle\operatorname{ch}_{5}(v_{0})$
$\displaystyle\geqslant-g(v_{0},u_{1}^{\prime})+\operatorname{ch}_{4}(v_{0})$
$\displaystyle\geqslant-\frac{1}{2}+5-\frac{1}{2}|I(v_{0})\backslash
S|-p_{1}(v_{0})-\frac{1}{2}p_{2}(v_{0})-\frac{1}{2}p_{3}(v_{0})$
$\displaystyle\geqslant-\frac{1}{2}+5-\frac{1}{2}(4-i_{0}(v_{0}))-\frac{1}{2}p_{1}(v_{0})-\frac{1}{2}(3-p_{0}(v_{0}))$
$\displaystyle\geqslant\frac{1}{2}+\frac{1}{2}(i_{0}(v_{0})+p_{0}(v_{0}))$
$\displaystyle\geqslant 1.$

Now, we have shown any rich friend of type B has charge
$\operatorname{ch}_{5}$ at least one. Suppose $v_{0}$ is a rich friend of type
C, then we have the following two cases remaining.

If $v_{0}$ is a rich friend of type C for deficient vertex $u_{1}^{\prime}$
and $v_{0}$ is also a rich friend of type C for another deficient vertex
$u_{2}^{\prime}$, then from the facts(4.12), we know three of those four
$\sqrt{2}$-neighbors of $v_{0}$ are in $I\backslash S$ and the fourth one is
the partner $m(v_{0})$. Then, $p_{0}(v_{0})\geqslant 3$ and

$\displaystyle\operatorname{ch}_{5}(v_{0})$
$\displaystyle\geqslant-g(v_{0},u_{1}^{\prime})-g(v_{0},u_{2}^{\prime})+\operatorname{ch}_{4}(v_{0})$
$\displaystyle\geqslant-1+\frac{9}{2}-\frac{1}{2}|I(v_{0})\backslash
S|-p_{1}(v_{0})-\frac{1}{2}p_{2}(v_{0})-\frac{1}{2}p_{3}(v_{0})$
$\displaystyle\geqslant-1+\frac{9}{2}-\frac{1}{2}*2-\frac{1}{2}p_{1}(v_{0})-\frac{1}{2}(5-p_{0}(v_{0}))$
$\displaystyle\geqslant-\frac{1}{2}+\frac{1}{2}(p_{0}(v_{0}))$
$\displaystyle\geqslant 1.$

If $v_{0}$ is only a rich friend of type C for deficient vertex
$u_{1}^{\prime}$ and not a rich friend for another deficient vertex different
from $u_{1}^{\prime}$, then the two $\sqrt{2}$-neighbors in $I\backslash S$
and the fact(4.12) indicates $p_{0}(v_{0})\geqslant 2$. Then,

$\displaystyle\operatorname{ch}_{5}(v_{0})$
$\displaystyle\geqslant-g(v_{0},u_{1}^{\prime})+\operatorname{ch}_{4}(v_{0})$
$\displaystyle\geqslant-\frac{1}{2}+\frac{9}{2}-\frac{1}{2}|I(v_{0})\backslash
S|-p_{1}(v_{0})-\frac{1}{2}p_{2}(v_{0})-\frac{1}{2}p_{3}(v_{0})$
$\displaystyle\geqslant-\frac{1}{2}+\frac{9}{2}-\frac{1}{2}*2-\frac{1}{2}p_{1}(v_{0})-\frac{1}{2}(5-p_{0}(v_{0}))$
$\displaystyle\geqslant\frac{1}{2}(p_{0}(v_{0}))$ $\displaystyle\geqslant 1.$

∎

We have shown the charge $\operatorname{ch}_{5}$ is at least one everywhere in
$G$, which finishes the proof of Theorem 2. ∎

##  5\. More LPDS patterns

To give a lower bound of the density of an optimal LPDS on the king grid,
Hussain, Niepel, and Kinawi gave the tiling as shown in Figure 3. To be
specific,

$L_{1}=\\{a+k_{1}(2,1)+k_{2}(-3,3)\in\mathbb{Z}^{2}|a=(0,0)\mbox{ or
}(-1,1),(k_{1},k_{2})\in\mathbb{Z}^{2}\\}.$ (5.1)

Figure 3.  the LPDS $L_{1}$ in the king grid

It is not hard to find that there are only finite many different LPDS obtained
from the symmetric transformation of $L_{1}$.

Let $L_{0}=\\{(0,0),(0,3),(2,2),(3,1),(4,3),(5,0),(7,1),(7,2)\\}$, then a
different LPDS is given by

$L_{2}=\\{a+k_{1}(9,0)+k_{2}(0,4)\in\mathbb{Z}^{2}|a\in
L_{0},(k_{1},k_{2})\in\mathbb{Z}^{2}\\},$ (5.2)

as shown in Figure 4.

Figure 4.  the LPDS $L_{2}$ in the king grid

It is trivial to check that $L_{2}$ is a LPDS of the king grid.

###### Proof of Theorem 3.

For the uncountable set $\\{X|X\subset\mathbb{Z}\\}$, we construct a LPDS

$L_{X}=\\{a+k_{1}(9,0)+k_{2}(0,4)+1_{X}(k_{1})(0,1)|a\in
L_{0},(k_{1},k_{2})\in\mathbb{Z}^{2}\\},$

where $1_{X}(k_{1})=1$ when $k_{1}\in X$ and $1_{X}(k_{1})=0$ when
$k_{1}\notin X$. Remark that $L_{2}$ is just $L_{\emptyset}$.

It is not hard to check that $L_{X}$ is a LPDS with density $\frac{2}{9}$ in
the king grid. Apparently, $X\rightarrow L_{X}$ is injective. ∎

Remark that the cardinality of the automorphism group of the king grid is
countable, so we can also say there are uncountable many non-isomorphic LPDS
in the king grid.

It is interesting to see that $T_{3}\backslash I$ is empty for all the
examples in this section, but, as you can see, $T_{3}\backslash I$ is the main
difficulty in the proof of Theorem 2 in the last section. This fact may be a
hint for future research.

## Acknowledgements

The author would like to thank Mei Lu for introducing related topics and
providing useful comments.

## References

  * [1] I. Charon, O. Hudry and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoretical Computer Science 290 3 (2003) 2109-2120.
  * [2] R. Dantas, and F. Havet and R. M. Sampaio, Minimum density of identifying codes of king grids, Discrete Mathematics 341 10 (2018) 2708-2719
  * [3] T. W. Haynes and P. J. Slater, Paired-domination and the paired-dominatic number, Congressus Numerantium 109 (1995) 65-72.
  * [4] T. W. Haynes and P. J. Slater, Paired-domination in graphs, Networks 32 3 (1998) 199-206.
  * [5] I. Honkala, An optimal locating-dominating set in the infinite triangular grid, Discrete Mathematics 306 21 (2006) 2670-2681.
  * [6] I. Honkala and T. Laihonen, On locating-dominating in infinite grids, European Journal of Combinatorics 27 2 (2006) 218-227.
  * [7] M. Kinawi, Z. Hussain and L. Niepel, Minimal Locating-paired-dominating sets in triangular and king grids, Kuwait Journal of Science 45 3 (2018) 39-45.
  * [8] J. McCoy and M. A. Henning, Locating and paired-dominating sets in graphs, Discrete Applied Mathematics 157 15 (2009) 3268-3280.
  * [9] L. Niepel, Locating-paired-dominating sets in square grids, Discrete Mathematics 338 10 (2015) 1699-1705.
  * [10] P. J. Slater, Fault-tolerant locating-dominating sets, Discrete Mathematics 249 1-3 (2002) 179-189.


# Floquet-engineered chiral-induced spin selectivity

Nguyen Thanh Phuc<EMAIL_ADDRESS>Department of Molecular
Engineering, Graduate School of Engineering, Kyoto University, Kyoto 615-8510,
Japan

###### Abstract

The control of electron spin, which is crucial to the stability of matter,
offers new possibilities for manipulating the properties of molecules and
materials with potential applications in spintronics and chemical reactions.
Recent experiments have demonstrated that the electron transmission through
chiral molecules depends on the electron spin orientation, a phenomenon known
as chiral-induced spin selectivity (CISS). In this study, we show that CISS
can be observed in achiral systems driven by an external circularly polarized
laser field in the framework of Floquet engineering. By using the Floquet
theory for a time-periodically driven system to investigate spin-dependent
electron transport in a two-terminal setup, we demonstrate that the spin
polarization can approach unity if the light intensity is sufficiently strong,
the rate of dephasing is sufficiently small, and the average chemical
potential of the two leads is within an appropriate range of values, which is
narrow because of the high frequency of the laser field. To obtain a wider
range of energies for large spin polarization, a combination of chiral
molecules and light-matter interactions is considered and the spin
polarization of electrons transported through a helical molecule driven by a
laser field is evaluated.

chiral induced spin selectivity, light-matter interaction, Floquet engineering

##  I Introduction

The spin angular momentum is a fundamental characteristic of the electron
which can regulate the properties of atoms, molecules, and materials. In
accordance with their quantum statistics, two electrons occupying the same
orbital must have opposite spins, namely the Pauli exclusive principle. The
exchange energy that determines the energy gap between spin singlet and
triplet states is particularly important for understanding the electronic
configurations and the accompanying magnetic and optical properties of
different atoms and molecules. The recently discovered effect of chiral-
induced spin selectivity (CISS) Ray99  offers a new method for controlling
electron spin in chiral molecules and materials. In CISS, electron spins are
polarized when they are transported through chiral molecules, and the spin
polarization depends on the handedness of the molecule Naaman12 ; Naaman15 ;
Naaman19 . CISS has been extensively studied Medina15 ; Diaz18 ; Geyer19 ;
Michaeli19 ; Fransson19 ; Zollner20 ; Liu21 ; Kato22  and observed in a wide
range of molecules and materials, including DNA, bacteriorhodopsin, helicenes,
and others Xie11 ; Carmeli02 ; Gohler11 ; Mishra13 ; Kettner15 ; Kettner18 ;
Lu19 ; Mishra19 ; Jia20 . Applications of CISS go beyond those in the field of
spintronics Dor17 ; Suda19  as it can be employed for enantiomer selection
Rosenberg15 ; Ghosh18  and promotion of chemical reactions, such as
electrochemical water splitting Mtangi15 ; Mtangi17 . Using an argument based
on Kramer’s degeneracy, it can be shown that the spin polarization in the
linear transport through a single-orbital-per-site and two-terminal chiral
system would vanish unless the time-reversal symmetry is broken Kiselev05 ;
Bardarson08 ; Gutierrez13 ; Utsumi20 . Non-unitary effects, such as dephasing
or leaking, can effectively break the time-reversal symmetry Guo12 ; Guo14 ;
Matityahu13 ; Matityahu16 . However, the effect of dephasing tends to disrupt
the quantum interference across different transport channels, which is
essential to CISS as implicitly indicated by the fact that CISS cannot be
detected in a single-orbital-per-site single-helix model without an electron’s
long-range tunneling Gohler11 ; Mishra13 ; Guo12 ; Guo14 .

It has recently been demonstrated that CISS can be observed in achiral
molecules and materials strongly coupled to a circularly polarized mode of an
optical cavity or waveguide Phuc23 . Here, the optical degree of freedom was
treated quantum mechanically, the light-matter coupling is strong at the
single-photon level, and the quantum fluctuation in the vacuum state of the
optical mode can give rise to CISS in the complete absence of an external
light field. In this study, we consider a conventional setup of light-matter
interaction in which an external laser is applied to an electronic system. The
effect of laser field on electrons is treated classically in terms of a time-
periodic potential, that is in the framework of Floquet engineering Bukov15 ;
Eckardt17 ; Moessner17 ; Oka19 ; Weitenberg21 . It has been proposed and
demonstrated that Floquet engineering can be used to control charge and energy
transports Dakhnovskii95 ; Kohler05 ; Phuc18 ; Phuc19 , manipulate quantum
phase transitions Zenesini09 , generate artificial magnetic fields for charge-
neutral particles Aidelsburger11 ; Struck12 ; Aidelsburger13 ; Miyake13 , and
create topologically nontrivial band structures Oka09 ; Jotzu14 ; McIver19 .
In this study, we show that the spin selectivity can be observed in electron
transport through achiral molecules and materials driven by an external
circularly polarized laser field. Unlike the ordinary CISS in chiral
molecules, the spin polarization under Floquet engineering can be nonzero
without dephasing. This is because the light-matter interaction can
effectively break the time-reversal symmetry in the dynamics of electrons, no
matter if light is treated in a quantum or classical manner. The Floquet
theory is applied to investigate spin-dependent electron transport in a two-
terminal setup Kohler05 . The spin polarization is found to approach unity if
the average chemical potential of the two leads is within an appropriate range
of values, which is narrow because of the high frequency of the laser. Chiral
molecules and light-matter interactions can be combined to produce substantial
spin polarization over a wider energy range. This is demonstrated by
evaluating the spin polarization of the electrons transported through a
helical molecule under the influence of a circularly polarized laser field.
How the spin polarization varies with molecular length, driving frequency and
amplitude, and dephasing rate is investigated.

##  II Floquet-engineered CISS

As an example of achiral systems, we consider spin-dependent electron
transport through a two-dimensional (2D) square lattice (of size $N_{x}\times
N_{y}$ in the $x-y$ plane) in a two-terminal setup, as illustrated in Fig. 1a.
With the potential gradient pointing along the $z$ direction, the Rashba spin-
orbit coupling (SOC) has the following form:
$\hat{H}_{\text{SO}}=\alpha(\hat{\sigma}_{x}\hat{p}_{y}-\hat{\sigma}_{y}\hat{p}_{x})$,
where $\alpha=-(e\hbar/4m_{\text{e}}^{2}c^{2})(\text{d}V/\text{d}z)$, and
$\hat{\boldsymbol{\sigma}}$ and $\hat{\mathbf{p}}$ are the spin Pauli matrices
and momentum operators of electrons, respectively. An external circularly
polarized laser field with the time-dependent vector potential given by
$A_{x}(t)=A_{0}\cos\Omega t$, $A_{y}(t)=A_{0}\sin\Omega t$, and $A_{z}(t)=0$
is applied to the system. Here, $A_{0}$ is the amplitude of the vector
potential. The spatial dependence of the vector potential can be ignored as
the system is typically small compared to the optical wavelength. The
interaction between electrons and the laser field is taken into account in the
lattice model by using Peierls substitution Peierls33 , where the tunneling
amplitude between two sites centered at $\mathbf{r}_{i}$ and $\mathbf{r}_{j}$
is multiplied by a factor
$\exp\left\\{(ie/\hbar)\int_{\mathbf{r}_{i}}^{\mathbf{r}_{j}}\mathbf{A}(t)\cdot\text{d}\mathbf{r}\right\\}$.
Here, the path integral is performed along the line connecting the two sites.
The time-dependent Hamiltonian of the laser-driven electron system is then
given by

$\displaystyle\hat{H}(t)=$
$\displaystyle\sum_{j_{x}=1}^{N_{x}-1}\sum_{j_{y}=1}^{N_{y}}\sum_{s,s^{\prime}}\Big{\\{}\hat{c}_{j_{x}+1,j_{y},s}^{\dagger}\left[t_{x}(t)\delta_{ss^{\prime}}+it_{x}^{\text{SO}}(t)(\sigma_{y})_{ss^{\prime}}\right]$
$\displaystyle\times\hat{c}_{j_{x},j_{y},s^{\prime}}+\text{h.c.}\Big{\\}}+\sum_{j_{x}=1}^{N_{x}}\sum_{j_{y}=1}^{N_{y}-1}\sum_{s,s^{\prime}}\Big{\\{}\hat{c}_{j_{x},j_{y}+1,s}^{\dagger}$
$\displaystyle\times\left[t_{y}(t)\delta_{ss^{\prime}}-it_{y}^{\text{SO}}(t)(\sigma_{x})_{ss^{\prime}}\right]\hat{c}_{j_{x},j_{y},s^{\prime}}+\text{h.c.}\Big{\\}},$
(1)

where

$\displaystyle t_{x}^{(\text{SO})}(t)=$ $\displaystyle
t_{x}^{(\text{SO})}e^{-i\mathcal{A}_{x}\cos\Omega t},$ (2) $\displaystyle
t_{y}^{(\text{SO})}(t)=$ $\displaystyle
t_{y}^{(\text{SO})}e^{-i\mathcal{A}_{y}\sin\Omega t}.$ (3)

Here, $\hat{c}_{j_{x},j_{y},s}$ denotes the annihilation operator of an
electron with spin $s$ at site $(j_{x},j_{y})$; $t_{x,y}$ and
$t_{x,y}^{\text{SO}}$ represent the spin-conserved and SOC-induced tunneling
amplitudes, respectively, which are proportional to
$\langle\psi_{j_{x}+1,j_{y}}|\nabla_{x}|\psi_{j_{x},j_{y}}\rangle$ and
$\langle\psi_{j_{x},j_{y}+1}|\nabla_{y}|\psi_{j_{x},j_{y}}\rangle$
[$\psi_{j_{x},j_{y}}$ is the Wannier wave function at site $(j_{x},j_{y})$];
$\mathcal{A}_{x,y}=eA_{0}d_{x,y}/\hbar=eE_{0}d_{x,y}/\hbar\Omega$ are the
dimensionless driving amplitudes in the $x$ and $y$ directions ($E_{0}$ is the
electric field amplitude, and $d_{x}$ and $d_{y}$ are the lattice constants);
h.c. refers to Hermitian conjugate; without loss of generality, the site
energy is set to zero.

Figure 1: Illustration of the (a) Floquet-engineered CISS in achiral matters
and (b) ordinary CISS in chiral molecules and materials. In panel a, electrons
being transported through an achiral system, such as a square two-dimensional
lattice, are time-periodically driven by a circularly polarized laser field,
whose vector potential rotates in the counter-clockwise direction. The two-
terminal configuration in which the system is connected to a source and a
drain is considered in both panels a and b. The spin polarization is reflected
by the difference in the transmission of electrons with one spin orientation
over the other.

Using the Floquet theory, the average current of electrons with spin
$s=\uparrow,\downarrow$ in the two-terminal setup can be expressed as Kohler05

$\displaystyle I_{s}=$
$\displaystyle\frac{e}{h}\sum_{k=-\infty}^{\infty}\int\text{d}\epsilon\sum_{s^{\prime}=\uparrow,\downarrow}\Big{[}T_{\text{R}s,\text{L}s^{\prime}}^{(k)}(\epsilon)f_{\text{L}}(\epsilon)$
$\displaystyle-$ $\displaystyle
T_{\text{L}s,\text{R}s^{\prime}}^{(k)}(\epsilon)f_{\text{R}}(\epsilon)\Big{]},$
(4)

where $f_{\text{L,R}}(\epsilon)$ are the Fermi-Dirac distribution functions
for electrons in the left and right leads, respectively. The transmission
probability from the left to the right lead for electrons with initial spin
$s^{\prime}$, initial energy $\epsilon$ and final spin $s$, final energy
$\epsilon+k\hbar\Omega$, that is, the probability for a scattering event under
the absorption (emission) of $|k|$ photons if $k>0$ ($k<0$), is given in terms
of the broadening functions $\Gamma_{\text{L,R}}$ and the Fourier components
$G^{(k)}$ of the retarded Green’s function by

$\displaystyle T_{\text{R}s,\text{L}s^{\prime}}^{(k)}(\epsilon)=$
$\displaystyle\Gamma_{\text{R}}(\epsilon+k\hbar\Omega)\Gamma_{\text{L}}(\epsilon)$
$\displaystyle\times\left|\sum_{j_{y},j_{y}^{\prime}=1}^{N_{y}}G_{j_{x}=1,j_{y},s^{\prime};j_{x}^{\prime}=N,j_{y}^{\prime},s}^{(k)}(\epsilon)\right|^{2}.$
(5)

Similarly, the transmission probability for electrons from the right to the
left lead is given by

$\displaystyle T_{\text{L}s,\text{R}s^{\prime}}^{(k)}(\epsilon)=$
$\displaystyle\Gamma_{\text{L}}(\epsilon+k\hbar\Omega)\Gamma_{\text{R}}(\epsilon)$
$\displaystyle\times\left|\sum_{j_{y},j_{y}^{\prime}=1}^{N_{y}}G_{j_{x}=N,j_{y},s^{\prime};j_{x}^{\prime}=1,j_{y}^{\prime},s}^{(k)}(\epsilon)\right|^{2}.$
(6)

The wide-band limit is taken by assuming that the broadening functions are
energy independent: $\Gamma_{\text{R,L}}(\epsilon)\to\Gamma_{\text{R,L}}$. If
a bias voltage $V_{\text{b}}$ is applied, the chemical potentials of the two
leads are given by $\mu_{\text{L,R}}=\bar{\mu}\pm eV_{\text{b}}/2$ where
$\bar{\mu}$ is the average chemical potential. At zero temperature, the Fermi-
Dirac distribution function reduces to the step function, and the differential
conductance $c_{s}\equiv(\text{d}I_{s}/\text{d}V_{\text{b}})_{V_{\text{b}}=0}$
is given by

$\displaystyle
c_{s}=\frac{e^{2}}{2h}\sum_{k=-\infty}^{\infty}\sum_{s^{\prime}=\uparrow,\downarrow}\left[T_{\text{L}s,\text{R}s^{\prime}}^{(k)}(\bar{\mu})+T_{\text{R}s,\text{L}s^{\prime}}^{(k)}(\bar{\mu})\right].$
(7)

The spin polarization is defined by

$\displaystyle
P_{\text{s}}=\frac{c_{\uparrow}-c_{\downarrow}}{c_{\uparrow}+c_{\downarrow}}.$
(8)

The Fourier components of the Green’s function can be expressed in terms of
the Fourier components of the Floquet states as

$\displaystyle
G^{(k)}(\epsilon)=\sum_{\alpha,k^{\prime}}\frac{|u_{\alpha,k^{\prime}+k}\rangle\langle
u_{\alpha,k^{\prime}}^{+}|}{\epsilon-(\epsilon_{\alpha}+k^{\prime}\hbar\Omega-i\hbar\gamma_{\alpha})},$
(9)

where the Fourier components $|u_{\alpha,k}\rangle$ of the Floquet state
$|u_{\alpha}(t)\rangle$ are defined by

$\displaystyle|u_{\alpha}(t)\rangle=$
$\displaystyle\sum_{k}|u_{\alpha,k}\rangle e^{-ik\Omega t},$ (10)
$\displaystyle|\psi_{\alpha}(t)\rangle=$
$\displaystyle\,e^{(-i\epsilon_{\alpha}/\hbar-\gamma_{\alpha})t}|u_{\alpha}(t)\rangle.$
(11)

Here, the state $|\psi_{\alpha}(t)\rangle$ satisfies the time-dependent
Schrodinger equation, from which the Floquet state $|u_{\alpha}(t)\rangle$ is
a solution of the eigenvalue equation in the extended Hilbert space with a
periodic time coordinate

$\displaystyle\left[\hat{H}(t)-i\hat{\Sigma}-i\hbar\frac{\text{d}}{\text{d}t}\right]|u_{\alpha}(t)\rangle=(\epsilon_{\alpha}-i\hbar\gamma_{\alpha})|u_{\alpha}(t)\rangle.$
(12)

The self-energy $\hat{\Sigma}$, which results from the coupling of electrons
to the leads, has the following matrix elements:

$\displaystyle\Sigma_{j_{x},j_{y},s;j_{x}^{\prime},j_{y}^{\prime},s^{\prime}}=\delta_{ss^{\prime}}\left(\frac{\Gamma_{\text{L}}}{2}\delta_{j_{x},1}\delta_{j_{x}^{\prime},1}+\frac{\Gamma_{\text{R}}}{2}\delta_{j_{x},N}\delta_{j_{x}^{\prime},N}\right).$
(13)

Due to the Brillouin zone structure of the Floquet spectrum, it is sufficient
to compute all eigenvalues in the first Brillouin zone
$-\hbar\Omega/2\leq\epsilon_{\alpha}<\hbar\Omega/2$. Since the operator on the
left-hand side of Eq. (12) is non-Hermitian, the eigenvalues
$\epsilon_{\alpha}-i\hbar\gamma_{\alpha}$ are generally complex valued and the
right eigenvectors are not mutually orthogonal. To determine the Green’s
function, it is needed to solve the adjoint Floquet eigenvalue equation

$\displaystyle\left[\hat{H}(t)+i\hat{\Sigma}-i\hbar\frac{\text{d}}{\text{d}t}\right]|u_{\alpha}^{+}(t)\rangle=(\epsilon_{\alpha}+i\hbar\gamma_{\alpha})|u_{\alpha}^{+}(t)\rangle.$
(14)

The Floquet states $|u_{\alpha}(t)\rangle$ together with the adjoint states
$|u_{\alpha}^{+}(t)\rangle$ form at equal times a complete bi-orthogonal
basis:

$\displaystyle\langle u_{\alpha}^{+}(t)|u_{\beta}(t)\rangle=$
$\displaystyle\,\delta_{\alpha\beta},$ (15)
$\displaystyle\sum_{\alpha}|u_{\alpha}(t)\rangle\langle u_{\alpha}^{+}(t)|=$
$\displaystyle\,1.$ (16)

The Floquet eigenvalue equations (12) and (14) can be rewritten in terms of
the Fourier components as

$\displaystyle\sum_{j}\left[\hat{H}_{k-j}-\delta_{jk}(j\Omega\hat{I}+i\hat{\Sigma})\right]|u_{\alpha,j}\rangle=$
$\displaystyle(\epsilon_{\alpha}-i\hbar\gamma_{\alpha})|u_{\alpha,j}\rangle,$
(17)
$\displaystyle\sum_{j}\left[\hat{H}_{k-j}-\delta_{jk}(j\Omega\hat{I}-i\hat{\Sigma})\right]|u_{\alpha,j}^{+}\rangle=$
$\displaystyle(\epsilon_{\alpha}+i\hbar\gamma_{\alpha})|u_{\alpha,j}^{+}\rangle,$
(18)

where $\hat{I}$ is the identity operator in the original Hilbert space, and

$\displaystyle\hat{H}_{m}=\frac{1}{T}\int_{0}^{T}\text{d}t\,e^{im\Omega
t}\hat{H}(t).$ (19)

In the following calculations, the system parameters are set to
$t_{x}=t_{y}=0.1\,\text{eV}$,
$t_{x}^{\text{SO}}=t_{y}^{\text{SO}}=0.012\,\text{eV}$, and
$\Gamma_{\text{L}}=\Gamma_{\text{R}}=1\,\text{eV}$, which are typical orders
of magnitude for electron transport in organic molecules, such as DNA and
proteins Yan02 ; Endres04 ; Senthilkumar05 ; Hawke10 .

The spin polarization is shown in Fig. 2a as a function of the average
chemical potential in the range of $225\,\text{meV}<\bar{\mu}<234\,\text{meV}$
for $N_{x}=30$ and $N_{y}=2$. The driving frequency and dimensionless
amplitudes were set to $\Omega=1\,\text{eV}/\hbar$ and
$\mathcal{A}_{x}=\mathcal{A}_{y}=1$, respectively, and the dephasing was
ignored. It is evident that the spin polarization is non-zero without
dephasing, in contrast to the ordinary CISS in chiral molecules and materials.
This is due to the fact that the light-matter interaction effectively breaks
the time-reversal symmetry in the dynamics of electrons. This can be
understood by considering the high-frequency limit of the Floquet theory,
where $\Omega$ is larger than the other system parameters. In this limit, the
effective Hamiltonian for electrons can be derived using Van Vleck degenerate
perturbation theory Shavitt80 ; Eckardt15 . Up to the first order in
$1/\Omega$, the effective Hamiltonian is given by

$\displaystyle\hat{H}_{\text{eff}}=\hat{H}_{0}+\sum_{m\not=0}\frac{[\hat{H}_{-m},\hat{H}_{m}]}{2m\hbar\Omega}.$
(20)

The spin-dependent effective tunneling amplitude between the $i$th and $j$th
sites then reads

$\displaystyle
t_{i,s;j,s^{\prime}}^{\text{eff}}=t_{i,s;j,s^{\prime}}^{0}+\sum_{m\not=0}\sum_{k\not=i,j}\sum_{s^{\prime\prime}}\frac{t_{i,s;k,s^{\prime\prime}}^{-m}t_{k,s^{\prime\prime},j,s^{\prime}}^{m}}{m\hbar\Omega}.$
(21)

The Fourier components of the effective tunneling amplitudes in the $x$ and
$y$ directions are given by

$\displaystyle t_{x}^{(\text{SO})m}=$
$\displaystyle\frac{1}{T}\int_{0}^{T}\text{d}t\,e^{im\Omega
t}t_{x}^{(\text{SO})}(t)=t_{x}^{(\text{SO})}\mathcal{J}_{m}(\mathcal{A}_{x})(-i)^{m},$
(22) $\displaystyle t_{y}^{(\text{SO})m}=$
$\displaystyle\frac{1}{T}\int_{0}^{T}\text{d}t\,e^{im\Omega
t}t_{y}^{(\text{SO})}(t)=t_{y}^{(\text{SO})}\mathcal{J}_{m}(\mathcal{A}_{y}).$
(23)

Here, $\mathcal{J}_{m}(x)$ is the spherical Bessel function of the first kind.
When $m=1$, for which the denominator on the right-hand side of Eq. (21) is
minimum, Eqs. (22) and (23) show that the effective tunneling amplitude is
proportional to $-i=e^{-i\pi/2}$ and $1$ in the $x$ and $y$ directions,
respectively. As a result, a $\pi/2$ phase emerges in the effective tunneling
of electrons around a triangular closed loop made by the diagonal and two
sides of the square unit cell. Because the time-reversed process would be
associated with a $-\pi/2$ phase, the time-reversal symmetry is effectively
broken. If larger values of $m$ are used in Eq. (21), the emergent phase would
be different from $\pi/2$, but the time-reversal symmetry breaking would
remain unchanged, as justified by the outcome of the spin polarization
computation. As shown in Fig. 2a, $P_{\text{s}}$ changes its sign when the
circular polarization of the laser field is reversed. Moreover, $P_{\text{s}}$
can approach unity if $\bar{\mu}$ is within an appropriate range of values,
which is narrow compared to the ordinary CISS in chiral molecules Guo12 ;
Guo14  because of the high frequency of the laser. Future works will examine
how the width of this energy range for $\bar{\mu}$ changes in achiral systems
other than the 2D square lattice.

Figure 2: Spin polarization $P_{\text{s}}$ of electrons transported through
(a) a square lattice and (b) a helical molecule in a two-terminal setup as a
function of the average chemical potential $\bar{\mu}$ of the two leads. In
both cases, an external circularly polarized laser field with frequency
$\Omega=1\,\text{eV}/\hbar$ and dimensionless amplitude $\mathcal{A}=1$ is
applied (see the text for details). The red and black curves correspond to the
circular polarization in the clockwise and anticlockwise directions,
respectively. Here, the chemical potential is measured relative to the site
energy of electrons.

Chiral molecules can be combined with light-matter interactions to obtain a
wider energy range for large spin polarization. As an example, CISS in a
helical molecule driven by a circularly polarized laser field is considered as
follows. A one-dimensional Hubbard model with a spatially dependent SOC-
induced tunneling amplitude is used to describe the transport of electrons
through a helical molecule Guo14 . The Hamiltonian is given by

$\displaystyle\hat{H}_{\text{SO}}=\sum_{j=1}^{N-1}\sum_{k=1}^{N-j}\sum_{s,s^{\prime}}\left(2it^{\text{SO}}_{k}\cos\varphi_{j,k}^{-}\hat{c}^{\dagger}_{j+k,s}\sigma^{j,k}_{ss^{\prime}}\hat{c}_{j,s^{\prime}}+\text{h.c.}\right),$
(24)

where $N$ is the number of sites, $t^{\text{SO}}_{k}$ represents the tunneling
amplitude over $k$ sites, and
$\sigma^{j,k}=\left(\sigma_{x}\sin\varphi_{j,k}^{+}-\sigma_{y}\cos\varphi_{j,k}^{+}\right)\sin\theta_{k}+\sigma_{z}\cos\theta_{k}$
with $\varphi_{j,k}^{\pm}=(\varphi_{j+k}\pm\varphi_{j})/2$ and
$\varphi_{j}=j\Delta\varphi$. Here, $\Delta\varphi$ denotes the twist angle
between the nearest neighbor sites, and $\theta_{k}$ represents the angle
between the vector connecting $k$-neighbor sites and the $x-y$ plane
orthogonal to the helical axis ($z$ axis). Long-range electron tunneling is
needed for the occurrence of CISS in a single helix, indicating the
significance of quantum interference between different transport pathways
Gohler11 ; Mishra13 . An exponential decay of tunneling amplitude with
distance is assumed. The values of the system parameters were set to be the
same as those for the $\alpha$-helical protein studied in Ref. Guo14 . Peierls
substitution is used to describe the light-matter coupling in the same manner
as above. This guarantees that, even in the presence of a long-range
tunneling, the phase acquired by an electron tunneling around a closed loop is
determined by the magnetic flux piercing through the area circumvented by the
loop. The spin polarization is shown in Fig. 2b as a function of the average
chemical potential for $N=30$. The values of the driving frequency and
dimensionless amplitude $\mathcal{A}=eA_{0}R/\hbar$, where $R$ is the helix
radius, are the same as those in the case of a square lattice. A wider range
of energies is observed for large spin polarization than in the case of a
square lattice.

Figure 3a shows the dependence of the maximum spin polarization (over the
variable average chemical potential) on the driving amplitude and frequency.
It is clearly seen that the spin polarization increases with the driving
amplitude, and $P_{\text{s}}^{\text{max}}$ approaches unity for a
dimensionless amplitude $A\gtrsim 0.3$. In contrast, the maximum spin
polarization is essentially frequency independent over a broad range
$0.5\,\text{eV}\leq\hbar\Omega\leq 5\,\text{eV}$. Figure 3b shows the
dependence of $P_{\text{s}}^{\text{max}}$ on the length of the molecule ($N$
atomic sites). Evidently, the maximum spin polarization increases with $N$ and
$P_{\text{s}}^{\text{max}}$ can be large, even for a relatively short molecule
with $N=10$. Additionally, when the average chemical potential of the leads
deviates from the site energy of the system by an integer multiple of
$\hbar\Omega$, electrons can be transported through the system driven by the
laser field. Physically, the energy disparity is transformed into photons by
light absorption or emission.

Figure 3: Dependence of maximum spin polarization $P_{\text{s}}^{\text{max}}$
of electron transport through a helical molecule driven by an external
circularly polarized laser field on (a) dimensionless driving amplitude
$\mathcal{A}$ and driving frequency $\Omega$ and (b) length of the molecule
(the number of atomic sites $N$) and dephasing rate $\Gamma_{\text{d}}$.

Finally, the dependence of the spin polarization on the rate of dephasing is
examined. Dephasing is the loss of phase and spin memory of electrons due to
inelastic scattering of electrons by lattice or molecular vibrations, namely
phonons. Buttiker’s virtual leads are introduced at each site with broadening
$\Gamma_{\text{d}}$ to simulate the effect of dephasing Datta-book . Because
there are no net currents flowing through the virtual leads, the voltages of
virtual leads can be determined by using the Landauer-Buttiker formula for the
current in the $q$th lead (real or virtual) with spin $s$ at energy
$\epsilon$:
$I_{q,s}(\epsilon)=(e^{2}/h)\sum_{m}T_{q,m,s}(\epsilon)(V_{m}-V_{q})$, where
$V_{q}$ denotes the voltage in the $q$th lead and
$T_{q,m,s}(\epsilon)=\text{Tr}_{s}\left\\{\Gamma^{q}G^{\text{R}}(\epsilon)\Gamma^{m}G^{\text{A}}(\epsilon)\right\\}$
is the transmission coefficient from the $m$th to the $q$th lead. Here,
$\Gamma^{q}$ represents the broadening matrix of the $q$th lead. The
electronic Green’s functions can be obtained from the effective Hamiltonian
for electrons in the high-frequency limit using
$G^{\text{R}}(\epsilon)=[G^{\text{A}}(\epsilon)]^{\dagger}=\left[\epsilon
I-\hat{H}_{\text{eff}}-\sum_{q}\Sigma^{\text{R}}_{q}\right]^{-1}$ with
$\Sigma^{\text{R}}_{q}=-i\Gamma^{q}/2$. The maximum spin polarization is shown
in Fig. 3b as a function of $\Gamma_{\text{d}}$, which is proportional to the
dephasing rate. It is clear that $P_{\text{s}}^{\text{max}}$ rises
monotonically as the rate of dephasing decreases. This is in contrast to the
ordinary CISS in chiral systems not driven by a laser field, where the spin
polarization first rises with the dephasing rate before reaching its maximum
value and then it starts to fall with a further increase in the dephasing
rate. As a result, it is possible to systematically increase the spin
polarization, for instance, by lowering the temperature. For the electron
transport through a molecule at room temperature, where the rate of dephasing
is $\Gamma_{\text{d}}\simeq 5\,\text{meV}$ Guo12 ; Guo14 ,
$P_{\text{s}}^{\text{max}}$ can be as high as 0.83 for $\mathcal{A}=1$.

##  III Conclusion

We have shown that achiral molecules and materials can be used to realize CISS
in two-terminal electron transport provided that the system is driven by an
external circularly polarized laser field and the average chemical potential
of the two leads is within the proper range of values, which is narrow because
of the high frequency of the laser. Because the light-matter interaction can
effectively break the time-reversal symmetry in the dynamics of electrons,
spin polarization is nonzero without dephasing, in contrast to ordinary CISS
in chiral molecules. Chiral molecules can be combined with light-matter
interactions to obtain a wider range of energies for large spin polarization.
For sufficiently strong driving and a slow dephasing rate, which are
achievable in current experiments, the spin polarization can get close to
unity. With potential applications in spintronics and chemical reactions,
Floquet-engineered CISS provides a potent tool for controlling spin dynamics
in a variety of molecules and materials.

###### Acknowledgements.

N. T. P. thanks Pham Quang Trung for fruitful discussion on numerical
calculations. The computations were performed at the Research Center for
Computational Science, Okazaki, Japan.

## References

  * (1) Ray, K; Ananthavel, S. P.; Waldeck, D. H.; Naaman, R. Asymmetric scattering of polarized electrons by organized organic films made of chiral molecules. Science 1999, 283, 814.
  * (2) Naaman, R.; Waldeck, D. H. Chiral-induced spin selectivity effect. J. Phys. Chem. Lett. 2012, 3, 2178–2187.
  * (3) Naaman, R.; Waldeck, D. H. Spintronics and chirality: spin selectivity in electron transport through chiral molecules. Annu. Rev. Phys. Chem. 2015, 66, 263–281.
  * (4) Naaman, R.; Paltiel, Y.; Waldeck, D. H. Chiral molecules and the electron spin. Nat. Rev. Chem. 2019, 3, 250–260.
  * (5) Medina, E.; Gonzalez-Arraga, L. A.; Finkelstein-Shapiro, D.; Berche, B.; Mujica, V. Continuum model for chiral induced spin selectivity in helical molecules. J. Chem. Phys. 2015, 142, 194308.
  * (6) Diaz, E.; Dominguez-Adame, F.; Gutierrez, R.; Cuniberti, G.; Mujica, V. Thermal Decoherence and Disorder Effects on Chiral-Induced Spin Selectivity. J. Phys. Chem. Lett. 2018, 9, 5753–5758.
  * (7) Geyer, M.; Gutierrez, R.; Mujica, V.; Cuniberti, G. Chirality-Induced Spin Selectivity in a Coarse-Grained Tight-Binding Model for Helicene. J. Phys. Chem. C 2019, 123, 27230–27241.
  * (8) Michaeli, K.; Naaman, R. Origin of Spin-Dependent Tunneling Through Chiral Molecules. J. Phys. Chem. C 2019, 123, 17043–17048.
  * (9) Fransson, J. Chirality-Induced Spin Selectivity: The Role of Electron Correlations. J. Phys. Chem. Lett. 2019, 10, 7126–7132.
  * (10) Zollner, M. S.; Varela, S.; Medina, E.; Mujica, V.; Herrmann, C. Insight into the Origin of Chiral-Induced Spin Selectivity from a Symmetry Analysis of Electronic Transmission. J. Chem. Theory Comput. 2020, 16, 2914–2929.
  * (11) Liu, Y.; Xiao, J.; Koo, J.; Yan, B. Chirality-driven topological electronic structure of DNA-like materials. Nat. Mater. 2021, 20, 638–644.
  * (12) Kato, A.; Yamamoto, H. M.; Kishine, J.-i. Chirality-induced spin filtering in pseudo Jahn-Teller molecules. Phys. Rev. B 2022, 105, 195117.
  * (13) Xie, Z.; Markus, T. Z.; Cohen, S. R.; Vager, Z.; Gutierrez, R.; Naaman, R. Spin specific electron conduction through DNA oligomers. Nano Lett. 2011, 11, 4652–4655.
  * (14) Carmeli, I.; Skakalova, V.; Naaman, R.; Vager, Z. Magnetization of chiral monolayers of polypeptide: a possible source of magnetism in some biological membranes. Angew. Chem. Int. Ed. 2002, 41, 761–764.
  * (15) Gohler, B.; Hamelbeck, V.; Markus, T. Z.; Kettner, M.; Hanne, G. F.; Vager, Z.; Naaman, R.; Zacharias, H. Spin selectivity in electron transmission through self-assembled monolayer of double-stranded DNA. Science 2011, 331, 894.
  * (16) Mishra, D.; Markus, T. Z.; Naaman, R.; Kettner, M.; Gohler, B.; Zacharias, H.; Friedman, N.; Sheves, M.; Fontanesi, C. Spin-dependent electron transmission through bacteriorhodopsin embedded in purple membrane. Proc. Natl. Acad. Sci. U.S.A 2013, 110, 14872–14876.
  * (17) Kettner, M.; Gohler, B.; Zacharias, H.; Mishra, D.; Kiran, V.; Naaman, R.; Fontanesi, C.; Waldeck, D. H.; Sek, S.; Pawlowski, J.; Juhaniewicz, J. Spin filtering in electron transport through chiral oligopeptides. J. Phys. Chem. C 2015, 119, 14542–14547.
  * (18) Kettner, M.; EMaslyuk, V. V.; Nurenberg, D.; Seibel, J.; Gutierrez, R.; Cuniberti, G.; Ernst, K.-H.; Zacharias, H. Chirality-dependent electron spin filtering by molecular monolayers of helicenes. J. Phys. Chem. Lett. 2018, 9, 2025–2030.
  * (19) Lu, H.; Wang, J.; Xiao, C.; Pan, X.; Chen, X.; Brunecky, R.; Berry, J. J.; Zhu, K.; Beard, M. C.; Vardeny, Z. V. Spin-dependent charge transport through 2D chiral hybrid lead-iodide perovskites. Sci. Adv. 2019, 5, 0571.
  * (20) Mishra, S.; Pirbadian, S.; Mondal, A. K.; El-Naggar, M. Y.; Naaman, R. Spin-dependent electron transport through bacterial cell surface multiheme electron conduits. J. Am. Chem. Soc. 2019, 141, 19198–19202.
  * (21) Jia, L.; Wang, C.; Zhang, Y.; Yang, L.; Yan, Y. Efficient Spin Selectivity in Self-Assembled Superhelical Conducting Polymer Microfibers. ACS Nano 2020, 14, 6607.
  * (22) Dor, O. B.; Yochelis, S.; Radko, A.; Vankayala, K.; Capua, E.; Capua, A.; Yang, S.-H.; Baczewski, L. T.; Parkin, S. S. P.; Naaman, R.; Paltiel, Y. Magnetization switching in ferromagnets by adsorbed chiral molecules without current or external magnetic field. Nat. Comm. 2017, 8, 1.
  * (23) Suda, M.; Thathong, Y.; Promarak, V.; Kojima, H.; Nakamura, M.; Shiraogawa, T.; Ehara, M.; Yamamoto, H. M. Light-driven molecular switch for reconfigurable spin filters. Nat. Comm. 2019, 10, 2455.
  * (24) Rosenberg, R. A.; Mishra, D.; Naaman, R. Chiral selective chemistry induced by natural selection of spin-polarized electrons. Angew. Chem. Int. Ed. 2015, 127, 7403.
  * (25) Banerjee-Ghosh, K.; Dor, O. B.; Tassinari, F.; Capua, E.; Yochelis, S.; Capua, A.; Yang, S.-H.; Parkin, S. S. P.; Sarkar, S.; Kronik, L.; Baczewski, L. T.; Naaman, R.; Paltiel, Y. Separation of enantiomers by their enantiospecific interaction with achiral magnetic substrates. Science 2018, 360, 1331.
  * (26) Mtangi, W.; Kiran, V.; Fontanesi, C.; Naaman, R. Role of the Electron Spin Polarization in Water Splitting. J. Phys. Chem. Letters 2015, 6, 4916 (2015).
  * (27) Mtangi, W.; Tassinari, EF.; Vankayala, K.; Jentzsch, A. V.; Adelizzi, B.; Palmans, A. R. A.; Fontanesi, C.; Meijer, E. W.; Naaman, R. Control of electrons E spin eliminates hydrogen peroxide formation during water splitting. J. Am. Chem. Soc. 2017, 139, 2794.
  * (28) Kiselev, A. A.; Kim, K. W. Prohibition of equilibrium spin currents in multiterminal ballistic devices. Phys. Rev. B 2005, 71, 153315.
  * (29) Bardarson, J. H. A proof of the Kramers degeneracy of transmission eigenvalues from antisymmetry of the scattering matrix. J. Phys. A: Math. Theor. 2008, 41, 405203.
  * (30) Gutierrez, R.; Diaz, E.; Gaul, C.; EBrumme, T.; Dominguez-Adame, EF.; Cuniberti, G. Modeling Spin Transport in Helical Fields: Derivation of an Effective Low-Dimensional Hamiltonian. J. Phys. Chem. C 2013, 117, 22276.
  * (31) Utsumi, Y.; Entin-Wohlman, O.; Aharony, A. Spin selectivity through time-reversal symmetric helical junctions. Phys. Rev. B 2020, 102, 035445.
  * (32) Guo, A.-M.; Sun, Q.-F. Spin-selective transport of electrons in DNA double helix. Phys. Rev. Lett. 2012, 108, 218102.
  * (33) Guo, A.-M.; Sun, Q.-F. Spin-dependent electron transport in protein-like single-helical molecules. Proc. Natl. Acad. Sci. U.S.A. 2014, 111, 11658.
  * (34) Matityahu, S.; Aharony, A.;Entin-Wohlman, O.; Katsumoto, S. Robustness of spin filtering against current leakage in a Rashba-DresselhausAharonov-Bohm interferometer. Phys. Rev. B 2013, 87, 205438.
  * (35) Matityahu, S.; Utsumi, Y.; Aharony, A.; Entin-Wohlman, O.; Balseiro, C. A. Spin-dependent transport through a chiral molecule in the presence of spin-orbit interaction and nonunitary effects. Phys. Rev. B 2016, 93, 075407.
  * (36) Phuc, N. T. Chiral-induced spin selectivity in photon-coupled achiral matters. J. Phys. Chem. Lett. 2023, 14, 1626–1632.
  * (37) Bukov, M.; D’ Alessio, L.; Polkovnikov, A. Universal high-frequency behavior of periodically driven systems: from dynamical stabilization to Floquet engineering. Adv. Phys. 2015, 64, 139.
  * (38) Eckardt, A. Colloquium: Atomic quantum gases in periodically driven optical lattices. Rev. Mod. Phys. 2017, 89, 011004.
  * (39) Moessner R.; Sondhi, S. L. Equilibration and order in quantum Floquet matter. Nat. Phys. 2017, 13, 424–428.
  * (40) Oka, T.; Kitamura, S. Floquet engineering of quantum materials. Annu. Rev. Condens. Matter Phys. 2019, 10, 387–408.
  * (41) Weitenberg, C.; Simonet, J. Tailoring quantum gases by Floquet engineering. Nat. Phys. 2021, 17, 1342–1348.
  * (42) Dakhnovskii, Y.; Evans, D. G.; Kim, H. J.; Coalson, R. D. The effect of a laser field on electron transfer in metal complexes: Quantum degrees of freedom. J. Chem. Phys. 1995, 103, 5461–5469.
  * (43) Kohler, S.; Lehmann, J.; Hanggi, P. Driven quantum transport on the nanoscale. Phys. Rep. 2005, 406, 379–443.
  * (44) Phuc, N. T.; Ishizaki, A. Control of excitation energy transfer in condensed phase molecular systems by Floquet engineering. J. Phys. Chem. Lett. 2018, 9, 1243.
  * (45) Phuc, N. T.; Ishizaki, A. Control of quantum dynamics of electron transfer in molecular loop structures: Spontaneous breaking of chiral symmetry under strong decoherence. Phys. Rev. B 2019, 99, 064301.
  * (46) Zenesini, A.; Lignier, H.; Ciampini, D.; Morsch, O.; Arimondo, E. Coherent control of dressed matter waves. Phys. Rev. Lett. 2009, 102, 100403.
  * (47) Aidelsburger, M.; Atala, M.; Nascimbene, S.; Trotzky, S.; Chen, Y.-A.; Bloch, I. Experimental realization of strong effective magnetic fields in an optical lattice. Phys. Rev. Lett. 2011, 107, 255301.
  * (48) Struck, J.; Olschlager, C.; Weinberg, M.; Hauke, P.; Simonet, J.; Eckardt, A.; Lewenstein, M.; Sengstock, K.; Windpassinger, P. Tunable gauge potential for neutral and spinless particles in driven optical lattices. Phys. Rev. Lett. 2012, 108, 225304.
  * (49) Aidelsburger, M.; Atala, M.; Lohse, M.; Barreiro, J. T.; Paredes, B.; Bloch, I. Realization of the Hofstadter Hamiltonian with ultracold atoms in optical lattices. Phys. Rev. Lett. 2013, 111, 185301.
  * (50) Miyake, H.; Siviloglou, G. A.; Kennedy, C. J.; Burton, W. C.; Ketterle, W. Realizing the Harper Hamiltonian with laser assisted tunneling in optical lattices. Phys. Rev. Lett. 2013, 111, 185302.
  * (51) Oka, T.; Aoki, H. Photovoltaic Hall effect in graphene. Phys. Rev. B 2009, 79, 081406(R).
  * (52) Jotzu, G.; Messer, M.; Desbuquois, R.; Lebrat, M.; Uehlinger, T.; Greif, D.; Esslinger, T. Experimental realization of the topological Haldane model with ultracold fermions. Nature 2014, 515, 237.
  * (53) McIver, J. W.; Schulte, B.; Stein, F.-U.; Matsuyama, T.; Jotzu, G.; Meier, G.; Cavalleri, A. Light-induced anomalous Hall effect in graphene. Nat. Phys. 2019, 16, 38–41.
  * (54) Peierls, R. Zur theorie des diamagnetismus von leitungselektronen. Z. Phys. 1933, 80, 763.
  * (55) Yan, Y. J.; Zhang, H. Toward the mechanism of long-range charge transfer in DNA: Theories and models. J. Theor. Comput. Chem. 2002, 1, 225.
  * (56) Endres, R. G.; Cox, D. L.; Singh, R. R. P. The quest for high-conductance DNA. Rev. Mod. Phys. 2004, 76, 195.
  * (57) Senthilkumar, K.; Grozema, F. C.; Guerra, C. F.; Bickelhaupt, F. M.; Lewis, F. D.; Berlin, Y. A.; Ratner, M. A.; Siebbeles, L. D. A. Absolute rates of hole transfer in DNA. J. Am. Chem. Soc. 2005, 127, 14894.
  * (58) Hawke, L. G. D.; Kalosakas, G.; Simserides, C. Electronic parameters for charge transfer along DNA. Eur. Phys. J. E 2010, 32, 291.
  * (59) Shavitt, I.; Redmon, L. T. Quasidegenerate perturbation theories: a canonical van Vleck formalism and its relationship to other approaches. J. Chem. Phys. 1980, 73, 5711.
  * (60) Eckardt, A.; Anisimovas, E. High-frequency approximation for periodically driven quantum systems from a Floquet-space perspective. New J. Phys. 2015, 17, 093039.
  * (61) Datta, S. Quantum Transport: Atom to Transistor; Cambridge University Press, New York, USA, 2005.