# Edge Contraction and Line Graphs

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 and line 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 paper, 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 [2]. 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 ([11]) notion of a _$k$
-contractible_ edge 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 [3].

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

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 paper, however, it translates this problem to
a new one, namely 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)\setminus S$ is independent and

  2. 2.

there is no corner in $V(G)\setminus 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)\setminus S$ is not
independent. Hence, there are two vertices $u,v\in V(G)\setminus 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)\setminus S$ is independent, the neighborhood of any vertex in
$V(G)\setminus S$ is a subset of $S$. For the sake of contradiction, assume
that there is a corner $u\in V(G)\setminus 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)\setminus 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)\setminus 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)\setminus 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)\setminus 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$. ∎

In the following section, we demonstrate how to use Theorem 4 by using it to
characterize claw-free graphs and line graphs.

##  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}$.

###  2.1 Claw-Free Graphs

A _claw_ is a star $S_{3}$. 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 [7]. Additionally, for more structural results about
claw-free graphs, please consult [4, 5]. 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.

Identifying the claw-free graphs among the graphs presented in Figure 1, we
obtain the following.

######  Corollary 17.

Bull is the only claw-free-split graph.

$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$ Figure 1: The 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: The 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)\setminus S$ is independent. Thus, any vertex in
$V(G)\setminus S$ is adjacent to vertices only in $S$. By Corollary 12, if
$v\in V(G)\setminus S$, then neither $|N(v)|=1$ nor $v$ is adjacent to $u$.

Let $v,w\in V(G)\setminus S$ such that $N(v)=N(w)$ where $|N(v)|=2$. W.l.o.g.,
assume that $N(v)=\\{r,s\\}$, however, $G/tu[\\{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)\setminus S$ such that $|N(v)|=|N(w)|=2$, then $N(v)\not=N(w)$.

Let $v,w,x\in V(G)\setminus 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)$. The graph $G/tx[\\{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)\setminus S$ such that $|N(v)|=|N(w)|=2$, then $G$ is isomorphic
to $H_{5}$ in Figure 2.

Let $v,w,x\in V(G)\setminus S$ such that $|N(v)|=|N(w)|=3$. W.l.o.g., assume
that $s$ is adjacent to $x$. The graph $G/sx[\\{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)\setminus S$ such that $N(v)=N(w)$ and $|N(v)|=3$, then $G$ is
isomorphic to $H_{3}$ in Figure 2.

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.

###  2.2 Line Graphs

The _line_ graph of a graph $G$, denoted by $L(G)$, is the graph whose vertex
set is the edge set of $G$ and two vertices in $L(G)$ are adjacent if and only
if the corresponding edges in $G$ intersect in a vertex. Line graphs were
characterized as follows.

######  Theorem 20 ([10, 9]).

A graph $G$ is a line graph if and only if its edges can be partitioned into
cliques where every vertex of $G$ belong to at most two of such cliques.

######  Theorem 21 ([1]).

A graph $G$ is a line graph if and only if $G$ is
$\\{L_{1},\dots,L_{9}\\}$-free.

We call a graph that is $\\{L_{1},\dots,L_{9}\\}$-exist _non-line_.

$L_{1}$$L_{2}$$L_{3}$$L_{4}$$L_{5}$$L_{6}$$L_{7}$$L_{8}$$L_{9}$ Figure 3: The
forbidden subgraphs in line graphs $L_{10}$$L_{11}$$L_{12}$$L_{13}$ Figure 4:
Critically non-line graphs

####  2.2.1 Critically Non-Line Graphs

We present the following proposition, which will be useful later.

######  Proposition 22.

Let $G$ be a critically non-line graph where $\\{r,s,t,u,v\\}\subset V(G)$
such that $\\{r,s,t\\}$ induces $P_{3}$ in $G$ and $rs,st,uv\in E(G)$. If
$w\in V(G)\setminus\\{r,s,t,u,v\\}$ is adjacent to $s$, then $w$ is adjacent
to $r$ or $t$.

###### Proof.

For the sake of contradiction, assume that $w\in V(G)\setminus\\{r,s,t,u,v\\}$
is adjacent to $s$ but neither $r$ nor $t$. However, $\\{r,s,t,w\\}$ is a claw
while $u,v$ are two adjacent vertices outside the claw, which is a
contradiction to Theorem 11. ∎

####  2.2.2 The critically non-line graphs that are $L_{1}$-exist

######  Lemma 23.

The graphs $L_{1},L_{10},\dots,L_{13}$ are the only critically non-line graphs
that are $L_{1}$-exist.

###### Proof.

By Proposition 18, it was proved that the graphs in Figure 2 are the graphs
that are critically claw-exist. Hence, we identify which of these graphs are
critically non-line. The graph $L_{1}$ is trivially critically non-line. Any
$L_{10}$-contraction and $L_{12}$-contraction has independence number $2$ and
order $4$. Thus, any $L_{10}$-contraction and $L_{12}$-contraction is claw-
free. Thus, $L_{10}$ and $L_{12}$ are critically non-line. Any
$L_{11}$-contraction has independence number $2$, order $5$, and maximum
degree $4$. Thus, any $L_{11}$-contraction is claw-free and $L_{2}$-free.
Thus, $L_{11}$ is a critically non-line. Any $L_{13}$-contraction has
independence number $2$ and, order $5$, and either maximum degree $4$ or three
vertices of degree $2$. Thus, any $L_{13}$-contraction is $L_{1}$-free and
$L_{2}$-free. Thus, $L_{13}$ is a critically non-line. Finally, we note that
contracting an edge incident to the vertex of degree $2$ in graph $H_{6}$ in
Figure 2 construct a graph that is isomorphic to $L_{2}$. Thus, that graph is
not critically non-line. ∎

####  2.2.3 The critically non-line graphs that are $L_{2}$-exist

######  Lemma 24.

The graph $L_{2}$ is the only critically non-line graph that is $L_{2}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
$G$ that is non-isomorphic to $L_{2}$ where $G$ has a vertex set
$S:=\\{r,s,t,u,v\\}$ that induces $L_{2}$ as in the following figure on right.

Let $w\in V(G)\setminus S$. By Theorem 11, we note that $V(G)\setminus S$ is
independent. By Corollary 12, the neighborhood of $w$ is neither one vertex
nor a set of two adjacent vertices. If the neighborhood of $w$ is two
nonadjacent vertices, then $w$ is adjacent to a non leaf vertex in a $P_{3}$,
but not to a leaf of the path, which contradicts Proposition 22.

$r$$s$$t$$u$$v$$G[S]$

By Corollary 12, the neighborhood of $w$ is not three vertices that induce
either $P_{3}$ or $C_{3}$. If $N(w)=\\{r,s,t\\}$, then $w$ is adjacent to a
nonleaf vertex $r$ while $\\{r,u,v\\}$ induces $P_{3}$ and $s,t$ are two
adjacent vertices, which contradicts Proposition 22. If
$N(w)=S\setminus\\{u\\}$, $N(w)=S\setminus\\{v\\}$, or
$N(w)=S\setminus\\{r\\}$, then $w$ is a corner dominated by a vertex in $S$
while $S$ induces $L_{2}$, which is a contradiction to Theorem 11. If
$\\{r,s,u,v\\}\subseteq N(w)$ (or similarly $\\{r,t,u,v\\}\subseteq N(w)$),
then in $G/tu$ the set $S\cup\\{w\\}$ induces $L_{8}$, which is a
contradiction to the assumption that $G$ is a critically non-line graph.
Finally, we prove that $L_{2}$ is a critically non-line graph to complete the
proof. Any $L_{2}$-contraction has independence number at most $2$ and order
$4$. Thus, any $L_{2}$-contraction is claw-free. Thus, $L_{2}$ is a critically
non-line graph. ∎

####  2.2.4 The critically non-line graphs that are $L_{3}$-exist

######  Lemma 25.

There is no critically non-line graph that is $L_{3}$-exist.

###### Proof.

For the sake of contradiction assume that there is a critically non-line graph
$G$ that is $L_{3}$-exist. Let $S$ be a vertex set in $G$ that induces a graph
isomorphic to $L_{3}$ where $u,v\in S$ such that $deg_{S}(u)=deg_{S}(v)=2$.
However, $G/uv[S]$ induces a graph isomorphic to $L_{2}$, which contradicts
the assumption that $G$ is a critically non-line. ∎

####  2.2.5 The critically non-line graphs that are $L_{4}$-exist

######  Lemma 26.

The graph $L_{4}$ is the only critically non-line graph that is $L_{4}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{4}$ where $G$ has a vertex set $S$
that induce $L_{4}$.

Assume that $S:=\\{r,s,t,u,v,w\\}$ as presented in the following figure on
right. Let $x\in V(G)\setminus S$. By Theorem 11, we note that $V(G)\setminus
S$ is independent. By Corollary 12, the neighborhood of $x$ is not one vertex
in $S$. According to the cardinality of the neighborhood of $x$ we partition
the proof to cases.

$r$$w$$s$$t$$u$$v$$G[S]$

Case $1$: The cardinality of the neighborhood of $x$ is $2$. By Corollary 12,
$x$ is nonadjacent to two adjacent vertices. If $N(x)=\\{r,w\\}$, then
$G/rx[S\cup\\{x\\}]$ induces $L_{3}$, which is a contradiction to the fact
that $G$ is a critically non-line graph. If $x$ is adjacent to $u$ (or
similarly to $v$), then $\\{r,s,u,x\\}$ induces a claw while $t$ is a corner
dominated by $s$ which is a contradiction to Theorem 11. Otherwise, $x$ is
adjacent to $s$ (or similarly $t$) in which $\\{s,u,v,x\\}$ induces a claw
while $t$ is a corner dominated by $s$ which is a contradiction to Theorem 11.
Thus, $|N(x)|\not=2$.

Case 2: The cardinality of the neighborhood of $x$ is $3$. By Corollary 12,
$x$ is nonadjacent to three vertices that induce either $P_{3}$ or $C_{3}$. If
$N(x)=\\{r,s,w\\}$ (or similarly $\\{r,t,w\\}$), then $\\{r,s,w,x\\}$ induces
a claw while $t$ is a corner dominated by $s$, which is a contradiction to
Theorem 11. If $N(x)=\\{r,u,w\\}$ (or similarly $N(x)=\\{r,v,w\\}$), then
$\\{x\\}\cup S\setminus\\{r\\}$ induces $L_{3}$ which is a contradiction to
Lemma 25. If $N(x)=\\{r,u,v\\}$ (or similarly $N(x)=\\{u,v,w\\}$), then
$\\{s,v,w,x\\}$ induces a claw while $t$ is a corner dominated by $s$, which
is a contradiction to Theorem 11. if $N(x)=\\{r,s,v\\}$ (or similarly
$\\{r,t,v\\},\\{s,u,w\\},\\{t,u,w\\}$), then $G/ru[\\{t,v,w,x\\}]$ induces a
claw, which is a contradiction to the fact that $G$ is a critically non-line
graph. Finally, if $N(x)=\\{r,s,t\\}$ (or similarly $N(x)=\\{s,t,w\\}$), then
in $G/vw$, $\\{t,u,v,x\\}$ induces a claw, which is a contradiction to the
assumption that $G$ is a critically non-line. Thus, $|N(x)|\not=3$.

Case 3: The cardinality of the neighborhood of $x$ is at least $4$. The
neighborhood of $x$ is neither $\\{r,s,t,u\\}$ nor $\\{s,t,v,w\\}$, otherwise
$x$ is a corner dominated by $u$ or $v$ respectively, which contradicts
Theorem 11. If $\\{r,s,w\\}\subseteq N(x)$ (or similarly $\\{r,t,w\\}\subseteq
N(x)$), then $\\{r,s,w,x\\}$ induces a claw while $t$ is a corner dominated by
$s$, which is a contradiction to Theorem 11. If $N(x)=\\{r,u,v,w\\}$, then
$\\{x\\}\cup S\setminus\\{r,w\\}$) induces $L_{2}$ while $r$ is a corner
dominated by $x$, which is a contradiction to Theorem 11. If
$N(x)=\\{r,s,u,v\\}$ (similarly $N(x)=\\{r,t,u,v\\}$, $N(x)=\\{s,u,v,w\\}$, or
$N(x)=\\{t,u,v,w\\}$), then $\\{t,v,w,x\\}$ induces a claw while $s$ is a
corner dominated by $v$, which is a contradiction to Theorem 11. If
$N(x)=\\{r,s,t,v\\}$ (or similarly $N(x)=\\{s,t,u,w\\}$), then in $G/vx$,
$\\{r,s,t,u,x\\}$ induces $L_{2}$, which is a contradiction to the assumption
that $G$ is a critically non-line graph. If $S\setminus\\{r,w\\}\subseteq
N(x)$, then $\\{x\\}\cup S\setminus\\{r,w\\}$ induces $L_{8}$ while $r$ is a
corner dominated by $u$, which is a contradiction to Theorem 11. Consequently,
$|N(x)|\not\geq 4$.

Finally, we prove that $L_{4}$ is a critically non-line to complete the proof.
Any $L_{4}$-contraction has a vertex with degree $1$, its order is $5$,
independence number at most $3$ and no vertex with degree three has more than
two independent vertices in its neighborhood. Hence, any $L_{4}$-contraction
is $\\{L_{1},L_{2}\\}$-free. Thus, $L_{4}$ is a critically non-line graph. ∎

####  2.2.6 The critically non-line graphs that are $L_{5}$-exist

######  Lemma 27.

The graph $L_{5}$ is the only critically non-line graph that is $L_{5}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{5}$ where $G$ has a vertex set $S$
that induces $L_{5}$.

Assume that $S:=\\{r,s,t,u,v,w\\}$ that induces $L_{5}$ as in the following
figure on right and $x\in V(G)\setminus S$. By Theorem 11, we note that
$V(G)\setminus S$ is independent. By Corollary 12, the neighborhood of $x$ is
not one vertex in $S$. According to the cardinality of the neighborhood of $x$
we partition the proof to cases.

$r$$s$$t$$u$$v$$w$$G[S]$

Case $1$: The cardinality of the neighborhood of $x$ is $2$. By Corollary 12,
$x$ is nonadjacent to two adjacent vertices. If $N(w)=\\{r,w\\}$ (or similarly
$N(w)=\\{r,v\\}$), then $\\{x\\}\cup S\setminus\\{v\\}$ induces $L_{3}$ which
is a contradiction to Lemma 25. Otherwise, $x$ is adjacent to a vertex with
two independent neighbors where $x$ is adjacent to neither, which contradicts
Proposition 22. Consequently, $|N(x)|\not=2$.

Case $2$: The cardinality of the neighborhood of $x$ is $3$. If
$N(x)=\\{r,s,w\\}$ (or similarly $\\{r,s,v\\}$), then $\\{x\\}\cup
S\setminus\\{r,v\\}$ induces $L_{2}$ while $v$ is a corner dominated by $t$
which is a contradiction to Theorem 11. If $N(x)=\\{r,t,u\\}$, then
$\\{s,t,w,x\\}$) induces a claw while $u$ is a corner dominated by $t$, which
is a contradiction to Theorem 11. If $N(x)=\\{r,t,v\\}$ (similarly
$N(x)=\\{r,t,w\\}$, $N(x)=\\{r,u,v\\}$, or $N(x)=\\{r,u,w\\}$), then
$\\{s,t,w,x\\}$ induces a claw while $u$ is a corner dominated by $t$, which
is a contradiction to Theorem 11. If $N(x)=\\{r,v,w\\}$, then $\\{x\\}\cup
S\setminus\\{w\\}$ induces $L_{3}$ which is a contradiction to Lemma 25.
Finally, if $N(x)=\\{s,v,w\\}$, then $\\{x\\}\cup S\setminus\\{r,w\\}$ induces
$L_{2}$ while $w$ is a corner dominated by $u$ which is a contradiction to
Theorem 11. Consequently, $|N(x)|\not=3$.

Case $3$: The cardinality of the neighborhood of $x$ is $4$. If
$N(x)=\\{r,s,t,u\\}$ (similarly $\\{s,t,u,v\\}$, $\\{s,t,u,w\\}$,
$\\{s,t,v,w\\}$, $\\{s,u,v,w\\}$, or $\\{t,u,v,w\\}$), then $x$ is a corner
dominated by a vertex in its neighborhood, which contradicts Theorem 11. If
$N(x)=\\{r,s,t,w\\}$ (similarly $\\{r,s,t,v\\}$, $\\{r,s,u,w\\}$, or
$\\{r,s,u,v\\}$), then $\\{x\\}\cup S\setminus\\{u\\}$ induces $L_{7}$ while
$u$ is a corner dominated by $t$, which is a contradiction to Theorem 11. If
$N(x)=\\{r,t,u,v\\}$ (or similarly $N(x)=\\{r,t,u,w\\}$), then in $G/xv$ the
set $\\{x\\}\cup S\setminus\\{w\\}$ induces $L_{2}$ which is a contradiction
to the assumption that $G$ is a critically non-line graph. if
$N(x)=\\{r,s,v,w\\}$, then in $G/rs$ the set $\\{x\\}\cup S\setminus\\{w\\}$
induces $L_{2}$ which is a contradiction to the assumption that $G$ is a
critically non-line. Finally, if $N(x)=\\{r,u,v,w\\}$ (or similarly
$\\{r,t,v,w\\}$), then in $G/xv$ the set $\\{x\\}\cup S\setminus\\{w\\}$
induces $L_{2}$ which is a contradiction to the assumption that $G$ is a
critically non-line. Consequently, $|N(x)|\not=4$.

Case $4$: The cardinality of the neighborhood of $x$ is at least $5$. If
$N(x)=S\setminus\\{r\\}$, then $S$ induces $L_{5}$ while $x$ is a corner
dominated by $t$, which is a contradiction to Theorem 11. If $x$ is
nonadjacent to $s$, then $\\{x\\}\cup S\setminus\\{v,w\\}$ induces $L_{2}$
while $w$ is a corner dominated by $x$, which is a contradiction to Theorem
11. If $\\{r,s\\}\subseteq N(x)$ and $|N(x)|=5$, then $\\{x\\}\cup
S\setminus\\{r,s\\}$ induces $L_{8}$ while $r$ is a corner dominated by $x$,
which is a contradiction to Theorem 11. Otherwise, $\\{x\\}\cup
S\setminus\\{r,v\\}$ induces $L_{8}$ while $r$ is a corner dominated by $x$,
which is a contradiction to Theorem 11. Consequently, $|N(x)|\not\geq 5$.

Finally, we prove that $L_{5}$ is a critically non-line to complete the proof.
Any $L_{5}$-contraction has independence number at most $2$ and a vertex with
degree $1$ or an induced subgraph isomorphic to $K_{4}$. Hence, any
$L_{5}$-contraction is $\\{L_{1},L_{2}\\}$-free. Thus, $L_{5}$ is a critically
non-line graph. ∎

####  2.2.7 The critically non-line graphs that are $L_{6}$-exist

######  Lemma 28.

The graph $L_{6}$ is the only critically non-line graph that is $L_{6}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{6}$ where $G$ has a vertex set
$S:=\\{r,s,t,u,v,w\\}$ that induces $L_{6}$.

Assume that $G[S]$ is labeled as in the following figure on right. By Theorem
11, we note that $V(G)\setminus S$ is independent. By Corollary 12, there is
no vertex $x\in V(G)\setminus S$ whose neighborhood is one vertex in $S$, or
two adjacent vertices in $S$. Moreover, $x$ is nonadjacent to $t$ or $u$.

$r$$s$$t$$u$$v$$w$$G[S]$

If $x$ is adjacent to two independent vertices say $r,v$, then
$\\{r,t,u,v,x\\}$ induces a graph isomorphic to $L_{2}$ while $w$ is a corner
dominated by $v$, which contradicts Theorem 11. We complete the proof by
showing that $L_{6}$ is a critically non-line. Any $L_{6}$-contraction has
independence number $2$, order $5$, and a vertex with degree $4$. Hence any
$L_{6}$-contraction is $\\{L_{1},L_{2}\\}$-free. Thus, $L_{6}$ is a critically
non-line. ∎

####  2.2.8 The critically non-line graphs that are $L_{7}$-exist

######  Lemma 29.

The graph $L_{7}$ is the only critically non-line graph that is $L_{7}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{7}$ where $G$ has a vertex set $S$
that induce $L_{7}$.

Assume that $G[S]$ is labeled as in the figure on the right and $x\in
V(G)\setminus S$. By Theorem 11, we note that $V(G)\setminus S$ is
independent. By Corollary 12, the neighborhood of $x$ is not one vertex in
$S$. According to the cardinality of the neighborhood of $x$ we consider four
proof cases.

$r$$s$$t$$u$$v$$w$$G[S]$

Case $1$: The cardinality of the neighborhood of $x$ is $2$. By Corollary 12,
$x$ is nonadjacent to two adjacent vertices. If $N(w)=\\{s,v\\}$, then in
$G/st$ $\\{x\\}\cup S\setminus\\{r\\}$ induces $L_{2}$, which contradicts the
assumption that $G$ is a critically non-line graph. Otherwise, $x$ is adjacent
to a vertex that is adjacent to two independent vertices while $x$ is
nonadjacent to any of them. Hence, the four vertices induces claw while there
is two other adjacent vertices outside the claw, which is a contradiction to
Theorem 11. Thus, $|N(x)|\not=2$.

Case $2$: The cardinality of the neighborhood of $x$ is $3$. By Corollary 12,
$x$ is nonadjacent to any three vertices that induce either $P_{3}$ or
$C_{3}$. If $N(w)=\\{r,s,v\\}$ (or similarly $N(w)=\\{s,v,w\\}$), then in
$G/rt$ the set $\\{x\\}\cup S\setminus\\{s\\}$ induces $L_{3}$, which
contradicts the assumption that $G$ is a critically non-line graph. Otherwise,
$x$ is adjacent to a vertex that is adjacent to two independent vertices while
$x$ is nonadjacent to any of them. Hence, the four vertices induce claw while
there are two other adjacent vertices outside the claw, which is a
contradiction to Theorem 11. Thus, $|N(x)|\not=3$.

Case $3$: The cardinality of the neighborhood of $x$ is $4$. If $y\in N(x)$,
then $(N(x)\setminus\\{y\\})\not\subseteq N(y)$, otherwise $x$ is a corner
dominated by $y$. If $N(x)=\\{r,s,v,w\\}$, then $G/rs[\\{x\\}\cup
S\setminus\\{v\\}]$ induces $L_{2}$, which contradicts the assumption that $G$
is a critically non-line. Furthermore, if $N(x)=\\{r,s,t,v\\}$ (similarly
$N(x)=\\{s,u,v,w\\}$), however, $G/rt[\\{x\\}\cup S\setminus\\{s\\}]$ induces
$L_{2}$, which contradicts the assumption that $G$ is a critically non-line
graph. Moreover, if $N(x)=\\{r,s,u,v\\}$ (similarly $N(x)=\\{s,t,v,w\\}$),
then in $G/tw$ the set $\\{,u,v,w,x\\}$ induces $L_{2}$, which contradicts the
assumption that $G$ is a critically non-line graph. Otherwise, $x$ has a
neighbor $y$ that is adjacent to two independent vertices while $x$ is
nonadjacent to any of them. Hence, the four vertices induces claw while there
are two other adjacent vertices outside the claw, which is a contradiction to
Theorem 11. Thus, $|N(x)|\not=4$.

Case $4$: The cardinality of the neighborhood of $x$ is at least $5$. If $x$
is nonadjacent to $s$ (or $v$), then $x$ is a corner dominated by $t$ (or
$u$), which is a contradiction to Theorem 11. Furthermore, if $x$ is
nonadjacent to $r$ (or similarly $x$ is nonadjacent to $w$), then $\\{x\\}\cup
S\setminus\\{r,v\\}$ induces $L_{8}$ in $G/ru$, which contradicts the
assumption that $G$ is a critically non-line graph. Otherwise, $x$ is
nonadjacent to $t$ (or $u$) or adjacent to all vertices in $S$, then
$\\{x\\}\cup S\setminus\\{v\\}$ induces $L_{8}$ in $G/st$, yielding the same
contradiction. Thus, $|N(x)|\not\geq 5$.

Finally, to complete the proof, we prove that $L_{7}$ is a critically non-
line. Any $L_{7}$-contraction has independence number $2$, order $5$, and a
vertex with degree either $4$ or $1$. Hence any $L_{7}$-contraction is
$\\{L_{1},L_{2}\\}$-free. Thus, $L_{7}$ is a critically non-line graph. ∎

####  2.2.9 The critically non-line graphs that are $L_{8}$-exist

######  Lemma 30.

The graph $L_{8}$ is the only critically non-line graph that is $L_{8}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{8}$ where $G$ has a vertex set $S$
that induce $L_{8}$.

Assume that $G[S]$ is labeled as in the figure at the right. By Theorem 11, we
note that $V(G)\setminus S$ is independent. By Corollary 12, we conclude that
there is no vertex in $V(G)\setminus S$ whose neighborhood is one vertex in
$S$. Furthermore, no vertex in $V(G)\setminus S$ exists that is adjacent to
any vertex in $\\{r,s,t\\}$.

$r$$s$$t$$u$$v$$G[S]$

Furthermore, there is no vertex $w$ in $V(G)\setminus S$ that is adjacent to
both $u,v$, otherwise, in $G/rt$ the set $\\{s,t,u,v,w\\}$ induces a graph
isomorphic to $L_{2}$, which contradicts that $G$ is a critically non-line
graph. Finally to complete our proof, we prove that $L_{8}$ is a critically
non-line. Contracting any edge in $L_{8}$ generates a graph with independence
number $2$ and order $4$, which is claw-free graph. Thus, $L_{8}$ is a
critically non-line. ∎

####  2.2.10 The critically non-line graphs that are $L_{9}$-exist

######  Lemma 31.

The graph $L_{9}$ is the only critically non-line graph that is $L_{9}$-exist.

###### Proof.

For the sake of contradiction, we assume that there is a critically non-line
graph $G$ that is non-isomorphic to $L_{9}$ where $G$ has a vertex set $S$
that induces $L_{9}$.

Assume that $G[S]$ is labeled as in the figure at the right. By Theorem 11, we
note that $V(G)\setminus S$ is independent. By Corollary 12, there is no
vertex $V(G)\setminus S$ whose neighborhood is one vertex in $S$, two adjacent
vertices, or three vertices inducing $P_{3}$. Furthermore, no vertex in
$V(G)\setminus S$ is adjacent to $r$. By Proposition 22, the neighborhood of
$x$ is neither a pair of nonadjacent vertices nor three vertices.

$r$$s$$t$$u$$v$$w$$G[S]$

If the neighborhood of $x$ is four vertices in $S\setminus\\{r\\}$, say
$S\setminus\\{r,s\\}$, then $\\{r,s,t,w,x\\}$ induces $L_{2}$ while $u,v$ are
adjacent, which is a contradiction to Theorem 11. If $x$ is adjacent to every
vertex in $S\setminus\\{r\\}$, then In $G/rs$, $\\{r,u,v,w,x\\}$ induces
$L_{8}$ which contradicts the assumption that $G$ is a critically non-line
graph. Finally to complete the proof, we prove that $L_{9}$ is a critically
non-line graph. Any $L_{9}$-contraction has independence number $2$ and a
maximum degree $4$. Thus, any $L_{9}$-contraction is $\\{L_{1},L_{2}\\}$-free.
Thus, $L_{9}$ is a critically non-line graph. ∎

By Lemmas 23 to 31, we deduce the following.

######  Theorem 32.

The graphs in $\\{L_{1},\dots,L_{13}\\}-\\{L_{3}\\}$ are the critically non-
line graphs.

####  2.2.11 Line-Split Graphs

######  Theorem 33.

The graphs $L_{14},\dots,L_{34}$ are line graphs.

###### Proof.

We note that the edge sets of the graphs $L_{14},\dots,L_{34}$ can be
partitioned cliques such that every vertex is contained in at most two of such
cliques. Thus, by Theorem 20 the result follows. ∎

######  Theorem 34.

The set $\operatorname{elm}(\\{L_{14},\dots,L_{34}\\})$ is equivalent to the
set of graphs $\\{L_{14},\dots,\\\ L_{21}\\}$.

###### Proof.

The graphs $L_{22},\dots,L_{32}$ are $L_{14}$-exist. The graph $L_{33}$ is
$L_{20}$-exist. The graph $L_{34}$ is $L_{15}$-exist. Moreover, it is not hard
to see that the graphs $\\{L_{14},\dots,L_{21}\\}$ are minimal. ∎

$L_{14}$$L_{15}$$L_{16}$$L_{17}$$L_{18}$$L_{19}$$L_{20}$$L_{21}$ Figure 5: The
$\operatorname{elm}$(line-split) graphs
$L_{22}$$L_{23}$$L_{24}$$L_{25}$$L_{26}$$L_{27}$$L_{28}$$L_{29}$$L_{30}$$L_{31}$$L_{32}$$L_{33}$$L_{34}$
Figure 6: The line-split graphs that are not $\operatorname{elm}$(line-split)
graphs

####  2.2.12 L1-split graphs that are line

######  Lemma 35.

The graph $L_{14}$ is the only $L_{1}$-split graph that is line.

###### Proof.

To obtain the $L_{1}$-free-split graphs that are line, we construct the set of
graphs $splitting(L_{1})$ followed by identifying among it the graphs that are
line.

Hence, we partition the vertex set into its orbits generated by the
automorphism group. Afterwards, we select an arbitrary vertex from every orbit
and construct the set of graphs $splitting(L_{1})$ related to such vertex and
identify the line graphs among them. The graph $G$ on the right is a labeled
$L_{1}$ graph whose vertex set admits the following partition into its orbits
$\\{\\{r\\},\\{s,t,u\\}\\}$. W.l.o.g, we choose an arbitrary vertex from every
block from the partition. Hence we have two cases.

$r$$s$$t$$u$$G$

Case 1, vertex $r$: we replace $r$ by two adjacent vertices $r_{1}$ and
$r_{2}$. If $r_{1}$ or $r_{2}$ is adjacent to $\\{s,t,u\\}$ then the
constructed graphs is claw-exist. Otherwise, the constructed graphs are either
isomorphic to $L_{14}$ or claw-exist. Thus, the line graph in $splitting(G,r)$
is $L_{14}$.

Case 2, vertex $s$: we replace $s$ by two adjacent vertices $s_{1}$ and
$s_{2}$. At least one of $s_{1}$ and $s_{2}$ is adjacent to $r$, say $s_{1}$.
Hence $\\{r,s_{1},t,u\\}$ induces claw. Thus, there is no line graph in
$splitting(G,s)$. ∎

The proofs of Lemma 36 to 43 are similar to the proof of Lemma 35. Hence, we
present sketches of the proofs for the interested readers.

####  2.2.13 L2-split graphs that are line

######  Lemma 36.

The graphs $L_{15}$ and $L_{16}$ are the only $L_{2}$-split graphs that are
line.

###### Proof.

The graph $G$ on the right is a labeled $L_{2}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r\\},\\{s,t\\},\\{u,v\\}\\}$.

W.l.o.g, we arbitrarily choose a vertex from every block from the partition.
Hence we have three cases.

Case 1,vertex $r$: the $L_{2}$-free-split graph in $splitting(G,r)$ is
$L_{3}$. Thus, no $L_{2}$-free-split graph in $splitting(G,r)$ is line.

$r$$s$$t$$u$$v$$G$

Case 2, vertex $s$: the $L_{2}$-free-split graphs in $splitting(G,s)$ are
$L_{1}$-exist or isomorphic to $L_{15}$. Thus, the graph in $splitting(G,s)$
that is line is $L_{15}$.

Case 3, vertex $u$: the $L_{2}$-free-split graphs in $splitting(G,u)$ are
$L_{1}$-exist, $L_{3}$-exist, or isomorphic to either $L_{15}$ or $L_{16}$.
Thus, the graphs in $splitting(G,u)$ that are line are $L_{15}$ or $L_{16}$. ∎

####  2.2.14 L3-split graphs that are line

######  Lemma 37.

The graphs $L_{22}$ and $L_{23}$ are the only $L_{3}$-split graphs that are
line.

###### Proof.

The graph $G$ on the right is a labeled $L_{3}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r,w\\},\\{s,t\\},\\{u,v\\}\\}$.
W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have three cases.

Case 1, vertex $r$: the $L_{3}$-free-split graph in $splitting(G,r)$ is a
graph that is $L_{4}$-exist. Thus, no $L_{3}$-split graph in $splitting(G,r)$
is line.

Case 2, vertex $s$: the $L_{3}$-free-split graphs in $splitting(G,s)$ are
$L_{1}$-exist or isomorphic to $L_{22}$. Thus, the $L_{3}$-split graph in
$splitting(G,s)$ that is line is $L_{22}$.

$r$$w$$s$$t$$u$$v$$G$

Case 3, vertex $u$: the $L_{3}$-free-split graphs in $splitting(G,u)$ are
$L_{1}$-exist, $L_{4}$-exist, or isomorphic to either $L_{22}$ or $L_{23}$.
Thus, the $L_{3}$-split graphs in $splitting(G,u)$ that are line are $L_{22}$
and $L_{23}$. ∎

####  2.2.15 L4-split graphs that are line

######  Lemma 38.

The graphs $L_{24}$ and $L_{25}$ are the only $L_{4}$-split graphs that are
line.

###### Proof.

The graph $G$ is a labeled $L_{4}$ graph whose vertex set admits the following
partition into its orbits $\\{\\{r,w\\},\\{s,t\\},\\{u,v\\}\\}$.

W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have three cases.

Case 1, vertex $r$: there is no $L_{4}$-free-split graph in $splitting(G,r)$.

Case 2, vertex $s$: the $L_{4}$-free-split graphs in $splitting(G,s)$ are
$L_{1}$-exist or isomorphic to $L_{24}$. Thus, the $L_{4}$-split graph in
$splitting(G,s)$ that is line is $L_{24}$.

$r$$w$$s$$t$$u$$v$$G$

Case 3, vertex $u$: the $L_{4}$-free-split graphs in $splitting(G,u)$ are
$L_{1}$-exist or isomorphic to either $L_{24}$ or $L_{25}$. Thus, the
$L_{4}$-split graphs in $splitting(G,u)$ that are line are $L_{24}$ and
$L_{25}$. ∎

####  2.2.16 L5-split graphs that are line

######  Lemma 39.

The graphs $L_{17},L_{26},L_{27}$, and $L_{28}$ are the only $L_{5}$-split
graphs that are line.

###### Proof.

The graph $G$ on the right is a labeled $L_{5}$ graph whose vertex set admits
the following partition into its orbits
$\\{\\{r\\},\\{s\\},\\{t,u\\},\\{v,w\\}\\}$. W.l.o.g, we choose an arbitrary
vertex from every block out of the partition. Hence we have four cases.

Case 1, vertex $r$: there is no line graph in $splitting(G,r)$.

Case 2, vertex $s$: the $L_{5}$-free-split graphs in $splitting(G,s)$ are
$L_{1}$-exist or isomorphic to either $L_{26}$ or $L_{17}$. Thus, $L_{26}$ and
$L_{17}$ are the only $L_{5}$-split graphs in $splitting(G,s)$ that are line.

Case 3, vertex $t$: the $L_{5}$-free-split graphs in $splitting(G,t)$ are
$L_{1}$-exist, $L_{2}$-exist, or isomorphic to one of the following graphs:
$L_{26}$,$L_{27}$, and $L_{28}$. Consequently, the only line graphs in the
family of $L_{5}$-split graphs are $L_{26}$, $L_{27}$, and $L_{28}$.

$r$$s$$t$$u$$v$$w$$G$

Case 4, vertex $v$: the $L_{5}$-free-split graphs in $splitting(G,v)$ are
$L_{1}$-exist or isomorphic to $L_{27}$. Thus, $L_{27}$ is the only
$L_{5}$-split graph in $splitting(G,v)$ that is line. ∎

####  2.2.17 L6-split graphs that are line

######  Lemma 40.

The graphs $L_{18},L_{19},$ and $L_{33}$ are the only $L_{6}$-split graphs
that are line.

###### Proof.

The graph $G$ on the right is a labeled $L_{6}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r,s,v,w\\},\\{t,u\\}\\}$.
W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have two cases.

Case 1, vertex $r$: the $L_{6}$-free-split graphs in $splitting(G,r)$ are
$L_{1}$-exist or isomorphic to $L_{18}$. Thus, $L_{18}$ is the only
$L_{6}$-split graph in $splitting(G,r)$ that is line.

Case 2, vertex $t$: the $L_{6}$-free-split graphs in $splitting(G,t)$ are
$L_{1}$-exist, $L_{2}$-exist, $L_{8}$-exist or isomorphic to either $L_{18}$,
$L_{19}$, or $L_{33}$.

$r$$s$$t$$u$$v$$w$$G$

Thus, $L_{18}$, $L_{19}$, and $L_{33}$ are the only $L_{6}$-split graphs in
$splitting(G,t)$ that are line. ∎

####  2.2.18 L7-split graphs that are line

######  Lemma 41.

The graphs $L_{29},L_{30},L_{31}$, and $L_{32}$ are the only $L_{7}$-split
graphs that are line.

###### Proof.

The graph $G$ on the right is a labeled $L_{7}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r,w\\},\\{s,v\\},\\{t,u\\}\\}$.

W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have three cases.

Case 1, vertex $r$: the $L_{7}$-free-split graphs in $splitting(G,r)$ are
$L_{1}$-exist. Thus, there is no $L_{7}$-split graph in $splitting(G,r)$ that
is line.

Case 2, vertex $s$: the $L_{7}$-free-split graph in $splitting(G,s)$ is
$L_{1}$-exist. Thus, there is no $L_{7}$-free-split graph in $splitting(G,s)$
that is line.

$r$$s$$t$$u$$v$$w$$G$

Case 3, vertex $t$: the $L_{7}$-free-split graphs in $splitting(G,t)$ are
$L_{1}$-exist, $L_{2}$-exist, or isomorphic to one of the following graphs:
$L_{29},L_{30},L_{31},L_{32}$. Thus, the $L_{7}$-split graphs in
$splitting(G,t)$ that are line are $L_{29},L_{30},L_{31},L_{32}$. ∎

####  2.2.19 L8-split graphs that are line

######  Lemma 42.

The graphs $L_{20}$ and $L_{21}$ are the only $L_{8}$-split graphs that are
line.

###### Proof.

The graph $G$ on the right is a labeled $L_{8}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r,s,t\\},\\{u,v\\}\\}$.

W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have two cases.

Case 1, vertex $r$: the $L_{8}$-free-split graphs in $splitting(G,r)$ are
$L_{1}$-exist, $L_{2}$-exist, or isomorphic to either $L_{20}$ or $L_{21}$.
Thus, the $L_{8}$-split graphs in $splitting(G,r)$ that are line are $L_{20}$
and $L_{21}$.

Case 2, vertex $u$: The $L_{8}$-free-split graphs in $splitting(G,u)$ are
$L_{2}$-exist or isomorphic to $L_{20}$.

$r$$s$$t$$u$$v$$G$

Thus, the $L_{8}$-split graph in $splitting(G,u)$ that is line is $L_{20}$. ∎

####  2.2.20 L9-split graphs that are line

######  Lemma 43.

The graphs $L_{34}$ is the only $L_{9}$-split graphs that are line.

###### Proof.

The graph $G$ on the right is a labeled $L_{9}$ graph whose vertex set admits
the following partition into its orbits $\\{\\{r\\},\\{s,t,u,v,w\\}\\}$.
W.l.o.g, we choose an arbitrary vertex from every block out of the partition.
Hence we have two cases.

Case 1, vertex $r$: the $L_{9}$-free-split graphs in $splitting(G,r)$ are
$L_{1}$-exist or $L_{2}$-exist. Thus, there is no $L_{9}$-split graph in
$splitting(G,r)$ that is line.

Case 2, vertex $d$: the $L_{9}$-free-split graphs in $splitting(G,s)$ are
$L_{1}$-exist, $L_{2}$-exist, $L_{3}$-exist, or isomorphic to $L_{34}$.

$r$$s$$t$$u$$v$$w$$G$

Thus, the $L_{9}$-split graph in $splitting(G,s)$ that is line is $L_{34}$. ∎

By Theorems 33 and 34 and Lemmas 35 to 43, the following result follows.

######  Theorem 44.

The graphs $\\{L_{14},\dots,L_{21}\\}$ are the $\operatorname{elm}$(line-
split) graphs.

By Theorems 4, 32, and 44, we deduce the following.

######  Theorem 45.

Let $G$ be a $\\{L_{14},\dots,L_{21}\\}$-free graph that is non-isomorphic to
any graph in $\\{L_{1},\dots,L_{13}\\}-\\{L_{3}\\}$. The graph $G$ is line if
and only if any $G$-contraction is line.

##  3 Acknowledgments

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

## References

  * Beineke [1970] Beineke, L. W. (1970).  Characterizations of derived graphs.  Journal of Combinatorial Theory 9(2), 129–135.
  * Bondy and Murty [2000] Bondy, J. A. and U. S. Murty (2000).  Graph Theory.  Springer.
  * 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.
  * 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.
  * 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 [1976] Foldes, S. and P. Hammer (1976).  Class of matroid-producing graphs.  Volume 23, pp. A420–A420.
  * Harary [2018] Harary, F. (2018).  Graph Theory.  CRC Press.
  * Krausz [1943] Krausz, J. (1943).  Démonstration nouvelle d’une théoreme de whitney sur les réseaux.  Mat. Fiz. Lapok 50(1), 75–85.
  * Kriesell [2002] Kriesell, M. (2002).  A survey on contractible edges in graphs of a prescribed vertex connectivity.  Graphs and Combinatorics 18(1), 1–30.
  * 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.


# Refined Policy Improvement Bounds for MDPs

J. G. Dai  Mark Gluzman

###### Abstract

The policy improvement bound on the difference of the discounted returns plays
a crucial role in the theoretical justification of the trust-region policy
optimization (TRPO) algorithm. The existing bound leads to a degenerate bound
when the discount factor approaches one, making the applicability of TRPO and
related algorithms questionable when the discount factor is close to one. We
refine the results in (Schulman et al., 2015; Achiam et al., 2017) and propose
a novel bound that is “continuous” in the discount factor. In particular, our
bound is applicable for MDPs with the long-run average rewards as well.

average reward reinforcement learning, policy improvement bound

##  1 Introduction

In (Kakade & Langford, 2002) the authors developed a conservative policy
iteration algorithm for Markov decision processes (MDPs) that can avoid
catastrophic large policy updates; each iteration generates a new policy as a
mixture of the old policy and a greedy policy. They proved that the updated
policy is guaranteed to improve when the greedy policy is properly chosen and
the updated policy is sufficiently close to the old one. In (Schulman et al.,
2015) the authors generalized the proof of (Kakade & Langford, 2002) to a
policy improvement bound for two _arbitrary_ randomized policies. This policy
improvement bound allows one to find an updated policy that guarantees to
improve by solving an unconstrained optimization problem. (Schulman et al.,
2015) also proposed a practical algorithm, called trust region policy
optimization (TRPO), that approximates the theoretically-justified update
scheme by solving a constrained optimization problem in each iteration. In
recent years, several modifications of TRPO have been proposed (Schulman et
al., 2016, 2017; Achiam et al., 2017; Abdolmaleki et al., 2018). These studies
continued to exploit the policy improvement bound to theoretically motivate
their algorithms.

The policy improvement bounds in (Schulman et al., 2015; Achiam et al., 2017)
are lower bounds on the difference of the expected _discounted returns_ under
two policies. Unfortunately, the use of these policy improvement bounds
becomes questionable and inconclusive when the discount factor is close to
one. These policy improvement bounds degenerate as discount factor converges
to one. That is, the lower bounds on the difference of discounted returns
converge to negative infinity as the discount factor goes to one, although the
difference of discounted returns converges to the difference of (finite)
average rewards. Nevertheless, numerical experiments demonstrate that the TRPO
algorithm and its variations perform best when the discount factor $\gamma$ is
close to one, a region that the existing bounds do not justify; e.g. (Schulman
et al., 2015, 2016, 2017) used $\gamma=0.99$, and (Schulman et al., 2016;
Achiam et al., 2017) used $\gamma=0.995$ in their experiments.

Recent studies (Dai & Gluzman, 2021; Zhang & Ross, 2021) proposed policy
improvement bounds for average rewards, showing that a family of TRPO
algorithms can be used for continuing problems with long-run average reward
objectives. Still it remains unclear how the large values of the discount
factor can be justified and why the policy improvement bounds in (Schulman et
al., 2015; Achiam et al., 2017) for the discounted rewards do not converge to
one of the bounds provided in (Dai & Gluzman, 2021; Zhang & Ross, 2021).

In this study, we provide a unified derivation of policy improvement bounds
for both discounted and average reward MDPs. Our bounds depend on the discount
factor _continuously_. When the discount factor converges to $1$, the
corresponding bound for discounted returns converges to a policy improvement
bound for average rewards. We achieve these results by two innovative
observations. First, we embed the discounted future state distribution under a
fixed policy as the stationary distribution of a modified Markov chain.
Second, we introduce an _ergodicity coefficient_ from Markov chain
perturbation theory to bound the one-norm of the difference of discounted
future state distributions, and prove that this bound is optimal in a certain
sense. Our results justify the use of a large discount factor in TRPO
algorithm and its variations.

##  2 Preliminaries

We consider an MDP defined by the tuple $(\mathcal{X},\mathcal{A},P,r,\mu)$,
where $\mathcal{X}$ is a finite state space; $\mathcal{A}$ is a finite action
space; $P$ is the transition probability function,
$r:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward function;
$\mu$ is the probability distribution of the initial state $x_{0}$.

We let $\pi$ denote a stationary randomized policy
$\pi:\mathcal{X}\rightarrow\Delta(\mathcal{A})$, where $\Delta(\mathcal{A})$
is the probability simplex over $\mathcal{A}$. Under policy $\pi$, the
corresponding Markov chain has a transition matrix $P^{\pi}$ given by
$P^{\pi}(x,y):=\sum\limits_{a\in\mathcal{A}}\pi(a|x)P(y|x,a),~{}x,y\in\mathcal{X}.$
We assume that MDPs we consider are unichain, meaning that for any stationary
policy $\pi$ the corresponding Markov chain with transition matrix $P^{\pi}$
contains only one recurrent class (Puterman, 2005). We use $d^{\pi}$ to denote
a unique stationary distribution of Markov chain with transition matrix
$P^{\pi}$.

For a vector $a$ and a matrix $A$, $a^{T}$ and $A^{T}$ denote their
transposes. For a vector $a$, we use the following vector norm:
$\|a\|_{1}:=\sum\limits_{x\in\mathcal{X}}\lvert a(x)\rvert$. For a matrix $A$,
we define the following induced norm:
$\|A\|_{1}:=\max\limits_{y\in\mathcal{X}}\sum\limits_{x\in\mathcal{X}}\lvert
A(x,y)\rvert$.

###  2.1 MDPs with infinite horizon discounted returns

We let $\gamma\in[0,1)$ be a discount factor. We define the value function for
a given policy $\pi$ as

$\displaystyle
V_{\gamma}^{\pi}(x):=\mathbb{E}\left[\sum\limits_{t=0}^{\infty}\gamma^{t}r(x_{t},a_{t})\Big{|}\pi,x_{0}=x\right],$

where $x_{t}$, $a_{t}$ are random variables for the state and action at time
$t$ upon executing the policy $\pi$ from the initial state $x$. For policy
$\pi$ we define the state-action value function as
$Q_{\gamma}^{\pi}(x,a):=r(x,a)+\gamma\mathbb{E}_{y\sim
P^{\pi}(\cdot|x,a)}\left[V^{\pi}_{\gamma}(y)\right],$ and the advantage
function as
$A_{\gamma}^{\pi}(x,a):=Q_{\gamma}^{\pi}(x,a)-V_{\gamma}^{\pi}(x).$

We define the discounted future state distribution of policy $\pi$ as

$d_{\gamma}^{\pi}(x):=(1-\gamma)\sum\limits_{t=0}^{\infty}\gamma^{t}\mathbb{P}\Big{[}x_{t}=x|x_{0}\sim\mu;x_{1},x_{2},...\sim\pi\Big{]}.$

We measure the performance of policy $\pi$ by its expected discounted return
from the initial state distribution $\mu$:

$\displaystyle\eta_{\gamma}^{\pi}(\mu):=(1-\gamma)\mathbb{E}_{x\sim\mu}[V_{\gamma}^{\pi}(x)]=\mathbb{E}_{x\sim
d_{\gamma}^{\pi},a\sim\pi(\cdot|x)}[r(x,a)].$

In the following lemma we give an alternative definition of the discounted
future state distribution as a stationary distribution of a modified
transition matrix.

######  Lemma 1.

For a stationary policy $\pi$, we define a discounted transition matrix for
policy $\pi$ as

$\displaystyle P^{\pi}_{\gamma}:=\gamma P^{\pi}+(1-\gamma)e\mu^{T},$ (1)

where $e:=(1,1,..,1)^{T}$ is a vector of ones, $e\mu^{T}$ is the matrix which
rows are equal to $\mu^{T}$.

Then the discounted future state distribution of policy $\pi$,
$d_{\gamma}^{\pi}$, is the stationary distribution of transition matrix
$P^{\pi}_{\gamma}$.

###### Proof of Lemma 1.

We need to show that
$(d_{\gamma}^{\pi})^{T}P^{\pi}_{\gamma}=(d_{\gamma}^{\pi})^{T}$. Indeed, we
get

$\displaystyle(d_{\gamma}^{\pi})^{T}P^{\pi}_{\gamma}$
$\displaystyle=(1-\gamma)\mu^{T}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t}P^{\pi}_{\gamma}$
$\displaystyle=(1-\gamma)\mu^{T}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t}\Big{(}\gamma P^{\pi}+(1-\gamma)e\mu^{T}\Big{)}$
$\displaystyle=(1-\gamma)\mu^{T}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t+1}+(1-\gamma)^{2}\mu^{T}\sum\limits_{t=0}^{\infty}\gamma^{n}e\mu^{T}$
$\displaystyle=(1-\gamma)\mu^{T}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t+1}+(1-\gamma)\mu^{T}$
$\displaystyle=(1-\gamma)\mu^{T}\Big{(}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t+1}+I\Big{)}$
$\displaystyle=(1-\gamma)\mu^{T}\sum\limits_{t=0}^{\infty}(\gamma
P^{\pi})^{t}$ $\displaystyle=(d_{\gamma}^{\pi})^{T}.$

∎

###  2.2 MDPs with long-run average rewards

The long-run average reward of policy $\pi$ is defined as

$\displaystyle\eta^{\pi}:$
$\displaystyle=\lim\limits_{N\rightarrow\infty}\frac{1}{N}\mathbb{E}\left[\sum\limits_{t=0}^{N-1}r(x_{t},a_{t})~{}|~{}\pi,x_{0}\sim\mu\right]$
$\displaystyle=\mathbb{E}_{x\sim
d^{\pi},a\sim\pi(\cdot|x)}\left[r(x,a)\right].$

For an MDP with a long-run average reward objective we define the relative
value function

$\displaystyle
V^{\pi}(x):=\lim\limits_{N\rightarrow\infty}\mathbb{E}\left[\sum\limits_{t=0}^{N-1}(r(x_{t},a_{t})-\eta^{\pi})~{}|~{}\pi,x_{0}=x\right],$

the relative state-action value function
$Q^{\pi}(x,a):=r(x,a)-\eta^{\pi}+\mathbb{E}_{y\sim
P^{\pi}(\cdot|x,a)}\left[V^{\pi}(y)\right],$ and the relative advantage
function $A^{\pi}(x,a):=Q^{\pi}(x,a)-V^{\pi}(x)$. The following relations hold
for value, state-action value, and advantage functions.

######  Lemma 2.

We let $\pi$ be a stationary policy, $\gamma$ be the discount factor, and
$\mu$ be the initial state distribution. Then the following limits hold for
each $x\in\mathcal{X}$, $a\in\mathcal{A}$:

$\eta^{\pi}=\lim\limits_{\gamma\rightarrow 1}\eta^{\pi}_{\gamma}(\mu)$,
$V^{\pi}(x)=\lim\limits_{\gamma\rightarrow
1}\left(V^{\pi}_{\gamma}(x)-(1-\gamma)^{-1}\eta^{\pi}\right)$,
$Q^{\pi}(x,a)=\lim\limits_{\gamma\rightarrow
1}\left(Q^{\pi}_{\gamma}(x,a)-(1-\gamma)^{-1}\eta^{\pi}\right)$, and
$A^{\pi}(x,a)=\lim\limits_{\gamma\rightarrow 1}A^{\pi}_{\gamma}(x,a)$.

The proofs of identities for the average rewards and value functions can be
found in Section 8 in (Puterman, 2005). The rest results follow directly.

##  3  Novel Policy Improvement Bounds

The policy improvement bound in (Schulman et al., 2015; Achiam et al., 2017)
for the discounted returns serves to theoretically justify the TRPO algorithm
and its variations. The following lemma is a reproduction of Corollary 1 in
(Achiam et al., 2017).

######  Lemma 3.

For any two policies $\pi$ and $\tilde{\pi}$ the following bound holds:

$\displaystyle\eta_{\gamma}^{\tilde{\pi}}(\mu)-$
$\displaystyle\eta_{\gamma}^{\pi}(\mu)\geq\underset{\begin{subarray}{c}x\sim
d_{\gamma}^{\pi},a\sim\tilde{\pi}(\cdot|x)\end{subarray}}{\mathbb{E}}\left[A_{\gamma}^{\pi}(x,a)\right]$
(2)
$\displaystyle-\frac{2\gamma\epsilon_{\gamma}^{\tilde{\pi}}}{1-\gamma}\underset{x\sim
d_{\gamma}^{\pi}}{\mathbb{E}}\left[\text{TV}\Big{(}\tilde{\pi}(\cdot|x)~{}||~{}\pi(\cdot|x)\Big{)}\right],$

where
${\text{TV}}\Big{(}\tilde{\pi}(\cdot|x)||\pi(\cdot|x)\Big{)}:=\frac{1}{2}\sum\limits_{a\in\mathcal{A}}\lvert\tilde{\pi}(a|x)-\pi(a|x)\rvert$,
and
$\epsilon_{\gamma}^{\tilde{\pi}}:=\max\limits_{x\in\mathcal{X}}\Big{|}\underset{a\sim\tilde{\pi}(\cdot|x)}{\mathbb{E}}[A_{\gamma}^{\pi}(x,a)]\Big{|}$.

The left-hand side of (2) converges to the difference of average rewards as
$\gamma\rightarrow 1$. Unfortunately, the right-hand side of (2) converges to
the negative infinity because of $(1-\gamma)^{-1}$ factor in the second term.
Our goal is to get a new policy improvement bound for discounted returns that
does not degenerate.

The group inverse $D$ of a matrix $A$ is the unique matrix such that
$ADA=A,~{}DAD=D,\text{ and }DA=AD.$ From (Meyer, 1975), we know that if
stochastic matrix $P$ is aperiodic and irreducible then the group inverse
matrix of $I-P$ is well-defined and equals to
$D=\sum\limits_{t=0}^{\infty}(P^{t}-ed^{T}),$ where $d$ is the stationary
distribution of $P$.

We let $D_{\gamma}^{\pi}$ be the group inverse of matrix $I-P_{\gamma}^{\pi}$,
where $P_{\gamma}^{\pi}$ is defined by (1). Following (Seneta, 1991), we
define a one-norm ergodicity coefficient for a matrix $A$ as

$\displaystyle\tau_{1}[A]:=\underset{\begin{subarray}{c}\|x\|_{1}=1\\\
x^{T}e=0\end{subarray}}{\max}\|A^{T}x\|_{1}.$ (3)

The one-norm ergodicity coefficient has two important properties. First,

$\displaystyle\|A^{T}x\|_{1}\leq\tau_{1}[A]\|x\|_{1},$ (4)

for any matrix $A$ and vector $x$ such that $x^{T}e=0.$ Second,
$\tau_{1}[A]=\tau_{1}[A+ec^{T}]$, for any vector $c$. By Lemma 4 below,
$\tau_{1}\left[D_{\gamma}^{\pi}\right]=\tau_{1}\left[(I-\gamma
P^{\pi})^{-1}\right]$, for $\gamma<1$.

######  Lemma 4.

We let $\pi$ be an arbitrary policy. Then

$\displaystyle D_{\gamma}^{\pi}=(I-\gamma
P^{\pi})^{-1}+e(d_{\gamma}^{\pi})^{T}(I-\left(I-\gamma
P^{\pi}\right)^{-1})-e(d^{\pi})^{T}.$

We are ready to state the main result of our study.

######  Theorem 1.

The following bound on the difference of discounted returns of two policies
$\pi$ and $\tilde{\pi}$ holds:

$\displaystyle\eta_{\gamma}^{\tilde{\pi}}(\mu)-$
$\displaystyle\eta_{\gamma}^{\pi}(\mu)\geq\underset{\begin{subarray}{c}x\sim
d_{\gamma}^{\pi},a\sim\tilde{\pi}(\cdot|x)\end{subarray}}{\mathbb{E}}\left[A_{\gamma}^{\pi}(x,a)\right]$
(5)
$\displaystyle-2\gamma\epsilon_{\gamma}^{\tilde{\pi}}\tau_{1}\left[D_{\gamma}^{\tilde{\pi}}\right]\underset{x\sim
d_{\gamma}^{\pi}}{\mathbb{E}}\left[\text{TV}\Big{(}\tilde{\pi}(\cdot|x)~{}||~{}\pi(\cdot|x)\Big{)}\right].$

We provide a sketch of the proof of Theorem 1.

###### Proof of Theorem 1.

We closely follow the first steps in the proof of Lemma 2 in (Achiam et al.,
2017) and start with

$\displaystyle\eta_{\gamma}^{\tilde{\pi}}(\mu)-$
$\displaystyle\eta_{\gamma}^{\pi}(\mu)\geq\underset{\begin{subarray}{c}x\sim
d_{\gamma}^{\pi},a\sim\tilde{\pi}(\cdot|x)\end{subarray}}{\mathbb{E}}\left[A_{\gamma}^{\pi}(x,a)\right]$
$\displaystyle-\max\limits_{x\in\mathcal{X}}\Big{|}\underset{a\sim\tilde{\pi}(\cdot|x)}{\mathbb{E}}[A_{\gamma}^{\pi}(x,a)]\Big{|}\|d_{\gamma}^{\pi}-d_{\gamma}^{\tilde{\pi}}\|_{1}.$

Next, unlike (Achiam et al., 2017), we obtain an upper bound on
$\|d_{\gamma}^{\tilde{\pi}}-d_{\gamma}^{\pi}\|_{1}$ that does not degenerate
as $\gamma\rightarrow 1$. We use the following perturbation identity:

$\displaystyle(d_{\gamma}^{\tilde{\pi}})^{T}-(d_{\gamma}^{\pi})^{T}=\gamma(d_{\gamma}^{\pi})^{T}(P^{\pi}-P^{\tilde{\pi}})D_{\gamma}^{\tilde{\pi}}.$
(6)

Identity (6) follows from the perturbation identity for stationary
distributions, see equation (4.1) in (Meyer, 1980), and the fact that
$d_{\gamma}^{\tilde{\pi}}$ and $d_{\gamma}^{\pi}$ are the stationary
distributions of the discounted transition matrices $P^{\tilde{\pi}}_{\gamma}$
and $P^{\pi}_{\gamma}$, respectively. We make use of the ergodicity
coefficient (3) to get a new perturbation bound:

$\displaystyle\|d_{\gamma}^{\tilde{\pi}}$ $\displaystyle-
d_{\gamma}^{\pi}\|_{1}=\gamma\left\|\left(D_{\gamma}^{\tilde{\pi}}\right)^{T}(P^{\pi}-P^{\tilde{\pi}})^{T}d_{\gamma}^{\pi}\right\|_{1}$
$\displaystyle\leq\gamma\tau_{1}\left[D_{\gamma}^{\tilde{\pi}}\right]\left\|(P^{\pi}-P^{\tilde{\pi}})^{T}d_{\gamma}^{\pi}\right\|_{1}$
(7) $\displaystyle\leq
2\gamma\tau_{1}\left[D_{\gamma}^{\tilde{\pi}}\right]\underset{x\sim
d_{\gamma}^{\pi}}{\mathbb{E}}\left[\text{TV}\Big{(}\tilde{\pi}(\cdot|x)~{}||~{}\pi(\cdot|x)\Big{)}\right],$

where inequality (7) holds due to (4) and equality
$(P^{\pi}-P^{\tilde{\pi}})e=0.$

∎

The novel policy improvement bound (5) converges to a meaningful bound on the
difference of average rewards as $\gamma$ goes to 1. Corollary 1 follows from
Theorem 1, Lemma 2 and the fact that
$\tau_{1}\left[D_{\gamma}^{\tilde{\pi}}\right]\rightarrow\tau_{1}\left[D^{\tilde{\pi}}\right]$
as $\gamma\rightarrow 1$.

######  Corollary 1.

The following bound on the difference of long-run average rewards of two
policies $\pi$ and $\tilde{\pi}$ holds:

$\displaystyle\eta^{\tilde{\pi}}-$
$\displaystyle\eta^{\pi}\geq\underset{\begin{subarray}{c}x\sim
d^{\pi},a\sim\tilde{\pi}(\cdot|x)\end{subarray}}{\mathbb{E}}\left[A^{\pi}(x,a)\right]$
(8)
$\displaystyle-2\epsilon^{\tilde{\pi}}\tau_{1}\left[D^{\tilde{\pi}}\right]\underset{x\sim
d^{\pi}}{\mathbb{E}}\left[\text{TV}\Big{(}\tilde{\pi}(\cdot|x)~{}||~{}\pi(\cdot|x)\Big{)}\right],$

where $D^{\tilde{\pi}}$ is the group inverse of matrix $I-P^{\tilde{\pi}}$,
$\epsilon^{\tilde{\pi}}:=\max\limits_{x\in\mathcal{X}}\Big{|}\underset{a\sim\tilde{\pi}(\cdot|x)}{\mathbb{E}}[A^{\pi}(x,a)]\Big{|}$.

Lemma 5 demonstrates that we use the best (smallest) norm-wise bound on the
difference of stationary distributions in the proof of Theorem 1. Lemma 5 is
based on (Kirkland et al., 2008).

######  Lemma 5.

We consider two irreducible and aperiodic transition matrices $P$ and
$\tilde{P}$ with stationary distributions $d$ and $\tilde{d}$, respectively.
We say that $\tau[\tilde{P}]$ is a condition number of matrix $\tilde{P}$ if
inequality

$\displaystyle\|d-\tilde{d}\|_{1}\leq\tau[\tilde{P}]\|(P-\tilde{P})^{T}d\|_{1},$
(9)

holds for any transition matrix $P$. We let $\tilde{D}$ be a group inverse
matrix of $I-\tilde{P}$.

Then $\tau_{1}[\tilde{D}]$ is the smallest condition number:
$\tau_{1}[\tilde{D}]\leq\tau[\tilde{P}]$ holds for any condition number
$\tau(\tilde{P})$ satisfying (9).

Lemma 5 shows that inequality (7) in the proof of Theorem 1 is a key to the
improvement of the policy improvement bounds in (Schulman et al., 2015; Achiam
et al., 2017). Moreover, it follows from Lemma 5 that Corollary 1 provides a
better policy improvement bound for the average reward criterion than (Dai &
Gluzman, 2021; Zhang & Ross, 2021).

##  4 Interpretation of $\tau_{1}[D_{\gamma}^{\pi}]$

We provide several bounds on $\tau_{1}[D_{\gamma}^{\pi}]$ to reveal its
dependency on the discount factor $\gamma$ and policy $\pi$. First, we show
how the magnitude of $\tau_{1}[D_{\gamma}^{\pi}]$ is governed by the
subdominant eigenvalues of the Markov chain. We let $P$ be an irreducible
Markov chain and let $D$ be the group inverse matrix of $I-P$. We define the
spectrum of transition matrix $P$ as
$\\{1,\lambda_{2},\lambda_{3},...,\lambda_{|\mathcal{X}|}\\}$, where
$|\mathcal{X}|$ is a cardinality of the state space $\mathcal{X}$. Then, the
ergodicity coefficient can be bounded as

$\displaystyle\tau_{1}[D]\leq\sum\limits_{i=2}^{|\mathcal{X}|}\frac{1}{1-\lambda_{i}}=\text{trace}(D),$

see (Seneta, 1993). Matrix $P_{\gamma}$ defined by (1) is called the Google
matrix, and if the spectrum of transition matrix $P$ is
$\\{1,\lambda_{2},\lambda_{3},...,\lambda_{|\mathcal{X}|}\\}$, then the
spectrum of the Google matrix $P_{\gamma}$ is
$\\{1,\gamma\lambda_{2},\gamma\lambda_{3},...,\gamma\lambda_{|\mathcal{X}|}\\}$,
see (Haveliwala & Kamvar, 2003; Langville & Meyer, 2003). Hence, the
discounting decreases the subdominant eigenvalue of the transition matrix that
leads to the following bound.

######  Lemma 6.

We let $D_{\gamma}^{\pi}$ be the group inverse matrix of $I-P_{\gamma}^{\pi}$.
Then for any discount factor $\gamma\in(0,1]$

$\displaystyle\tau_{1}[D_{\gamma}^{\pi}]\leq\sum\limits^{|\mathcal{X}|}_{i=2}\frac{1}{1-\gamma\lambda_{i}}\leq\frac{|\mathcal{X}|-1}{1-\gamma|\lambda_{2}|},$

where $\lambda_{2}$ is an eigenvalue of $P^{\pi}$ with the second largest
absolute value.

In Lemma 7 below we derive an alternative upper bound on
$\tau_{1}[D_{\gamma}^{\pi}]$. For a given policy $\pi$, we assume the
transition matrix $P^{\pi}$ is aperiodic and irreducible. By Proposition 1.7
in (Levin & Peres, 2017), there exists an integer $\ell$ such that
$(P^{\pi})^{q}(x,y)>0$ for all $x,y\in\mathcal{X}$, and $q\geq\ell.$ Then,
there exists a sufficiently small constant $\delta^{\pi}_{\mu}>0$, such that

$\displaystyle(P^{\pi})^{\ell}(x,y)\geq\delta_{\mu}^{\pi}\mu(y),\quad\text{
for each }x,y\in\mathcal{X},$ (10)

where $\mu$ denotes the distribution of the initial state.

######  Lemma 7.

We let $D_{\gamma}^{\pi}$ be the group inverse matrix of $I-P_{\gamma}^{\pi}$.

We let $\delta_{\mu}^{\pi}$ be a constant that satisfies (10) for $P^{\pi}$
and some integer $\ell$. Then

$\displaystyle\tau_{1}[D_{\gamma}^{\pi}]\leq\frac{2\ell}{1-\gamma+\gamma^{\ell}\delta^{\pi}_{\mu}},$

where $\delta_{\mu}^{\pi}$ and $\ell$ are independent of $\gamma$.

## References

  * Abdolmaleki et al. (2018) Abdolmaleki, A., Springenberg, J. T., Tassa, Y., Munos, R., Heess, N., and Riedmiller, M.  Maximum a Posteriori Policy Optimisation.  In _Proceedings of ICLR’18_ , 2018.
  * Achiam et al. (2017) Achiam, J., Held, D., Tamar, A., and Abbeel, P.  Constrained Policy Optimization.  _Proceedings of ICML’17_ , 70:22–31, 2017.
  * Dai & Gluzman (2021) Dai, J. G. and Gluzman, M.  Queueing Network Controls via Deep Reinforcement Learning.  2021\.  URL http://arxiv.org/abs/2008.01644.
  * Haveliwala & Kamvar (2003) Haveliwala, T. H. and Kamvar, S. D.  The Second Eigenvalue of the Google Matrix.  Technical report, 2003.  URL https://nlp.stanford.edu/pubs/secondeigenvalue.pdf.
  * Kakade & Langford (2002) Kakade, S. and Langford, J.  Approximately Optimal Approximate Reinforcement Learning.  In _Proceedings of ICML’02_ , pp. 267–274, 2002.
  * Kirkland et al. (2008) Kirkland, S. J., Neumann, M., and Sze, N. S.  On optimal condition numbers for markov chains.  _Numerische Mathematik_ , 110(4):521–537, 2008\.
  * Langville & Meyer (2003) Langville, A. N. and Meyer, C. D.  Deeper Inside PageRank.  _Internet Mathematics_ , 1(3):335–380, 2003.
  * Levin & Peres (2017) Levin, D. A. and Peres, Y.  _Markov Chains and Mixing Times_.  American Mathematical Society, 2nd edition, 2017.
  * Meyer (1975) Meyer, C. D.  The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains.  _SIAM Review_ , 17(3):443–464, 1975.
  * Meyer (1980) Meyer, C. D.  The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities.  _SIAM Journal on Algebraic Discrete Methods_ , 1(3):273–283, 1980.
  * Puterman (2005) Puterman, M. L.  _Markov decision processes : discrete stochastic dynamic programming_.  Wiley-Interscience, 2005.
  * Schulman et al. (2015) Schulman, J., Levine, S., Moritz, P., Jordan, M. I., and Abbeel, P.  Trust Region Policy Optimization.  In _Proceedings of ICML’15_ , pp. 1889–1897, 2015.
  * Schulman et al. (2016) Schulman, J., Moritz, P., Levine, S., Jordan, M. I., and Abbeel, P.  High-Dimensional Continuous Control Using Generalized Advantage Estimation.  In _Procedings of ICLR’16_ , 2016.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal Policy Optimization Algorithms.  2017\.  URL http://arxiv.org/abs/1707.06347.
  * Seneta (1991) Seneta, E.  Sensitivity analysis, ergodicity coefficients, and rank-one updates for finite Markov chains.  In Stewart, W. (ed.), _Numerical Solution of Markov Chains_ , pp. 121–129. Marcel Dekker, New York, 1991.
  * Seneta (1993) Seneta, E.  Sensitivity of finite Markov chains under perturbation.  _Statistics & Probability Letters_, 17(2):163–168, 1993.  doi: 10.1016/0167-7152(93)90011-7.
  * Zhang & Ross (2021) Zhang, Y. and Ross, K. W.  On-Policy Deep Reinforcement Learning for the Average-Reward Criterion.  _Proceedings of ICML’21_ , 2021.