11institutetext: Indian Institute of Technology Palakkad, India 11email:
jasine<EMAIL_ADDRESS>22institutetext: National
Institute of Technology Calicut, India 22email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Eternal vertex cover number of maximal outerplanar graphs

Jasine Babu 11 K. Murali Krishnan 22 Veena Prabhakaran 11 Nandini J. Warrier
22

###### Abstract

Eternal vertex cover problem is a variant of the classical vertex cover
problem modeled as a two player attacker-defender game. Computing eternal
vertex cover number of graphs is known to be NP-hard in general and the
complexity status of the problem for bipartite graphs is open. There is a
quadratic complexity algorithm known for this problem for chordal graphs.
Maximal outerplanar graphs forms a subclass of chordal graphs, for which no
algorithm of sub-quadratic time complexity is known. In this paper, we obtain
a recursive algorithm of linear time for computing eternal vertex cover number
of maximal outerplanar graphs.

###### Keywords:

Eternal Vertex Cover, Maximal Outerplanar Graph, Linear Time Algorithm

##  1 Introduction

A set $S$ of vertices in a graph $G$ forms a vertex cover of $G$ if every edge
in $G$ has at least one end point in $S$. The size of a minimum vertex cover
in $G$, called the vertex cover number of $G$, will be denoted by
$\operatorname{mvc}(G)$. The eternal vertex cover problem of graphs is
motivated by the following dynamic network security / fault-tolerance model. A
network can be modeled by a graph $G(V,E)$, where the nodes of the network are
represented by the vertices of $G$ and the links by the edges of $G$. The
problem is to deploy a minimum set of guards at the nodes, so that if there is
an attack (or fault) on a single link at any time, a guard is available at the
end of the link, who can move across the link to defend (or repair) the attack
(or fault). Simultaneously, the remaining guards need to reconfigure
themselves, possibly by repositioning themselves to one of their adjacent
nodes, so that any attack (or fault) on a single edge at any future instant of
time can also be protected in the same manner. Thus, the model requires
guaranteeing protection against single link attacks/failures ad-infinitum. It
is immediate that lowest number of guards needed to achieve this goal in a
graph $G$ is at least $\operatorname{mvc}(G)$. If $k$ guards are sufficient to
achieve the goal, then we say that $G$ is $k$-defendable.

Formally, guards are initially placed on a vertex cover $C_{0}$ of $G$,
forming an initial configuration. Suppose at instant $i$, guards are placed in
a configuration $C_{i}$ and an attack occurs on an arbitrary edge $uv\in
E(G)$, then a guard at either $u$ or $v$ (or both) must move across the edge.
Other guards may or not move across one of their neighboring edges
simultaneously. At the end of these movements, the next configuration
$C_{i+1}$ is reached. To ensure that all edges remain guarded at the instant
$i+1$, we require $C_{i+1}$ to be a vertex cover of $G$. The minimum number of
guards necessary for a graph $G$ to be protected against any infinite sequence
of single edge attacks is called the eternal vertex cover number of $G$,
denoted by $\operatorname{evc}(G)$. The eternal vertex cover problem has two
models. The first one allows only at most one guard on a vertex in any
configuration, while in the second model this constraint is absent. The
results in this paper work in both the models.

Computing $\operatorname{evc}(G)$ for an arbitrary graph $G$ is NP-hard,
though in PSPACE [1], and is fixed parameter tractable with
$\operatorname{evc}(G)$ as parameter[1]. The problem appears significantly
harder than $\operatorname{mvc}$ computation. For instance,
$\operatorname{mvc}$ computation is polynomial time for bipartite graphs, but
the complexity status of the problem is open for bipartite graphs[1].
Consequent to the hardness results, work on solving the problem on various
graph classes have been attempted in the literature. It is known that the
problem is NP-complete even for biconnected internally triangulated planar
graphs[2]. Polynomial time algorithms for computing $\operatorname{evc}(G)$
were known exactly only for very elementary graph classes such as an $O(n)$
algorithm for trees [3], a polynomial time algorithm for a tree-like graph
class [4] and a linear time algorithm for cactus graphs [5]. A recent
structure theorem developed in [6] has resulted in a quadratic time algorithm
for chordal graphs. Similar graph protection problems defined on parameters
like dominating sets [7, 8, 9, 10, 11, 12] and independent sets [13, 14] are
also studied in literature.

An outerplanar graph is a planar graph that admits a planar embedding with all
its vertices lying on the exterior face and it is maximal outerplanar if
addition of any more edges between existing vertices will make the graph not
outerplanar. Since maximal outerplanar graphs are chordal, it follows from [6]
that its $\operatorname{evc}$ number can be computed in quadratic time. We
improve the complexity and show that the $\operatorname{evc}$ number of
maximal outerplanar graphs can be computed in linear time.

Our algorithm takes a maximal outerplanar graph $G$ on at least three vertices
and an edge $uv$ on the outer face of $G$ and recursively computes
$\operatorname{evc}(G)$, $\operatorname{mvc}(G)$ along with some related
parameters. If both $u$ and $v$ are of degree greater than two, then the
recursion is applied on the two induced subgraphs $G_{u}$ and $G_{v}$ of $G$
as shown in Fig. 1. Otherwise, the recursion works on the graph obtained by
deleting the degree two end point of the edge $uv$ from $G$. Since
$\operatorname{evc}(G)$ happens to be not merely a function of the eternal
vertex cover number and vertex cover number of these associated subgraphs, the
algorithm has to recursively compute this larger set of parameters. The linear
time complexity of the algorithm is derived from Theorems 3.1 to 5.2, which
assert that $\operatorname{evc}(G)$ can be determined in constant time from
this larger set of parameters of the associated subgraphs. Apart from the
algorithmic result, these theorems serve to demonstrate the structural
connection between the $MVC$ problem and the $EVC$ problem for maximal
outerplanar graphs.

##  2 Preliminaries

Let $G$ be a graph with $S\subseteq V$. The parameter
$\operatorname{evc}_{S}(G)$ denotes the minimum number $k$ such that $G$ is
$k$-defendable with all vertices of $S$ occupied in all configurations.
Similarly, $\operatorname{mvc}_{S}(G)$ denote the size of the smallest
cardinality vertex cover of $G$ containing all vertices of $S$. When
$S=\\{v_{1}\cdots v_{i}\\}$ for $1\leq i\leq 3$, we shorten the notation
$\operatorname{evc}_{\\{v_{1}\cdots v_{i}\\}}(G)$ and
$\operatorname{mvc}_{\\{v_{1}\cdots v_{i}\\}}(G)$ as
$\operatorname{evc}_{v_{1}\cdots v_{i}}(G)$ and
$\operatorname{mvc}_{v_{1}\cdots v_{i}}(G)$ respectively.
Proposition 1 is an easy adaptation of a result from known literature.

###### Proposition 1

[2] Let $G(V,E)$ be a maximal outerplanar graph with at least two vertices and
$S\subseteq V$. If for every vertex $v\in V\setminus S$,
$\operatorname{mvc}_{{}_{S\cup\\{v\\}}}(G)=\operatorname{mvc}_{{}_{S}}(G)$,
then $\operatorname{evc}_{{}_{S}}(G)=\operatorname{mvc}_{{}_{S}}(G)$.
Otherwise, $\operatorname{evc}_{{}_{S}}(G)=\operatorname{mvc}_{{}_{S}}(G)+1$.
Hence, $\operatorname{evc}_{{}_{S}}(G)=\max_{v\in
V(G)}\operatorname{mvc}_{{}_{S\cup\\{v\\}}}(G)$.

###### Proposition 2

Let $G$ be a maximal outerplanar graph with an edge $uv$. Then,
$\operatorname{evc}_{v}(G)\leq\operatorname{evc}_{uv}(G)\leq\operatorname{evc}(G)+1$.

###### Proof

Let $\operatorname{evc}(G)=k$. The first part of the inequality is obvious.
So, we prove the second part. By Proposition 1, for each vertex $x\in V(G)$,
$\operatorname{mvc}_{x}(G)\leq k$. Since $uv\in E(G)$, this implies that
$\operatorname{mvc}_{xu}(G)\leq k$ or $\operatorname{mvc}_{xv}(G)\leq k$.
Therefore, for any vertex $x\in V(G)$, we have
$\operatorname{mvc}_{xuv}(G)\leq k+1$. Hence by Proposition 1,
$\operatorname{evc}_{uv}(G)\leq k+1=\operatorname{evc}(G)+1$.∎

From now on, whenever we say a graph is maximal outerplanar, we assume a fixed
outerplanar embedding of the graph.

For a maximal outerplanar graph $G$ on at least three vertices and any edge
$uv$ on the outer face of $G$, we use the notation $\Delta(uv)$ to denote the
unique common neighbor of $u$ and $v$.

######  Definition 1 ($uv$-segments)

Let $G$ be a maximal outerplanar graph with at least three vertices. Let $uv$
be an edge on the outer face of $G$. Let $w=\Delta(uv)$. We define the graph
$G_{u}(uv)$ (respectively, $G_{v}(uv)$) to be the maximal biconnected
outerplanar subgraph of $G$ that satisfies the following two properties (see
Fig. 1):

  1. 1.

The edge $uw$ (respectively, $vw$) is on the outer face of $G_{u}(uv)$
(respectively, $G_{v}(uv)$).

  2. 2.

$G_{u}(uv)$ (respectively, $G_{v}(uv)$) does not contain the vertex $v$
(respectively $u$).

$G_{u}(uv)$ and $G_{v}(uv)$ will be called the $uv$ segments of $G$.

###### Note 1

We will write $G_{u}$ and $G_{v}$ instead of $G_{u}(uv)$ and $G_{v}(uv)$ when
there is no scope for confusion. Observe that $G_{u}$ (respectively, $G_{v}$)
will be a single edge, if $deg_{G}(u)=2$ (respectively, $deg_{G}(v)=2$).

Figure 1: $G_{u}$ is the $uv$ segment of the graph that contains $u$ and
$G_{v}$ is the $uv$ segment that contains $v$. In (a), $G_{u}$ is a single
edge.

######  Definition 2 (mvc and evc parameters)

For a maximal outerplanar graph $G$ and an edge $uv$, the set of parameters
$\mathscr{M}(G,uv)=\\{\operatorname{mvc}(G)$, $\operatorname{mvc}_{u}(G)$,
$\operatorname{mvc}_{v}(G)$, $\operatorname{mvc}_{uv}(G)\\}$ is called the
(set of) mvc parameters of $G$ with respect to $uv$ and the set
$\mathscr{E}(G,uv)=\\{\operatorname{evc}(G)$, $\operatorname{evc}_{u}(G)$,
$\operatorname{evc}_{v}(G)$, $\operatorname{evc}_{uv}(G)\\}$ is called the
(set of) evc parameters of $G$ with respect to $uv$.

The following observation, which gives the mvc and evc parameters of a
triangle, is the base case of the recursive computation of these parameters
for larger graphs described in subsequent sections.

###### Observation 1

Let $G$ be a triangle $uvw$. Consider the edge $uv$. Then, (1)
$\operatorname{mvc}(G)=\operatorname{mvc}_{u}(G)=\operatorname{mvc}_{v}(G)=\operatorname{mvc}_{uv}(G)=2$
(2)
$\operatorname{evc}(G)=\operatorname{evc}_{u}(G)=\operatorname{evc}_{v}(G)=2$
and $\operatorname{evc}_{uv}(G)=3$.

##  3 Computation of the mvc parameters

Throughout this section, we assume that $G$ is a maximal outerplanar graph of
at least four vertices, $uv$ is an edge on the outer face of $G$ and
$w=\Delta(uv)$. The results in this section show that the mvc parameters of
$G$ with respect to the edge $uv$ \- viz., $\mathscr{M}(G,uv)$, can be
computed in constant time if the mvc parameters of $G_{u}$ with respect to
$uw$ \- viz., $\mathscr{M}(G_{u},uw)$ and the mvc parameters of $G_{v}$ with
respect to $vw$ \- viz., $\mathscr{M}(G_{v},vw)$ are given.

The following observation is easy to see.

###### Observation 2

If $deg_{G}(u)=2$ and $deg_{G}(v)>2$, then, (1)
$\operatorname{mvc}(G)=\operatorname{mvc}_{vw}(G_{v})$ (2)
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G_{v})+1$, (3)
$\operatorname{mvc}_{v}(G)=\operatorname{mvc}(G)$ and (4)
$\operatorname{mvc}_{uv}(G)=\operatorname{mvc}_{v}(G_{v})+1$.

The following theorem is a consequence of Observation 2.

###### Theorem 3.1

Let $G$ be a maximal outerplanar graph and $uv$ be an edge on the outer face
of $G$ such that $deg_{G}(u)=2$. Let $w=\Delta(uv)$.

  1. 1.

Given $\mathscr{M}(G_{v},vw)$, it is possible to compute
$\operatorname{mvc}(G)$ in constant time.

  2. 2.

Given $\operatorname{mvc}(G)$ and $\mathscr{M}(G_{v},vw)$, it is possible to
compute the remaining mvc parameters of $G$ with respect to $uv$ in constant
time.

Now, we look at the computation of $\mathscr{M}(G,uv)$ when $deg_{G}(u)>2$ and
$deg_{G}(v)>2$.
The following observation is easy to obtain.

###### Observation 3

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then
$\operatorname{mvc}(G)\in\\{\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})\\}$.

The next lemma gives a method to compute $\operatorname{mvc}(G)$ using
$\mathscr{M}(G_{u},uw)$ and $\mathscr{M}(G_{v},vw)$.

###### Lemma 1

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then
$\operatorname{mvc}(G)=\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})\\}$.

###### Proof

It can be easily seen that
$\operatorname{mvc}(G)\leq\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})\\}$.
By Observation 3, we have the following two cases to consider.

If
$\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})-1$,
then both $G_{u}$ and $G_{v}$ have a minimum vertex cover with $w$. Further,
either $\operatorname{mvc}_{uw}(G_{u})=\operatorname{mvc}(G_{u})$ or
$\operatorname{mvc}_{vw}(G_{v})=\operatorname{mvc}(G_{v})$. Hence, it is clear
that
$\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})-1=\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\\}$.
From this, the result follows.

If
$\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})$,
then by the upper bound shown in the beginning of this proof,
$\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})=\operatorname{mvc}(G)\leq\min\\{\operatorname{mvc}_{w}(G_{u})+mvc_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\\}$.
From this, the result follows.∎

The next lemma shows that given $\operatorname{mvc}(G)$,
$\mathscr{M}(G_{u},uw)$ and $\mathscr{M}(G_{v},vw)$, the values of
$\operatorname{mvc}_{u}(G)$, $\operatorname{mvc}_{v}(G)$ and
$\operatorname{mvc}_{uv}(G)$ are computable in constant time.

###### Lemma 2

Let $deg_{G}(u)>2$ and $deg_{G}(v)>2$. If
$\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})-1$,
then
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$,
$\operatorname{mvc}_{v}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$
and
$\operatorname{mvc}_{uv}(G)=\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$.

###### Proof

Let $\operatorname{mvc}(G_{u})=k_{u}$ and $\operatorname{mvc}(G_{v})=k_{v}$.
Since $\operatorname{mvc}(G)=k_{u}+k_{v}-1$, both $G_{u}$ and $G_{v}$ have a
minimum vertex cover with $w$. Let $k=\operatorname{mvc}_{u}(G)$. Since
$\operatorname{mvc}_{w}(G_{v})=k_{v}$, we can observe that $G$ has a vertex
cover $C$ of size $k$ such that $u,w\in C$. Now, it can be easily seen that
$C$ is the union of a vertex cover of $G_{u}$ containing both $u$ and $w$ and
a minimum vertex cover of $G_{v}$ with $w$. Therefore,
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
Similarly, it is easy to see that
$\operatorname{mvc}_{v}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$
and
$\operatorname{mvc}_{uv}(G)=\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$.
∎

###### Lemma 3

Let $deg_{G}(u)>2$ and $deg_{G}(v)>2$. If
$\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})$,
then
$\operatorname{mvc}_{u}(G)=\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{mvc}_{w}(G_{v}),\operatorname{mvc}(G)+1\\}$,
$\operatorname{mvc}_{v}(G)=\min\\{\operatorname{mvc}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G)+1\\}$
and
$\operatorname{mvc}_{uv}(G)=\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{mvc}(G)+1\\}$.

###### Proof

Let $\operatorname{mvc}(G_{u})=k_{u}$ and $\operatorname{mvc}(G_{v})=k_{v}$.
First we prove that
$\operatorname{mvc}_{u}(G)=\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{mvc}_{w}(G_{v}),\operatorname{mvc}(G)+1\\}$.
It can be easily seen that
$\operatorname{mvc}_{u}(G)\leq\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{mvc}_{w}(G_{v}),\operatorname{mvc}(G)\\\
+1\\}$. Now, we need to show that
$\operatorname{mvc}_{u}(G)\geq\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{mvc}_{w}(G_{v}),\\\
\operatorname{mvc}(G)+1\\}$. We know that
$\operatorname{mvc}_{u}(G)\in\\{\operatorname{mvc}(G),\operatorname{mvc}(G)+1\\}$.
If $\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G)+1$, then the proof is
immediate, because $\operatorname{mvc}_{u}(G)$ is equal to one of the three
quantities listed and so it is greater than or equal to their minimum.
Otherwise, we have
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G)=\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})$.
In this case, it is enough to show that among the three parameters, the first
or the second will be equal to
$\operatorname{mvc}(G_{u})+\operatorname{mvc}(G_{v})$. For contradiction,
suppose this was not the case. Then, $\operatorname{mvc}_{u}(G_{u})=k_{u}+1$
and $\operatorname{mvc}_{w}(G_{v})=k_{v}+1$. Consider any minimum vertex cover
$S$ of $G$ such that $u\in S$. If $w\in S$, then
$|S|\geq\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\geq
k_{u}+k_{v}+1$, a contradiction. If $w\notin S$, again
$|S|\geq\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}(G_{v})\geq
k_{u}+k_{v}+1$, a contradiction. Hence, we are done. The proof for
$\operatorname{mvc}_{v}(G)$ is symmetric to the previous case.

Now, we show that
$\operatorname{mvc}_{uv}(G)=\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{mvc}(G)+1\\}$.
It is easy to see that
$\operatorname{mvc}_{uv}(G)\leq\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{mvc}(G)+1\\}$.
We know that
$\operatorname{mvc}_{uv}(G)\in\\{\operatorname{mvc}(G),\operatorname{mvc}(G)+1\\}$.
Suppose $\operatorname{mvc}_{uv}(G)=\operatorname{mvc}(G)=k_{u}+k_{v}$. In
this case, it suffices to show that $\operatorname{mvc}_{u}(G_{u})=k_{u}$ and
$\operatorname{mvc}_{v}(G_{v})=k_{v}$. For contradiction, assume
$\operatorname{mvc}_{u}(G_{u})=k_{u}+1$. Then,
$\operatorname{mvc}_{w}(G_{u})=k_{u}$. Since,
$\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$,
$\operatorname{mvc}_{vw}(G_{v})=k_{v}$. Then,
$\operatorname{mvc}(G)=k_{u}+k_{v}-1$, which is a contradiction. Hence,
$\operatorname{mvc}_{u}(G_{u})\leq k_{u}$. Similarly,
$\operatorname{mvc}_{v}(G_{v})\leq k_{v}$ as required. Now, suppose
$\operatorname{mvc}_{uv}(G)=\operatorname{mvc}(G)+1=k_{u}+k_{v}+1$. In this
case, it suffices to show that
$\operatorname{mvc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\geq\operatorname{mvc}_{uv}(G)=\operatorname{mvc}(G)+1$,
which is straightforward to obtain. ∎

From Lemma 1, Lemma 2 and Lemma 3, the following theorem is immediate.

###### Theorem 3.2

Let $G$ be a maximal outerplanar graph and $uv$ be an edge on the outer face
of $G$ such that $deg_{G}(u)>2$ and $deg_{G}(v)>2$. Let $w=\Delta(uv)$.

  1. 1.

Given $\mathscr{M}(G_{u},uw)$ and $\mathscr{M}(G_{v},vw)$, it is possible to
compute $\operatorname{mvc}(G)$ in constant time.

  2. 2.

Given $\operatorname{mvc}(G)$, $\mathscr{M}(G_{u},uw)$ and
$\mathscr{M}(G_{v},vw)$, it is possible to compute the remaining mvc
parameters of $G$ with respect to $uv$ in constant time.

##  4 Bounds on the evc parameters

In this section, we will derive some bounds on the evc parameters of a maximal
outerplanar graph. These bounds will be used in the next section for the
recursive computation of the evc parameters. Throughout this section, we
consider $G$ to be a maximal outerplanar graph on at least four vertices, $uv$
an edge on its outer face and $w=\Delta(uv)$.

First, we derive some bounds for $\mathscr{E}(G,uv)$ when $deg_{G}(u)=2$.

###### Lemma 4

If $u$ is a degree-2 vertex in $G$, then:

  1. 1.

$\operatorname{evc}(G)\leq\operatorname{evc}_{u}(G)=\operatorname{evc}(G_{v})+1$

  2. 2.

$\operatorname{evc}_{uv}(G)=\operatorname{evc}_{v}(G_{v})+1$

  3. 3.

$\operatorname{evc}(G)\geq
max\\{\operatorname{mvc}(G_{v})+1,\operatorname{evc}_{vw}(G_{v})\\}$

  4. 4.

$\operatorname{evc}_{v}(G)=\text{max}\\{\operatorname{mvc}_{uv}(G),\operatorname{evc}(G)\\}$

###### Proof

Let $\operatorname{evc}(G)=k$.

  1. 1.

First inequality is straightforward. So, it suffices to show that
$\operatorname{evc}_{u}(G)=\operatorname{evc}(G_{v})+1$. From Proposition 1,
$\max_{x\in V(G_{v})}\operatorname{mvc}_{x}(G_{v})=\operatorname{evc}(G_{v})$.
Hence, $\max_{x\in
V(G_{v})}\operatorname{mvc}_{xu}(G)=\operatorname{evc}(G_{v})+1$. Hence, by
Proposition 1, we get $\operatorname{evc}_{u}(G)=\operatorname{evc}(G_{v})+1$.

  2. 2.

Similar to the previous case, by Proposition 1, $\max_{x\in
V(G_{v})}\operatorname{mvc}_{x}(G_{v})=\operatorname{evc}(G_{v})$. Hence,
$\max_{x\in
V(G_{v})}\operatorname{mvc}_{xuv}(G)\leq\operatorname{evc}(G_{v})+1$. Hence,
by Proposition 1, we get
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}(G_{v})+1$. By Proposition 2
and Part 1 of this lemma,
$\operatorname{evc}_{uv}(G)\geq\operatorname{evc}_{u}(G)=\operatorname{evc}_{v}(G_{v})+1$.
Therefore, $\operatorname{evc}_{uv}(G)=\operatorname{evc}_{v}(G_{v})+1$.

  3. 3.

By Observation 2, we get
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G_{v})+1$. By Proposition 1,
since $\operatorname{evc}(G)\geq\operatorname{mvc}_{u}(G)$, we have
$\operatorname{evc}(G)\geq\operatorname{mvc}(G_{v})+1$.
By Proposition 1, for any vertex $x\in V(G)$, $\operatorname{mvc}_{x}(G)\leq
k$. Further, any vertex cover of $G$ contain at least two vertices among $u$,
$v$ and $w$. Let $x$ be an arbitrary vertex in $G_{v}$ and $C$ be a vertex
cover of $G$ of size $k$ containing $x$. If $C$ contains both $v$ and $w$, the
vertex cover obtained by restricting $C$ to $V(G_{v})$ gives a vertex cover of
$G_{v}$ of size at most $k$. If $G$ does not contain $v$ (respectively, $w$),
then $C^{\prime}=C\setminus\\{u\\}\cup\\{v\\}$ (respectively,
$C^{\prime}=C\setminus\\{u\\}\cup\\{w\\}$) is a vertex cover of $G_{v}$ of
size $k$ that contains $x$, $v$ and $w$. Therefore, for any vertex $x\in
V(G_{v})$, $\operatorname{mvc}_{xvw}(G_{v})\leq k$ containing $x$ along with
both $v$ and $w$. By Proposition 1, $\operatorname{evc}_{vw}(G_{v})\leq
k=\operatorname{evc}(G)$.

  4. 4.

By Proposition 1, $\operatorname{evc}_{v}(G)\geq\operatorname{mvc}_{uv}(G)$
and it is easy to see that
$\operatorname{evc}_{v}(G)\geq\operatorname{evc}(G)$. Hence,
$\operatorname{evc}_{v}(G)\geq\max\\{\operatorname{mvc}_{uv}(G),\operatorname{evc}(G)\\}$.
Now, we need to show that
$\operatorname{evc}_{v}(G)\leq\max\\{\operatorname{mvc}_{uv}(G),\operatorname{evc}(G)\\}$.
By Proposition 2, $\operatorname{evc}_{v}(G)\leq\operatorname{evc}(G)+1$. If
$\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$, then we are done. Hence,
suppose $\operatorname{evc}_{v}(G)=\operatorname{evc}(G)+1$. In this case, it
is enough to show that
$\operatorname{mvc}_{uv}(G)\geq\operatorname{evc}(G)+1$. By Proposition 1, we
know that $\operatorname{evc}(G)=\max_{x\in V(G)}\operatorname{mvc}_{x}(G)$.
Since degree of $u$ is $2$, this implies that for any vertex $x\in
V(G)\setminus\\{u\\}$, $\operatorname{mvc}_{xv}(G)\leq\operatorname{evc}(G)$.
If $\operatorname{mvc}_{uv}(G)\leq\operatorname{evc}(G)$, then by Proposition
1, $\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$ which is a contradiction.
Hence, $\operatorname{mvc}_{uv}(G)\geq\operatorname{evc}(G)+1$ as required.∎

Now, we derive some upper bounds for $\mathscr{E}(G,uv)$ when $deg_{G}(u)>2$
and $deg_{G}(v)>2$.

###### Proposition 3

  1. 1.

$\max_{x\in
V(G_{v})}\operatorname{mvc}_{x}(G)\leq\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})\\\
-1,\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})\\}$

  2. 2.

$\max_{x\in
V(G_{u})}\operatorname{mvc}_{x}(G)\leq\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}(G_{u})+\operatorname{mvc}(G_{v})\\}$.

###### Proof

Since Parts 1 and 2 are symmetric, we only prove Part 1. Consider a vertex
$x\in V(G_{v})$. It can be easily seen that
$\operatorname{mvc}_{x}(G)\leq\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}_{xvw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{xw}(G_{v})-1\\}$.
By Proposition 1, we get
$\operatorname{mvc}_{x}(G)\leq\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.
Now, it remains to prove that
$\operatorname{mvc}_{x}(G)\leq\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})$.
If $\operatorname{mvc}_{x}(G_{v})=\operatorname{mvc}_{xv}(G_{v})$, then
$\operatorname{mvc}_{x}(G)\leq\operatorname{mvc}(G_{u})+\operatorname{mvc}_{xv}(G_{v})=\operatorname{mvc}(G_{u})+\operatorname{mvc}_{x}(G_{v})\leq\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})$
by Proposition 1. Otherwise, it is the case that
$\operatorname{mvc}_{x}(G_{v})=\operatorname{mvc}_{xw}(G_{v})$. This implies
$\operatorname{mvc}_{x}(G)\leq\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{xw}(G_{v})-1$.
Since, $\operatorname{mvc}_{uw}(G)\leq\operatorname{mvc}(G_{u})+1$, we get
$\operatorname{mvc}_{x}(G)\leq\operatorname{mvc}(G_{u})+\operatorname{mvc}_{xw}(G_{v})=\operatorname{mvc}(G_{u})+\operatorname{mvc}_{x}(G_{v})\leq\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})$
by Proposition 1. ∎

Lemma 5 gives an upper bound for $\operatorname{evc}(G)$ when $deg_{G}(u)>2$
and $deg_{G}(v)>2$.

###### Lemma 5

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then:

  1. 1.

$\operatorname{evc}(G)\leq\min\\{\operatorname{mvc}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$

  2. 2.

$\operatorname{evc}(G)\leq\max\\{U,V\\}$ where
$U=\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}(G_{u})+\operatorname{mvc}(G_{v})\\}$
and
$V=\min\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})\\}$

###### Proof

  1. 1.

By Proposition 1, it is easy to see that
$\operatorname{evc}(G)\leq\min\\{\operatorname{mvc}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.

  2. 2.

By Proposition 3, we have $\max_{x\in
V(G)}\operatorname{mvc}_{x}(G)\leq\max(U,V)$. Hence, by Proposition 1, we get
$\operatorname{evc}(G)\leq\max(U,V)$.

###### Proposition 4

  1. 1.

$\max_{x\in
V(G_{v})}\operatorname{mvc}_{xv}(G)\leq\min\\{\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v}),\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$

  2. 2.

$\max_{x\in
V(G_{u})}\operatorname{mvc}_{xv}(G)\leq\min\\{\operatorname{evc}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1\\}$

###### Proof

  1. 1.

It is easy to see that for any vertex $x\in V(G_{v})$,
$\operatorname{mvc}_{xv}(G)\leq\operatorname{mvc}_{w}(G_{u})+\operatorname{mvc}_{xvw}(G_{v})-1$
and
$\operatorname{mvc}_{xv}(G)\leq\operatorname{mvc}(G_{u})+\operatorname{mvc}_{xv}(G_{v})$.
By Proposition 1, we get the result.

  2. 2.

It is easy to see that for any vertex $x\in V(G_{u})$,
$\operatorname{mvc}_{xv}(G)\leq\operatorname{mvc}_{x}(G_{u})+\operatorname{mvc}_{v}(G_{v})$
and
$\operatorname{mvc}_{xv}(G)\leq\operatorname{mvc}_{xw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$.
By Proposition 1, we get the result. ∎

Lemma 6 gives an upper bound for $\operatorname{evc}_{v}(G)$ when
$deg_{G}(u)>2$ and $deg_{G}(v)>2$.

###### Lemma 6

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then:

  1. 1.

$\operatorname{evc}_{v}(G)\leq\min\\{\operatorname{evc}(G)+1,\operatorname{mvc}_{v}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$

  2. 2.

$\operatorname{evc}_{v}(G)\leq\max\\{U,V\\}$, where
$U=\min\\{\operatorname{evc}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1\\}$
and
$V=\min\\{\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v}),\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$

###### Proof

  1. 1.

By Proposition 2, we know that
$\operatorname{evc}_{v}(G)\leq\operatorname{evc}(G)+1$. By Proposition 4,
$\max_{x\in V(G_{u})}\\\
\operatorname{mvc}_{xv}(G)\leq\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1\leq\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$
and $\max_{x\in
V(G_{v})}\operatorname{mvc}_{xv}(G)\leq\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\leq\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$.
By Proposition 1, we get
$\operatorname{evc}_{v}(G)\leq\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$.
By Proposition 1, we also get
$\operatorname{evc}_{v}(G)\leq\operatorname{mvc}_{v}(G)+1$. Hence, we are
done.

  2. 2.

By Proposition 4, we have $\max_{x\in V(G_{u})}\operatorname{mvc}_{vx}(G)\leq
U$ and $\max_{y\in V(G_{v})}\operatorname{mvc}_{vy}(G)\leq V$. Therefore, by
Proposition 1, we get $\operatorname{evc}_{v}(G)=\max_{x\in
V(G)}\operatorname{mvc}_{vx}(G)\leq\max\\{U,V\\}$.

Proposition 5 and Lemma 7 are symmetric to Proposition 4 and Lemma 6
respectively.

###### Proposition 5

  1. 1.

$\max_{x\in
V(G_{u})}\operatorname{mvc}_{xu}(G)\leq\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\\}$

  2. 2.

$\max_{x\in
V(G_{v})}\operatorname{mvc}_{xu}(G)\leq\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}(G_{v}),\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$

###### Lemma 7

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then:

  1. 1.

$\operatorname{evc}_{u}(G)\leq\min\\{\operatorname{evc}(G)+1,\operatorname{mvc}_{u}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$

  2. 2.

$\operatorname{evc}_{u}(G)\leq\max\\{U,V\\}$, where
$U=\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\\}$
and
$V=\min\\{\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}(G_{v}),\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$

###### Proposition 6

  1. 1.

$\max_{x\in
V(G_{u})}\operatorname{mvc}_{xuv}(G)\leq\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$

  2. 2.

$\max_{x\in
V(G_{v})}\operatorname{mvc}_{xuv}(G)\leq\min\\{\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$

###### Proof

  1. 1.

Consider any vertex $x\in V(G_{u})$. By Proposition 1, we have
$\operatorname{mvc}_{xuw}(G_{u})\leq\operatorname{evc}_{uw}(G_{u})$. This
implies
$\operatorname{mvc}_{xuv}(G)\leq\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$.
Similarly, by Proposition 1, we have
$\operatorname{mvc}_{xu}(G_{u})\leq\operatorname{evc}_{u}(G_{u})$. This
implies
$\operatorname{mvc}_{xuv}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})$.
Thus, for any $x\in V(G_{u})$, we have
$\operatorname{mvc}_{xuv}(G)\leq\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$.

  2. 2.

This case is symmetric to the previous one.

Lemma 8 gives an upper bound for $\operatorname{evc}_{uv}(G)$ when
$deg_{G}(u)>2$ and $deg_{G}(v)>2$.

###### Lemma 8

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then:

  1. 1.

$\operatorname{evc}_{uv}(G)\leq\min\\{\operatorname{evc}(G)+1,\operatorname{mvc}_{uv}(G)+1,\max\\{P_{1},P_{2}\\}\\}$,
where
$P_{1}=\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$
and
$P_{2}=\min\\{\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$

  2. 2.

$\operatorname{evc}_{uv}(G)\leq\min\\{Q,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{evc}(G_{v}),\operatorname{evc}_{v}(G_{v})+\operatorname{evc}(G_{u})\\}$,
where
$Q=\max\\{\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$

###### Proof

  1. 1.

By Proposition 2, we know that
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}(G)+1$. By Proposition 1, we
know that $\operatorname{evc}_{uv}(G)\leq\operatorname{mvc}(G)+1$. By
Proposition 1 and Proposition 6, we get $\operatorname{evc}_{uv}(G)=\max_{x\in
V(G)}\\\ \operatorname{mvc}_{xuv}(G)\leq max(P_{1},P_{2})$.

  2. 2.

It can be easily seen that
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$.
Now, we show that $\operatorname{evc}_{uv}(G)\leq Q$. By Proposition 6, we get
$\max_{x\in
V(G)}\operatorname{mvc}_{xuv}(G)\leq\max\\{\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$.
Hence, by Proposition 1, we get $\operatorname{evc}_{uv}(G)\leq Q$.
Next, we show that
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}(G_{v})$.
By Proposition 1 and Proposition 6, we get $\max_{x\in
V(G_{u})}\operatorname{mvc}_{xuv}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}(G_{v})$.
Since $\operatorname{mvc}_{uw}(G_{u})\leq\operatorname{evc}_{u}(G_{u})$ by
Proposition 1 and
$\operatorname{evc}_{vw}(G_{v})\leq\operatorname{evc}(G_{v})+1$ by Proposition
2, using Proposition 6, we get $\max_{x\in
V(G_{v})}\operatorname{mvc}_{xuv}(G)\leq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}(G_{v})$.
Hence, by Proposition 1, we get
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}(G_{v})$.
Symmetrically, we can prove that
$\operatorname{evc}_{uv}(G)\leq\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})$.

The following lemma gives some lower bounds for $\mathscr{E}(G,uv)$ when
$deg_{G}(u)>2$ and $deg_{G}(v)>2$.

###### Lemma 9

If $deg_{G}(u)>2$ and $deg_{G}(v)>2$, then:

  1. 1.

$\operatorname{evc}(G)\geq\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$

  2. 2.

$\operatorname{evc}_{u}(G)\geq\max\\{\operatorname{evc}(G),\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1,\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1,\\\
\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1\\}$

  3. 3.

$\operatorname{evc}_{uv}(G)\geq\max\\{\operatorname{evc}(G),\operatorname{evc}_{u}(G),\operatorname{evc}_{v}(G),\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{v}(G_{v})-1,\\\
\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{v}(G_{v})-1,\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$

###### Proof

  1. 1.

For any vertex $x\in V(G_{u})$, consider a minimum vertex cover $S_{x}$ of $G$
of size $\operatorname{mvc}_{x}(G)$ containing $x$. It is easy to see that
$|S_{x}\cap V(G_{v})|\geq\operatorname{mvc}(G_{v})$. If $w\in S_{x}$, then
$|S_{x}\cap V(G_{u})|\geq\operatorname{mvc}_{wx}(G_{u})$ and hence,
$\operatorname{mvc}_{x}(G)\geq\operatorname{mvc}_{wx}(G_{u})+\operatorname{mvc}(G_{v})-1$.
If $w\notin S_{x}$, then $|S_{x}\cap
V(G_{u})|\geq\operatorname{mvc}_{x}(G_{u})$. Therefore,
$\operatorname{mvc}_{x}(G)\geq\operatorname{mvc}_{x}(G_{u})+\operatorname{mvc}(G_{v})$.
Since $\operatorname{mvc}_{wx}(G_{u})\leq\operatorname{mvc}_{x}(G_{u})+1$, in
this case also we get
$\operatorname{mvc}_{x}(G)\geq\operatorname{mvc}_{wx}(G_{u})+\operatorname{mvc}(G_{v})-1$.
By Proposition 1, we get $\operatorname{evc}(G)\geq\max_{x\in
V(G_{u})}\operatorname{mvc}_{x}(G)\\\ \geq\max_{x\in
V(G_{u})}\operatorname{mvc}_{wx}(G_{u})+\operatorname{mvc}(G_{v})-1\geq\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1$.
Symmetrically, we get
$\operatorname{evc}(G)\geq\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.
From this, the result follows.

  2. 2.

By Proposition 1, it can be easily seen that
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}(G)$. By Proposition 1, there
exists a vertex $x\in V(G_{v})$ such that
$\operatorname{mvc}_{x}(G_{v})=\operatorname{evc}(G_{v})$. Let $S_{xu}$ be a
vertex cover of $G$ of size $\operatorname{mvc}_{xu}(G)$ containing $x$ and
$u$. If $w\in S_{xu}$, then it can be seen that
$|S_{xu}|\geq\operatorname{mvc}_{uw}(G_{u})+\operatorname{mvc}_{x}(G_{v})-1=\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1$.
Otherwise, we get
$|S_{xu}|\geq\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}(G_{v})\geq\operatorname{mvc}_{uw}(G_{u})-1+\operatorname{evc}(G_{v})$.
Hence, by Proposition 1, we get
$\operatorname{evc}_{u}(G)\geq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1$.
Next, we to show that
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
For every vertex $x\in V(G_{u})$,
$\operatorname{mvc}_{xu}(G)\geq\operatorname{mvc}_{xuw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
By Proposition 1, it can be seen that $\operatorname{evc}_{u}(G)\geq\max_{x\in
V(G_{u})}\operatorname{mvc}_{xu}(G)\geq\max_{x\in
V(G_{u})}\operatorname{mvc}_{xuw}(G_{u})+\operatorname{mvc}(G_{v})-1=\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
Now, it remains to show that
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1$.
By Proposition 1, there exists a vertex $x\in V(G_{u})$ such that
$\operatorname{mvc}_{xu}(G_{u})=\operatorname{evc}(G_{u})$. Let $S_{xu}$ be a
vertex cover of $G$ of size $\operatorname{mvc}_{xu}(G)$ containing $x$ and
$u$. If $w\in S_{xu}$, then it can be seen that
$|S_{xu}|\geq\operatorname{mvc}_{xuw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1=\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1$.
Otherwise, we get
$|S_{xu}|\geq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v})\geq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1$.
Hence, by Proposition 1, we get
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1$.

  3. 3.

By Proposition 1, it can be easily seen that
$\operatorname{evc}_{uv}(G)\geq\max\\{\operatorname{evc}(G),\operatorname{evc}_{u}(G),\operatorname{evc}_{v}(G)\\}$.
Similar to the proof of
$\operatorname{evc}_{u}(G)\geq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})$
in the previous case, we get
$\operatorname{evc}_{uv}(G)\geq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{v}(G_{v})-1$
and
$\operatorname{evc}_{uv}(G)\geq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1$.
Similar to the proof of
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$
in the previous case, we get
$\operatorname{evc}_{uv}(G)\geq\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{v}(G_{v})-1$
and
$\operatorname{evc}_{uv}(G)\geq\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$.∎

##  5 Computation of the evc parameters

Let $G$ be a maximal outerplanar graph with at least four vertices, $uv$ be an
edge on its outer face and $w=\Delta(uv)$. In this section, we describe the
method of computing $\mathscr{E}(G,uv)$ using the bounds obtained in Section
4.

###  5.1 Computing $\mathscr{E}(G,uv)$ when $deg_{G}(u)=2$

In this subsection, we consider the case when $u$ is a degree-$2$ vertex in
$G$.

###### Lemma 10

Let $\operatorname{mvc}(G_{v})\neq\operatorname{evc}(G_{v})$. Then,
$\operatorname{evc}(G)=\operatorname{evc}(G_{v})$ if and only if
$\operatorname{evc}_{vw}(G_{v})=\operatorname{evc}(G_{v})$.

###### Proof

Let
$\operatorname{mvc}(G_{v})<\operatorname{evc}(G_{v})\leq\operatorname{evc}_{vw}(G_{v})$.
Then, by Proposition 1,
$\operatorname{evc}(G_{v})=\operatorname{mvc}(G_{v})+1$. Lemma 4 Part 3,
$\operatorname{evc}(G)\geq\operatorname{evc}_{vw}(G_{v})$.

To prove the forward direction, assume
$\operatorname{evc}(G)=\operatorname{evc}(G_{v})$. This gives
$\operatorname{evc}(G_{v})=\operatorname{evc}(G)\geq\operatorname{evc}_{vw}(G_{v})$.
This implies $\operatorname{evc}(G_{v})=\operatorname{evc}_{vw}(G_{v})$. Now,
to prove the reverse direction, assume
$\operatorname{evc}_{vw}(G_{v})=\operatorname{evc}(G_{v})$. It is enough to
show that $\operatorname{evc}(G)\leq\operatorname{evc}_{vw}(G_{v})$. By
Proposition 1, for any vertex $x\in V(G_{v})$, we get
$\operatorname{mvc}_{xvw}(G_{v})\leq\operatorname{evc}(G_{v})$ which implies
$\operatorname{mvc}_{x}(G)\leq\operatorname{evc}(G_{v})$. Moreover, since
$\operatorname{mvc}_{u}(G)\leq\operatorname{mvc}(G_{v})+1=\operatorname{evc}(G_{v})$,
by Proposition 1,
$\operatorname{evc}(G)\leq\operatorname{evc}(G_{v})=\operatorname{evc}_{vw}(G_{v})$.∎

###### Lemma 11

$\operatorname{evc}(G)=\text{max}\\{\operatorname{mvc}(G_{v})+1,\operatorname{evc}_{vw}(G_{v})\\}$.

###### Proof

We prove this lemma by splitting into following two cases.

  1. 1.

Suppose $\operatorname{mvc}(G_{v})=\operatorname{evc}(G_{v})$. In this case,
by Lemma 4, Part 1 and Part 3, we have
$\operatorname{evc}(G)=\operatorname{evc}(G_{v})+1=\operatorname{mvc}(G_{v})+1$.
Further by Part 3 of Lemma 4,
$\operatorname{evc}_{vw}(G_{v})\leq\operatorname{evc}(G)$. Thus, we have
$\operatorname{evc}(G)=\text{max}\\{\operatorname{mvc}(G_{v})+1,\operatorname{evc}_{vw}(G_{v})\\}$.

  2. 2.

Suppose $\operatorname{mvc}(G_{v})<\operatorname{evc}(G_{v})$. If
$\operatorname{evc}_{vw}(G_{v})=\operatorname{evc}(G_{v})$, then by Lemma 10,
we have
$\operatorname{evc}(G)=\operatorname{evc}(G_{v})=\operatorname{evc}_{vw}(G_{v})=\operatorname{mvc}(G_{v})+1$.
Else if $\operatorname{evc}_{vw}(G_{v})\neq\operatorname{evc}(G_{v})$, then by
Lemma 10 and Proposition 2, we get
$\operatorname{evc}(G)=\operatorname{evc}(G_{v})+1=\operatorname{evc}_{vw}(G_{v})$.
In both the cases, we can observe that
$\operatorname{evc}(G)=\max\\{\operatorname{mvc}(G_{v})+1,\operatorname{evc}_{vw}(G_{v})\\}$.∎

From Lemma 4 and Lemma 11, the following theorem is immediate.

###### Theorem 5.1

Let $G$ be a maximal outerplanar graph and $u$ be a degree-2 vertex in $G$
with neighbors $v$ and $w$.

  1. 1.

Given $\operatorname{mvc}(G_{v})$ and $\mathscr{E}(G_{v},vw)$, it is possible
to compute $\operatorname{evc}(G)$ in constant time.

  2. 2.

Given $\operatorname{evc}(G)$, $\mathscr{M}(G,uv)$ and
$\mathscr{E}(G_{v},vw)$, it is possible to compute the remaining evc
parameters of $G$ with respect to $uv$ in constant time.

###  5.2 Computing $\mathscr{E}(G,uv)$ when $deg_{G}(u)>2$ and $deg_{G}(v)>2$

Now, we will see how $\mathscr{E}(G,uv)$ can be computed when $deg_{G}(u)>2$
and $deg_{G}(v)>2$ using $\operatorname{mvc}(G)$, $\mathscr{M}(G_{u},uw)$,
$\mathscr{M}(G_{v},vw)$, $\mathscr{E}(G_{u},uw)$ and $\mathscr{E}(G_{v},vw)$.
For this subsection, we will assume that $deg_{G}(u)>2$ and $deg_{G}(v)>2$. We
will also assume that $\operatorname{mvc}(G_{u})=k_{u}$ and
$\operatorname{mvc}(G_{v})=k_{v}$.

Lemmas 12-14 handle the computation of $\operatorname{evc}(G)$.

###### Lemma 12

If $\operatorname{evc}(G_{u})=k_{u}$ and $\operatorname{evc}(G_{v})=k_{v}$,
then
$\operatorname{evc}(G)=\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.

###### Proof

First, suppose $\operatorname{evc}_{w}(G_{u})=k_{u}$ and
$\operatorname{evc}_{w}(G_{v})=k_{v}$. By Lemma 5 Part 1, we have
$\operatorname{evc}(G)\leq k_{u}+k_{v}-1$. By Observation 3 and Proposition 1,
we get $\operatorname{evc}(G)=k_{u}+k_{v}-1$. Note that in this case
$\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}=k_{u}+k_{v}-1$
as well.

Now, by Proposition 2, it remains to consider the case when
$\operatorname{evc}_{w}(G_{u})=k_{u}+1$ or
$\operatorname{evc}_{w}(G_{v})=k_{v}+1$. In this case,
$\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}=k_{u}+k_{v}$.
We will show that $\operatorname{evc}(G)=k_{u}+k_{v}$. From Lemma 5 Part 2, we
get
$\operatorname{evc}(G)\leq\max\\{\operatorname{evc}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}(G_{v})\\}=k_{u}+k_{v}$.
By Lemma 9 Part 1, we get
$\operatorname{evc}(G)\geq\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.
Hence, we are done.∎

###### Lemma 13

If $\operatorname{evc}(G_{u})=k_{u}$ and $\operatorname{evc}(G_{v})=k_{v}+1$,
then
$\operatorname{evc}(G)=\min\\{\operatorname{mvc}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.

###### Proof

Since $\operatorname{evc}(G_{v})=k_{v}+1$, by Lemma 9 Part 1, we get
$\operatorname{evc}(G)\geq k_{u}+k_{v}$. By Observation 3 and Proposition 1,
we get $\operatorname{evc}(G)\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$. By
Proposition 2, it is easy to see that
$\min\\{\operatorname{mvc}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$.

Let $U$ and $V$ be as defined in Lemma 5 Part 2. From our assumptions, it
follows that $U\leq k_{u}+k_{v}$ and $V\geq k_{u}+k_{v}$. Hence by Lemma 5
Part 2, we get $\operatorname{evc}(G)\leq V\leq
min\\{\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$. From
this, using Proposition 1, we get $\operatorname{evc}(G)\leq
min\\{\operatorname{mvc}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.

Hence, it suffices to show that when $\operatorname{evc}(G)=k_{u}+k_{v}$, then
$min\\{\operatorname{mvc}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}=k_{u}+k_{v}$.
For this, suppose $\operatorname{evc}(G)=k_{u}+k_{v}$. By Lemma 9 Part 1, we
have $\operatorname{evc}_{w}(G_{u})\leq k_{u}+1$ and
$\operatorname{evc}_{w}(G_{v})\leq k_{v}+1$. If
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$, we get
$\min\\{\operatorname{evc}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1$,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}\leq
k_{u}+k_{v}=\operatorname{evc}(G)$ as required. Therefore, let us assume that
$\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$. In this case, it is enough to show
that $\operatorname{evc}_{vw}(G_{v})=k_{v}+1$. By Proposition 1, there exists
a vertex $x\in V(G_{v})$ such that $\operatorname{mvc}_{x}(G_{v})=k_{v}+1$.
Consider such a vertex $x$. By Proposition 1, we know there exits a vertex
cover $S_{x}$ of $G$ such that $x\in S_{x}$ and
$|S_{x}|=\operatorname{evc}(G)=k_{u}+k_{v}$. Since
$\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$ and
$\operatorname{mvc}_{x}(G_{v})=k_{v}+1$, it is easy to see that $u\notin
S_{x}$ and hence $v,w\in S_{x}$. Further, $|S_{x}\cap V(G_{v})|=k_{v}+1$ and
hence $\operatorname{mvc}_{xvw}(G_{v})=k_{v}+1$. By Proposition 1, this
implies that $\operatorname{evc}_{vw}(G_{v})=k_{v}+1$, as required.∎

###### Lemma 14

If $\operatorname{evc}(G_{u})=k_{u}+1$ and
$\operatorname{evc}(G_{v})=k_{v}+1$, then
$\operatorname{evc}(G)=\min\\{\operatorname{mvc}(G)+1,\max\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}\\}$.

###### Proof

Since $\operatorname{evc}(G_{v})=k_{v}+1$, by Lemma 9 Part 1, we get
$\operatorname{evc}(G)\geq k_{u}+k_{v}$. By Observation 3 and Proposition 1,
we get $\operatorname{evc}(G)\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$. By
Proposition 2, it is easy to see that
$\min\\{\operatorname{mvc}(G)+1,\max\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}\\}\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$.

By Lemma 5, we get
$\operatorname{evc}(G)\leq\min\\{\operatorname{mvc}(G)+1,\max\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{evc}_{vw}(G_{v})+\operatorname{mvc}_{w}(G_{u})-1\\}\\}$.
Hence, it is enough to show that if $\operatorname{evc}(G)=k_{u}+k_{v}$, then
$\min\\{\operatorname{mvc}(G)+1,\max\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{evc}_{vw}(G_{v})+\operatorname{mvc}_{w}(G_{u})-1\\}\\}=k_{u}+k_{v}$.

For this, suppose $\operatorname{evc}(G)=k_{u}+k_{v}$. Since
$\operatorname{evc}(G)=k_{u}+k_{v}$, $\operatorname{evc}(G_{u})=k_{u}+1$ and
$\operatorname{evc}(G_{v})=k_{v}+1$, by Lemma 9 Part 1, we get
$\operatorname{evc}_{w}(G_{u})=k_{u}+1$ and
$\operatorname{evc}_{w}(G_{v})=k_{v}+1$. Now, it is enough to show that
$\operatorname{mvc}_{w}(G_{u})=k_{u}$ and
$\operatorname{mvc}_{w}(G_{v})=k_{v}$. Since
$\operatorname{evc}_{w}(G_{u})=k_{u}+1$, by Proposition 1, there exists a
vertex $x\in V(G_{u})$ such that $\operatorname{mvc}_{xw}(G_{u})=k_{u}+1$. By
Proposition 1, we know
$k_{u}+k_{v}=\operatorname{evc}(G)\geq\operatorname{mvc}_{x}(G)$. Therefore,
it has to be the case that $\operatorname{mvc}_{w}(G_{v})=k_{v}$.
Symmetrically, we get $\operatorname{mvc}_{w}(G_{u})=k_{u}$.∎

Lemmas 15\- 21 deal with the computation of the remaining parameters in
$\mathscr{E}(G,uv)$ using $\operatorname{evc}(G)$, $\mathscr{M}(G,uv)$,
$\mathscr{M}(G_{u},uw)$, $\mathscr{M}(G_{v},vw)$, $\mathscr{E}(G_{u},uw)$ and
$\mathscr{E}(G_{v},vw)$.

###### Lemma 15

If $\operatorname{evc}(G_{u})=k_{u}$, $\operatorname{evc}(G_{v})=k_{v}$ and
$\operatorname{evc}(G)=k_{u}+k_{v}-1$, then
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$,
$\operatorname{evc}_{v}(G)=\operatorname{evc}_{vw}(G_{v})+\operatorname{mvc}(G_{u})-1$
and
$\operatorname{evc}_{uv}(G)=min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$.

###### Proof

By Lemma 9 Part 1, we know
$\operatorname{evc}(G)\geq\max\\{\operatorname{evc}_{w}(G_{u})+\operatorname{mvc}(G_{v})-1,\operatorname{mvc}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.
Therefore, we get $\operatorname{evc}_{w}(G_{u})=k_{u}$ and
$\operatorname{evc}_{w}(G_{v})=k_{v}$. By Proposition 1, we know
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$ and
$\operatorname{mvc}_{vw}(G_{v})=k_{v}$. Hence, we get
$\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}-1$.

First, we will prove the expression for $\operatorname{evc}_{u}(G)$. By Lemma
7,
$\operatorname{evc}_{u}(G)\leq\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1=\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
By Lemma 9 Part 2, we get
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
Hence,
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}(G_{v})-1$.
Similarly, we get
$\operatorname{evc}_{v}(G)=\operatorname{evc}_{vw}(G_{v})+\operatorname{mvc}(G_{u})-1$.
Now, we show that
$\operatorname{evc}_{uv}(G)=min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$.
By Lemma 8, we have $\operatorname{evc}_{uv}(G)\leq
min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$.
By Proposition 1, we know that
$\operatorname{evc}_{uv}(G)\in\\{\operatorname{mvc}_{uv}(G),\operatorname{mvc}_{uv}(G)+1\\}$.
Now, it is enough to show that if
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)$, then
$\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1=\operatorname{mvc}_{uv}(G)$
Recall that $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}-1$. Suppose
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}-1$. Then,
by Lemma 9 Part 3, we get $\operatorname{evc}_{uw}(G_{u})=k_{u}$ and
$\operatorname{evc}_{vw}(G_{v})=k_{v}$. Therefore,
$\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1=k_{u}+k_{v}-1$.∎

###### Lemma 16

If $\operatorname{evc}(G_{u})=k_{u}$, $\operatorname{evc}(G_{v})=k_{v}$ and
$\operatorname{evc}(G)=k_{u}+k_{v}$, then
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$
and
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{evc}_{v}(G_{v})+\operatorname{mvc}(G_{u}),\operatorname{mvc}_{uv}(G)+1\\}$.

###### Proof

Since $\operatorname{evc}_{uw}(G_{u})\leq k_{u}+1$ by Proposition 2 and
$\operatorname{mvc}_{w}(G_{v})=k_{v}$ by Proposition 1, it follows by Lemma 7
that
$\operatorname{evc}_{u}(G)\leq\max\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{w}(G_{v})-1,\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}(G_{v})\\}=k_{u}+k_{v}=\operatorname{evc}(G)$
and by Lemma 9 Part 2, we get
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}(G)=k_{u}+k_{v}$, Hence, we
get $\operatorname{evc}_{u}(G)=\operatorname{evc}(G)$. Similarly, we get
$\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$.

Now, we show that
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v}),\operatorname{mvc}_{uv}(G)+1\\}$.
Since by Proposition 1, $\operatorname{mvc}_{u}(G_{u})=k_{u}$ and
$\operatorname{mvc}_{v}(G_{v})=k_{v}$, by Lemma 8 Part 1, we have
$\operatorname{evc}_{uv}(G)\leq\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v}),\operatorname{mvc}_{uv}(G)+1\\}$.
We know that
$\operatorname{evc}_{uv}(G)\in\\{\operatorname{mvc}_{uv}(G),\operatorname{mvc}_{uv}(G)+1\\}$.
So, it is now enough to show that when
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)$, then
$\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}=\operatorname{evc}_{uv}(G)$.

Consider the case when
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)$. In this case, we will
show that $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$. Since we have already
proved that $\operatorname{evc}_{u}(G)=\operatorname{evc}(G)=k_{u}+k_{v}$, by
Proposition 1, we know that $\operatorname{mvc}_{uv}(G)\leq k_{u}+k_{v}$.
Moreover, since
$\operatorname{evc}_{uv}(G)\geq\operatorname{evc}(G)=k_{u}+k_{v}$, we get
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$. It
remains to show that
$\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}=k_{u}+k_{v}$.
Since $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$, it can be easily seen that
either $\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$ or
$\operatorname{mvc}_{vw}(G_{v})=k_{v}+1$. Without loss of generality, assume
that $\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$. In this case, since
$\operatorname{evc}_{uv}(G)=k_{u}+k_{v}$, by Lemma 9 Part 3, we get
$\operatorname{evc}_{v}(G_{v})=k_{v}$. Hence, we get
$\min\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}=k_{u}+k_{v}$.∎

###### Lemma 17

If $\operatorname{evc}(G_{u})=k_{u}$, $\operatorname{evc}(G_{v})=k_{v}+1$ and
$\operatorname{mvc}(G)=k_{u}+k_{v}-1$, then:
$\operatorname{evc}_{u}(G)=\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1$,
$\operatorname{evc}_{v}(G)=\min\\{\operatorname{mvc}_{v}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\\\
\indent\indent\indent\indent\max\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}\\}$
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\max\\{\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{v}(G_{v})\\}\\}$.

###### Proof

Since $\operatorname{evc}(G_{v})=k_{v}+1$, by Lemma 13, it can be seen that
$\operatorname{evc}(G)=k_{u}+k_{v}$.

First, we will look at $\operatorname{evc}_{u}(G)$. By Lemma 9 Part 2, we get
$\operatorname{evc}_{u}(G)\geq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1$.
Now, it is enough to show that
$\operatorname{evc}_{u}(G)\leq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1$.
We know that
$\operatorname{mvc}_{u}(G)\in\\{\operatorname{mvc}(G),\operatorname{mvc}(G)+1\\}$.
First, suppose $\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G)$. In this
case, it can be seen that $\operatorname{mvc}_{uw}(G_{u})=k_{u}$ and hence,
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1=k_{u}+k_{v}$.
Moreover, by Proposition 1, we know
$\operatorname{evc}_{u}(G)\leq\operatorname{mvc}_{u}(G)+1=k_{u}+k_{v}$. Hence,
we are done. Next, suppose
$\operatorname{mvc}_{u}(G)=\operatorname{mvc}(G)+1$. In this case, by Lemma 2,
we get $\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$. Hence, we get
$\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}(G_{v})-1=k_{u}+k_{v}+1$. By
Lemma 7, we have
$\operatorname{evc}_{u}(G)\leq\operatorname{evc}(G)+1=k_{u}+k_{v}+1$. Hence,
we are done.

Now we will look at $\operatorname{evc}_{v}(G)$. Let
$Q=\min\\{\operatorname{mvc}_{v}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\max\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}\\}$,
the expression for $\operatorname{evc}_{v}(G)$ to be proved. By Lemma 6, we
have $\operatorname{evc}_{v}(G)\leq Q$. Since
$\operatorname{evc}_{v}(G)\in\\{\operatorname{mvc}_{v}(G),\operatorname{mvc}_{v}(G)+1\\}$
by Proposition 1, it is enough to show that if
$\operatorname{evc}_{v}(G)=\operatorname{mvc}_{v}(G)$, then
$Q\leq\operatorname{mvc}_{v}(G)$. Assume
$\operatorname{evc}_{v}(G)=\operatorname{mvc}_{v}(G)$. Since
$\operatorname{evc}_{v}(G)\geq\operatorname{evc}(G)=k_{u}+k_{v}$ and
$\operatorname{mvc}_{v}(G)\leq\operatorname{evc}(G)=k_{u}+k_{v}$, we have
$\operatorname{evc}_{v}(G)=\operatorname{mvc}_{v}(G)=k_{u}+k_{v}$. By Lemma 9
Part 2, we get $\operatorname{evc}_{vw}(G_{v})\leq k_{v}+1$. If
$\operatorname{evc}_{w}(G_{u})=k_{u}$, then we get $Q\leq k_{u}+k_{v}$, as
required. If this was not the case, then there exists a vertex $x\in V(G_{u})$
with $\operatorname{mvc}_{xw}(G_{u})=k_{u}+1$. If
$\operatorname{mvc}_{v}(G_{v})=k_{v}$, then we get $Q\leq k_{u}+k_{v}$
immediately. Hence, we assume $\operatorname{mvc}_{v}(G_{v})=k_{v}+1$. Then,
for the vertex $x\in V(G_{u})$ for which
$\operatorname{mvc}_{xw}(G_{u})=k_{u}+1$, we get
$\operatorname{mvc}_{xv}(G)>k_{u}+k_{v}$. Since
$\operatorname{evc}_{v}(G)\geq\operatorname{mvc}_{xv}(G)$ by Proposition 1,
this is a contradiction. Thus, $Q\leq k_{u}+k_{v}$.

Now, we will consider $\operatorname{evc}_{uv}(G)$. Let
$P=\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\max\\{\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{v}(G_{v})\\}\\}$,
the expression for $\operatorname{evc}_{uv}(G)$ to be proved. By Lemma 8, we
get $\operatorname{evc}_{uv}(G)\leq P$. Now, we will show that
$\operatorname{evc}_{uv}(G)\geq P$. Since
$\operatorname{evc}_{uv}(G)\in\\{\operatorname{mvc}_{uv}(G),\operatorname{mvc}_{uv}(G)+1\\}$
by Proposition 1, it is enough to show that if
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)$, then
$P\leq\operatorname{mvc}_{uv}(G)$. Assume
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)$. Since
$\operatorname{evc}_{uv}(G)\geq\operatorname{evc}(G)=k_{u}+k_{v}$ and
$\operatorname{mvc}_{uv}(G)\leq k_{u}+k_{v}$, we know that
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$. By Lemma
9 Part 3, we get $\operatorname{evc}_{vw}(G_{v})=k_{v}+1$. If
$\operatorname{evc}_{uw}(G_{u})=k_{u}$, then it can be seen that $P\leq
k_{u}+k_{v}$. Hence, assume $\operatorname{evc}_{uw}(G_{u})=k_{u}+1$. Then, by
Lemma 9 Part 3, we get $\operatorname{mvc}_{v}(G_{v})=k_{v}$. Further, by
Lemma 9 Part 3, it can be seen that $\operatorname{mvc}_{uw}(G_{u})=k_{u}$.
This implies $\operatorname{mvc}_{vw}(G_{v})=k_{v}+1$ by Lemma 2. Hence, by
Lemma 9, we get $\operatorname{evc}_{u}(G_{u})=k_{u}$. Therefore, we get
$P\leq k_{u}+k_{v}=\operatorname{evc}_{uv}(G)$.

###### Lemma 18

If $\operatorname{evc}(G_{u})=k_{u}$, $\operatorname{evc}(G_{v})=k_{v}+1$ and
$\operatorname{mvc}(G)=evc(G)=k_{u}+k_{v}$, then:
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$,
$\operatorname{evc}_{v}(G)=\min\\{\operatorname{mvc}_{v}(G)+1,\operatorname{evc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\\\
\indent\indent\indent\indent\max\\{\operatorname{mvc}_{w}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{evc}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}\\}$
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{evc}(G)+1,\max\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}\\}$.

###### Proof

First, we will show that
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.
Since $\operatorname{evc}(G)=k_{u}+k_{v}$, by Lemma 9 Part 1,
$\operatorname{evc}_{w}(G_{v})\leq k_{v}+1$, which implies
$\operatorname{evc}_{w}(G_{v})=k_{v}+1$. Further, by Proposition 2,
$\operatorname{evc}_{u}(G)\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$. Now, it is
enough to show that if
$\operatorname{evc}_{u}(G)=\operatorname{evc}(G)=k_{u}+k_{v}$, then
$\operatorname{evc}_{u}(G_{u})=k_{u}$ and if
$\operatorname{evc}_{u}(G)=\operatorname{evc}(G)+1=k_{u}+k_{v}+1$, then
$\operatorname{evc}_{u}(G_{u})=k_{u}+1$. First, suppose
$\operatorname{evc}_{u}(G)=k_{u}+k_{v}$. By Lemma 9 Part 2, we get
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$ and by Lemma 1, we get
$\operatorname{mvc}_{w}(G_{v})\neq k_{v}$. Hence, we have
$\operatorname{mvc}_{v}(G_{v})=k_{v}$. For contradiction, suppose
$\operatorname{evc}_{u}(G_{u})=k_{u}+1$. Then, by Proposition 1, there exists
a vertex $x\in V(G_{u})$, such that $\operatorname{mvc}_{xu}(G_{u})=k_{u}+1$.
Since $\operatorname{mvc}_{w}(G_{v})=k_{v}+1$, this implies
$\operatorname{mvc}_{xu}(G)\geq k_{u}+k_{v}+1$. By Proposition 1, this
contradicts the value of $\operatorname{evc}_{u}(G)$. Hence, we get
$\operatorname{evc}_{u}(G_{u})=k_{u}$ as required. Next, suppose
$\operatorname{evc}_{u}(G)=k_{u}+k_{v}+1$. For contradiction, suppose
$\operatorname{evc}_{u}(G_{u})=k_{u}$. Then, by Proposition 1, we get
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$. By Lemma 7, we have
$\operatorname{evc}_{u}(G)\leq\max\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v}),\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}=k_{u}+k_{v}$,
which is a contradiction. Hence, $\operatorname{evc}_{u}(G_{u})=k_{u}+1$ and
we are done.

The proof of the expression for $\operatorname{evc}_{v}(G)$ is exactly the
same as that in the proof of Lemma 17.

Now we will look at $\operatorname{evc}_{uv}(G)$. Let
$P=\max\\{\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v}),\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1\\}$.
We need to show that
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{evc}(G)+1,P\\}$. By Lemma 8,
we get $\operatorname{evc}_{uv}(G)\leq\min\\{\operatorname{evc}(G)+1,P\\}$.
Now, we will show that
$\operatorname{evc}_{uv}(G)\geq\min\\{\operatorname{evc}(G)+1,P\\}$. If
$\operatorname{evc}_{uv}(G)=\operatorname{evc}(G)+1$, we are done. Therefore,
consider the case when
$\operatorname{evc}_{uv}(G)=\operatorname{evc}(G)=k_{u}+k_{v}$. In this case,
we show that $P\leq k_{u}+k_{v}$. Since $\operatorname{mvc}(G)=k_{u}+k_{v}$
and $\operatorname{mvc}_{w}(G_{u})=k_{u}$ by Proposition 1, we get
$\operatorname{mvc}_{vw}(G_{v})=k_{v}+1$ by Lemma 1. Hence, by Lemma 9 Part 3,
we get $\operatorname{evc}_{u}(G_{u})=k_{u}$. Moreover, we also get
$\operatorname{evc}_{vw}(G_{v})=k_{v}+1$ and
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$ by Lemma 9 Part 3. Therefore, since
$\operatorname{mvc}(G)=k_{u}+k_{v}$, we know
$\operatorname{mvc}_{w}(G_{v})\neq k_{v}$. This implies
$\operatorname{mvc}_{v}(G_{v})=k_{v}$. Thus, we get $P\leq k_{u}+k_{v}$.

###### Lemma 19

If $\operatorname{evc}(G_{u})=k_{u}$, $\operatorname{evc}(G_{v})=k_{v}+1$ and
$\operatorname{evc}(G)=k_{u}+k_{v}+1$, then
$\operatorname{evc}_{u}(G)=\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$
and
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.

###### Proof

First, we will show that $\operatorname{evc}_{u}(G)=\operatorname{evc}(G)$.
Since we know that $\operatorname{evc}_{u}(G)\geq\operatorname{evc}(G)$ by
Lemma 9 Part 2, it is enough to show that
$\operatorname{evc}_{u}(G)\leq\operatorname{evc}(G)$. For any vertex $x\in
V(G_{u})$, we have $\operatorname{mvc}_{x}(G_{u})=k_{u}$ by Proposition 1 and
hence $\operatorname{mvc}_{xu}(G_{u})\leq k_{u}+1$. This implies
$\operatorname{mvc}_{xu}(G)\leq k_{u}+k_{v}+1=\operatorname{evc}(G)$.
Similarly, for any vertex $y\in V(G_{v})$, we have
$\operatorname{mvc}_{y}(G_{v})\leq k_{v}+1$. Hence,
$\operatorname{mvc}_{yu}(G)\leq k_{u}+k_{v}+1$. Therefore, by Proposition 1,
$\operatorname{evc}_{u}(G)\leq k_{u}+k_{v}+1$. Hence,
$\operatorname{evc}_{u}(G)=\operatorname{evc}(G)$.

Next, we will show that $\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$.
Since we know that $\operatorname{evc}_{v}(G)\geq\operatorname{evc}(G)$ by
Lemma 9 Part 2, it is enough to show that
$\operatorname{evc}_{v}(G)\leq\operatorname{evc}(G)$. For any vertex $x\in
V(G_{u})$, we have $\operatorname{mvc}_{x}(G_{u})=k_{u}$ by Proposition 1 and
hence $\operatorname{mvc}_{xv}(G)\leq k_{u}+k_{v}+1=\operatorname{evc}(G)$.
Similarly, for any vertex $y\in V(G_{v})$,
$\operatorname{mvc}_{yvw}(G_{v})\leq k_{v}+2$. Since
$\operatorname{mvc}_{w}(G_{u})=k_{u}$, this gives
$\operatorname{mvc}_{yv}(G)\leq k_{u}+k_{v}+1$. Therefore, by Proposition 1,
$\operatorname{evc}_{v}(G)\leq k_{u}+k_{v}+1$. Hence,
$\operatorname{evc}_{v}(G)=\operatorname{evc}(G)$.

Now, we will show that
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.
By Lemma 8, we get
$\operatorname{evc}_{uv}(G)\leq\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.
Next, we show that
$\operatorname{evc}_{uv}(G)\geq\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.
If $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}$ or
$\operatorname{evc}_{v}(G_{v})=k_{v}+1$, this is trivial. So, we are left with
the case when $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}+1$ and
$\operatorname{evc}_{v}(G_{v})=k_{v}+2$. For contradiction, suppose
$\operatorname{evc}_{uv}(G)\leq k_{u}+k_{v}+1$. By Proposition 1, there exists
a vertex $x\in V(G_{v})$ such that $\operatorname{mvc}_{xv}(G_{v})=k_{v}+2$
and this implies $\operatorname{mvc}_{xuv}(G)\geq k_{u}+k_{v}+1$ and
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$. Since
$\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}+1$, we get
$\operatorname{mvc}_{v}(G_{v})=k_{v}+1$ and
$\operatorname{mvc}_{w}(G_{v})=k_{v}$. This implies
$\operatorname{mvc}(G)=k_{u}+k_{v}-1$ and $\operatorname{mvc}_{uv}(G)\leq
k_{u}+k_{v}$, a contradiction. Therefore, $\operatorname{evc}_{uv}(G)\geq
k_{u}+k_{v}+2$, as required. Hence,
$\operatorname{evc}_{uv}(G)=\min\\{\operatorname{mvc}_{uv}(G)+1,\operatorname{evc}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.

∎

###### Lemma 20

If $\operatorname{evc}(G_{u})=k_{u}+1$ and
$\operatorname{evc}(G_{v})=k_{v}+1$, then
$\operatorname{evc}_{u}(G)=\min\\{\operatorname{mvc}_{u}(G)+1,\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$
and
$\operatorname{evc}_{v}(G)=\min\\{\operatorname{mvc}_{v}(G)+1,\operatorname{evc}_{v}(G_{v})+\operatorname{evc}_{w}(G_{u})-1\\}$.

###### Proof

Since the statement of the lemma is symmetric with respect to $u$ and $v$, we
will only prove the expression for $\operatorname{evc}_{u}(G)$. We first show
that
$\operatorname{evc}_{u}(G)\leq\min\\{\operatorname{mvc}_{u}(G)+1,\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.
Since $\operatorname{evc}_{u}(G)\leq\operatorname{mvc}_{u}(G)+1$ by
Proposition 1, it is enough to show that
$\operatorname{evc}_{u}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.
By Proposition 5, we get $\max_{x\in
V(G_{u})}\operatorname{mvc}_{ux}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}(G_{v})\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$
and $\max_{x\in
V(G_{v})}\operatorname{mvc}_{ux}(G)\leq\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.
Hence, by Proposition 1, we get
$\operatorname{evc}_{u}(G)\leq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.

Next, we need to show that
$\operatorname{evc}_{u}(G)\geq\min\\{\operatorname{mvc}_{u}(G)+1,\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1\\}$.
By Proposition 1, it is enough to show that when
$\operatorname{evc}_{u}(G_{u})=\operatorname{mvc}_{u}(G)$, then
$\operatorname{evc}_{u}(G)\geq\operatorname{evc}_{u}(G_{u})+\operatorname{evc}_{w}(G_{v})-1$.
Suppose $\operatorname{evc}_{u}(G)=\operatorname{mvc}_{u}(G)$. Since
$\operatorname{mvc}_{u}(G)\leq\operatorname{evc}(G)\leq\operatorname{evc}_{u}(G)$,
we have
$\operatorname{mvc}_{u}(G)=\operatorname{evc}(G)=\operatorname{evc}_{u}(G)$.
By Observation 3 and Lemma 14, we have
$\operatorname{evc}(G)\in\\{k_{u}+k_{v},k_{u}+k_{v}+1\\}$. First, suppose
$\operatorname{evc}_{u}(G)=k_{u}+k_{v}$. We will show a contradiction in this
case. By Lemma 9 Part 2, we get $\operatorname{mvc}_{w}(G_{v})=k_{v}$ and
$\operatorname{mvc}_{uw}(G_{u})=k_{u}$. This implies
$\operatorname{mvc}_{u}(G)=k_{u}+k_{v}-1$, which is a contradiction.

Next, suppose $\operatorname{evc}_{u}(G)=k_{u}+k_{v}+1$. In this case, it is
enough to show that $\operatorname{evc}_{u}(G_{u})=k_{u}+1$ and
$\operatorname{evc}_{w}(G_{v})=k_{v}+1$. We have
$\operatorname{mvc}_{uw}(G_{u})\leq k_{u}+1$. If
$\operatorname{mvc}_{w}(G_{v})=k_{v}$, we get
$\operatorname{mvc}_{u}(G)=k_{u}+k_{v}$, a contradiction. Therefore,
$\operatorname{mvc}_{w}(G_{v})=k_{v}+1$. By Lemma 9 Part 2, we get
$\operatorname{evc}_{u}(G_{u})=k_{u}+1$. If
$\operatorname{mvc}_{u}(G_{u})=k_{u}$, we get
$\operatorname{mvc}_{u}(G)=k_{u}+k_{v}$, a contradiction. Therefore,
$\operatorname{mvc}_{u}(G_{u})=k_{u}+1$. Consider any vertex $x\in V(G_{v})$.
By Proposition 1, we have $\operatorname{mvc}_{xu}(G)\leq k_{u}+k_{v}+1$.
Since, $\operatorname{mvc}_{u}(G_{u})=k_{u}+1$, it can be verified that
$\operatorname{mvc}_{xw}(G_{v})\leq k_{v}+1$. Hence, by Proposition 1,
$\operatorname{evc}_{w}(G_{v})=k_{v}+1$, as required.

###### Lemma 21

If $\operatorname{evc}(G_{u})=k_{u}+1$ and
$\operatorname{evc}(G_{v})=k_{v}+1$, then:

  1. 1.

If $\operatorname{mvc}_{uv}(G)\leq k_{u}+k_{v}$ then
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)+1$.

  2. 2.

Otherwise,
$\operatorname{evc}_{uv}(G)=min\\{\operatorname{mvc}_{uv}(G)+1,max\\{P_{1},P_{2}\\}\\}$,
where
$P_{1}=\min\\{\operatorname{evc}_{uw}(G_{u})+\operatorname{mvc}_{vw}(G_{v})-1,\operatorname{evc}_{u}(G_{u})+\operatorname{mvc}_{v}(G_{v})\\}$
and
$P_{2}=\min\\{\operatorname{mvc}_{uw}(G_{u})+\operatorname{evc}_{vw}(G_{v})-1,\operatorname{mvc}_{u}(G_{u})+\operatorname{evc}_{v}(G_{v})\\}$.

###### Proof

  1. 1.

Suppose $\operatorname{mvc}_{uv}(G)\leq k_{u}+k_{v}$. By Proposition 1,
$\operatorname{evc}_{uv}(G)\in\\{\operatorname{mvc}_{uv}(G),\operatorname{mvc}_{uv}(G)+1\\}$.
Therefore it is enough to show that
$\operatorname{evc}_{uv}(G)\neq\operatorname{mvc}_{uv}(G)$. For contradiction,
suppose this was not true. By Lemma 9 Part 1, we get
$\operatorname{evc}(G)\geq k_{u}+k_{v}$. Therefore,
$\operatorname{evc}_{uv}(G)\geq k_{u}+k_{v}$. Hence, we may assume that
$\operatorname{mvc}_{uv}(G)=\operatorname{evc}_{uv}(G)=k_{u}+k_{v}$. By Lemma
9 Part 3, we get $\operatorname{mvc}_{uw}(G_{u})=k_{u}$ and
$\operatorname{mvc}_{vw}(G_{v})=k_{v}$. This gives
$\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}-1$, a contradiction. Hence,
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)+1$.

  2. 2.

Suppose $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}+1$. By Lemma 8, we know
$\operatorname{evc}_{uv}(G)\leq\min\\{\operatorname{mvc}_{uv}(G)+1,\max(P_{1},P_{2})\\}$.
Now, we will show that
$\operatorname{evc}_{uv}(G)\geq\min(\operatorname{mvc}_{uv}(G)+1,\max(P_{1},P_{2}))$.
Recall that we are in a case when $\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}+1$
and by Proposition 1
$\operatorname{evc}_{uv}(G)\in\\{\operatorname{mvc}_{uv}(G),\operatorname{mvc}_{uv}(G)+1\\}$.
If $\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)+1$, we are done.
Therefore we are left with the case where
$\operatorname{evc}_{uv}(G)=\operatorname{mvc}_{uv}(G)=k_{u}+k_{v}+1$. In this
case $\operatorname{mvc}_{uw}(G_{u})=k_{u}+1$ and
$\operatorname{mvc}_{vw}(G_{v})=k_{v}+1$. It is enough to show that
$\max(P_{1},P_{2})\leq k_{u}+k_{v}+1$. For contradiction, suppose
$P_{1}>k_{u}+k_{v}+1$. This implies $\operatorname{evc}_{uw}(G_{u})=k_{u}+2$.
By Lemma 9 Part 3, we get $\operatorname{mvc}_{v}(G_{v})=k_{v}$,
$\operatorname{evc}_{v}(G_{v})=k_{v}+1$ and
$\operatorname{evc}_{u}(G_{u})=k_{u}+1$. From this, we get $P_{1}\leq
k_{u}+k_{v}+1$, a contradiction.

Symmetrically, we get contradiction when $P_{2}>k_{u}+k_{v}+1$. Therefore,
$\max(P_{1},P_{2})\leq k_{u}+k_{v}+1$.∎

From Lemma 12-21, the following theorem is immediate.

###### Theorem 5.2

Let $G$ be a maximal outerplanar graph and $uv$ be an edge on the outer face
of $G$ such that $deg_{G}(u)>2$ and $deg_{G}(v)>2$. Let $w=\Delta(uv)$.

  1. 1.

Given $\mathscr{M}(G_{u},uw)$, $\mathscr{E}(G_{u},uw)$,
$\mathscr{M}(G_{v},vw)$ and $\mathscr{E}(G_{v},vw)$, it is possible to compute
$\operatorname{evc}(G)$ in constant time.

  2. 2.

Given $\operatorname{evc}(G)$, $\mathscr{M}(G,uv)$, $\mathscr{M}(G_{u},uw)$,
$\mathscr{E}(G_{u},uw)$, $\mathscr{M}(G_{v},vw)$ and $\mathscr{E}(G_{v},vw)$,
it is possible to compute the remaining evc parameters of $G$ with respect to
$uv$ in constant time.

##  6 A linear time algorithm to compute $\operatorname{evc}$ number

In this section, we formulate a divide and conquer algorithm that takes a pair
$(G,uv)$ as input where $G$ is a maximal outerplanar graph and $uv$ is an edge
on its outer face and recursively computes $\mathscr{M}(G,uv)$ and
$\mathscr{E}(G,uv)$. The case when $G$ is a triangle forms the base case of
the recursion and it is handled using Observation 1. Let $w=\Delta(uv)$. If
$deg_{G}(u)>2$ and $deg_{G}(v)>2$, then the recursion works on $(G_{u},uw)$
and $(G_{v},vw)$ using Theorem 3.2 and Theorem 5.2. Otherwise, suppose
$u^{\prime}$ is the degree-2 vertex among $u$ and $v$ and $v^{\prime}$ is the
other one. In this case, the recursion works on $(G_{v^{\prime}},v^{\prime}w)$
using Theorem 3.1 and Theorem 5.1.

A high level overview of our method is given in Algorithm 1. To obtain the
linear time guarantee, we need to ensure that the time spent in steps other
than the recursive calls is $O(1)$. Theorems 3.1-5.2 guarantee that lines
$8-11$ and lines $17-20$ work in constant time, forming the most crucial part
of our algorithm. However, we will have to avoid the explicit computation of
the subgraphs and passing them as explicit parameters in the recursive calls
using a refinement of Algorithm 1. For this refinement, we maintain a Vertex
Edge Face Adjacency List data structure using which the following are
possible:

  1. 1.

For any edge $e$, we can traverse through the internal faces on which the edge
lies in $O(1)$ time.

  2. 2.

For any internal face $f$, we can traverse through the edges on the boundary
of $f$ in $O(1)$ time.

The details of the data structure is given in Fig. 2 in the appendix. An
example for Vertex Edge Face Adjacency List of a maximal outerplanar graph on
four vertices is given in Fig. 3 in the appendix. Vertex Edge Face Adjacency
List of an outerplanar graph can be produced by modifying the algorithm
suggested by N. Chiba and T. Nishizeki [15] for listing all the triangles of a
planar graph in linear time. An algorithm for producing the Vertex Edge Face
Adjacency List is given in Algorithm 2 in the appendix.

By using the visit field of faces in the Vertex Edge Face Adjacency List data
structure, we avoid passing the subgraph as an explicit parameter in recursive
calls, maintaining the following invariants:

  1. 1.

The edge $e$ passed as parameter to the recursion is present in exactly one
unvisited face $f$.

  2. 2.

The $e$-segment of $G$ that contains the unvisited face $f$ is precisely the
subgraph on which the recursive call in Algorithm 1 would have been made.

Further, line numbers $2$, $3$, $5$ and $6$ of Algorithm 1 can also be
implemented in linear time using the new data structure.

Algorithm 1 To compute $\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$ of a
maximal outerplanar graph $G$ with $uv$ an edge on its outer face.

Inputs: A maximal outerplanar graph $G$ with at least three vertices, an edge
$uv$ on the outer face of $G$.
Outputs: $\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$.

1:procedure EVC_Parameters($G$, $uv$)

2: $w\leftarrow$ $\Delta(uv)$.

3: if $G$ is a triangle then

4:
$\operatorname{mvc}(G)$=$\operatorname{evc}(G)$=$\operatorname{mvc}_{u}(G)$=$\operatorname{mvc}_{v}(G)$=$\operatorname{mvc}_{uv}(G)$=$2$,
$\operatorname{evc}_{u}(G)$=$\operatorname{evc}_{v}(G)$=$2$,
$\operatorname{evc}_{uv}(G)$=$3$.

5: else if One end point of $uv$ is degree-2 then

6: $u^{\prime}$=degree-2 end point of $uv$, $v^{\prime}$=higher degree end
point of $uv$.

7: Recursively call EVC_Parameters$(G_{v^{\prime}},v^{\prime}w)$.

8: Compute $\operatorname{mvc}(G)$ using Theorem 3.1 (Part 1).

9: Compute $\operatorname{mvc}_{u}(G)$, $\operatorname{mvc}_{v}(G)$ and
$\operatorname{mvc}_{uv}(G)$ using Theorem 3.1 (Part 2).

10: Compute $\operatorname{evc}(G)$ using Theorem 5.1 (Part 1).

11: Compute $\operatorname{evc}_{uv}(G)$ in constant using Theorem 5.1 (Part
2).

12: else

13: $G_{u}\leftarrow$ $uv$-segment of $G$ containing the vertex $u$

14: $G_{v}\leftarrow$ $uv$-segment of $G$ containing the vertex $v$

15: Recursively call EVC_Parameters$(G_{u},uw)$.

16: Recursively call EVC_Parameters$(G_{v},vw)$.

17: Compute $\operatorname{mvc}(G)$ using Theorem 3.2 (Part 1).

18: Compute $\operatorname{mvc}_{u}(G)$, $\operatorname{mvc}_{v}(G)$,
$\operatorname{mvc}_{uv}(G)$ using Theorem 3.2 (Part 2).

19: Compute $\operatorname{evc}(G)$ using Theorem 5.2 (Part 1).

20: Compute $\operatorname{evc}_{u}(G)$, $\operatorname{evc}_{v}(G)$,
$\operatorname{evc}_{uv}(G)$ using Theorem 5.2 (Part 2).

21: end if

22: return ($\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$)

23:end procedure

Algorithm 2 (in the appendix) gives a linear time refinement of Algorithm 1.
The details of the correspondence between the two algorithms are given in the
appendix.

##  7 Conclusion

This paper presents a linear time algorithm for computing the eternal vertex
cover number of maximal outerplanar graphs, lowering the best known upper
bound to the complexity of the problem from quadratic [6] time to linear. The
techniques presented in the paper make crucial use of the planarity of the
underlying graph to yield a divide and conquer algorithm for computing the
$\operatorname{evc}$ number of a maximal outerplanar graph. Attempts to
generalize the techniques to maximal planar graphs may not be successful due
to the known NP hardness result on the evc computation of biconnected
internally triangulated planar graphs [2]. However, the complexity status of
the problem of computing the $\operatorname{evc}$ number of outerplanar graphs
is open and may be attempted using the techniques developed in this work.

## References

  * [1] Fomin, F.V., Gaspers, S., Golovach, P.A., Kratsch, D., Saurabh, S.:  Parameterized algorithm for eternal vertex cover.  Information Processing Letters 110(16) (2010) 702 – 706
  * [2] Babu, J., Chandran, L.S., Francis, M., Prabhakaran, V., Rajendraprasad, D., Warrier, N.J.:  On graphs whose eternal vertex cover number and vertex cover number coincide.  Discrete Applied Mathematics (2021)
  * [3] Klostermeyer, W., Mynhardt, C.:  Edge protection in graphs.  Australasian Journal of Combinatorics 45 (2009) 235 – 250
  * [4] Araki, H., Fujito, T., Inoue, S.:  On the eternal vertex cover numbers of generalized trees.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (06 2015) 1153–1160
  * [5] Babu, J., Prabhakaran, V., Sharma, A.:  A substructure based lower bound for eternal vertex cover number.  Theoretical Computer Science (2021)
  * [6] Babu, J., Prabhakaran, V.:  A new lower bound for the eternal vertex cover number of graphs.  Journal of Combinatorial Optimization (2021) 1–17
  * [7] Rinemberg, M., Soulignac, F.J.:  The eternal dominating set problem for interval graphs.  Information Processing Letters 146 (2019) 27–29
  * [8] Goldwasser, J.L., Klostermeyer, W.F.:  Tight bounds for eternal dominating sets in graphs.  Discrete Mathematics 308(12) (2008) 2589–2593
  * [9] Klostermeyer, W.F., Mynhardt, C.:  Vertex covers and eternal dominating sets.  Discrete Applied Mathematics 160(7) (2012) 1183–1190
  * [10] Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T.:  Eternal security in graphs.  J. Combin. Math. Combin. Comput 52 (2005) 169–180
  * [11] Klostermeyer, W.F., Mynhardt, C.M.:  Graphs with equal eternal vertex cover and eternal domination numbers.  Discrete Mathematics 311 (2011) 1371 – 1379
  * [12] Anderson, M., Carrington, J.R., Brigham, R.C., D.Dutton, R., Vitray, R.P.:  Graphs simultaneously achieving three vertex cover numbers.  Journal of Combinatorial Mathematics and Combinatorial Computing 91 (2014) 275 – 290
  * [13] Hartnell, B., Mynhardt, C.:  Independent protection in graphs.  Discrete Mathematics 335 (2014) 100 – 109
  * [14] Caro, Y., Klostermeyer, W.:  Eternal independent sets in graphs.  Volume 3. (2016)
  * [15] Chiba, N., Nishizeki, T.:  Arboricity and subgraph listing algorithms.  SIAM Journal on computing 14(1) (1985) 210–223

##  8 Appendix - Refinement of Algorithm 1 to Work in Linear Time

###  8.1 Vertex Edge Face Adjacency List

To make Algorithm 1 work in linear time, we should avoid the explicit passing
of the subgraphs $G_{u}$ and $G_{v}$ as parameters for the recursive calls.
Instead, we do the following.

Using an algorithm suggested by N. Chiba and T. Nishizeki [15], in linear time
all the triangles of a planar graph can be listed/ printed. Let $G$ be a
maximal outerplanar graph with a fixed outerplanar embedding. When $G$ is
given as input to the algorithm of Chiba and Nishizeki, it will precisely list
all the internal faces of the graph. By modifying the algorithm proposed in
[15], we produce a global data structure named Vertex Edge Face Adjacency
List. The details of the data structure is given in Fig. 2. The algorithm for
producing this data structure is given in Algorithm 2 and will be discussed
later.

Figure 2: Details of the Vertex Edge Face Adjacency List data structure.

In a Vertex Edge Face Adjacency List data structure, for any edge
$v_{i}v_{j}$, there are links between the edge node $v_{i}v_{j}$ and the edge
node $v_{j}v_{i}$. For each face node representing a face $f$ in $G$, there
are links to the edge nodes corresponding to the bounding edges of $f$ and
vice versa. Remember that each edge of $G$ has 2 edge nodes corresponding to
it. Hence, for each face node $f$, there are 6 pointers to edge nodes. For
each face node, there is a visit field which is initialized to unvisited. Each
vertex node has a mark field, which is initialized to unmarked, the cur-edge
field which is initialized to null and a pointer to the beginning of the
adjacency list of that vertex.

The Vertex Edge Face Adjacency List of a maximal outerplanar graph on four
vertices is given in Fig. 3.

###  8.2 Refined algorithm and its correspondence with Algorithm 1

We will first assume that Vertex Edge Face Adjacency List of the graph has
been already produced and give the remaining details of the linear time
implementation. Algorithm 2 gives a linear time version of Algorithm 1. To
compute the $\operatorname{evc}$ number of a maximal outerplanar graph, we
pass an edge $uv$ on the outer face of the graph as input to the algorithm.
Initially, the visit field of all faces are set to unvisited. Note that, the
edge $uv$ is present in exactly one unvisited face $uvw$ initially. On
entering the algorithm, the face $uvw$ is marked as visited. Once this marking
is done, the edges $uw$ and $vw$ can be in at most one unvisited face each.
Note that if $uw$ is not in any unvisited face, then $deg_{G}(u)=2$. Otherwise
$deg_{G}(u)>2$. Similarly we can check if $deg_{G}(v)=2$ or not from the
number of unvisited faces containing the edge $vw$.

Algorithm 2 For computing $\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$ of a
maximal outerplanar graph $G$ with $uv$ an edge on its outer face in linear
time

Inputs: An edge $uv$ on the outer face of the maximal outerplanar graph $G$.
Output: $\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$.
Assumption: The Vertex Edge Face Adjacency List is maintained globally.

1:procedure EVC_Parameters

2: Identify the unvisited face $uvw$ in which the edge $uv$ lie.

3:$\triangleright$ Possible in constant time by Vertex Edge Face Adjacency
List

4: Set the visit field of the face $uvw$ to visited.

5: if neither edge $uw$ nor edge $vw$ is in any unvisited faces then

6:$\triangleright$ Possible to check in constant time using Vertex Edge Face
Adjacency List

7:
$\operatorname{mvc}(G)$=$\operatorname{evc}(G)$=$\operatorname{mvc}_{u}(G)$=$\operatorname{mvc}_{v}(G)$=$\operatorname{mvc}_{uv}(G)$=$2$,
$\operatorname{evc}_{u}(G)$=$\operatorname{evc}_{v}(G)$=$2$,
$\operatorname{evc}_{uv}(G)$=$3$.

8: else if exactly one among $uw$ and $vw$ lie in an unvisited face then

9:$\triangleright$ Possible to check in constant time using the Vertex Edge
Face Adjacency List

10: $e$ be the edge among $uw$ and $vw$ that lie in an unvisited face.

11: $t\longleftarrow$ EVC_Parameters$(e)$.

12: Compute $\operatorname{mvc}(G)$ in constant time using Theorem 3.1 (part
1).

13: Compute $\operatorname{mvc}_{u}(G)$, $\operatorname{mvc}_{v}(G)$ and
$\operatorname{mvc}_{uv}(G)$ in constant time using Theorem 3.1 (part 2).

14: Compute $\operatorname{evc}(G)$ in constant time using Theorem 5.1 (part
1).

15: Compute $\operatorname{evc}_{uv}(G)$ in constant using Theorem 5.1 (part
2).

16: else

17: $t_{1}\longleftarrow$ EVC_Parameters$(uw)$.

18: $t_{2}\longleftarrow$ EVC_Parameters$(vw)$.

19: Compute $\operatorname{mvc}(G)$ in constant time using Theorem 3.2 (part
1).

20: Compute $\operatorname{mvc}_{u}(G)$, $\operatorname{mvc}_{v}(G)$,
$\operatorname{mvc}_{uv}(G)$ in constant time using Theorem 3.2 (part 2).

21: Compute $\operatorname{evc}(G)$ in constant time using Theorem 5.2 (part
1).

22: Compute $\operatorname{evc}_{u}(G)$, $\operatorname{evc}_{v}(G)$,
$\operatorname{evc}_{uv}(G)$ in constant time using Theorem 5.2 (part 2).

23: end if

24: return ($\mathscr{M}(G,uv)$ and $\mathscr{E}(G,uv)$)

25:end procedure

In subsequent recursive calls, the following invariants will be maintained:
(1) the edge $e$ passed as parameter to the recursion is present in exactly
one unvisited face $f$.
(2) The $e$-segment of $G$ that contains the unvisited face $f$ is precisely
the subgraph on which the recursive call in Algorithm 1 would have been made.
By maintaining the visit field of faces, we avoid passing the subgraph as an
explicit parameter in recursive calls in Algorithm 2.

From these observations, we show that Algorithm 2 is a linear time
implementation of Algorithm 1. The inputs of the function EVC_Parameters of
Algorithm 1 are a maximal outerplanar graph $G$ and an edge $uv$ on the outer
face. The algorithm is divided into following three cases:

  1. 1.

The input graph is a triangle (degrees of both the end vertices of the edge
$uv$ are $2$). Refer to line number 3 of Algorithm 1.

  2. 2.

The input graph is not a triangle and exactly one end vertex of the input edge
$uv$ is of degree $2$. Refer to line number 5 of Algorithm 1.

  3. 3.

The input graph is not a triangle and both the end vertices of the input edge
$uv$ has degree greater than $2$. Refer to line number 12 of Algorithm 1..

The input to the function EVC_Parameters of Algorithm 2 is an edge $uv$ on the
outer face of the input graph. For the input edge $uv$, let $uvw$ be the
unvisited face in which $uv$ lies. The three cases of Algorithm 2
corresponding to the three cases of Algorithm 1 are as follows:

  1. 1.

Both edges $uw$ and $vw$ lie in no unvisited face and thereby $uvw$ is a
triangle. Refer to line number 5 of Algorithm 2.

  2. 2.

Exactly one among the edges $uw$ and $vw$ lie in an unvisited face. Refer to
line number 8 of Algorithm 2.

  3. 3.

Both $uw$ and $vw$ lie in one unvisited face each. Refer to line number 16 of
Algorithm 2.

In line number 2 of Algorithm 1, we find the unique common neighbor $w$ of $u$
and $v$ in the input graph. Instead of this step, line number 2 of Algorithm
2, identifies $w$ as the third vertex in the unique unvisited face containing
the edge $uv$. After this the face $uvw$ is marked as visited in line number 4
of Algorithm 2 and subsequently the edges $uw$ and $vw$ are in at most one
unvisited face each.

Now, we show that line number 3 of Algorithm 1 is equivalent to line number 5
of Algorithm 2. In line number 3 of Algorithm 1, we check whether the input
graph is a triangle, which is the base case. Equivalently, by the invariants
stated above, in Algorithm 2, it is enough to check if the $uv$-segment of $G$
containing the face $uvw$ is a triangle. In line 5 of Algorithm 2, we do the
following in constant time using vertex edge face adjacency list: We check if
$uw$ or $vw$ lie in any unvisited face. If neither $uw$ nor $vw$ lie in an
unvisited face, then we can infer that $uv$-segment of $G$ containing the face
$uvw$ is a triangle.

In line 5 of Algorithm 1, we check whether exactly one end vertex of the edge
$uv$ is of degree $2$. In line number 8 of Algorithm 2, if $uw$ (respectively,
$vw$) is in any univisited face, then we can infer that the degree of the
vertex $u$ (respectively, $v$) is greater than $2$ in the $uv$-segment of $G$
that contains the face $uvw$. Otherwise, the degree of $u$ (respectively, $v$)
in the $uv$-segment of $G$ that contains the face $uvw$ is equal to $2$.

In line number 7 of Algorithm 1, we recursively call the function
EVC_Parameters with two input parameters: (1) the graph obtained by deleting
the degree-2 endpoint $u^{\prime}$ of the edge $uv$ from the input graph and
(2) the edge $v^{\prime}w$ bounding the face $uvw$, where degree of
$v^{\prime}$ is greater than $2$ in the input graph. Since in Algorithm 2,
$uvw$ is already marked as visited in line number 4, it is enough to invoke
the recursive call with the edge $e$ as parameter, where $e$ is the bounding
edge of the face $uvw$ with one unvisited face adjacent to it. This is
achieved in line number 12 of Algorithm 2, in which we recursively call the
function EVC_Parameters with the edge $e$ as input, where $e$ is that edge
among the edges $uw$ and $vw$ which lies in an unvisited face. Note that the
invariants of the Algorithm 2 are maintained.

The equivalence between line number 12 of Algorithm 1 and line number 16 of
Algorithm 2 follows from our arguments so far. In line number 15
(respectively, 16) of Algorithm 1, a recursive call to the algorithm is made
with input parameters: (1) $G_{u}$ (respectively, $G_{v}$), the $uw$-segment
(respectively, $vw$-segment) of $G$ that does not contain the edge $vw$
(respectively, $uw$) and (2) the edge $uw$ (respectively, $vw$). Note that the
edges bounding the face $uvw$, other than $uv$, are used as parameters in
these two calls. Equivalently, in line number 17 and 18 of Algorithm 2,
recursive calls are made respectively with the edges $uw$ and $vw$ as input
parameters. Since the face $uvw$ is marked as visited already, the invariants
of the algorithm are maintained here as well.

Thus, we can see that Algorithm 2 is linear time implementation of Algorithm
1.

###  8.3 Building the Vertex Edge Face Adjacency List

We can use the algorithm given below to populate the Vertex Edge Face
Adjacency List of a maximal outerplanar graph.

1:procedure Populate Vertex Edge Face Adjacency List

1: Inputs: Bare vertex edge face adjacency list $L$ of a maximal outerplanar
graph $G$, in which face nodes are absent and links to face nodes from edge
nodes are initialized to NULL.

2: Outputs: Modified vertex edge face adjacency list $L$ with all relevant
details filled in.

3: Create a copy $L^{\prime}$ of $L$.

4: For any edge node $v_{i}v_{j}$ in $L^{\prime}$, keep a pointer to and from
the corresponding edge node in $L$.

5: Sort the vertices of $G$ in decreasing order of vertex degree. (using
bucket sort in linear time)

6: for i=1 to n do

7: Let $v_{i}=$ next highest degree vertex.

8: $p=s=Varray[v_{i}].head$ in $L^{\prime}$.

9: while ($s!=NULL$) do $\triangleright$ Parse the edge list of $v_{i}$.

10: $x=s.vertex_{2}$

11: $Varray[x].mark=Marked$

12: $Varray[x].cur$-$edge=s$

13: $s=s.next$

14: end while

15: while ($p!=NULL$) do

16: $v_{j}=p.vertex_{2}$

17: $q=Varray[v_{j}].head$ $\triangleright$ Beginning of adjacency list of
$v_{j}$

18: while ($q!=NULL$) do

19: $v_{k}=q.vertex_{2}$

20: if $(Varray[v_{k}].status=Marked)$ then

21: $r=Varray[v_{k}].cur$-$edge$

22: $p^{\prime}=$Copy$(p)$ in $L$, $q^{\prime}=$Copy$(q)$ in $L$ and
$r^{\prime}=$Copy$(r)$ in $L$.

23: In $L$, create face node $f$ with links to edge nodes $p^{\prime}$,
$q^{\prime}$ and

24: $r^{\prime}$ and reverse.

25: Simultaneously insert links from $f$ to pair nodes of $p^{\prime}$,
$q^{\prime}$

26: and $r^{\prime}$ and reverse.

27: end if

28: $q=q.next$;

29: end while

30: $v_{j}.mark=Unmarked$

31: $p=p.next$;

32: end while

33: In $L^{\prime}$, $Varray[v_{i}].mark=Deleted$ and delete the edge list of
$v_{i}$.

34: Whenever edge $v_{i},v_{k}$ is deleted, delete $v_{k},v_{i}$ also.

35: end for

36:end procedure

Algorithm 3 For populating the Vertex Edge Face Adjacency List

We assume a bare Vertex Edge Face Adjacency List $L$ as the input graph
representation in which the face nodes and the links to and from face nodes
are absent. The Algorithm 2, begins by creating a copy $L^{\prime}$ of the
bare Vertex Edge Face Adjacency List $L$ and links from an edge node in
$L^{\prime}$ to its copy in $L$. (For simplicity, in the data structure given
in Fig. 2, we have avoided a field for this link.) During the running of
Algorithm 2, we traverse through $L^{\prime}$ and each time a new face node is
created corresponding to a face $f_{i}$ in $G$ , we assign links from the
newly created face node to the edge nodes (bounding edges of $f_{i}$) in $L$
and also the reverse links. This step can be done in constant time by
utilizing the links from each edge nodes of $L^{\prime}$ to its copy in $L$.
During the running of Algorithm 2, some edge nodes of $L^{\prime}$ gets
deleted while their copies in $L$ are retained. Note that, this way of
deletion of edge nodes of $L^{\prime}$ is necessary to obtain linear time
complexity, as it was done in [15]. Hence, the linear time complexity of the
construction follows from the analysis in [15].

Figure 3: The Vertex Edge Face Adjacency List of a maximal outerplanar graph
$G$ on four vertices and two faces. $F_{1}$ and $F_{2}$ denote the face nodes.