# Edge Contraction and Forbidden Induced Subgraphs

Hany Ibrahim Peter Tittmann
University of Applied Sciences Mittweida

###### Abstract

Given a family of graphs $\mathcal{H}$, a graph $G$ is $\mathcal{H}$-free if
any subset of $V(G)$ does not induce a subgraph of $G$ that is isomorphic to
any graph in $\mathcal{H}$. We present sufficient and necessary conditions for
a graph $G$ such that $G/e$ is $\mathcal{H}$-free for any edge $e$ in $E(G)$.
Thereafter, we use these conditions to characterize claw-free, $2K_{2}$-free,
$P_{4}$-free, $C_{4}$-free, $C_{5}$-free, split, pseudo-split, and threshold
graphs.

##  1 Introduction

A graph $G$ is an ordered pair $(V(G),E(G))$ where $V(G)$ is a set of vertices
and $E(G)$ is a set of $2$-elements subsets of $V(G)$ called edges. The set of
all graphs is $\mathcal{G}$. The degree of a vertex $v$, denoted by $deg(v)$,
is the number of edges incident to $v$. We denote the maximum degree of a
vertex in a graph $G$ by $\Delta(G)$. We call two vertices adjacent if there
is an edge between them, otherwise, we call them nonadjacent. Moreover, the
set of all vertices adjacent to a vertex $v$ is called the _neighborhood_ of
$v$, which we denote by $N(v)$. On the other hand, the _closed neighborhood_
of $v$, denoted by $N[v]$, is $N(v)\cup\\{v\\}$. Generalizing this to a set of
vertices $S$, the neighborhood of $S$, denoted by $N(S)$, is defined by
$N(S):=\bigcup_{v\in S}N(v)-S$. Similarly the closed neighborhood of $S$,
denoted by $N[S]$, is $N(S)\cup S$. Moreover, for a subset of vertices $S$, we
denote the set of vertices in $S$ that are adjacent to $v$ by $N_{S}(v)$.
Furthermore, we write $v$ is adjacent to $S$ to mean that $S\subseteq N(v)$
and $v$ is adjacent to exactly $S$ to mean that $S=N(v)$.

A set of vertices $S$ is _independent_ if there is no edge between any two
vertices in $S$. We call a set $S$ _dominating_ if $N[S]=V(G)$. A subgraph $H$
of a graph $G$ is a graph where $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$.
An _induced_ graph $G[S]$ for a given set $S\subseteq V$, is a subgraph of $G$
with vertex set $S$ and two vertices in $G[S]$ are adjacent if and only if
they are adjacent in $G$. Two graphs $G,H$ are _isomorphic_ if there is a
bijective mapping $f:V(G)\to V(H)$ where $u,v\in V(G)$ are adjacent if and
only if $f(u),f(v)$ are adjacent in $H$. In this case we call the mapping $f$
an isomorphism. Two graphs that are not isomorphic are called _non-
isomorphic_. In particular, an isomorphism from a graph to itself is called
_automorphism_. Furthermore, two vertices $u,v$ are similar in a graph $G$ if
there is an automorphism that maps $u$ to $v$. The set of all automorphisms of
a graph $G$ forms a group called the automorphism group of $G$, denoted by
_Aut( $G$)_. The complement of a graph $G$, denoted by $\bar{G}$, is a graph
with the same vertex set as $V(G)$ and two vertices in $\bar{G}$ are adjacent
if and only if they are nonadjacent in $G$.

The _independence number_ of a graph $G$, denoted by $\alpha(G)$, is the
largest cardinality of an independent set in $G$. In this thesis, we write
singletons $\\{x\\}$ just as $x$ whenever the meaning is clear from the
context. A vertex $u$ is a _corner dominated_ by $v$ if $N[u]\subseteq N[v]$.
Let $\mathcal{H}$ be a set of graphs. A graph $G$ is called _$\mathcal{H}$
-free_ if there is no induced subgraph of $G$ that is isomorphic to any graph
in $\mathcal{H}$, otherwise, we say $G$ is _$\mathcal{H}$ -exist_.

By _contracting_ the edge between $u$ and $v$, we mean the graph constructed
from $G$ by adding a vertex $w$ with edges from $w$ to the union of the
neighborhoods of $u$ and $v$, followed by removing $u$ and $v$. We denote the
graph obtained from contracting $uv$ by $G/uv$. If $e$ is the edge between $u$
and $v$, then we also denote the graph $G/uv$ by $G/e$. Further, we call $G/e$
a $G$-contraction. Finally, any graph in this paper is simple. For notions not
defined, please consult [3]. Additionally, we divide longer proofs into
smaller claims, and we prove them only if their proofs are not apparent.

For a graph invariant $c$, a graph $G$, and a $G$-contraction $H$, the
question of how $c(G)$ differs from $c(H)$ is investigated for different graph
invariants. For instance, how contracting an edge in a graph affects its
$k$-connectivity. Hence, the intensively investigated ([18]) notion of _$k$
-contractible_ edges in a $k$-connected graph $G$ is defined as the edge whose
contraction yields a $k$-connected graph. Another example is in the game Cops
and Robber where a policeman and a robber are placed on two vertices of a
graph in which they take turns to move to a neighboring vertex. For any graph
$G$, if the policeman can always end in the same vertex as the robber, we call
$G$ _cop-win_. However, $G$ is _$CECC$_ if it is not cop-win, but any
$G$-contraction is cop-win. The characteristics of a $CECC$ graph are studied
in [6].

A further example is the investigation of the so-called _contraction critical_
, with respect to independence number, that is, an edge $e$ in a graph $G$
where $\alpha(G/e)\leq\alpha(G)$, studied in [24]. Furthermore, the case where
$c$ is the chromatic and clique number, respectively, has been investigated in
[11, 22, 23].

In this article, we investigate the graph invariant $H$-free for a given set
of graphs $\mathcal{H}$. In particular, we present sufficient and necessary
conditions for a graph $G$ such that any $G$-contraction is
$\mathcal{H}$-free.

Let $\mathcal{H}$ be a set of graphs. The set of _elementary (minimal)_ graphs
in $\mathcal{H}$, denoted by _$\operatorname{elm}$($\mathcal{H}$)_, is defined
as $\\{H\in\mathcal{H}:$ if $G\in\mathcal{H}$ and $H$ is $G$-exist, then $G$
is isomorphic to $H\\}$. From the previous definition, we can directly obtain
the following.

######  Proposition 1.

Let $\mathcal{H}$ be a set of graphs. Graph $G$ is $\mathcal{H}$-free if and
only if G is $\operatorname{elm}(\mathcal{H})$-free.

We call an $\mathcal{H}$-free graph $G$, _strongly $\mathcal{H}$-free_ if any
$G$-contraction is $\mathcal{H}$-free. Furthermore, an $\mathcal{H}$-exist
graph $G$ is a _critically $\mathcal{H}$-exist_ if any $G$-contraction is
$\mathcal{H}$-free. If we add any number of isolated vertices to a strongly
$H$-free or critically $H$-exist graph, we obtain a graph with same property.
Thus, from this section and forward, we exclude graphs having isolated
vertices unless otherwise stated.

We conclude directly the following.

######  Proposition 2.

Let $\mathcal{H}$ be a set of graphs and $G$ be a graph where $G$ is neither
critically $\mathcal{H}$-exist nor $\mathcal{H}$-free but not strongly
$\mathcal{H}$-free. The graph $G$ is $\mathcal{H}$-free if and only if any
$G$-contraction is $\mathcal{H}$-free.

Given a graph $G$ and a set of graphs $\mathcal{H}$, we call $G$
_$\mathcal{H}$ -split_ if there is a $G$-contraction isomorphic to a graph in
$\mathcal{H}$. Furthermore, $G$ is _$\mathcal{H}$ -free-split_ if $G$ is
$\mathcal{H}$-split and $\mathcal{H}$-free. Moreover, the set of all
$\mathcal{H}$-free-split graphs, for a given $\mathcal{H}$, is denoted by
_$\operatorname{fs}(\mathcal{H})$_.

######  Proposition 3.

Let $\mathcal{H}$ be a set of graphs and $G$ be a $\mathcal{H}$-free graph.
Then $G$ is strongly $\mathcal{H}$-free if and only if $G$ is
$\operatorname{fs}(\mathcal{H})$-free.

###### Proof.

Assume for the sake of contradiction that there exists a strongly
$\mathcal{H}$-free graph $G$ with an induced $\mathcal{H}$-free-split subgraph
$J$. Consequently, there is an edge $e$ in $J$ such that $J/e$ induces a graph
in $\mathcal{H}$. As a result, $G/e$ is $\mathcal{H}$-exist, which contradicts
the fact that $G$ is strongly $\mathcal{H}$-free.

In contrast, if $G$ is an $\mathcal{H}$-free but not a strongly
$\mathcal{H}$-free, then there is a set $U\subseteq V(G)$ such that there is
an edge $e\in E(G[U])$ where $G/e$ is $\mathcal{H}$-exist. Let $U$ be a
minimum set with such a property. Thus $G[U]$ is $\mathcal{H}$-free-split. ∎

From Propositions 2 and 3, we deduce the following.

######  Theorem 4.

Let $\mathcal{H}$ be a set of graphs and $G$ be a
$\operatorname{fs}(\mathcal{H})$-free graph where $G$ is not critically
$\mathcal{H}$-exist. The graph $G$ is $\mathcal{H}$-free if and only if any
$G$-contraction is $\mathcal{H}$-free.

Theorem 4 provides a sufficient and necessary condition that answers the
question we investigate in this thesis, however, it translates the problem to
determining characterizations for critically $\mathcal{H}$-exist and
$\mathcal{H}$-free-split graphs for a set of graphs $\mathcal{H}$. In Sections
1.1 and 1.2, we present some properties for these families of graphs.

###  1.1 The $\mathcal{H}$-Split Graphs

Let $H$ be a graph with $v\in V(H)$ and $N_{H}(v)=U\cup W$. The
_$splitting(H,v,U,W)$_ is the graph obtained from $H$ by removing $v$ and
adding two vertices $u$ and $w$ where $N_{H}(u)=U\cup\\{w\\}$ and
$N_{H}(w)=W\cup\\{u\\}$. Furthermore, _$splitting(H,v)$_ is the set of all
graphs for any possible $U$ and $W$. Moreover, _$splitting(H)$_ is the union
of the $splitting(H,v)$ for any vertex $v\in V(H)$. Given a set of graphs
$\mathcal{H}$, _$splitting(\mathcal{H})$_ is the union of the splittings of
every graph in $\mathcal{H}$.

######  Theorem 5.

For a graph $G$ and a set of graphs $\mathcal{H}$, $G$ is an
$\mathcal{H}$-split if and only if $G\in splitting(\mathcal{H})$.

###### Proof.

Let $G$ be an $\mathcal{H}$-split. Hence there is a graph $H\in\mathcal{H}$
such that $G$ is $H$-split. Thus, there are two vertices $u,w\in V(G)$ such
that $G/uw$ is isomorphic to $H$. Let $x:=V(G/uw)-V(G)$, then
$N_{G/uw}(x)=(N_{G}(u)\cup N_{G}(w))-\\{u,w\\}$. As a result, $G\in
splitting(H,x)$. Consequently, $G\in splitting(\mathcal{H})$.

Conversely, let $G\in splitting(\mathcal{H})$. Hence there is a graph
$H\in\mathcal{H}$ such that $G\in splitting(H)$. Thus, there are two adjacent
vertices $u,w\in V(G)$ such that $G/uw\cong H$. Thus, $G$ is
$\mathcal{H}$-split. ∎

For a set of graphs $\mathcal{H}$ and using Theorem 5, we can use
$splitting(\mathcal{H})$ to construct all $\mathcal{H}$-split graphs,
consequently $\mathcal{H}$-free-split graphs.

######  Proposition 6.

In a graph $G$, let $u,v\in V(G)$. If $u$ is similar to $v$, then
$splitting(G,u)=splitting(G,v)$.

By the previous proposition, for a graph $H$, the steps to construct the
$H$-free-split graphs are:

  * •

Let $\pi$ be the partition of $V(H)$ induced by the orbits generated from
$Aut(H)$;

  * •

for every orbit $o\in\pi$, we choose a vertex $v\in o$; and

  * •

construct $splitting(H,v)$.

######  Proposition 7.

Let $G$ be a graph, $v$ a vertex in $V(G)$ where $N_{G}(v)=U\cup W$. If
$U=N_{G}(v)$ or $W=N_{G}(v)$, then $splitting(G,v,U,W)$ is not $G$-free-split.

######  Proposition 8.

Let $G$ be a graph and $v$ a vertex in $V(G)$. If $deg(v)=1$, then
$splitting(G,v)$ contains no $G$-free-split graph.

######  Proposition 9.

If $G$ is a path, then $splitting(G)$ contains no $G$-free-split graph.

######  Proposition 10.

If $G$ is a $C_{n}$ for an integer $n\geq 3$, then the $G$-free-split is
$C_{n+1}$.

###  1.2 Critically $\mathcal{H}$-Exist Graphs

######  Theorem 11.

Let $G$ be a graph and $\mathcal{H}$ be a set of graphs. If $G$ is a
critically $\mathcal{H}$-exist, then for any $S\subseteq V(G)$ such that
$G[S]$ is isomorphic to a graph in $\mathcal{H}$, the followings properties
hold:

  1. 1.

$V(G)-S$ is independent and

  2. 2.

there is no corner in $V(G)-S$ that is dominated by a vertex in $S$.

###### Proof.

  1. 1.

For the sake of contradiction, assume there is a $S\subseteq V(G)$ such that
$G[S]$ is isomorphic to a graph $H\in\mathcal{H}$ but $V(G)-S$ is not
independent. Hence, there are two vertices $u,v\in V(G)-S$ where $u$ and $v$
are adjacent. Consequently, $G/uv[S]$ is isomorphic to $H$, which contradicts
the fact that $G$ is a critically $\mathcal{H}$-exist.

  2. 2.

Since $V(G)-S$ is independent, the neighborhood of any vertex in $V(G)-S$ is a
subset of $S$. For the sake of contradiction, assume that there is a corner
$u\in V(G)-S$ that is dominated by $v\in S$. However, $G/uv[S]$ is isomorphic
to a graph $H\in\mathcal{H}$, which contradicts the fact that $G$ is a
critically $\mathcal{H}$-exist.

∎

######  Corollary 12.

Let $G$ be a critically $\mathcal{H}$-exist graph for a set of graphs
$\mathcal{H}$. If $S$ is a vertex set that induces a graph in $\mathcal{H}$,
then no vertex in $V(G)-S$ is adjacent to exactly one vertex, two adjacent
vertices, three vertices that induce either $P_{3}$ or $C_{3}$, or a vertex
with degree $|V(G)|-1$.

Let $G$ be a graph with adjacent vertices $u,v$, and $\\{w\\}:=V(G/uv)-V(G)$.
We define the mapping $f:2^{V(G)}\to 2^{V(G/uv)}$ as follows:

$f(S)=\begin{cases}S&\text{if }u,v\notin S,\\\
(S\cup\\{w\\})-\\{u,v\\}&\text{otherwise.}\\\ \end{cases}$

Let $S$ be a vertex set such that $G[S]$ is isomorphic to a given graph $H$.
We call an edge $uv$, $H$-critical for $S$ if $G/uv[f(S)]$ is non-isomorphic
to $H$. Furthermore, we call the edge $uv$ $H$-critical in $G$ if for any
vertex subset $S$ that induces $H$, $uv$ is $H$-critical for $S$.

######  Theorem 13.

Let $G$ be a graph and $S\subseteq V(G)$ where $H$ is the graph induced by $S$
in $G$. For any edge $uv\in E(G)$, $uv$ is $H$-critical for $S$ if and only if

  1. 1.

$u,v\in S$ or

  2. 2.

$u\in V(G)-S$, $v\in S$, and $u$ is not a corner dominated by $v$ in the
subgraph $G[S\cup\\{u\\}]$.

###### Proof.

  1. 1.

If $u,v\in S$, then $|f(S)|<|S|$. Thus, $G/uv[f(S)]$ is non-isomorphic to $H$.

  2. 2.

Let $u\in V(G)-S$, $v\in S$, and $u$ is not a corner dominated by $v$ in the
subgraph $G[S\cup\\{u\\}]$. Additionally, let $w\in N_{S}(u)$ but $w\notin
N_{S}(v)$. In $G/uv$, let $x:=V(G/uv)-V(G)$. Clearly, $x$ is adjacent to any
vertex in $N_{S}(v)\cup\\{w\\}$. Hence, the size of $G/uv[f(S)]$ is larger
than that of $G[S]$. Thus, $G/uv[f(S)]$ is non-isomorphic to $H$.

Conversely, if none of the conditions in the theorem hold, then one of the
following holds:

  1. 1.

both $u$ and $v$ are not in $S$, or

  2. 2.

$u\in V(G)-S$, $v\in S$, and $u$ is a corner dominated by $v$ in the subgraph
$G[S\cup\\{u\\}]$.

In both cases, $G[S]\cong G/uv[f(S)]\cong H$. Consequently, $uv$ is not
$H$-critical for $S$. ∎

##  2 Special graphs

######  Proposition 14.

If a graph $G$ is $C_{n}$-exist, where $n\geq 4$, then there is a
$G$-contraction that is $C_{n-1}$-exist.

######  Proposition 15.

The only critical $C_{3}$-exist graph is $C_{3}$.

##  3 Claw-Free Graphs

There are several graph families that are subfamilies of claw-free graphs, for
instance, line graphs and complements of triangle-free graphs. For more graph
families and results about claw-free graphs, please consult [13].
Additionally, for more structural results about claw-free graphs, please
consult [7, 8]. In the following, we call the graph $H_{5}$ in Figure 1 bull.

######  Proposition 16.

The graphs in Figure 1 are the only claw-split graphs.

######  Corollary 17.

Bull is the only claw-free-split graph.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$ Figure 1: Claw-split graphs

######  Proposition 18.

The graphs in Figure 2 are the only critically claw-exist graphs.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$ Figure 2: Critically claw-exist
graphs

###### Proof.

Through this proof, we assume that $G$ is a critically claw-exist graph with
$S:=\\{r,s,t,u\\}$, where $G[S]$ is isomorphic to a claw and $u$ is its
center. By Theorem 11, $V(G)-S$ is independent. Thus, any vertex in $V(G)-S$
is adjacent to vertices only in $S$. By Corollary 12, if $v\in V(G)-S$, then
neither $|N(v)|=1$ nor $v$ is adjacent to $u$.

Let $v,w\in V(G)-S$ such that $N(v)=N(w)$ where $|N(v)|=2$. W.l.o.g., assume
that $N(v)=\\{r,s\\}$, however, in $G/tu$, $f(\\{r,u,v,w\\})$ induces a claw,
which contradicts the fact that $G$ is a critically claw-exist. Thus, if
$v,w\in V(G)-S$ such that $|N(v)|=|N(w)|=2$, then $N(v)\not=N(w)$.

Let $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=2$. No two vertices of $v,w$,
and $x$ (if $|N(x)|=2$) are adjacent to the same vertices in $S$. W.l.o.g.,
assume that $N(v)=\\{r,s\\}$, $N(w)=\\{r,t\\}$, and $\\{s,t\\}\subseteq N(x)$.
In $G/tx$, $f(\\{r,u,v,w\\})$ induces a claw, which contradicts the fact that
$G$ is a critically claw-exist. Thus, if $v,w\in V(G)-S$ such that
$|N(v)|=|N(w)|=2$, then $G$ is isomorphic to $H_{5}$.

Let $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=3$. W.l.o.g., assume that $s$
is adjacent to $x$. In $G/sx$, $f(\\{r,u,v,w\\})$ induces a claw, which
contradicts the fact that $G$ is a critically claw-exist. Thus, if $v,w\in
V(G)-S$ such that $N(v)=N(w)$ and $|N(v)|=3$, then $G$ is isomorphic to
$H_{3}$.

Consequently, the possible critically claw-exist graphs are those presented in
Figure 2. To complete the proof, we have to show that all these graphs are
critically claw-exist, which is straightforward in each case. ∎

By Theorem 4, Corollary 17, and Proposition 18, we obtain the following
result.

######  Theorem 19.

Let $G$ be a bull-free graph that is non-isomorphic to any graph in Figure 2.
The graph $G$ is claw-free if and only if any $G$-contraction is claw-free.

##  4 The $2K_{2}$-Free Graphs

Different graphs families are $2K_{2}$-free graphs; for instance split,
pseudo-split, threshold, and co-chordal graphs. Various graph invariants were
studied for $2K_{2}$-free graphs, please consult [15, 9, 12, 4, 5]. The class
of $2K_{2}$-free graphs has been characterized in different ways, see [20,
25]. We call the graph $H_{5}$ in Figure 1 Bull.

We call an edge $uv$ in a graph $G$ _almost-dominating_ if $V(G)-N[\\{u,v\\}]$
induces edgeless graph.

######  Proposition 20.

A graph $G$ is $2K_{2}$-free if and only if any edge in $E(G)$ is almost-
dominating.

######  Lemma 21.

Let $G$ be a graph with a unique subset $S\subseteq V(G)$ such that $G[S]$
induces $2K_{2}$. If every edge $e$ in $E(G)$ is $e$ is $2K_{2}$-critical for
$S$, then $G$ is a critically $2K_{2}$-exist.

###### Proof.

Let $H$ be a $G$-contraction. Every edge $e$ in $E(G)$ is $2K_{2}$-critical
for $S$, then $V(G)-S$ is independent set. Furthermore, every vertex in
$V(G)-S$ is adjacent to at least two nonadjacent vertices in $S$. In $H$, let
$u\in V(G)-f(S)$ and $v\in f(S)$. If $u,v$ are adjacent, then $uv$ is almost-
dominating. Let $u\in f(S)$, then $uv$ is almost-dominating. Hence, every edge
in $H$ is almost-dominating. Thus, $G$ is a critically $2K_{2}$-exist. ∎

######  Proposition 22.

The graphs $P_{2}\cup C_{3}$ and $P_{2}\cup P_{3}$ are the only $2K_{2}$-split
graphs.

######  Corollary 23.

There is no $2K_{2}$-free-split graph.

######  Proposition 24.

The graphs in Figure 3 are the only critically $2K_{2}$-exist graphs.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$Y$$W$$X$$H_{6}$$Z$$Y$$W$$X$ Figure 3:
Critically $2K_{2}$-exist graphs

###### Proof.

Through this proof, we assume that $G$ is a critically $2K_{2}$-exist graph
with $S=\\{r,s,t,u\\}$ such that $G[S]$ is isomorphic to $2K_{2}$, where $rs$
and $tu$ are edges in $G$. By Theorem 11, we note that $V(G)-S$ is
independent. Thus, any vertex in $V(G)-S$ is adjacent to vertices only in $S$.
By Corollary 12, if $v\in V(G)-S$, then neither $|N(v)|=1$ nor $v$ is adjacent
to exactly two adjacent vertices.

######  Claim 24.1.

If $v,w\in V(G)-S$ such that $|N(v)|=|N(w)|=2$ while $N(v)\cap N(w)=\phi$,
then $G$ is isomorphic to $H_{1}$.

###### Proof.

W.l.o.g., let $N(v)=\\{r,u\\}$ and $N(w)=\\{s,t\\}$. We will show that
$V(G)=S\cup\\{v,w\\}$. For the sake of contradiction, assume that there is a
vertex $x\in V(G)-S$. Thus, $x$ is adjacent to at least one vertex in $S$.
W.l.o.g., let $x$ be adjacent to $r$. In $G/rx$, $f(\\{s,u,v,w\\})$ induces
$2K_{2}$, which contradicts the fact that $G$ is a critically $2K_{2}$-exist.
∎

######  Claim 24.2.

If $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=2$, $|N(x)|=3$ while
$N(v)=N(w)$, then $N(v)\subset N(x)$.

###### Proof.

W.l.o.g., let $N(v)=N(w)=\\{r,u\\}$. For the sake of contradiction and
w.l.o.g., assume $N(x)=\\{r,s,t\\}$. In $G/rw$, $f(\\{s,u,v,x\\})$ induces
$2K_{2}$, which contradicts the fact that $G$ is a critically $2K_{2}$-exist.
∎

######  Claim 24.3.

If $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=2$ while $|N(v)\cap N(w)|=1$ and
$|N(x)|=3$ where $N(v)\cap N(w)\cap N(x)=\phi$, then $G$ is isomorphic to
$H_{4}$.

###### Proof.

W.l.o.g., let $N(v)=\\{r,u\\}$, $N(w)=\\{r,t\\}$, and $N(x)=\\{s,t,u\\}$. For
the sake of contradiction, assume that there is a vertex $y\in V(G)-S$. Hence,
$y$ is adjacent to at least one vertex in $S$. If $y$ is adjacent to $s$ (or
$u$), then $f(\\{r,t,v,x\\})$ induces $2K_{2}$ in $G/sy$ (or $G/uy$), which
contradicts the fact that $G$ is a critically $2K_{2}$-exist. Moreover, if $y$
is adjacent to $t$, then $f(\\{r,u,w,x\\})$ induces $2K_{2}$ in $G/ty$, which
contradicts the fact that $G$ is a critically $2K_{2}$-exist. ∎

######  Claim 24.4.

If $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=2$ while $|N(v)\cap N(w)|=1$ and
$|N(x)|=3$, then either $N(v)\cup N(w)=N(x)$ or $N(v)\cap N(w)\cap N(x)=\phi$
and $G$ is isomorphic to $H_{4}$.

###### Proof.

By Claim 24.3, if $N(v)\cap N(w)\cap N(x)=\phi$, then $G$ is isomorphic to
$H_{4}$. If $N(v)\cup N(w)=N(x)$, then we are done. As a result, and w.l.o.g,
let $N(v)=\\{r,u\\}$ and $N(w)=\\{r,t\\}$. Assume for the sake of
contradiction that $N(x)=\\{r,s,t\\}$. However, $f(\\{s,u,v,x\\})$ induces
$2K_{2}$ in $G/rw$, which contradicts the fact that $G$ is a critically
$2K_{2}$-exist. ∎

######  Claim 24.5.

If $v,w\in V(G)-S$ such that $|N(v)|=|N(w)|=3$, while $N(v)\cap N(w)$ consists
of two nonadjacent vertices in $S$, then $G$ is isomorphic to $H_{3}$.

###### Proof.

W.l.o.g., let $N(v)=\\{r,t,u\\}$ and $N(w)=\\{r,s,t\\}$. For the sake of
contradiction, assume that there is a vertex $x\in V(G)-S$. If $x$ is adjacent
to $r$ (or $t$), then $f(\\{s,u,v,w\\})$ induces $2K_{2}$ in $G/rx$ (or
$G/tx$), which contradicts the fact that $G$ is a critically $2K_{2}$-exist
graph. Thus, $N(x)=\\{s,u\\}$, however, $f(\\{s,t,v,x\\})$ induces $2K_{2}$ in
$G/rw$, which contradicts the fact that $G$ is a critically $2K_{2}$-exist. ∎

######  Claim 24.6.

If $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=3$, while $N(v)\cap N(w)$ is two
adjacent vertices in $S$, then $|N(x)|\not=2$.

###### Proof.

W.l.o.g., Let $N(v)=\\{r,t,u\\}$ and $N(w)=\\{s,t,u\\}$. W.l.o.g and for the
sake of contradiction, assume that $N(x)=\\{r,u\\}$. However,
$f(\\{r,t,w,x\\})$ induces $2K_{2}$ in $G/uv$, which contradicts the fact that
$G$ is a critically $2K_{2}$-exist. ∎

By Claims 24.1 to 24.6, the possible critically $2K_{2}$-exist graphs are
those presented in Figure 3 whose proofs of being critically $2K_{2}$-exist
for $H_{1}$, $H_{2}$, $H_{3}$, and $H_{4}$ are straightforward.

######  Claim 24.7.

The graph $H_{5}$ in Figure 3 is a critically $2K_{2}$-exist.

###### Proof.

Graph $H_{5}$ in Figure 3 is isomorphic to a graph $G$ that contains a vertex
subset $S=\\{r,s,t,u\\}$, where $G[S]$ is isomorphic to a $2K_{2}$ and
$rs,tu\in E(G)$. Moreover, $V(G)=S\cup W\cup X\cup Y$, such that $N(w\in
W)=\\{r,s,t\\}$, $N(x\in X)=\\{r,s,u\\}$, $N(y\in Y)=\\{r,s,t,u\\}$, and
$|W|,|X|,|Y|\geq 0$.

We note that $S$ is the only vertex set inducing $2K_{2}$ in $G$. Moreover,
every edge in $E(G)$ is $G[S]$-critical for $S$. Thus, and by Lemma 21,
$H_{5}$ in Figure 3 is a critically $2K_{2}$-exist. ∎

######  Claim 24.8.

Graph $H_{6}$ in Figure 3 is a critically $2K_{2}$-exist.

###### Proof.

Graph $H_{6}$ in Figure 3 is isomorphic to a graph $G$ that contains a vertex
subset $S=\\{r,s,t,u\\}$ where $G[S]$ is isomorphic to a $2K_{2}$ and
$rs,tu\in E(G)$. Moreover, $V(G)=S\cup W\cup X\cup Y\cup Z$, such that $N(w\in
W)=\\{s,t\\}$, $N(x\in X)=\\{s,u\\}$, $N(y)=\\{s,t,u\\}$,
$N(z)=\\{r,s,t,u\\}$, and $|W|,|X|,|Y|,|Z|\geq 0$.

We note that $S$ is the only vertex set inducing $2K_{2}$ in $G$. Moreover,
every edge in $E(G)$ is $G[S]$-critical for $S$. Thus, and by Lemma 21,
$H_{6}$ in Figure 3 is a critically $2K_{2}$-exist. ∎

By Claims 24.7 and 24.8, the proof is complete. ∎

By Theorem 4, Corollary 23, and Proposition 24, we obtain the following.

######  Theorem 25.

Let $G$ be a graph that is non-isomorphic to any graph in Figure 3. The graph
$G$ is $2K_{2}$-free if and only if any $G$-contraction is $2K_{2}$-free.

##  5 The $P_{4}$-Free Graphs

By Proposition 9, the following result follows.

######  Corollary 26.

There is no $P_{4}$-free-split graph.

######  Proposition 27.

The graphs in Figure 4 are the only critically $P_{4}$-exist graphs.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$$\vdots$$H_{5}$$\vdots$ Figure 4: The critically
$P_{4}$-exist graphs

###### Proof.

Through this proof, we assume that $G$ is a critically $P_{4}$-exist graph
with $S=\\{r,s,t,u\\}$ such that $G[S]$ is isomorphic to $P_{4}$ where
$rs,st,tu\in E(G)$. By Theorem 11, $V(G)-S$ is independent. Thus, any vertex
in $V(G)-S$ is adjacent to vertices only in $S$. By Corollary 12, if $v\in
V(G)-S$, then $v$ is nonadjacent to exactly: one vertex, two adjacent
vertices, or three vertices inducing a path.

Let $v,w\in V(G)-S$ such that $v$ is adjacent to exactly the leafs of $S$. If
$w$ is adjacent to $r$ (or $u$), then in $G/rw$, $f(\\{s,t,u,v\\})$ induces
$P_{4}$, which contradicts the fact that $G$ is a critically $P_{4}$-exist. If
$w$ is adjacent to $s$ (or $t$), then in $G/sw$, $f(\\{r,t,u,v\\})$ induces
$P_{4}$, which contradicts the fact that $G$ is a critically $P_{4}$-exist.
Thus, if there is a vertex $v\in V(G)-S$ such that $v$ is adjacent to exactly
the leaves of the path induced by $S$, then $G$ is isomorphic to $H_{1}$.

Let $v\in V(G)-S$ such that $|N(v)|=2$. If $v$ is adjacent to exactly the
leaves of the path induced by $S$, then $G$ is isomorphic to $H_{1}$. Assume
that $v$ is nonadjacent to exactly the leaves of the path induced by $S$.
Hence, $v$ is exactly adjacent to $\\{r,t\\}$ (or $\\{s,u\\}$). Assume that
there is a vertex $w\in V(G)-S$ that is not exactly adjacent to $\\{r,t\\}$.
Hence, $w$ is nonadjacent to exactly $\\{r,u\\}$. If $w$ is adjacent to $s$,
then in $G/sw$, $f(\\{r,t,u,v\\})$ induces $P_{4}$, which contradicts the fact
that $G$ is a critically $P_{4}$-exist. Hence, $w$ is adjacent to exactly
$\\{r,t,u\\}$, however, in $G/st$, $f(\\{r,u,v,w\\})$ induces $P_{4}$, which
contradicts the fact that $G$ is a critically $P_{4}$-exist. Thus, if $v\in
V(G)-S$ such that $|N(v)|=2$, then $G$ is isomorphic to either $H_{1}$ or a
graph in $H_{4}$.

Let $v,w\in V(G)-S$ such that $|N(v)|=|N(w)|=3$. Assume that $N(v)=N(w)$.
W.l.o.g, let $N(v)=\\{r,s,u\\}$. In $G/sv$, $f(\\{r,t,u,w\\})$ induces
$P_{4}$, which contradicts the fact that $G$ is a critically $P_{4}$-exist.
Thus, if $v,w\in V(G)-S$ such that $|N(v)|=|N(w)|=3$, then $N(v)\not=N(w)$.

Let $v,w\in V(G)-S$ such that $|N(v)|=3$. W.l.o.g, assume that
$N(v)=\\{r,s,u\\}$. Assume that $N(w)=\\{r,s,t,u\\}$, however, in $G/sw$,
$f(\\{r,t,u,v\\})$ induces $P_{4}$, which contradicts the fact that $G$ is a
critically $P_{4}$-exist. Thus, if $v,w\in V(G)-S$ such that $|N(v)|=3$, then
$|N(w)|\not=4$.

Consequently, the possible critically $P_{4}$-exist graphs are those presented
in Figure 4 whose proofs, of being critically $P_{4}$-exist, are
straightforward, which completes the proof. ∎

By Theorem 4, Corollary 26, and Proposition 27, we obtain the following.

######  Theorem 28.

Let $G$ be a graph that is non-isomorphic to any graph in Figure 4. The graph
$G$ is $P_{4}$-free if and only if any $G$-contraction is $P_{4}$-free.

##  6 The $C_{4}$-Free Graphs

######  Proposition 29.

The graphs in Figure 5 are the only $C_{4}$-split graphs.

######  Corollary 30.

$C_{5}$ is the only $C_{4}$-free-split graph.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$ Figure 5: $C_{4}$-split graphs

######  Proposition 31.

The graphs in Figure 6 are the only critically $C_{4}$-exist graphs.

$H_{1}$$\dots$$H_{2}$$H_{3}$ Figure 6: Critically $C_{4}$-exist graphs

###### Proof.

Through this proof, we assume that $G$ is a critically $C_{4}$-exist graph
with $S=\\{r,s,t,u\\}$ such that $G[S]$ is isomorphic to $C_{4}$ where $r$ and
$t$ are adjacent to both $s$ and $u$. By Theorem 11, we note that $V(G)-S$ is
independent. Thus, any vertex in $V(G)-S$ is adjacent to vertices only in $S$.
By Corollary 12, if $v\in V(G)-S$, then $v$ is nonadjacent to exactly: one
vertex, two adjacent vertices, or three vertices.

Let $v\in V(G)-S$ such that $|N(v)|=2$. W.l.o.g, assume that $N(v)=\\{r,t\\}$.
Let $w\in V(G)-S$, however, if $w$ is adjacent to $s$ (or $u$), then in
$G/sw$, $f(\\{r,t,u,v\\})$ induces $C_{4}$, which contradicts the fact that
$G$ is a critically $C_{4}$-exist. Thus, if $v\in V(G)-S$ such that
$|N(v)|=2$, then $G$ is isomorphic to a graph in $H_{1}$.

Let $v,w,x\in V(G)-S$ such that $|N(v)|=|N(w)|=4$. Hence, $|N(x)|=4$, however,
in $G/rv$, $f(\\{s,u,w,x\\})$ induces $C_{4}$, which contradicts the fact that
$G$ is a critically $C_{4}$-exist. Thus, if there is a vertex outside $S$ that
is adjacent to every vertex in $S$ then $G$ is isomorphic to either $H_{2}$ or
$H_{3}$.

Consequently, the possible critically $C_{4}$-exist graphs are those presented
in Figure 6 whose proofs, of being critically $C_{4}$-exist, are
straightforward, which completes the proof. ∎

By Theorem 4, Corollary 30, and Proposition 31, we obtain the following.

######  Theorem 32.

Let $G$ be a $C_{5}$-free graph that is non-isomorphic to any graph in Figure
6. The graph $G$ is $C_{4}$-free if and only if any $G$-contraction is
$C_{4}$-free.

##  7 The $C_{5}$-Free Graphs

######  Proposition 33.

The graphs in Figure 7 are the only $C_{5}$-split graphs.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$ Figure 7: $C_{5}$-split graphs

######  Corollary 34.

$C_{6}$ is the only $C_{5}$-free-split graph.

######  Proposition 35.

The graphs in Figure 8 are the only critically $C_{5}$-exist graphs.

$H_{1}$$H_{2}$$Y$$H_{3}$$Y$$H_{4}$$W$$X$$Y$$H_{5}$$W$$Z$$X$$Y$$H_{6}$$A$$Y$$\vdots$$Z$$W$$X$
Figure 8: Critically $C_{5}$-exist graphs

###### Proof.

Through this proof, we assume that $G$ is a critically $C_{5}$-exist graph
with $S=\\{r,s,t,u,v\\}$ such that $G[S]$ is isomorphic to a $C_{5}$ where
$rs,st,tu,uv$, and $vr$ are the edges in $E(G[S])$. By Theorem 11, we note
that $V(G)-S$ is independent. Thus, any vertex in $V(G)-S$ is adjacent to
vertices only in $S$. By Corollary 12, if $w\in V(G)-S$, then the neighborhood
of $w$ is not exactly: one vertex, two adjacent vertices, or three vertices
that induce a path.

######  Claim 35.1.

If $w,x\in V(G)-S$ such that $|N(w)|=2$, then for any vertex $y$ in $N(x)$,
$N(w)\cup\\{y\\}$ do not induce $P_{3}$.

###### Proof.

For the sake of contradiction, and w.l.o.g., assume that there are vertices
$w,x\in V(G)-S$ such that $N(w)=\\{r,t\\}$ and there is a vertex
$y\in|N_{S}(x)|$, where $N(w)\cup\\{y\\}$ induces $P_{3}$. Consequently,
$y=s$. In $G/sx$, the set $f(\\{r,t,u,v,w\\})$ induces $C_{5}$, which
contradicts the fact that $G$ is a critically $C_{5}$-exist. ∎

######  Claim 35.2.

If $w,x,y\in V(G)-S$ such that $|N(w)|=|N(x)|=3$ where $N(w)\cup N(x)=S$, then
$y$ is nonadjacent to any vertex in $S$ that is adjacent to $N(w)\cap N(x)$.

###### Proof.

W.l.o.g., assume that there are vertices $w,x,y\in V(G)-S$ such that
$N(w)=\\{r,t,u\\}$ and $N(w)\cup N(x)=S$. As a result, $N(x)=\\{s,t,v\\}$ or
$\\{s,u,v\\}$. Because of symmetry, we assume that $N(x)=\\{s,t,v\\}$. For the
sake of contradiction, we assume that $y$ is adjacent to $s$ (or $u$).
However, in $G/sy$ (or $G/uy$), the set $f(\\{r,t,v,w,x\\})$ induces $C_{5}$
which contradicts the fact that $G$ is a critically $C_{5}$-exist. ∎

######  Claim 35.3.

If $w,x,y\in V(G)-S$ such that $|N(w)|=|N(x)|=4$, where $N(w)\cap N(x)$
induces $P_{3}$, then $y$ is nonadjacent to the leaves in the path induced by
$N(w)\cap N(x)$.

###### Proof.

W.l.o.g., assume that there are vertices $w,x,y\in V(G)-S$ such that
$N(w)=\\{r,s,t,u\\}$, while $N(w)\cap N(x)$ induces $P_{3}$. As a result,
$N(x)=\\{s,t,u,v\\}$ or $\\{r,t,u,v\\}$. Because of symmetry, we assume that
$N(x)=\\{s,t,u,v$ $\\}$. For the sake of contradiction, we assume that $y$ is
adjacent to $s$ (or $u$). However, in $G/sy$ (or $G/uy$), the set
$f(\\{r,t,v,w,x\\})$ induces $C_{5}$, which contradicts the fact that $G$ is a
critically $C_{5}$-exist. ∎

######  Claim 35.4.

If $w,x\in V(G)-S$ such that $|N(w)|=3$ and $|N(x)|=4$ where neither of the
leaves of the $P_{4}$ induced by $N(x)$ are in $N(w)$, then $G$ is isomorphic
to $H_{1}$.

###### Proof.

W.l.o.g., assume vertices $w,x\in V(G)-S$ such that $N(w)=\\{r,t,u\\}$ and
$N(x)=\\{s,t,u,v\\}$. For the sake of contradiction, we assume that there is a
vertex $y\in V(G)-S$. If $y$ is adjacent to $s$ (or $u$), then in $G/sy$ (or
$G/uy$), the set $f(\\{r,t,v,w,x\\})$ induces $C_{5}$, which contradicts the
fact that $G$ is a critically $C_{5}$-exist. In contrast, if $y$ is adjacent
to $t$ (or $v$), then in $G/ty$ (or $G/vy$), the set $f(\\{r,s,u,w,x\\})$
induces $C_{5}$, which contradicts the fact that $G$ is a critically
$C_{5}$-exist. ∎

By Claims 35.1 to 35.4, we deduce that the possible critically $C_{5}$-exist
graphs are the ones presented in Figure 8. To complete the proof, we
demonstrate that every graph in Figure 8 is a critically $C_{5}$-exist.

######  Claim 35.5.

There is no $C_{6}$-exist graph in Figure 8.

###### Proof.

Assume for the sake of contradiction, there is a graph $G$ in in Figure 8 that
is $C_{6}$-exist. Moreover, $T\subseteq V(G)$ where $G[T]$ induces $C_{6}$.
Let $S\subseteq V(G)$ such that $G[S]$ induces $C_{5}$. No more than two
vertices in $S$ can form an independent set. Hence $T$ can contain at most two
vertices from $S$. Consequently, $T$ has four vertices from $V(G)-S$, however,
two of such four vertices are adjacent, which contradicts the fact that
$V(G)-S$ is independent set. ∎

All graphs in Figure 8 are $C_{6}$-free. Consequently, any contraction of a
graph of Figure 8 has an induced $C_{5}$, then this $C_{5}$ must be an induced
subgraph of the original graph too. Thus, it would be sufficient to prove that
in every graph $G$ in Figure 8, the edges of $G$ are critical for every
induced $C_{5}$ in $G$.

######  Claim 35.6.

The graph $H_{1}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{1}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup\\{w,x\\}$ such that
$N(w)=\\{r,t,u\\}$ and $N(x)=\\{s,t,u,v\\}$. Clearly, the vertex subsets of
$V(G)$ that induce $C_{5}$ are $S$, $\\{r,s,u,w,x\\}$, and $\\{r,t,v,w,x\\}$.
Furthermore, it is straightforward that every edge in $E(G)$ is
$C_{5}$-critical for the previous three vertex subsets. Thus, $G$ is a
critically $C_{5}$-exist. ∎

######  Claim 35.7.

The graph $H_{2}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{2}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup\\{w,x\\}\cup Y$, such that
$N(w)=\\{r,t,u\\}$, $N(x)=\\{s,u,v\\}$, $N(y\in Y)=\\{r,s,u\\}$, and $|Y|\geq
0$.

We prove that $G$ contains only two induced $C_{5}$. For any $i,j$ where
$1\leq i<j\leq|Y|$, if both $y_{i}$ and $y_{j}$ are in a vertex subset that
induces a cycle in $G$, then this vertex subset would be
$\\{r,u,y_{i},y_{j}\\}$ and $\\{s,u,y_{i},y_{j}\\}$. Thus, no induced $C_{5}$
in $G$ contains both $y_{i}$ and $y_{j}$. Moreover, the vertex subsets that
induce a cycle in $G$ that contain $y_{i}$ but not $y_{j}$ are
$\\{r,s,y_{i}\\}$, $\\{r,u,v,y_{i}\\}$, $\\{r,u,y_{i},w\\}$,
$\\{s,t,u,y_{i}\\}$, and $\\{s,u,x,y_{i}\\}$. Clearly, none of them induces
$C_{5}$. Thus, no induced $C_{5}$ in $G$ contain a vertex $y_{i}$ for any
$i\leq l$. Furthermore, no four vertices from $S$ with either $w$ or $x$
induce a $C_{5}$. Consequently, no vertex subset that induces $C_{5}$ in $G$
contains either $w$ or $x$. As a result, a cycle $C_{5}$ is induced in $G$
only by $S$ or $\\{r,s,u,w,x\\}$. We note that any edge in $E(G)$ is a
critical edge for all subsets that induce $C_{5}$. Thus, $G$ is a critically
$C_{5}$-exist. ∎

The proof of the following claim can be performed in a similar way as that one
of Claim 35.7. We will just explain the structure of the graph $H_{3}$, the
remaining part is left to the interested reader.

######  Claim 35.8.

The graph $H_{3}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{3}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup\\{w,x\\}\cup Y$, such that
$N(w)=\\{r,s,t,u\\}$, $N(x)=\\{s,t,u,v\\}$, $N(y\in Y)=\\{r,t,v\\}$, and
$|Y|\geq 0$. ∎

######  Claim 35.9.

The graph $H_{4}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{4}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup W\cup X\cup Y$, such that
$N(w\in W)=\\{r,t\\}$, $N(x\in X)=\\{r,u\\}$, $N(y\in Y)=\\{r,t,u\\}$, and
$|W|,|X|,|Y|\geq 0$.

For any $k,p$ where $1\leq k<p\leq|Y|$, if both $y_{k}$ and $y_{p}$ are in a
vertex subset that induces cycle in $G$, then this vertex subset would be
$\\{r,u,y_{k},y_{p}\\}$ or $\\{r,t,y_{k},y_{p}\\}$. Thus, no induced $C_{5}$
in $G$ contains both $y_{k}$ and $y_{p}$. Additionally, the induced cycles in
$G$ that contain $y_{k}$ but not $y_{p}$ (or vice versa) are of length less
than five. Thus, no induced $C_{5}$ in $G$ contains one vertex $y_{k}$ for any
$k\leq n$. Indeed, a vertex subset in $G$ that induces a $C_{5}$ is composed
of $\\{r,t,u\\}$, one vertex from $W\cup\\{s\\}$, and one vertex from
$X\cup\\{v\\}$. We conclude that any edge in $E(G)$ is a critical edge for all
subsets that induce $C_{5}$. Thus, $G$ is a critically $C_{5}$-exist. ∎

######  Claim 35.10.

The graph $H_{5}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{5}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup W\cup X\cup Y\cup Z$, such
that $N(w\in W)=\\{r,t\\}$, $N(x\in X)=\\{r,t,u\\}$, $N(y\in Y)=\\{r,t,v\\}$,
$N(z\in Z)=\\{r,t,u,v\\}$, and $|W|,|X|,|Y|,|Z|\geq 0$.

It is clear that no vertex subset in $G$ that induces $C_{5}$ contains two
vertices from $V(G)-S$. Moreover, we can prove that no vertex subset in $G$
that induces $C_{5}$ contains one vertices from $V(G)-(S\cup W)$. As a result,
the vertex subsets that induces a $C_{5}$ in $G$ are either $S$ or
$\\{r,t,u,v\\}$ together with one vertex from $\\{w_{1},w_{2},\dots,w_{l}\\}$.
Any edge in $E(G)$ is a critical for all subsets that induce $C_{5}$. Thus,
$G$ is a critically $C_{5}$-exist. ∎

Being similar to the proof of Claim 35.10, the proof of Claim 35.11 is left
for the interested reader; however, we explain the structure of $H_{6}$ in
Figure 8 in the proof.

######  Claim 35.11.

The graph $H_{6}$ in Figure 8 is a critically $C_{5}$-exist.

###### Proof.

The graph $H_{6}$ in Figure 8 is isomorphic to a graph $G$ that contains a
vertex subset $S=\\{r,s,t,u,v\\}$ that induces $C_{5}$, where
$rs,st,tu,uv,vr\in E(G)$. Moreover, $V(G)=S\cup W\cup X\cup Y\cup Z\cup A$,
such $N(w\in W)=\\{r,t,u\\}$, $N(x\in X)=\\{r,t,v\\}$, $N(y\in
Y)=\\{r,s,t,u\\}$, $N(z\in Z)=\\{r,t,u,v\\}$, $N(a\in A)=S$, and
$|W|,|X|,|Y|,|Z|,|A|\geq 0$. ∎

By Claims 35.5 to 35.11, the proof is complete. ∎

By Theorem 4, Corollary 34, and Proposition 35, we obtain the following.

######  Theorem 36.

Let $G$ be a $C_{6}$-free graph that is non-isomorphic to any graph in Figure
8. The graph $G$ is $C_{5}$-free if and only if any $G$-contraction is
$C_{5}$-free.

##  8 Split Graphs

Split graphs were introduced in [14] and were characterized as follows:

######  Theorem 37.

[14] A graph $G$ is split if and only if $G$ is
$\\{2K_{2},C_{4},C_{5}\\}$-free.

Thus, we call a graph that is $\\{2K_{2},C_{4},C_{5}\\}$-exist _non-split_
graph. Additionally, split graphs have been characterized in [14] as chordal
graphs whose complements are also chordal. Furthermore, it was characterized
by its degree sequences in [16]. Moreover, further properties of split graphs
are studied in [1, 17, 21].

By Theorems 4, 25, 32, and 36 and Propositions 10, 14, and 15, we obtain:

######  Theorem 38.

Let $G$ be a graph that is non-isomorphic to any graph in Figure 9. The graph
$G$ is split if and only if any $G$-contraction is split.

The class of split graphs is a closed class under edge contraction. The
definition of a split graph implies that by contraction of an arbitrary edge
in a split graph leads to another split graph. So the contribution of Theorem
38 is in listing the critically non-split graphs.

$H_{1}$$\dots$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$$H_{7}$ Figure 9: Critically
non-split graphs

##  9 Pseudo-Split Graphs

In [2], the family of $\\{2K_{2},C_{4}\\}$-free graphs was investigated and
later referred to as pseudo-split graphs in [19]. Thus, we call a graph that
is $\\{2K_{2},C_{4}\\}$-exist _non-pseudo-split_ graph.

By Theorems 4, 25 and 32 and Propositions 10, 14, and 15, we obtain:

######  Theorem 39.

Let $G$ be a $C_{5}$-free graph that is non-isomorphic to any graph in Figure
10. The graph $G$ is Pseudo-split if and only if any $G$-contraction is
Pseudo-split.

$H_{1}$$\dots$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$$H_{7}$$H_{8}$ Figure 10: The
critically non-pseudo-split graphs

##  10 Threshold Graphs

Threshold graphs were characterized as follows:

######  Theorem 40.

[10] A given a graph $G$ is threshold if and only if $G$ is $\\{2K_{2}$,
$P_{4}$, $C_{4}\\}$-free.

Thus, we call a graph that is $\\{2K_{2},P_{4},C_{4}\\}$-exist _non-threshold_
graph.

By Theorems 4, 25, 28, and 32 and Propositions 10, 14, and 15, we obtain:

######  Theorem 41.

Let $G$ be a $C_{5}$-free graph that is non-isomorphic to any graph in Figure
9. The graph $G$ is threshold if and only if any $G$-contraction is threshold.

$H_{1}$$\dots$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$$H_{7}$ Figure 11: The
critically non-thershold graphs

##  11 Acknowledgments

The research presented here is funded by the European Social Fund (ESF).

## References

  * Bertossi [1984] Bertossi, A. A. (1984).  Dominating sets for split and bipartite graphs.  Information Processing Letters 19(1), 37–40.
  * Blázsik et al. [1993] Blázsik, Z., M. Hujter, A. Pluhár, and Z. Tuza (1993).  Graphs with no induced $C_{4}$ and $2K_{2}$.  Discrete Mathematics 115(1-3), 51–55.
  * Bondy and Murty [2000] Bondy, J. A. and U. S. Murty (2000).  Graph Theory.  Springer.
  * Brause et al. [2019] Brause, C., B. Randerath, I. Schiermeyer, and E. Vumar (2019).  On the chromatic number of $2{K}_{2}$-free graphs.  Discrete Applied Mathematics 253, 14–24.
  * Broersma et al. [2014] Broersma, H., V. Patel, and A. Pyatkin (2014).  On toughness and hamiltonicity of $2{K}_{2}$-free graphs.  Journal of Graph Theory 75(3), 244–255.
  * Cameron and Fitzpatrick [2015] Cameron, B. and S. Fitzpatrick (2015).  Edge contraction and cop-win critical graphs.  Australasian Journal of Combinatorics 63, 70–87.
  * Chudnovsky and Seymour [2008] Chudnovsky, M. and P. Seymour (2008).  Claw-free graphs. IV. Decomposition theorem.  Journal of Combinatorial Theory, Series B 98(5), 839–938.
  * Chudnovsky and Seymour [2005] Chudnovsky, M. and P. D. Seymour (2005).  The structure of claw-free graphs.  Surveys in Combinatorics 327, 153–171.
  * Chung et al. [1990] Chung, F. R., A. Gyárfás, Z. Tuza, and W. T. Trotter (1990).  The maximum number of edges in $2$K2-free graphs of bounded degree.  Discrete Mathematics 81(2), 129–135.
  * Chvtal and Hammer [1977] Chvtal, V. and P. Hammer (1977).  Aggregation of inequalities in integer programming.  Ann. Discrete Math 1, 145–162.
  * Diner et al. [2018] Diner, Ö. Y., D. Paulusma, C. Picouleau, and B. Ries (2018).  Contraction and deletion blockers for perfect graphs and h-free graphs.  Theoretical Computer Science 746, 49–72.
  * El-Zahar and Erdős [1985] El-Zahar, M. and P. Erdős (1985).  On the existence of two non-neighboring subgraphs in a graph.  Combinatorica 5(4), 295–300.
  * Faudree et al. [1997] Faudree, R., E. Flandrin, and Z. Ryjáček (1997).  Claw-free graphs a survey.  Discrete Mathematics 164(1-3), 87–147.
  * Foldes and Hammer [1977] Foldes, S. and P. L. Hammer (1977).  Split graphs.  Proc. 8th southeast. Conf. on Combinatorics, Graph Theory, and Computing; Baton Rouge 1977., 311–315.
  * Golan and Shan [2016] Golan, G. and S. Shan (2016).  Nonempty intersection of longest paths in $2k\\_2$-free graphs.  arXiv preprint arXiv:1611.05967.
  * Hammer and Simeone [1981] Hammer, P. L. and B. Simeone (1981).  The splittance of a graph.  Combinatorica 1(3), 275–284.
  * Kratsch et al. [1996] Kratsch, D., J. Lehel, and H. Müller (1996).  Toughness, hamiltonicity and split graphs.  Discrete Mathematics 150(1), 231–246.
  * Kriesell [2002] Kriesell, M. (2002).  A survey on contractible edges in graphs of a prescribed vertex connectivity.  Graphs and Combinatorics 18(1), 1–30.
  * Maffray and Preissmann [1994] Maffray, F. and M. Preissmann (1994).  Linear recognition of pseudo-split graphs.  Discrete Applied Mathematics 52(3), 307–312.
  * Meister [2006] Meister, D. (2006).  Two characterisations of minimal triangulations of $2{K}_{2}$-free graphs.  Discrete Mathematics 306(24), 3327–3333.
  * Merris [2003] Merris, R. (2003).  Split graphs.  European Journal of Combinatorics 24(4), 413–430.
  * Paulusma et al. [2016] Paulusma, D., C. Picouleau, and B. Ries (2016).  Reducing the clique and chromatic number via edge contractions and vertex deletions.  In International Symposium on Combinatorial Optimization, pp. 38–49. Springer.
  * Paulusma et al. [2019] Paulusma, D., C. Picouleau, and B. Ries (2019).  Critical vertices and edges in H-free graphs.  Discrete Applied Mathematics 257, 361–367.
  * Plummer and Saito [2014] Plummer, M. D. and A. Saito (2014).  A note on graphs contraction-critical with respect to independence number.  Discrete Mathematics 325, 85–91.
  * S. Dhanalakshmi and Manogna [2016] S. Dhanalakshmi, N. S. and V. Manogna (2016).  On $2{K}_{2}$-free graphs.  International Journal of Pure and Applied Mathematics 109(7), 167–173.


# Ambient FSK Backscatter Communications using LTE Cell Specific Reference
Signals

Jingyi Liao, Xiyu Wang, Kalle Ruttik, Riku Jäntti, and Phan-Huy Dinh-Thuy  J.
Liao, X. Wang, K. Ruttik, and R. Jäntti are with Department of Information and
Communications Engineering, Aalto University, 02150 Espoo, Finland (email:
{firstname.lastname}@aalto.fi). Phan-Huy Dinh-Thuy is with Networks, Orange
Innovation, Chatillon, France (email: dinhthuy.phanhuy@orange.com).

###### Abstract

Long Term Evolution (LTE) signal is ubiquitously present in electromagnetic
(EM) background environment, which make it an attractive signal source for the
ambient backscatter communications (AmBC). In this paper, we propose a system,
in which a backscatter device (BD) introduces artificial Doppler shift to the
channel which is larger than the natural Doppler but still small enough such
that it can be tracked by the channel estimator at the User Equipment (UE).
Channel estimation is done using the downlink cell specific reference signals
(CRS) that are present regardless the UE being attached to the network or not.
FSK was selected due to its robust operation in a fading channel. We describe
the whole AmBC system, use two receivers. Finally, numerical simulations and
measurements are provided to validate the proposed FSK AmBC performance.

###### Index Terms:

Ambient Backscatter Communications, LTE Cell Specific Reference Signals,
Channel Estimation

##  I Introduction

Figure 1:  High level structure of the proposed system.

The introduction of ambient backscatter communications (AmBC) [1] in mobile
networks [2] has recently been proposed for the sustainable development of
asset tracking services [3], and to overcome the limitation of radio frequency
identification (RFID) based solutions.

In RFID-based asset tracking [4] an energy-autonomous and passive RFID tag is
illuminated by an RFID reader, with a radio frequency (RF) carrier-wave [5].
The tag reflects (backscatters) the wave in a modulated way to send its
message, and the reader detects the tag’s message in the variations of the
backscattered signal. As the tag harvests RF energy to power itself, the
reader-to-tag range is limited by the reader transmit power to several meters.
Tags can therefore be tracked only in places where manual readers or portals
are deployed. The short communication range would need to be compensated by
increasing the number of readers of portals, but a massive deployment of such
devices is not sustainable.

In comparison, AmBC systems [1] involve three communication nodes instead of
only two: an ambient source of RF signals, a backscatter device (BD) and an
AmBC receiver device. The BD is similar to a tag. The AmBC receiver reads the
BD’s message, without having to generate any RF carrier wave, as the BD is
already illuminated by the ambient source. In practice, a BD can be
implemented with an antenna connected to various matching impedances, through
an RF switch driven by a micro-controller. The BD switches between impedances
to modulate the reflection according to the message to be transmitted. In [3],
it is proposed to use a cellular base station (BS) as an ambient source, and
to use a user equipment (UE) as AmBC receiver, to develop a service of asset
tracking with ubiquitous coverage. It is almost “out-of-thin-air”: i.e.
without generating additional waves, without additional energy, and without
deploying massively new equipment such as portals. An energy-autonomous BD
harvesting solar energy, called crowd-detectable zero-energy-devices (CD-ZED)
is put on the asset to be tracked. Each time the BD (or CD-ZED) gets within
few meters of a UE (connected to the cellular network and geo-localised), the
BD is detected by the UE and this contact event is reported to the network.
Thanks to the anonymous participation of the crowd of UEs, the localisation of
the BD is tracked over the cellular network coverage area. Such CD-ZED concept
is one example of the more general category of energy-autonomous devices
called zero-energy devices (ZED) [6]. Such asset tracking service is one
example of ambient internet of things (AIoT) applications, currently being
discussed in standardisation for cellular networks [7]. Finally, ZED is one of
the key technologies identified for the building of a future and sustainable
6G [8].

The CD-ZED concept is applicable to all generations of mobile networks.
Ambient backscatters in 5G networks has been studied in [2] where it was shown
that BD can be detected by a UE as long as the UE is in the BS coverage and
the tag is close to the UE. This is confirmed by successful experiments of
ambient backscattering communications conducted with ambient signals from a
commercial 4th generation (4G), 5th generation (5G) networks in [3], in very
few test locations, far from the BS. The previous works [9, 10] used power
detector based receivers that have limited performance due to the high
variability of the mobile downlink signals. Very recently, to improve 4G AmBC
performance, [11] proposed to use knowledge about pilots of the ambient source
(i.e. the BS) at the AmBC receiver (i.e. UE) side. Previously similar approach
has been utilized in the context of Wi-Fi standard [12]. Unfortunately Wi-Fi
pilot transmission is sporadic and thus sub-optimal for reading BD signals. In
comparison, LTE pilot signals called cell specific reference signals (CRS)
[11] are always broadcasted by LTE base station. The CRS structure is
standardised and known and used by the UE to estimate the downlink channel. In
this paper, we propose to use the UE channel estimator as a receiver for the
BD messages.

Performance of AmBC receivers using LTE CRS knowledge is affected by BD
modulation method. In [11], on-off keying (OOK) modulation was used. That is,
BD switched between two load impedances. Unfortunately, a simple OOK signal
occupies frequencies where Doppler components from all the channel paths are
also present making it difficult to separate scattered path from the direct
path causing so called direct path interference [13]. In addition, the symbol
duration (i.e. switching period) used by BD tend to be long compared to the
channel coherence time making the BD signal vulnerable to fast fading.

Contributions. In this paper, we propose to use FSK type modulation in AmBC
system. For FSK backscatter signal, backscattered path is separated from the
direct path in frequency domain, so that the direct path interference can be
cancelled. BD introduced artificial frequency shift, which we referred to as
_frequency key_ , is selected to be higher than Doppler effect, and to be
lower than channel estimation tracking speed. Also, the fact that CRS signals
are presented only at certain orthogonal frequency division multiplex (OFDM)
symbols, limited the frequency key selection. Moreover, FSK allows for
noncoherent reception that does not depend on the channel parameters. The
contributions are listed as follows.

  * •

The BD signal is generated by the same OOK modulator as in [11], but the
generated waveform is selected to approximate FSK. We also discuss square wave
FSK that uses rectangular pulses instead of sinusoidal signals. We investigate
the impact of non-uniform CRS sampling frequency. The FSK frequency keys are
carefully selected to cooperate with non-uniform LTE CRS.

  * •

The AmBC receiver directly utilizes the channel estimates obtained from LTE
CRS pilot signal, instead of full channel state information. Two types of
receivers, coherent and noncoherent methods are proposed. The simulation
proves that coherent method outperforms energy detector.

  * •

Finally, the proposed system is validated by a proof-of-concept implementation
and corresponding measurements.

The paper is structured as follows: Section I introduces AmBC, motivation and
contribution of this work. Section II describes components of the proposed
system. Section III derives the signal model of the backscatter signal.
Section IV outlines the channel estimation algorithm at the AmBC receiver.
Section V presents proposed receiver structure. Section VI simulates this AmBC
system performance and designs a measurement to validate it. Finally, a
conclusion is draw in Section VII.

##  II System description

Figure 2:  LTE Release 8 Cell Specific Reference Signal for antenna ports
0,1,2, and 3.

We consider an AmBC system consisted of LTE BS (also referred to as NodeB)
acting as an ambient source, a UE acting as an AmBC receiver, and a BD as
illustrated in Fig. 1. UE uses the primary and secondary synchronization
signals transmitted by NodeB to achieve radio frame, subframe, and symbol
synchronicity with the BS. It also identifies the center of the channel
bandwidth and deduces the Physical Channel Identity (PCI). After this initial
acquisition process, UE uses downlink CRS to estimate the downlink channel.
Fig. 2 illustrates CRS for antenna ports 0 to 3. As can be seen from the Fig.
2, two channel estimations are obtained per 0.5 ms slot leading to 4 kHz non-
uniform channel sampling rate.

BD does not have a pulse shaping filter so it is limited to square pulses
which will cause it to have very wide bandwidth. The square wave frequency
shift keying is illustrated as subplot in Fig. 1. Since our receiver has
narrowband, aliasing is unavoidable which causes further challenge for the
receiver operation. Furthermore, since we did not implement clock drift
compensation, we needed to use noncoherent FSK receiver for the backscatter
symbols. A synchronization header is prefixed at the beginning of data packet.

The impulse response of the channel from BS to the AmBC receiver is

$\displaystyle h[\tau;t]$
$\displaystyle=x(t)\sum_{k\in\mathcal{K}_{0}}a_{k}[t]\delta[\tau-\tau_{k}(t)]$
(1)
$\displaystyle+\sum_{k\in\mathcal{K}_{1}}a_{k}[t]\delta[\tau-\tau_{k}(t)],$

where $a_{k}(t)$, $\tau_{k}(t)$ are the time varying amplitude and delay of
the $k^{\textrm{th}}$ multipath component and $\delta(\tau)$ denotes the
Dirac’s delta function. The bandwidth of the channel tap gain $a_{k}(t)$ is
defined by the Doppler $f_{D}$ frequency shift in the channel. In fig 1, the
direct path components $\mathcal{K}_{1}$ from an LTE NodeB to UE is indicated
by the thick arrow. The thin arrow from BS to UE via BD represents
$\mathcal{K}_{0}$ BD modulated scattered components.

##  III Back scattered signal

The BD performs load modulation on the incident signal illuminating its
antenna, in Fig. 3. That is, it varies its complex antenna load impedance
between two states $Z_{0}$ and $Z_{1}$. The BD reflection coefficient is given
by

$\Gamma_{x}=\frac{Z_{x}-Z_{a}^{*}}{Z_{x}+Z_{a}^{*}}$

where $Z_{x}$ denotes the load impedance in state $x\in\\{0,1\\}$ and $Z_{a}$
is the antenna impedance. In on-off keying case, we would in ideal case have
$Z_{0}=Z_{a}^{*}$ and $Z_{1}=0$ resulting in $\Gamma_{0}=0$ and
$\Gamma_{1}=-1$. In practical implementation, the load impedance is switched
by a diode as control circuit [14]. In Fig. 3, a micro controller unit (MCU)
controls that diode switch, which introduces artificial Doppler.

RF$T_{1}$$C_{1}$$T_{2}$$T_{3}$$C_{2}$$R_{1}$$D_{1}$$T_{4}$Ambient
signalMCU$x(t)$

Figure 3:  Circuit diagram of the BD.

In the previous work [11], OOK method was introduced for backscatter
communication. The impulse response of channel $h[\tau;t]$ are different when
BD in on ($x(t)=1$) or off ($x(t)=0$) status in Eq. 1.

$\displaystyle h_{\text{on}}[\tau;t]$
$\displaystyle=\sum_{k\in\mathcal{K}_{0}}a_{k}[t]\delta[\tau-\tau_{k}(t)]+\sum_{k\in\mathcal{K}_{1}}a_{k}[t]\delta[\tau-\tau_{k}(t)]$
$\displaystyle h_{\text{off}}[\tau;t]$
$\displaystyle=\sum_{k\in\mathcal{K}_{0}}a_{k}[t]\delta[\tau-\tau_{k}(t)]$

For OOK, ambient signal and Doppler effect strongly influence the channel
estimation. Compared with OOK, FSK shifts the frequency in spectrum and avoids
the influence of ambient LTE signal. FSK shifts RF ambient signal on different
frequency key. It is a good feature so that the frequency keys could be
specially designed to compromise Doppler effect and avoid influence of ambient
signal.

The BD aims at causing artificial Doppler that is higher than the natural
Doppler in the channel such that the receiver would be able to distinguish
between the direct path components (multipath components in $\mathcal{K}_{1}$)
and BD modulated scattered components (multipath component in
$\mathcal{K}_{0}$). BD does this by generating periodic rectangular wave
$\tilde{x}_{k}(t)=\tilde{x}_{k}(t+T_{k})$:

$\tilde{x}_{k}(t)=\sum_{n=-\infty}^{\infty}\mathsf{rect}\left[\frac{2(t-nT_{k})}{T_{k}}\right],\quad
k=0,1$

where $\mathsf{rect}(t)$ is the unit rectangular pulse and the index $k$
indicates whether bit 0 or 1 was transmitted. $\tilde{x}_{0}(t)$ and
$\tilde{x}_{1}(t)$ are sparse or tight square waves with infinite extension.
However, the BD symbol duration is $T_{BC}$, which is the red line in the
subplot of Fig. 1. Hence the generated BD pulse is

$x_{k}(t)=\mathsf{rect}\left(\frac{t}{T_{BC}}\right)\tilde{x}_{k}(t),\quad
k=0,1$

In time domain, $x_{0}(t)$ or $x_{1}(t)$ look like blue line segments in the
subplot of Fig. 1. The Fourier transform of the BD symbol is given by

$X_{k}(f)=\frac{T_{BC}}{2}\sum_{l=-\infty}^{\infty}\operatorname{sinc}\left(\frac{1}{2}l\right)\operatorname{sinc}\left[\left(f-\frac{l}{T_{k}}\right)T_{BC}\right]$

where $\operatorname{sinc}(x)=\sin(\pi x)/(\pi x)$. The harmonics of the
rectangular wave nominal frequency $l\frac{1}{T_{k}}$, $l=3,5,...$ attenuate
slowly implying that the square wave has a wide bandwidth.

##  IV LTE channel estimation

In the LTE system, the BS transmits CRS in every subframe. Fig. 2 illustrates
the CRS allocation for antenna ports 0 to 3 when the system is using normal
cyclic prefix. LTE networks may operate using different CRS configurations. In
a non-shifted CRS configuration, all cells use the same CRS time and frequency
resources. In a shifted CRS configuration, different cells transmit CRSs on
resources that are shifted in frequency. The non-shifted configuration avoids
CRSs interference on data transmissions, but is also associated with a
systematic CSI estimation error; especially noticeable at low traffic. Using
the shifted configuration, the CRSs interfere with data transmissions, but the
CSI estimation error is smaller [15]. In this paper, we consider the case of
shifted CRS, and the AmBC receiver uses pilots transmitted from antenna port
0.

In case of normal cyclic prefix, the OFDM symbol duration in LTE is
$T_{s}=71.4\;\mathrm{\mu s}$ except for the symbol 0 that has longer prefix.
Also since pilots are only present in symbols 0 and 4, we get irregular
sampling of the channel. Let $T_{slot}=0.5\;\mathrm{ms}$ denote the slot
length and let $\Delta T=4T_{s}-\frac{T_{slot}}{2}=35.6\;\mathrm{\mu s}$
denote the offset of the second channel sampling instant compared to regular
sampling interval $T_{r}=T_{slot}/2$. If samples in regular sampling interval
$T_{r}=0.25\;\mathrm{ms}$, that would lead to 4 kHz sampling frequency.

From the transmitted CRS, we obtain frequency domain channel estimates
$\hat{H}[n;t]$ for time instants $t\in\\{0,T_{slot}/2+\Delta
T,T_{slot},3/2T_{slot}+\Delta T,\cdots\\}$ during which pilots were send. $n$
is discrete frequency. Assuming that the channel stays approximately constant
during the transmission of single OFDM symbol, inverse Fast Fourier Transform
of $H[n;t]$ at time instants $t$ yields the following channel taps

$\displaystyle\hat{h}[l;t]$ $\displaystyle=$ $\displaystyle
x(t)\sum_{k\in\mathcal{K}_{0}}a_{k}^{b}(t)\mathsf{sinc}\left(l-\tau_{k}(t)W\right)$
$\displaystyle+$
$\displaystyle\sum_{k\in\mathcal{K}_{1}}a_{k}^{b}(t)\mathsf{sinc}\left(l-\tau_{k}(t)W\right)+z_{l}(t),$

where $W=\frac{1}{T_{s}}$ denotes the utilized bandwidth,
$a_{k}^{b}(t)=e^{-i2\pi f_{c}\tau_{k}(t)}a_{k}(t)$ denotes the baseband
equivalent channel tap of the $k^{\textrm{th}}$ multipath component, $f_{c}$
is the carrier frequency, and $z_{l}(t)$ denotes the the estimation noise,
AmBC signal $x(t)$ could be $x_{0}(t)$ or $x_{1}(t)$. The LTE system is
synchronized to the shortest path which appears in the first channel tap.
Backscattered signal component is likely to be much smaller than the direct
path component leading to very small signal-to-noise ratio (SNR). As a
consequence, the distance between BD and receiver is short in most practical
deployments and thus most of the BD scattered power would be in the first
channel tap. Hence, in the receiver it is sufficient to find just

$\hat{h}[0;t]=x(t)h_{0}(t)+h_{1}(t),$

where $h_{0}(t)$ and $h_{1}(t)$ contain the scattered and direct path
components that appear in the first channel tap after sampling.

Let ${s}(t)=\delta(t)+\delta(t-T_{slot}/2-\Delta T)$ be periodic sampling
signal ${s}(t+T_{slot})={s}(t)$ where $T_{slot}$ denotes the slot length and
$\Delta T$ denotes the time offset of the second pilot in the slot compared to
half of the slot time $T_{slot}/2$. Since $s(t)$ is periodic, we can express
it in terms of Fourier-series as

$\displaystyle s(t)=\sum_{l=\infty}^{\infty}s_{l}e^{i2\pi\frac{t}{T_{slot}}l}$

where the Fourier series coefficient are given by

$\displaystyle s_{l}$ $\displaystyle=$
$\displaystyle\frac{1}{T_{slot}}\int_{0}^{T_{slot}}s(t)e^{-i2\pi\frac{t}{T_{slot}}l}dt$
$\displaystyle=$
$\displaystyle\frac{1}{T_{slot}}\left(1+e^{-i\pi\left(1+2\frac{\Delta
T}{T_{slot}}\right)l}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{T_{slot}}\left(1+(-1)^{l}e^{-i2\pi\frac{\Delta
T}{T_{slot}}l}\right)$ $\displaystyle=$
$\displaystyle\frac{2}{T_{slot}}\frac{1+(-1)^{l}}{2}+\frac{1}{T_{slot}}(-1)^{l}\left(e^{-i2\pi\frac{\Delta
T}{T_{slot}}l}-1.\right)$

The sampled channel is $h_{s}(t)=\hat{h}[0;t]s(t)$. Now using the Fourier
series representation of $s(t)$ and taking the Fourier-transform of
$h_{s}(t)$, we obtain the Discrete Time Fourier Transform (DTFT) of the
sampled channel response:

$\displaystyle H_{s}(f)$ $\displaystyle=$
$\displaystyle\frac{2}{T_{slot}}\sum_{l=-\infty}^{\infty}H\left(f-\frac{2l}{T_{slot}}\right)$
$\displaystyle+$
$\displaystyle\frac{1}{T_{slot}}\sum_{l=-\infty}^{\infty}\varepsilon_{l}H\left(f-\frac{l}{T_{slot}}\right)$

where $\varepsilon_{l}=(-1)^{l}\left(e^{-i2\pi\frac{\Delta
T}{T_{slot}}l}-1\right)$.

The first (upper) sum corresponds to the spectrum of the channel sampled at
rate $\frac{2}{T_{slot}}=4$ kHz and the second (lower) sum contains additional
aliased components due to the irregularity of the sampling $\Delta T$. The
figure 5 shows that after sampling, the spectrum contains the desired FSK
signal, its harmonic components as well as aliased harmonics.

Even with 4 kHz sampling frequency, we would experience severe aliasing of the
harmonic components of the square waves. Due to irregular sampling, we will
see additional aliased components, but they are attenuated by the factor
$|\varepsilon_{l}|$. To be on the safe side, we select the square wave nominal
frequencies be on the range $f_{k}\in[200,1000]$ Hz. The lower limit is
selected to be larger than the natural Doppler in the channel such that the
direct path $h_{1}(t)$ can be filtered away using high-pass filter. The upper
frequency is selected to be small enough to avoid additional aliasing due to
irregular sampling.

Even if the two backscatter symbols $x_{0}(t)$ and $x_{1}(t)$ would have been
selected to be orthogonal, after sampling they will interfere with each other.
Due to aliasing, it turns out that orthogonal choices $f_{1}=Kf_{0}$ for
integer $K$ leads to high interference from aliased harmonics hitting the
other symbol. It is thus seems advantageous to take $K$ not to be integer.

##  V Receiver structure

The flow chart in Fig. 4 shows the algorithm steps of the proposed backscatter
receiver. In this section, the purposes of some steps in receiver are
elaborated on.

Figure 4: Flow chart of the proposed backscatter receiver.

###  V-A Band-pass Filter

It easy to assume BD symbol keeps frame synchronicity when received and
demodulated by UE. $m\in\mathbb{N}$ is defined as the $m$-th symbol
backscatter sending at time $t=mT_{BC}$.

Channel phase of scatter path $\mathrm{arg}\\{g_{0}(mT_{BC})\\}$ is ambiguous
due to synchronization. Power of the first channel tap $l=0$ does not contain
the phase uncertainty. The receiver only operates with channel tap power
$y[m]=|\hat{h}[0;m]|^{2}$.

If we don’t consider noise in the channel, the channel power approximately
satisfied the following relationship

$y[m]\approx x[m]\beta[m]+\alpha[m],$

where $x[m]$ is the BD signal, $\alpha[m]=|h_{1}(mT_{BC})|^{2}$, and
$\beta[m]=|h_{0}(mT_{BC})|^{2}+2{\mathrm{Re}}\\{h_{1}^{*}(mT_{BC})h_{0}(mT_{BC})\\}$,
considering the fact that $x^{2}[m]=x[m]$.

To separate this two channels, a high-pass filter and a low-pass filter is
required. High pass is designed to block $\alpha[m]$. And low-pass aims to
constrain the harmonic frequency and other interference. In practice, they can
be combined as a band-pass filter (BPF). Considering the frequency keys of FSK
are only several hundreds Hz, Doppler effect is the principle thereat of
propose backscatter receiver. Doppler effect and frequency drift of BS and UE
contribute to the channel change of $\alpha[m]$ and $\beta[m]$ in a small time
scale. By switching the BD at a higher frequency than the maximum Doppler in
the channel, the Doppler frequency is restrained by filter. With help of a
high-pass filter on $y[m]$ to remove the direct path interference $\alpha[m]$,
BD modulated path $\beta[m]$ component is distinguished in frequency domain.
Thus, two frequency keys of the BD FSK symbols left. In the base band, FSK
symbol is designed two frequency keys, namely $f_{0}$ and $f_{1}$.

$f_{k}=1/T_{k},\quad k=0,1$

###  V-B FSK Demodulator

After passing a high-pass filter and low-pass filter, received 2-FSK signal
$y_{f}[m]$ is demodulated. We propose both coherent and noncoherent, power
detection based method for the task in Fig. 6.

Figure 5:  Discrete Time Fourier Transfrom of the sampled FSK signal.

Both of them share one step, that is, filtering $y_{f}[m]$ at $f_{0}$ and
$f_{1}$ firstly. There are aliasing effect of two FSK as Fig. 5 illustrated.
Harmonic components of one FSK key could unfortunately hit another FSK key. A
BPF is applied to exclude others frequency leakage and to constrain
interference frequency. Denote $y_{f}[m]$ pass BPF at center frequency
$f_{0}$, as $y_{\text{f0}}[m]$, and $y_{f}[m]$ pass BPF at center frequency
$f_{1}$, as $y_{\text{f1}}[m]$.

Figure 6:  Flowchart of the FSK demodulator. We proposed both coherent and
noncoherent detectors. Flow chart (a) is shared step of both detectors. Flow
char (b) and (c) are energy detector and coherent method separately. Complete
energy detector is composed by (a) and (b). Also, total coherent method
consists of (a) and (c).

Energy detector compares the power of specturm $f_{0}\pm\Delta f$ and power of
spectrum $f_{1}\pm\Delta f$. An FSK symbol is decided based on the frequency
spectrum which contains higher power. For FSK symbol $x[m]$, hypothesis
testing $\mathcal{H}_{0}$ denotes that backsactter device sends $x[m]$ symbol
0. Similarly, hypothesis testing $\mathcal{H}_{1}$ refers that $x[m]$ is
symbol 1. So for energy detector,

$E\left[\left|y_{\text{f1}}[m](t)\right|^{2}\right]\mathrel{\begin{subarray}{c}\mathcal{H}_{0}\\\
\lessgtr\\\
\mathcal{H}_{1}\end{subarray}}E\left[\left|y_{\text{f0}}[m](t)\right|^{2}\right]$

Coherent method down convert the signal to base band by multiplying the signal
with $\exp\left(-j2\pi f_{c}t\right)$.

$\displaystyle y^{\prime}_{\text{f0}}[m](t)=y_{\text{f0}}[m](t)e^{-j2\pi
f_{0}t}$ $\displaystyle
y^{\prime}_{\text{f1}}[m](t)=y_{\text{f1}}[m](t)e^{-j2\pi f_{1}t}$

The decision is made by comparing the base band power of
$y^{\prime}_{\text{f0}}[m](t)$ and $y^{\prime}_{\text{f1}}[m](t)$. The base
band power is in fact the power of average signal. And then, the FSK symbol
decision is make based on the power comparison:

$\left|E\left[y^{\prime}_{\text{f1}}[m](t)\right]\right|^{2}\mathrel{\begin{subarray}{c}\mathcal{H}_{0}\\\
\lessgtr\\\
\mathcal{H}_{1}\end{subarray}}\left|E\left[y^{\prime}_{\text{f0}}[m](t)\right]\right|^{2}$

##  VI Simulation and Validation

###  VI-A Parameters

We propose to select FSK $f_{0}=300$ Hz and $f_{1}=650$ Hz, and $T_{BC}=40$ ms
which corresponds to six periods of the symbol ‘0’ wave, and 13 periods of the
symbol ‘1’ wave. A 200 Hz bandwidth BPF is applied in FSK demodulator with
different center frequency. $y_{\text{f0}}[m]$ is filtered by a bandwidth BPF
200 Hz at 300 Hz center frequency and $y_{\text{f1}}[m]$ is filtered by a BPF
bandwidth 200 Hz at 650 Hz center frequency.

The ambient signal is LTE CRS signal, whose paramters are given below.
Frequency Division Duplex (FDD) operation is assumed. BS, uses only antenna
port 0. That is, it has only single antenna. Also the UE is assumed to be
equipped only with a single antenna. The utilized downlink carrier frequency
is 486 MHz with bandwidth 7.68 MHz which accommodates 21 resource blocks.

###  VI-B Simulations

Free-space path loss (FSPL) model are applied on different propagation paths
with additive white Gaussian noise (AWGN) added in the channel. For
backscattered channel, the pathloss is the product of the two links: from
transmitter to BD and from BD to receiver [16]. No Doppler effect is
considered in this simulation. The channel impulse response $h(t)$ and FSPL is
supposed to obey

$L=\left(\frac{4\pi D}{\lambda}\right)^{2}=E\left[|h(t)|^{2}\right],$ (2)

where $D$ is distance between Tx and Rx, $\lambda=c/f_{c}$ is wave length of
carrier frequency. The path loss $L$ here is in linear scale. In this
simualtion, the distance from Tx to Rx is 125 m, distance from Tx to BD is 130
m and distance from BD to Rx is 10 m. In the simulation we consider two
propagation paths are both non-line of night (NLOS), obey Rayleigh
distribution.

$y(t)=h_{0}(t)s(t)+R_{\text{on}}h_{1}(t)s(t)x(t)+n(t),$ (3)

where $R_{\text{on}}$ is the reflection coefficients of BD under ‘on’ status,
$h_{0}(t)$ and $h_{1}(t)$ are channel impulse response of scattered path and
direct path, $s(t)$ is LTE CRS ambient signal and $n(t)$ is AWGN. Depending on
symbols AmBC sent, $x(t)$ can be either $x_{0}(t)$ or $x_{1}(t)$. Footnote 0
refers to direct path between Tx and Rx, and footnote 1 refers to backscatter
communication path between Tx and Rx via BD. In ideal backscater, the
reflection coefficient is $\Gamma=-1$ when BD in ‘on’ state and $\Gamma=0$ in
the ’off’ state, but in practice these values tend to be closer to each other.

To model non-idealities, we assume that the BD attenuates the reflected signal
power by $-20\log_{10}(R_{\text{on}})=6$ dB.

Figure 7: Theoretical BER of AmBC signal, based on coherent and energy
detector.

In Fig. 7, there are two SNR defined. Red and blue x-axis are both SNR in dB
scale. The only difference is the definition of signal power in SNR.
$n(t)\sim\mathcal{CN}(0,\sigma_{n}^{2})$. The power of noise is
$P_{n}=\sigma_{n}^{2}.$

The blue x-axis on the bottom is based on CRS power and the red axis at the
top is for the received BD modulated signal power.

The power of the CRS is

$P_{s1}=E\left[|h_{0}(t)s(t)+R_{\text{on}}h_{1}(t)s(t)x(t)|^{2}\right]$

which corresponds to the LTE Reference Signal Received Power (RSRP) in the
absence of noise.

Hence for the blue x-axis, we have

$\text{SNR}_{1}=\frac{P_{s1}}{P_{n}}=\frac{E\left[|h_{0}(t)s(t)+R_{\text{on}}h_{1}(t)s(t)x(t)|^{2}\right]}{\sigma_{n}^{2}}.$

The red x-axis on the top treats backscatter FSK signal from backscatter as
the signal of interest.The backcatter signal SNR of AmBC is defined as

$\text{SNR}_{2}=\frac{E\left[|R_{\text{on}}h_{1}(t)s(t)x(t)|^{2}\right]}{\sigma_{n}^{2}}.$

As Eq. (3) illustrating, the power of two path difference is exactly

$\displaystyle 10\log{\left(\Delta L\right)}$ $\displaystyle=10\log
E\left[|h_{0}(t)|^{2}\right]-10\log
E\left[|h_{1}(t)|^{2}R_{\text{on}}^{2}\right]$ $\displaystyle=10\log
L_{0}-10\log L_{1}-20\log R_{\text{on}}.$

Using MATLAB LTE toolbox, LTE fading channel model is applied. Doppler
frequency shift is not considered in this simulation, although Doppler effect
influences a lot in practice. MIMO channel propagation is also not setup,
because transmitter and receiver antenna is assumed to be SISO. LTE downlink
channel estimator estimates the channel based on that CRS signal. None OFDM
symbol is interpolated between CRS pilots.

The coherent detector algorithm and energy detector algorithm are discussed in
subsection V-B FSK demodulator. To smooth the simulation BER curve, we
simulate various times of experiments. High BER points ($\text{BER}>0.01$)
simulate 10000 times Monte Carlo experiments. Low BER points ($\text{BER}\leq
0.01$) simulate 100000 times Monte Carlo experiments.

Simulation uses backscatter communication parameters as subsection VI-A
Parameters mentioned. Fig. 7 is the results of simulation. The energy detector
is always worse than coherent detector. Under low SNR, such as -3 dB, the two
methods have similar performance. The BER difference of two FSK demodulators
is small. But the performance at SNR = 5 dB, coherent detector is better one
order of magnitude than energy detector.

###  VI-C Backscatter signal synchronization

Figure 8: Backscatter frame format of the proposed backscatter.

A special backscatter frame structure is designed to find out the beginning of
a backscatter signal. Backscatter signal is synchronized by three sequences of
7-Barker code. As Fig. 8 showing, there are two parts in one backscatter
frame, synchronization header and data packet. At the beginning of one packet,
two continuous sequences of 7-bit Barker code (‘0000110’) followed by an
inverse 7-bit Barker code (‘1111001’) compose a synchronization header. Then
data packet attaches the synchronize header.

Between two backscatter packets, there is a short period that no FSK symbol is
sent, called sleep period. During sleep period, ambient signal is not shifted
and BD kept ‘off’ state.

Compared to previous work [11], clock signal to synchronize is canceled in the
proposed method. Sometimes, backscatter packets would be synchronized
incorrectly. In that case, the data bit error could be incredibly high (over
than one third). The synchronization header bits is already known, as a part
of backscatter communication protocol. By comparing known synchronization bits
with demodulated bits, we can evaluate the quality of Rx received data and
decide whether synchronization was successful or not. If the measurement
indicates that the synchronization failed, we discard the whole packet.

###  VI-D Measurements

This measurement is a validation of aforementioned simulation. Parameters are
same as subsection VI-A Parameters mentioned.

The transmitter is Rhode&Schwarz (R&D) SMBV100 signal generator with LTE
signal generator packet. The generator emits standard LTE signal with 50
resource block (7.68 MHz bandwidth) at 486 MHz carrier frequency and
transmission power is 15 dBm. The frame structure is for SISO system with
corresponding synchronization signal and pilots for cell ID 3.

The BD node is an in house design BD as Fig. 3. Control signal from MCU is
driven by RaspberryPi nano, an RP2040-based microcontroller board.

The receiver is a universal software radio peripheral (USRP), connected to a
laptop. Some post signal processing is executed on that laptop, using MATLAB.

####  VI-D1 Wired measurement

Figure 9: Wired measurement of a FSK modulated BD signal in spectrum. Figure
10: Wired measurement of a FSK modulated BD signal in spectrogram.

This experiment measures over the cables in the absence of direct path
component $h_{1}(t)$. A circulator routes signal from LTE signal generator to
BD and then from BD to USRP. Fig. 9 and 10 simply give the spectrum and
spectrogram of USRP receiver, respectively.

The two symbols are clearly visible in the spectrum as well as their aliased
harmonic components. In addition there is a strong DC component and a
component at 2 kHz corresponding to the uniform sampling frequency
$1/T_{slot}$, which arrows $f_{\text{Nyquist}}$ points to in Fig. 9. The
spectrum was obtained using Fast Fourier Transform directly on the measured
channel samples $\hat{h}[0,t_{s}]$ without compensating for the irregularity
of the underlying sampling process. From the spectrogram that illustrates how
the spectrum changes in time, we can clearly see the transmitted symbol
sequence ‘11001010’ by observing the power at the frequencies $f_{0}$ and
$f_{1}$. As illustrated in Fig. 9 around 0.5 s, there is a 100 ms sleep
period, presenting a peak at direct current (DC) component.

The specterogram of square-wave FSK is illustrated as Fig 10. There are two
frequency keys $f_{0}$ (300 Hz) and $f_{1}$ (650 Hz) appear alternately. The
peak of 2 kHz is caused by uniform sampling frequency $1/T_{slot}$, same as
Fig. 9. Other peaks in the spectrum, such as 900 Hz, is caused by alias from
other components on the spectrum or harmonic frequency.

####  VI-D2 Wireless measurement

Figure 11: Wireless measurement devices and site floor plan. Figure 12:
Wireless measured performance of AmBC in SNR and BER. Figure 13: Variation in
the measured received LTE signal power and the simulated backscatter signal
power at the 21 RX positions. The backscatter signal power is calculated using
the FSPL with exponent of 2.

Fig. 11 presents the measurement environment in Maarintie 8 in Aalto
University campus. The transmitter antenna R&S HK300 is located at the left
lower corner in the Figure. The BD node is in the middle of the corridor next
to the measurement point 9 (at 9 m from the wall). The receiver is USRP B205
unit and laptop running in house created C++ implementation of a LTE receiver,
connected to UDP port with MATLAB implementation of AmBC signal detection. The
receiver implements real time decoding of received AmBC signal.

Differently from results reported in Fig. 5 in the previous work [11], no
external clock is distributed between transmitter, BD, and receiver.

In particular, the measurement system cannot detect weak signal which is lower
than analog digital converter (ADC) in the environment. In Fig. 13, a
simulation is given for received power of weak backscatter signal as a
supplement. Simulation is based on the backscatter pathloss mode [16] and
completely ignores the impact of walls. It can be thus treated as an upper
bound for the actual backcattered power.

Data at some positions are lost, due to the high BER. If BER is too high, a
possible explanation is that backscatter frame is not correctly synchronized
by three 7-barker bits header. As subsection VI-C said, that data sequence is
meaningless if packet is asynchronized. In our measurement, if the BER is
higher than one over three, then that backscatter data packet is omitted.

In Fig. 12, the SNR and BER are measured in the Fig. 11 corridor, with step
0.2 m, from 2 m to 21 m. Relationship between BER and SNR roughly satisfies
the following relationship: low BER positions are usually under high SNR
environments. A sinusoidal tendency appears in SNR via distance. That periodic
phenomena in the tunnel corridor (6 m to 16 m) is distinct from other
positions. BER shows the same periodic regular pattern with SNR. In the room
2536 (distance less than 6 m), SNR starts to deteriorate. Then at the fork
road corner (between 16 m and 18 m), SNR decreases steeply.

Received ambient signal power at each measurement position is estimated based
on received LTE signal power. Step length of the LTE ambient signal power
measurement is 1 m, which is blue line in Fig. 13. Backscatter signal power is
calculated based on Friis transmission equation, which is red line in Fig. 13.
We assume transmitter to BD and BD to each measurement position propagation
paths are all line of sight. FSPL module is applied in estimation of
backscatter signal power, as Eq. (2). But this FSPL module is higher than that
of real backscatter signal power received on measurement positions. In
practice, the difference between ambient LTE signal power and backscatter
signal power is even larger than that in Fig. 13.

Measured LTE signal power (blue line in Fig. 13) for 8 m to 21 m approximately
obeys FSPL. Because BD is set at 9 m, simulated backscatter signal power
(orange line in Fig. 13) peaks at 9m. It shows a typical FSPL pattern via
distance. Comparing the two plots, Fig. 12 and Fig. 13, some noteworthy
contrasts is given as following. Around 6 m the LTE signal deteriorates. That
ambient signal attenuation also can be observed in Fig. 12. Around 6 m, SNR
decreases dramatically with BER jumping to a high level. A steep drop of LTE
signal power from 1 m to 2 m is believed to be caused by a metal door between
room 2045 and room 2536, which exactly between transmitter and measurement
receiver.

##  VII Conclusions

In this paper, we proposed a system that uses the LTE cell specific reference
signals and channel estimator for receiving backscatter modulated signals. The
BD utilized two square waves having different nominal frequencies to perform
frequency shift modulation. The proposed receiver was validated using over the
air measurements in an indoor environment. Based on our experimental results,
we can conclude that the LTE channel estimator offers a great potential to be
utilized for receiving backscattered signals in Ambient Internet of Things
applications.

##  VIII Acknowledgements

This work is in part supported by the European Project Hexa-X under grant
101015956 and Business Finland project eMTC under grant 8028/31/2022.

## References

  * [1] V. Liu, A. Parks, V. Talla, S. Gollakota, D. Wetherall, and J. R. Smith, “Ambient backscatter: Wireless communication out of thin air,” _ACM SIGCOMM computer communication review_ , vol. 43, no. 4, pp. 39–50, 2013.
  * [2] R. Fara, “Ambient backscatter communications in mobile networks,” in _PhD Thesis_ , 2021. [Online]. Available: https://hal-cnrs.archives-ouvertes.fr/hal-03788716/document
  * [3] D.-T. Phan-Huy, D. Barthel, P. Ratajczak, R. Fara, M. Di Renzo, and J. De Rosny, “Ambient backscatter communications in mobile networks: Crowd-detectable zero-energy-devices,” _IEEE Journal of Radio Frequency Identification_ , vol. 6, no. 0, pp. 660–670, 2022.
  * [4] K. Finkenzeller, “Rfid handbook: Fundamentals and applications in contactless smart cards, radio frequency identification and near–field communication,” _Wiley_ , no. 0, 2010.
  * [5] H. Stockman, “Communication by means of reflected power,” _Proceedings of the IRE_ , vol. 36, no. 10, pp. 1196–1204, 1948.
  * [6] G. Wikström, J. Peisa, P. Rugeland, N. Johansson, S. Parkvall, M. Girnyk, G. Mildh, and I. L. Da Silva, “Challenges and technologies for 6g,” in _2020 2nd 6G Wireless Summit (6G SUMMIT)_ , 2020, pp. 1–5.
  * [7] 3rd Generation Partnership Project (3GPP); Technical Specification Group Radio Access Network, “Ambient iot device characteristics and categorization,” _3GPP TSG RAN Meeting #98e_ , vol. RP-223400, 2022.
  * [8] M. A. Uusitalo, P. Rugeland, M. R. Boldi, E. C. Strinati, P. Demestichas, M. Ericson, G. P. Fettweis, M. C. Filippou, A. Gati, M.-H. Hamon, M. Hoffmann, M. Latva-Aho, A. Pärssinen, B. Richerzhagen, H. Schotten, T. Svensson, G. Wikström, H. Wymeersch, V. Ziegler, and Y. Zou, “6g vision, value, use cases and technologies from european 6g flagship project hexa-x,” _IEEE Access_ , vol. 9, pp. 160 004–160 020, 2021.
  * [9] J. Qian, A. N. Parks, J. R. Smith, F. Gao, and S. Jin, “IoT communications with $m$ -psk modulated ambient backscatter: Algorithm, analysis, and implementation,” _IEEE Internet of Things Journal_ , vol. 6, no. 1, pp. 844–855, 2019.
  * [10] J. E. Palmer, H. A. Harms, S. J. Searle, and L. Davis, “DVB-T passive radar signal processing,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 8, pp. 2116–2126, 2013.
  * [11] K. Ruttik, X. Wang, J. Liao, R. Jäntti, and P.-H. Dinh-Thuy, “Ambient backscatter communications using lte cell specific reference signals,” in _2022 IEEE 12th International Conference on RFID Technology and Applications (RFID-TA)_ , 2022, pp. 67–70.
  * [12] P. ZHANG, M. Rostami, P. Hu, and D. Ganesan, “Enabling practical backscatter communication for on-body sensors,” in _Proceedings of the 2016 ACM SIGCOMM Conference_ , ser. SIGCOMM ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 370–383. [Online]. Available: https://doi.org/10.1145/2934872.2934901
  * [13] R. Biswas, M. U. Sheikh, H. Yiğitler, J. Lempiäinen, and R. Jäntti, “Direct path interference suppression requirements for bistatic backscatter communication system,” in _2021 IEEE 93rd Vehicular Technology Conference (VTC2021-Spring)_ , 2021, pp. 1–5.
  * [14] B. Badihi, A. Liljemark, M. U. Sheikh, J. Lietzén, and R. Jäntti, “Link budget validation for backscatter-radio system in sub-1ghz,” in _2019 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2019, pp. 1–6.
  * [15] G. Madhugiri, C. Koutsimanis, and P. Skillermark, “Impact of csi optimization and crs selection on performance of lte release 8 networks,” in _2014 IEEE 79th Vehicular Technology Conference (VTC Spring)_ , 2014, pp. 1–5.
  * [16] J. D. Griffin and G. D. Durgin, “Complete link budgets for backscatter-radio and rfid systems,” _IEEE Antennas and Propagation Magazine_ , vol. 51, no. 2, pp. 11–25, 2009.