# Weakly toll convexity in graph products

Polona Repolusk a

###### Abstract

The exploration of weakly toll convexity is the focus of this investigation. A
weakly toll walk is any walk $W:u,w_{1},\ldots,w_{k-1},v$ between $u$ and $v$
such that $u$ is adjacent only to the vertex $w_{1}$, which can appear more
than once in the walk, and $v$ is adjacent only to the vertex $w_{k-1}$, which
can appear more than once in the walk. Through an examination of general
graphs and an analysis of weakly toll intervals in both lexicographic and
(generalized) corona product graphs, precise values of the weakly toll number
for these product graphs are obtained. Notably, in both instances, the weakly
toll number is constrained to either 2 or 3. Additionally, the determination
of the weakly toll number for the Cartesian and the strong product graphs is
established through previously established findings in toll convexity theory.
Lastly for all graph products examined within our scope, the weakly toll hull
number is consistently determined to be 2.

Keywords: weakly toll convexity, weakly toll number, graph product

2010 Mathematical Subject Classification: 05C12, 52A01 05C76

a Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

<EMAIL_ADDRESS>

##  1 Introduction

The theory of convexity has been extensively explored, with numerous papers
delving into various aspects of the subject. Various forms of interval
convexities have been thoroughly investigated, with one particularly natural
aspect stemming from abstract convexity theory known as the convex geometry
property or Minkowski–Krein–Milman property. In this context, a vertex $s$ of
a convex set $S$ is an extreme vertex of $S$, if $S-\\{s\\}$ is also convex. A
graph $G$ is deemed a convex geometry concerning a given convexity if every
convex set of $G$ is the convex hull of its extreme vertices. Specifically,
under monophonic convexity, exactly chordal graphs are convex geometries [16],
while under geodesic convexity [15], Ptolemaic graphs (i.e., distance-
hereditary chordal graphs) hold this property, as detailed in [11].

A graph convexity, for which exactly the interval graphs are convex geometry,
was introduced and explored in [2]. The authors focused on interval graphs and
built upon concepts from [1], which characterized this graph family in terms
of tolled walks. The concept of a tolled walk, a generalization of monophonic
paths, led to the definition of toll convexity [2], which was further
investigated for instance in [7, 10].

Expanding on this research, [8] established a characterization of proper
interval graphs, which are convex geometry with respect to weakly toll
convexity. Thus, investigating weakly toll convexity holds significance. In
[8], the authors also investigated weakly toll number and weakly toll hull
number, determining these values for trees and providing bounds for interval
graphs. Additionally, [9] explored complexity results, demonstrating that the
weakly toll number of any graph can be computed in polynomial time.

Graph products have garnered significant interest over time. Concerning
various types of convexities, numerous papers have been published on the
subject, such as [3, 4, 5, 6, 12, 13]. In [8], the authors expressed interest
in exploring weakly toll convexity within the framework of graph products. In
our study, we describe weakly toll intervals in the lexicographic and the
corona product graphs, yielding weakly toll number values. In both cases, the
resulting values are either 2 or 3, depending on the second factor of the
product. Despite the polynomial algorithm presented in [9], our findings offer
precise numerical results. The outcomes for weakly toll number in the
Cartesian and the strong product graphs directly derive from results presented
for toll convexity in [12] and [13]. Additionally, we find that for all graph
products examined within our scope, the weakly toll hull number is
consistently determined to be 2.

##  2 Preliminaries

All graphs, considered in this paper, are finite, simple, non trivial (i.e.
graphs with at least two vertices), connected and without multiple edges or
loops.

Let $G=(V(G),E(G))$ be a graph and $u\in V(G)$. A set $N_{G}(u)=\\{v\in
V(G)~{}|~{}uv\in E(G)\\}$ is an open neighbourhood of $u$ and
$N_{G}\left[u\right]=N_{G}(u)\cup\\{u\\}$ is a closed neighbourhood of $u$. If
the graph is clear from the context, we will omit the subscriptions.

A tolled walk [2] is any walk $T:u_{0},u_{1},\ldots.,u_{k-1},u_{k}$ such that
$u_{0}$ is adjacent only to the second vertex of the walk, and $u_{k}$ is
adjacent only to the second-to-last vertex of the walk. This implies that each
of $u_{1}$ and $u_{k-1}$ occurs exactly once in the walk. Let
$T_{G}(u,v)=\\{x\in V(G)~{}|~{}x\text{ lies in a tolled walk between }u\text{
and }v\\}$ be the toll interval between $u$ and $v$ in $G$. A subset $S$ of
$V(G)$ is toll convex if $T_{G}(u,v)\subseteq S$ for all $u,v\in S.$ The toll
closure of a subset is the union of toll intervals between all pairs of
vertices from $S$, i.e., $T_{G}(S)=\cup_{u,v\in S}T_{G}(u,v).$ If
$T_{G}(S)=V(G)$, $S$ is called a toll set of $G$. The order of a minimum toll
set in $G$ is called the toll number of $G$ $(tn(G))$.

Let us recall the definition of the weakly toll walks from [8]: Let $u,v\in
V(G)$. A weakly toll walk $W$ between $u$ and $v$ in $G$ is a sequence of
vertices of the form

$W:u=w_{0},w_{1},\ldots,w_{k-1},w_{k}=v,$

where $k\geq 0$, which enjoys the following three conditions for $k>0$:

  * •

$w_{i}w_{i+1}\in E(G)$ for all $i\in\\{0,\ldots,k-1\\}$,

  * •

$uw_{i}\in E(G)$ implies $w_{i}=w_{1}$, where $i\in\\{1,\ldots,k\\}$,

  * •

$w_{i}v\in E(G)$ implies $w_{i}=w_{k-1}$, where $i\in\\{0,\ldots,k-1\\}$.

In other words, a weakly toll walk is any walk $W:u,w_{1},\ldots,w_{k-1},v$
between $u$ and $v$ such that $u$ is adjacent only to the vertex $w_{1}$,
which can appear more than once in the walk, and $v$ is adjacent only to the
vertex $w_{k-1}$, which can appear more than once in the walk. If $uv\in
E(G)$, then $W:u,v$ is a weakly toll walk, and if $k=0$ then $W:u$ is a wealky
toll walk consisting of a single vertex.

We define $WT_{G}(u,v)=\\{x\in V(G)~{}|~{}x\text{ lies in a weakly toll walk
between }u\text{ and }v\\}$ to be the weakly toll interval between $u$ and $v$
in $G$. Finally, a subset $S$ of $V(G)$ is weakly toll convex if
$WT_{G}(u,v)\subseteq S$ for all $u,v\in S$. Note that any weakly toll convex
set is also a toll convex set. Also, any toll convex set is a monophonically
convex set, and a monophonically convex set is a geodesically convex set. On
the other hand, consider the graph $K_{1,3}$ with vertices $a,b,c,d$, where
$b$ is the vertex with degree three, and let $S=\\{a,b,c\\}$. It is clear that
$S$ is toll convex but not weakly toll convex, since $W:a,b,d,b,c$ is a weakly
toll walk between $a$ and $c$ that contains $d\notin S$ [8].

The definition of weakly toll interval for two vertices $u$ and $v$ can be
generalized to an arbitrary subset $S$ of $V(G)$ as follows:

$WT_{G}(S)=\cup_{u,v\in S}WT_{G}(u,v).$

If $WT_{G}(S)=V(G)$, $S$ is called a weakly toll set of $G$. The order of a
minimum weakly toll set in $G$ is called the weakly toll number of $G$, and is
denoted by $wtn(G)$. In [9], this concept is defined as weakly toll interval
number. For any non trivial connected graph $G$, it is clear that $2\leq
wtn(G)\leq n.$

The weakly toll convex hull of a set $S\subseteq V(G)$ is defined as the
intersection of all weakly toll convex sets that contain $S$, and we will
denote this set by $\left[S\right]]_{WT}$. A set $S$ is a weakly toll hull set
of $G$ if $\left[S\right]]_{WT}=V(G)$. The weakly toll hull number of $G$,
denoted by $wth(G)$, is the minimum among all the cardinalities of weakly toll
hull sets. Given a set $S\subseteq V(G)$, define $WT^{k}(S)$ as follows:
$WT^{0}(S)=S$ and $WT^{k}(S)=WT(WT^{k-1}(S)),$ for $k\geq 1$. Note that
$\left[S\right]]_{WT}=\cup_{k\in{\mathbb{N}}}WT^{k}(S)$. From the definitions
we immediately infer that every weakly toll set is a weakly toll hull set, and
hence $wth(G)\leq wtn(G)$.

In this paper we will only consider non complete graphs. Note that
$wtn(K_{n})=n$. It is clear from the definitions that $wtn(G)\leq tn(G)$.
Also, $wtn(T)=2$ for any tree $T$ as weakly toll interval between any two
leaves is a whole vertex set. Similarly, assume that a graph $G$ has two
vertices of degree 1. Then also $wtn(G)=2$. Note that there are graphs with
$wtn(G)>2$. For instance, take two copies of a complete graph $K_{n}$. Now,
take one vertex of one copy of $K_{n}$ and join it with one vertex of another
copy of $K_{n}$ by a path of length 2. Then $wtn(G)=2n-2.$

We follow the definitions of graph products by the book [14]. Recall that for
all of the standard graph products, the vertex set of the product of graphs
$G$ and $H$ is equal to $V(G)\times V(H)$. In the lexicographic product
$G\left[H\right]$, vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent
if either $g_{1}g_{2}\in E(G)$ or ($g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$). In
the Cartesian product $G\Box H$ of graphs $G$ and $H$, two vertices
$(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent when ($g_{1}g_{2}\in E(G)$
and $h_{1}=h_{2}$) or ($g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$). In the strong
product $G\boxtimes H$ of graphs $G$ and $H$, two vertices $(g_{1},h_{1})$ and
$(g_{2},h_{2})$ are adjacent if either ($g_{1}g_{2}\in E(G)$ and
$h_{1}=h_{2}$) or ($g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$) or ($g_{1}g_{2}\in
E(G)$ and $h_{1}h_{2}\in E(H)$).

Let $G$ and $H$ be graphs and $*$ be one of the two graph products under
consideration. For a vertex $h\in V(H)$, we call the set $G^{h}=\\{(g,h)\in
V(G*H):g\in V(G)\\}$ a $G$-_layer_ of $G*H$. By abuse of notation we also
consider $G^{h}$ as the corresponding induced subgraph. Clearly $G^{h}$ is
isomorphic to $G$. For $g\in V(G)$, the $H$-_layer_ ${}^{g}\\!H$ is defined as
${}^{g}\\!H=\\{(g,h)\in V(G*H)\,:\,h\in V(H)\\}$. We also consider
${}^{g}\\!H$ as an induced subgraph and note that it is isomorphic to $H$. A
map $p_{G}:V(G*H)\rightarrow V(G)$, $p_{G}(g,h)=g$ is the _projection_ onto
$G$ and $p_{H}:V(G*H)\rightarrow V(H)$, $p_{H}(g,h)=h$ the _projection_ onto
$H$.

The corona product of two graphs $G$ and $H$, $G\circ H$, is defined as the
graph obtained by taking one copy of $G$ and $|V(G)|$ copies of $H$ and
joining the $i$-th vertex of $G$ to every vertex in the $i$-th copy of $H$.
For more details on graph products see [14].

In [12], authors derived that $tn(G\Box H)=2$ for any connnected non trivial
graphs $G$ and $H$. This leads to:

###### Corollary 2.1

Let $G$ and $H$ be two connected non trivial graphs. Then $wtn(G\Box H)=2.$

They also found a formula for computing $tn(G\left[H\right])$ in terms of the
so-called toll-dominating triples and some general bounds for this number. In
[13], the toll number of the strong product was determined as $tn(G\boxtimes
H)\leq 3$ with the characterization for both cases. Therefore:

###### Corollary 2.2

Let $G$ and $H$ be two connected non complete graphs. Then $wtn(G\boxtimes
H)\leq 3.$

In the subsequent sections, we will initially describe the weakly toll
intervals between non adjacent vetrices in the lexicographic product graphs,
outlined in Section 3. Subsequently, we will ascertain the weakly toll number
for this scenario. Section 4 will be dedicated to describing weakly toll
intervals between non adjacent vertices of the corona product of graphs. Once
again, we will demonstrate the precise values of $wtn(G\circ H)$. Concluding
this paper, we will offer remarks on the generalized corona product of graphs.

However, before delving further, we present two highly pertinent results that
will greatly assist in our subsequent analysis:

###### Lemma 2.3

Let $G$ be a connected non complete graph and $u,v$ two non adjacent vertices
of $G$. Let $W=WT_{G}(u,v)$ be a weakly toll interval between vertices $u$ and
$v$ and $x\in V(G)\setminus(N\left[u\right]\cup N\left[v\right])$ such that
$xy\in E(G)$ for some $y\in W\setminus\\{u,v\\}$. Then $x\in W$.

Proof.  Assume $xy\in E(G)$ for some $y\in W\setminus\\{u,v\\}.$ Let $W_{1}$
be a weakly toll walk between $u$ and $v$ which contains $y$, say
$W_{1}:u,w_{0},w_{1},\ldots,w_{i-1},y,w_{i+1},\ldots,w_{n},v$. Then
$W_{1}^{\prime}:u,w_{0},w_{1},\ldots,w_{i-1},y,x,y,w_{i+1},\ldots,w_{n},v$ is
a weakly toll walk containing $x$. Note that this also holds if $y=w_{0}$ or
$y=w_{n}$ as $xu\notin V(G)$ and $xv\notin V(G)$. $\square$

Combining this result with some propositions, that were used in the proof of
the main theorem in [9], we can derive the following:

###### Lemma 2.4

Let $G$ be a connected non complete graph and $u,v$ two non adjacent vertices
of $G$. Let $W=WT_{G}(u,v)$ be a weakly toll interval between vertices $u$ and
$v$. Assume that $W$ is such that $|WT_{G}(u,v)|\geq|WT_{G}(w,z)|$ for any
$w,z\in V(G).$ Let $X_{u}=N\left[u\right]\setminus W$,
$X_{v}=N\left[v\right]\setminus W$ and $X=V(G)\setminus W$. Then $X_{u}\cap
X_{v}=\emptyset$ and $X=X_{u}\cup X_{v}$.

Proof.  First, assume that $X=\emptyset$. Then $W=V(G)$, $X_{u}=\emptyset$,
$X_{v}=\emptyset$ and $\\{u,v\\}$ is a weakly toll set. Now, let
$X=V(G)\setminus W$ and $x\in X$. If $xy\in E(G)$ for some $y\in
W\setminus\\{u,v\\}$. Then, by Lemma 2.3, $x\in W$, a contradiction. To
complete the proof, let $x\in X\setminus(X_{u}\cup X_{v})$, such that for
every $y\in W$, $xy\notin E(G)$. Every shortest path from $u$ to $x$ (resp.
$v$ to $x$) contains:

  1. 1.

exactly one vetrex from $X_{u}$ (resp.$X_{v}$). If $uw\in E(G)$, where $w\in
N(u)\cap W$, Lemma 2.3 would imply that $x\in W$.

  2. 2.

no vertex of $N\left[v\right]$ (resp.$N\left[u\right]$). If it contains $v$,
then this path only between $u$ and $v$ is a weakly toll walk containing a
vertex of $X_{u}$, a contradiction. If it contains a neighbor of $v$, say $w$,
then if $w\in W$, by Lemma 2.3, $x\in W$, a contradiction. Otherwise, if $w\in
X_{v}$, observe that $v\in WT_{G}(x,u)$: Let
$P:u,w_{1},\ldots,w_{i},w,w_{i+1},\ldots,w_{k},x$ be a shortest path between
$u$ and $x$ going through $w$. As $uv\notin E(G)$ and $xv\notin E(G)$,
$P^{\prime}:u,w_{1},\ldots,w_{i},w,v,w,w_{i+1},\ldots,w_{k},x$ is a weakly
toll walk between $u$ and $x$, containing $v$. Therefore, $WT_{G}(x,u)\supset
WT_{G}(u,v)$, a contradiction.

To summarize, there are paths $P$ between $u$ and $x$ containing no vertex of
$N\left[v\right]$ and $Q$ between $x$ and $v$ containing no vertex of
$N\left[u\right]$. A concatenation of paths $P$ and $Q$ is a weakly toll walk
from $u$ to $v$ containing $x$, a contradiction. Therefore, $X=X_{u}\cup
X_{v}$. Assume that there is $z\in X_{u}\cap X_{v}$. Then $W:u,z,v$ is a
weakly toll walk and $z\in W$, a contradiction. $\square$

We say that a weakly toll interval between vertices $u$ and $v$ in a graph,
for which $|WT_{G}(u,v)|\geq|WT_{G}(w,z)|$ for any $w,z\in V(G)$, is maximum
weakly toll interval of $G$.

###### Corollary 2.5

Let $G$ be a connected non complete graph. Then $wtn(G)>2$ if and only if it
holds that for any two non-adjacent vertices $u,v\in V(G)$ such that
$|WT_{G}(u,v)|$ is maximum, $X_{u}\cup X_{v}\neq\emptyset$.

Proof.  Let $G$ be a connected non complete graph with $wtn(G)=2$ and let
$u,v\in V(G)$ be such that $WT_{G}(u,v)$ is maximum. Therefore, by Lemma 2.4,
$X=X_{u}\cup X_{v}$. On the other hand, as $WT_{G}(u,v)=V(G)$, it follows that
$X=V(G)\setminus WT_{G}(u,v)=\emptyset$, therefore $X_{u}\cup
X_{v}=\emptyset.$

Now let $wtn(G)>2$. Then, for every $z,w\in V(G)$, $WT_{G}(z,w)\neq V(G)$. Let
$u,v\in V(G)$ such that $WT_{G}(u,v)$ is maximum and let $x\in V(G)\setminus
WT_{G}(u,v)$. Then, by Lemma 2.4, $x\in X_{u}\cup X_{v}$. $\square$

Assume that we can describe weakly toll intervals between any two vertices of
a graph. Then Corollary 2.5 implies that $wtn(G)=2$ if and only if there is a
maximum weakly toll set of $G$ with $X_{u}\cup X_{v}=\emptyset$.

##  3 The lexicographic product of graphs

Let us first describe weakly toll intervals between non adjacent vertices in
the lexicographic product of two connected graphs $G$ and $H$.

###### Lemma 3.1

Let $G$ and $H$ be connected non complete graphs and consider a lexicographic
product graph $G\left[H\right]$. Let $g\in V(G)$ and let $h_{1},h_{2}\in V(H)$
be two non adjacent vertices. Then
$WT_{G\left[H\right]}((g,h_{1}),(g,h_{2}))=V(G\left[H\right])\setminus X$,
where

$X=\\{(g,x)\in V(G\left[H\right])~{}|~{}x\notin WT_{H}(h_{1},h_{2})\text{ and
}x\text{ is adjacent to exactly one of }h_{1}\text{ and }h_{2}\\}.$

Proof.  Obvioulsly, if $h\in WT_{H}(h_{1},h_{2})$, then $(g,h)\in
WT_{G\left[H\right]}((g,h_{1}),(g,h_{2}))$ for any $g\in V(G)$. Let
$g^{\prime}\in V(G)$ be a neighbor of $g$, i.e. $gg^{\prime}\in E(G)$. Then
$W:(g,h_{1}),(g^{\prime},h),(g,h_{2})$ is a weakly toll walk for any $h\in
V(H)$. Now, let $g^{\prime\prime}\in V(G)$ such that $gg^{\prime\prime}\notin
E(G)$. Let also $P:g,g_{1},\ldots,g_{k},g^{\prime\prime}$ be a shortest path
between $g$ and $g^{\prime\prime}$ in $G$. Then

$W:(g,h_{1}),(g_{1},h_{1}),\ldots,(g_{k},h_{1}),(g^{\prime\prime},h),(g_{k},h_{1}),\ldots,(g_{1},h_{1}),(g_{1},h_{2})$

is a weakly toll walk between $(g,h_{1})$ and $(g,h_{2})$, which contains a
vertex $(g^{\prime\prime},h)$ for any $h\in V(H)$.

To conclude the proof, let $(g,x)\in V(G\left[H\right])$ be such that $x\notin
WT_{H}(h_{1},h_{2})$. Let us consider three cases:

  1. 1.

If $xh_{1}\notin E(H)$ and $xh_{2}\notin E(H)$. Then for some neighbor
$g^{\prime}$ of $g$,

$W:(g,h_{1}),(g^{\prime},h_{1}),(g,x),(g^{\prime},h_{1}),(g,h_{2})$

is a weakly toll walk.

  2. 2.

If $xh_{1}\in E(H)$ and $xh_{2}\notin E(H)$, as $(g,x)\notin
WT_{H^{g}}((g,h_{1}),(g,h_{2}))$, then if $W$ is a weakly toll walk between
$(g,h_{1})$ and $(g,h_{2})$ containing a vertex $(g,x)$, $W$ must contain some
vertex in $V(^{g^{\prime}}\\!H)$, where $gg^{\prime}\in E(G)$. As
$(g,h_{1})(g^{\prime},h)\in E(G\left[H\right])$ for any $h\in V(H)$, this is a
contradiction with $W$ being a weakly toll walk.

  3. 3.

Similarly, if $xh_{1}\notin E(H)$ and $xh_{2}\in E(H)$, then as
$(g,h_{2})(g^{\prime},h)\in E(G\left[H\right])$ for any $h\in V(H)$, there is
no weakly toll walk between $(g,h_{1})$ and $(g,h_{2})$ which would contain
$(g,x)$.

Note that if $xh_{1}\in E(H)$ and $xh_{2}\in E(H)$, then $x\in
WT_{H}(h_{1},h_{2})$. $\square$

###### Lemma 3.2

Let $G$ and $H$ be connected non complete graphs and consider a lexicographic
product graph $G\left[H\right]$. Let $g_{1},g_{2}\in V(G)$ be non adjacent
vertices and let $h_{1},h_{2}\in V(H)$ be non adjacent vertices. Then
$WT_{G\left[H\right]}((g_{1},h_{1}),(g_{2},h_{2}))=\\{(g,h)~{}|~{}g\in
WT_{G}(g_{1},g_{2}),h\in V(H)\\}\setminus X$, where
$X=N_{{}^{g_{1}}\\!H}((g_{1},h_{1}))\cup N_{{}^{g_{2}}\\!H}((g_{2},h_{2})).$

Proof.  Let $g_{1},g_{2}\in V(G)$ be non adjacent vertices and let
$h_{1},h_{2}\in V(H)$ be non adjacent vertices. First, let $g\in
WT_{G}(g_{1},g_{2})\setminus\\{g_{1},g_{2}\\}$ and let
$W:g_{1},g_{1}^{\prime},\ldots,g_{k}^{\prime},g,g_{1}^{\prime\prime}\ldots,g_{l}^{\prime\prime},g_{2}$
be a weakly toll walk in $G$. Then

$W_{1}:(g_{1},h_{1}),(g_{1}^{\prime},h_{1}),\ldots,(g_{k}^{\prime},h_{1}),(g,h),(g_{1}^{\prime\prime},h_{2}),\ldots,(g_{l}^{\prime\prime},h_{2}),(g_{2},h_{2})$

is a weakly toll walk containing $(g,h)$ for any $h\in V(H)$.

Let now $h\in V(H)\setminus N\left[h_{1}\right]$ and
$P:g_{1},g_{1}^{\prime},\ldots g_{k}^{\prime},g_{2}$ a path in $V(G)$. Then

$W:(g_{1},h_{1}),(g_{1}^{\prime},h_{1}),(g_{1},h),(g_{1}^{\prime},h_{1}),(g_{2}^{\prime},h_{1}),\ldots,(g_{k}^{\prime},h_{1}),(g_{2},h_{2})$

is a weakly toll walk in $G\left[H\right]$ containing a vertex $(g_{1},h)$.
Similarly we get a weakly toll walk containing a vertex $(g_{2},h^{\prime})$,
where $h^{\prime}\in V(H)\setminus N\left[h_{2}\right]$.

Let $(g_{1},h)\in V(G\left[H\right])$ and let $hh_{1}\in E(H)$. Note that any
weakly toll walk between $(g_{1},h_{1})$ and $(g_{2},h_{2})$ contains a vertex
$(g^{\prime},h^{\prime})$, where $g_{1}g^{\prime}\in E(G)$ and $h^{\prime}\in
V(H)$. As $(g_{1},h_{1})(g_{1},h)\in E(G\left[H\right])$ and also
$(g_{1},h_{1})(g^{\prime},h^{\prime})\in E(G\left[H\right])$ for every
$h^{\prime}\in V(H)$, a weakly toll walk between $(g_{1},h_{1})$ and
$(g_{2},h_{2})$ cannot contain a vertex $(g_{1},h)$. Symetrically it follows
that no vertex of $N((g_{2},h_{2}))\cap^{g_{2}}\\!H$ is in
$WT_{G\left[H\right]}((g_{1},h_{1}),(g_{2},h_{2}))$.

To conclude the proof, let $(g,h)\in V(G\left[H\right])$, where $g\notin
WT_{G}(g_{1},g_{2})$ and $h\in V(H)$. Suppose that $(g,h)\in
WT_{G\left[H\right]}((g_{1},h_{1}),(g_{2},h_{2}))$ and let

$W_{2}:(g_{1},h_{1}),(g_{1}^{\prime},h_{1}^{\prime}),\ldots,(g_{k}^{\prime},h_{k}^{\prime}),(g,h),(g_{1}^{\prime\prime},h_{1}^{\prime\prime}),\ldots,(g_{l}^{\prime\prime},h_{l}^{\prime\prime}),(g_{2},h_{2})$

be a weakly toll walk containing $(g,h)$. Recall that
$(g_{1}^{\prime},h_{1}^{\prime})$ is the only neighbor of $(g_{1},h_{1})$ and
$(g_{l}^{\prime\prime},h_{l}^{\prime\prime})$ is the only neighbor of
$(g_{2},h_{2})$ in $W_{2}$. Therefore $g_{1}\neq g_{1}^{\prime}$ and
$g_{2}\neq g_{l}^{\prime\prime}$, moreover, $(N(g_{1})\times V(H))\cap
W_{2}=\\{(g_{1}^{\prime},h_{1}^{\prime})\\}$ and $(N(g_{2})\times V(H))\cap
W_{2}=\\{(g_{l}^{\prime\prime},h_{l}^{\prime\prime})\\}$. Assume that for some
$x\in V(H)$, $(g_{1},x)\in W_{2}$. Then $xh_{1}\notin E(H)$ and for every such
vertex $(g_{1},x)$, there is a subwalk
$S_{1}:(g_{1}^{\prime},h_{1}^{\prime}),(g_{1},x),(g_{1}^{\prime},h_{1}^{\prime})$
in $W$. Similarly, assume that for some $y\in V(H)$, $(g_{2},y)\in W$. Then
$yh_{2}\notin E(H)$ and for every such vertex $(g_{2},y)$, there is a subwalk
$S_{2}:(g_{l}^{\prime\prime},h_{l}^{\prime\prime}),(g_{2},y),(g_{l}^{\prime\prime},h_{l}^{\prime\prime})$
in $W_{2}$. Let $W_{2}^{\prime}$ be a walk in $G\left[H\right]$, in which we
replace each subwalk $S_{1}$ with $(g_{1}^{\prime},h_{1}^{\prime})$ and each
subwalk $S_{2}$ with $(g_{l}^{\prime\prime},h_{l}^{\prime\prime})$. Then the
projection of $W_{2}^{\prime}$ is a weakly toll walk in $G$ between $g_{1}$
and $g_{2}$, containing a vertex $g$, which is a contradiction. $\square$

###### Corollary 3.3

Let $G$ and $H$ be connected non complete graphs with $wtn(H)=2$. Then
$wtn(G\left[H\right])=2.$

Proof.  Let $W=\\{h_{1},h_{2}\\}$ be a weakly toll set of $H$ and $g\in V(G)$.
By Lemma 3.1, a set $\\{(g,h_{1}),(g,h_{2})\\}$ is a weakly toll set of
$G\left[H\right]$. $\square$

###### Proposition 3.4

Let $G$ and $H$ be connected non complete graphs. Then
$wtn(G\left[H\right])\leq 3.$

Proof.  Let $g_{1},g_{2}\in V(G)$ and $d_{G}(g_{1},g_{2})=2$ and denote with
$g\in V(G)$ a vertex, for which $gg_{1}\in E(G)$ and $gg_{2}\in E(G)$. We have
such vertices as $G$ is not a complete graph. Let $h_{1},h_{2}\in V(H)$ be two
non adjacent vertices. By Lemma 3.1,
$WT_{G\left[H\right]}((g_{1},h_{1}),(g_{1},h_{2}))=V(G\left[H\right])\setminus
X$, where

$X=\\{(g_{1},x)\in V(G\left[H\right])~{}|~{}x\notin WT_{H}(h_{1},h_{2})\text{
and }x\text{ is adjacent to exactly one of }h_{1}\text{ and }h_{2}\\}.$

Let now $(g_{1},x)\in V(G\left[H\right])$ be such a vertex, that $x\notin
WT_{H}(h_{1},h_{2})$ and $(g_{1},x)(g_{1},h_{1})\in E(G\left[H\right])$ but
$(g_{1},x)(g_{1},h_{2})\notin E(G\left[H\right])$. Then
$W:(g_{1},h_{2}),(g,h_{2}),(g_{1},x),(g,h_{2}),(g_{2},h_{1})$ is a weakly toll
walk between $(g_{1},h_{2})$ and $(g_{2},h_{1})$ containing $(g_{1},x)$. If
$(g_{1},x)(g_{1},h_{1})\notin E(G\left[H\right])$ and
$(g_{1},x)(g_{1},h_{2})\in E(G\left[H\right])$, then
$W:(g_{1},h_{1}),(g,h_{1}),(g_{1},x),(g,h_{1}),(g_{2},h_{1})$ is a weakly toll
walk between $(g_{1},h_{1})$ and $(g_{2},h_{1})$ containing $(g_{1},x)$.
Therefore, a set $\\{(g_{1},h_{1}),(g_{1},h_{2}),(g_{2},h_{1})\\}$ is a weakly
toll set of $G\left[H\right]$. $\square$

###### Theorem 3.5

Let $G$ and $H$ be connected non complete graphs. Then

$wtn(G\left[H\right])=\left\\{\begin{array}[]{cl}2;&wtn(H)=2,\\\
3;&\text{otherwise.}\end{array}\right.$

Proof.  By Proposition 3.4, $wtn(G\left[H\right])\leq 3$. Investigating Lemma
3.1 and Lemma 3.2 we observe that for given graphs $G$ and $H$, maximum weakly
toll intervals arrise when the interval is between two non adjacent vertices
of one copy of $H$. Such an interval is maximum iff a set

$X=\\{x\in V(H)~{}|~{}x\notin WT_{H}(h_{1},h_{2})\text{ and }x\text{ is
adjacent to exactly one of }h_{1}\text{ and }h_{2}\\}$

is minimum, i.e. an empty set. By the notation, used in Lemma 2.4, observe
that $X=X_{h_{1}}\cup X_{h_{2}}$. Moreover, applying Corolarry 2.5 leads to
$X_{h_{1}}\cup X_{h_{2}}=\emptyset$ if and only if $wtn(H)=2.$ $\square$

Even more:

###### Theorem 3.6

Let $G$ and $H$ be connected non complete graphs. Then
$wth(G\left[H\right])=2.$

Proof.  Note that $wth(G\left[H\right])\leq wtn(G\left[H\right])\leq 3.$
Recall the proof of Proposition 3.4. Let
$S=\\{(g_{1},h_{1}),(g_{1},h_{2})\\}$. Then
$\left[S\right]]_{WT}=V(G\left[H\right])$ as the vertex $(g_{2},h_{1})\in
WT((g_{1},h_{1}),(g_{1},h_{2}))$. $\square$

##  4 The Corona product of graphs

Let $G$ and $H$ be connected non complete graphs and denote $|V(G)|=n,$
$V(G)=\\{g_{1},\ldots,g_{n}\\}$, $|V(H)|=m$ and
$V(H)=\\{h_{1},\ldots,h_{m}\\}$. Let $H^{i}$ denote the $i$-th copy of $H$ for
all $i\in\\{1,\ldots,n\\}$ and $V(H^{i})=\\{h_{1}^{i},\ldots,h_{m}^{i}\\}$. We
define the corona produch of graphs $G$ and $H$, $G\circ H$, in the following
way: $V(G\circ H)=V(G)\cup\bigcup_{j=1}^{m}V(H^{j})$ and

$E(G\circ
H)=E(G)\cup\bigcup_{i=1}^{n}\left(E(H^{i})\cup\bigcup_{j=1}^{m}g_{i}h_{j}^{i}\right).$

For every $i\in\\{1,\ldots,n\\}$, $E(H^{i})$ represents the copy of the set
$E(H)$.

Let us describe weakly toll intervals between vertices of $G\circ H$. First we
begin with the case, where both vertices are of the same copy of $H$.

###### Lemma 4.1

Let $G$ and $H$ be connected non complete graphs and consider a corona product
graph $G\circ H$. Let $i\in\\{1,\ldots,n\\}$ and let $h_{1}^{i},h_{2}^{i}\in
V(H^{i})$ be arbitrary non adjacent vertices of the $i$-th copy of $H$ in
$G\circ H$. Then $WT_{G\circ H}(h_{1}^{i},h_{2}^{i})=V(G\circ H)\setminus X$,
where

$X=\\{x\in V(H^{i})~{}|~{}x\notin WT_{H^{i}}(h_{1}^{i},h_{2}^{i})\text{ and
}x\text{ is adjacent to exactly one of }h_{1}^{i}\text{ and }h_{2}^{i}\\}.$

Proof.  W.l.o.g., let $i=1.$ Let $h_{1}^{1},h_{2}^{1}\in V(H^{1})$ be
arbitrary non adjacent vertices of $H^{1}$. First, observe that if $x\in
V(G)\cup\bigcup_{k=2}^{n}V(H^{k})$, then $x\in WT_{G\circ
H}(h_{1}^{1},h_{2}^{1})$. As $W:h_{1}^{1},g_{1},h_{2}^{1}$ is a weakly toll
walk, $g_{1}\in WT_{G\circ H}(h_{1}^{1},h_{2}^{1})$. Note that if $x\neq
g_{1},$ then $x$ is not adjacent to either $h_{1}^{1}$ nor $h_{2}^{1}$.
Consider a vertex $g_{j}$ for any $j\in\\{2,3,\ldots,n\\}$. As $G$ is
connected, there is a path, say $P_{j}$ between $g_{1}$ and $g_{j}$ in $G$.
Let also $Q$ be a walk in $H^{j}$ that contains all vertices of $H^{j}$ and
$\tilde{P_{j}}$ a path in $G$ between $g_{j}$ and $g_{1}.$ Then

$W:h_{1}^{1},P_{j},Q,\tilde{P_{j}},h_{2}^{1},$

is a weakly toll walk containing $g_{j}$ and every vertex of $V(H^{j})$ for
every $j\in\\{2,3,\ldots,n\\}$. Therefore,
$V(G)\cup\bigcup_{k=2}^{n}V(H^{k})\subseteq WT_{G\circ
H}(h_{1}^{1},h_{2}^{1}).$

Now, let $x\in V(H^{1})\setminus\\{h_{1}^{1},h_{2}^{1}\\}$. Let us consider
three cases:

  1. 1.

If $xh_{1}^{1}\in E(H^{1})$ and $xh_{2}^{1}\in E(H^{1})$, then
$W:h_{1}^{1},x,h_{2}^{1}$ is a weakly toll walk and $x\in WT_{G\circ
H}(h_{1}^{1},h_{2}^{1})$.

  2. 2.

If $xh_{1}^{1}\notin E(H^{1})$ and $xh_{2}^{1}\notin E(H^{1})$, then
$W:h_{1}^{1},g_{1},x,g_{1},h_{2}^{1}$ is a weakly toll walk and $x\in
WT_{G\circ H}(h_{1}^{1},h_{2}^{1})$.

  3. 3.

Let $xh_{1}^{1}\in E(H^{1})$ and $xh_{2}^{1}\notin E(H^{1})$. If $x\in
WT_{H^{1}}(h_{1}^{1},h_{2}^{1})$, then $x\in WT_{G\circ
H}(h_{1}^{1},h_{2}^{1})$. To conclude the proof, assume that $x\notin
WT_{H^{1}}(h_{1}^{1},h_{2}^{1})$, but $x\in WT_{G\circ
H}(h_{1}^{1},h_{2}^{1})$. Therefore, a weakly toll walk between $h_{1}^{1}$
and $,h_{2}^{1}$ should contain $g_{1}$, but as $g_{1}h_{1}^{1}\in E(G\circ
H)$ and $xh_{1}^{1}\in E(G\circ H)$, this is a contradiction. Therefore, in
this case, $x\notin WT_{G\circ H}(h_{1}^{1},h_{2}^{1})$. Note that the case
$xh_{1}^{1}\notin E(H^{1})$ and $xh_{2}^{1}\in E(H^{1})$ is very similar.

$\square$

Let us continue with the description of weakly toll intervals between vertices
of $G\circ H$, which lie in different copies of $H$.

###### Lemma 4.2

Let $G$ and $H$ be connected non complete graphs and consider a corona product
graph $G\circ H$. Let $i,j\in\\{1,\ldots,n\\}$ be distinct and let
$k,l\in\\{1,\ldots,m\\}$. Consider vertices $h_{k}^{i}\in V(H^{i})$ and
$h_{l}^{j}\in V(H^{j})$. Then $WT_{G\circ H}(h_{k}^{i},h_{l}^{j})=V(G\circ
H)\setminus\left(N_{H^{i}}(h_{k}^{i})\cup N_{H^{j}}(h_{l}^{j})\right).$

Proof.  W.l.o.g, let $i=1$ and $j=2$. Let $P$ be a path between $g_{1}$ and
$g_{2}$ in $G$. Then $W:h_{k}^{1},P,h_{l}^{2}$ is a weakly toll walk.
Therefore $g_{1},g_{2}\in WT_{G\circ H}(h_{k}^{1},h_{l}^{2})$.

Let $g_{o}\in V(G)\setminus\\{g_{1},g_{2}\\}$. Let $P_{g_{1},g_{o}}$ be a path
between $g_{1}$ and $g_{o}$ in $G$ and let $P_{g_{o},g_{2}}$ be a path between
$g_{o}$ and $g_{2}$ in $G$. Note that concatenation of paths $P_{g_{1},g_{o}}$
and $P_{g_{o},g_{2}}$ is a walk and $g_{1}$ and $g_{2}$ can appear more than
once in this walk. Let also $Q$ be a walk in $H$, which contains every vertex
of $V(H)$ and $Q^{o}$ its copy in $V(H^{o})$. Then
$W:h_{k}^{1},P_{g_{1},g_{o}},Q^{o},P_{g_{o},g_{2}},h_{l}^{2}$ is a weakly toll
walk containing $g_{o}$ and every vertex of a set $V(H^{o})$. Therefore,
$\bigcup_{i=1}^{n}\\{g_{i}\\}\cup\bigcup_{i=3}^{n}V(H^{i})\subseteq WT_{G\circ
H}(h_{k}^{1},h_{l}^{2})$.

Let $x\in V(H^{1})$, $x\notin N\left[h_{k}^{1}\right]$ and $P$ a path between
vertices $g_{1}$ and $g_{2}$ in $G$. Then $W:h_{k}^{1},g_{1},x,P,h_{l}^{2}$ is
a weakly toll walk in $G\circ H$ containing $x$. Similarly, Let $y\in
V(H^{2})$, $y\notin N\left[h_{l}^{2}\right]$. Then
$W:h_{k}^{1},P,y,g_{2},h_{l}^{2}$ is a weakly toll walk in $G\circ H$
containing $y$.

To conclude the proof, let $x\in N_{H^{1}}(h_{k}^{1})$. Note that $g_{1}$ lies
on any weakly toll walk between $h_{k}^{1}$ and $h_{l}^{2}$. As
$h_{k}^{1}g_{1},h_{k}^{1}x\in E(G\circ H)$, $x\notin WT_{G\circ
H}(h_{k}^{i},h_{l}^{j})$. Similarly, if $y\in N_{H^{2}}(h_{l}^{2})$, $y\notin
WT_{G\circ H}(h_{k}^{i},h_{l}^{j})$ as $h_{l}^{2}g_{2},h_{l}^{2}y\in E(G\circ
H)$. $\square$

Before we consider weakly toll intervals in $G\circ H$ between vertices of
$G$, let us present an observation about weakly toll walks in the corona
product graphs:

###### Proposition 4.3

Let $G$ and $H$ be connected non complete graphs and consider a corona product
graph $G\circ H$. Let $g_{1},g_{2},g\in V(G)$, where $g_{1}g_{2}\notin E(G)$.
Then $g\in WT_{G}(g_{1},g_{2})$ if and only if $g\in WT_{G\circ
H}(g_{1},g_{2})$.

Proof.  If $g\in WT_{G}(g_{1},g_{2})$, then obviously $g\in WT_{G\circ
H}(g_{1},g_{2})$. Assume now that $g\notin WT_{G}(g_{1},g_{2})$ and suppose
that $g\in WT_{G\circ H}(g_{1},g_{2})$. Denote with $W$ a weakly toll walk
between $g_{1}$ and $g_{2}$ in $G\circ H$ that contains $g$. Then $W$ must
contain some vertex from the set $V(G\circ H)\setminus V(G)$. Now, construct a
new weakly toll walk $W^{\prime}$, which we get by taking $W$ and leaving out
any vertex that is not in $V(G)$. By the structure of the corona product graph
we see, that $W^{\prime}$ in fact is a walk and even a weakly toll walk
between $g_{1}$ and $g_{2}$, which contains $g$ and all vertices of
$W^{\prime}$ are in $V(G)$, a contradiction. $\square$

###### Lemma 4.4

Let $G$ and $H$ be connected non complete graphs and consider a corona product
graph $G\circ H$. Let $i,j\in\\{1,\ldots,n\\}$ be disctinct. Then $WT_{G\circ
H}(g_{i},g_{j})=WT_{G}(g_{i},g_{j})\cup\bigcup_{k\in A}H^{k}$, where
$A=\\{k\in\\{1,\ldots,n\\}~{}|~{}k\neq i,k\neq j,g_{k}\in
WT_{G}(g_{i},g_{j})\\}$.

Proof.  First, assume $g_{i}g_{j}\in E(G)$. Then $W:g_{i},g_{j}$ is (the only)
weakly toll walk between vertices $g_{i}$ and $g_{j}$ in $G\circ H,$
$A=\emptyset$ and $WT_{G\circ H}(g_{i},g_{j})=WT_{G}(g_{i},g_{j})$. Therefore,
assume from now on that $g_{i}g_{j}\notin E(G)$.

Let $g_{k}\in V(G)\setminus\\{g_{i},g_{j}\\}$. By Proposition 4.3, $g_{k}\in
WT_{G\circ H}(g_{i},g_{j})$ if and only if $g_{k}\in WT_{G}(g_{i},g_{j})$.
First, let $g_{k}\in WT_{G}(g_{i},g_{j})$, let
$W_{k}:g_{i},\ldots,g_{k},\ldots,g_{j}$ be a weakly toll walk in $G$ and
$Q_{k}$ a walk in $H^{k}$, which contains all vertices of $H^{k}$. Then
$W:g_{i},\ldots,g_{k},Q_{k},g_{k},\ldots,g_{j}$ is a weakly toll walk in
$G\circ H$ that contains every vertex of $H^{k}$.

To conclude the proof, observe that for any $k\in\\{1,\ldots,m\\}$
$h_{k}^{i}\notin WT_{G\circ H}(g_{i},g_{j})$ because $h_{k}^{i}g_{l}\notin
E(G\circ H)$ for any $l\neq i$. Similarly, $h_{k}^{j}\notin WT_{G\circ
H}(g_{i},g_{j})$ for any $k\in\\{1,\ldots,m\\}$. If $g_{k}\notin
WT_{G}(g_{i},g_{j})$ also $h^{k}_{l}\notin WT_{G\circ H}(g_{i},g_{j})$ for any
$l\in\\{1,\ldots,m\\}$. $\square$

To be able to describe weakly toll intervals for the last case, we need the
following definition:

###### Definition 4.5

Let $u$ and $v$ be two different, non-adjacent vertices of a graph $G$. A semi
weakly toll walk $\tilde{W}$ between $u$ and $v$ in $G$ is a sequence of
vertices of the form

$\tilde{W}:u=w_{0},w_{1},\ldots,w_{k-1},w_{k}=v,$

where $k\geq 0$, which enjoys the following conditions for $k>0$:

  * •

$w_{i}w_{i+1}\in E(G)$ for all $i\in\\{0,\ldots,k-1\\}$,

  * •

$uw_{i}\in E(G)$ implies $w_{i}=w_{1}$, where $i\in\\{1,\ldots,k\\}$.

A semi wekly toll interval is the set

$SWT_{G}(u,v)=\\{x\in V(G)~{}|~{}x\text{ lies on a semi weakly toll walk
between $u$ and $v$.}\\}.$

Note that it is important which vertex is the beginning of a semi weakly toll
walk and which the end (which was irrelevant in the definition of the weakly
toll walk.) The definition states that the first vertex of the semi weakly
toll walk ($u$) has the same restrictions as end-vertices in the definition of
the weakly toll walks, while there are no restrictions for the last vertex of
the semi weakly toll walk ($v$). It can also appear more than once in the
walk.

###### Lemma 4.6

Let $G$ and $H$ be connected non complete graphs and consider a corona product
graph $G\circ H$. Let $i,j\in\\{1,\ldots,n\\}$, $k\in\\{1,\ldots,m\\}$ and
consider vertices $g_{i},h^{j}_{k}$. Let $S=SWT_{G}(g_{i},g_{j})$.

$WT_{G\circ
H}(g_{i},h^{j}_{k})=\left\\{\begin{array}[]{cl}\\{g_{i},h_{k}^{i}\\};&\text{if
}i=j,\\\ \\{g_{i},g_{j}\\}\cup\left(V(H^{j})\setminus
N_{H^{j}}(h_{k}^{j})\right)\cup\bigcup_{x\in
S\setminus\\{g_{i},g_{j}\\}}\left(\\{x\\}\cup V(H^{x})\right);&\text{if }i\neq
j.\end{array}\right.$

Proof.  If $i=j$, then $g_{i}h_{k}^{i}\in E(G\circ H)$ and $WT_{G\circ
H}(g_{i},h^{j}_{k})=\\{g_{i},h_{k}^{i}\\}$.

Let now $i\neq j$. By the definition of the corona product graph, it is clear
that no vertex of $H^{i}$ belongs to $WT_{G\circ H}(g_{i},h^{j}_{k}).$ As any
weakly toll walk between $g_{i}$ and $h^{j}_{k}$ contains a vertex $g_{j}$, it
follows that if for some $l\in\\{1,\ldots,m\\}$, $h_{l}^{j}h_{k}^{j}\in
E(H^{j})$, then $h_{l}^{j}\notin WT_{G\circ H}(g_{i},h^{j}_{k}).$ Let $P$ be a
path from $g_{i}$ to $g_{j}$ in $G$ and $x\in V(H^{k})\setminus
N_{H^{j}}(h_{k}^{j})$. Then $W:P,x,g_{j},h_{k}^{j}$ is a weakly toll walk
containing a vertex $x$. Note that if $x=h_{k}^{j}$, then
$W:g_{i},P,g_{j},h_{k}^{j}$ is a corresponding weakly toll walk in $G\circ H$.

Let $g_{s}\in SWT_{G}(g_{i},g_{j})$. Then there is a semi weakly toll walk
$S^{\prime}$ between $g_{i}$ and $g_{j}$ in $G$ that contains a vertex
$g_{s}$. Denote with $S_{g_{i},g_{s}}$ a subwalk of $S^{\prime}$ between
$g_{i}$ and $g_{s}$, $S_{g_{s},g_{j}}$ a subwalk of $S^{\prime}$ between
$g_{s}$ and $g_{j}$ and $Q^{s}$ a walk in $H^{s}$, which goes throught every
vertex of $H^{s}$. Then $W:S_{g_{i},g_{s}},Q^{s},S_{g_{s},g_{j}},h_{k}^{j}$ is
a weakly toll walk in $G\circ H$ containing vertices $g_{s}$ and every vertex
of $V(H^{j})$.

To conclude the proof, assume that $g_{s}\notin SWT_{G}(g_{i},g_{j})$. As
every toll walk, that contains a vertex $h_{l}^{s}$ for some
$l\in\\{1,\ldots,m\\}$, must also contain a vertex $g_{s}$, no vertex of
$V(H^{s})$ belongs to $WT_{G\circ H}(g_{i},h^{j}_{k})$. $\square$

The description of weakly toll intervals in the corona product graphs gives
the following results on the weakly toll number of the corona product graphs.
By Lemma 4.1 it immidiately follows that $wtn(G\circ H)=2$ if $wtn(H)=2$.

###### Corollary 4.7

Let $G$ and $H$ be connected graphs with $wtn(H)=2$. Then $wtn(G\circ H)=2.$

Proof.  Let $W=\\{h_{1},h_{2}\\}$ be a weakly toll set of $H$. By Lemma 4.1, a
set $\\{h_{1}^{1},h_{2}^{1}\\}$ is a weakly toll set of $G\circ H$ as the case
$x\notin WT_{H^{1}}(h_{1}^{1},h_{2}^{1})$ cannot happen. $\square$

Even more, one additional vertex gives an upper bound for arbitrary connected
graph $H$.

###### Proposition 4.8

Let $G$ and $H$ be connected graphs and $H$ non complete graph. Then
$wtn(G\circ H)\leq 3.$

Proof.  Let $h_{1}^{1},h_{2}^{1}$ be two non adjacent vertices of $H^{1}.$
Note that if $\\{h_{1}^{1},h_{2}^{1}\\}$ is a weakly toll set of $H^{1}$, by
Corollary 4.7, $wtn(G\circ H)=2$. So, assume that $\\{h_{1}^{1},h_{2}^{1}\\}$
is not a weakly toll set of $H^{1}$. By Lemma 4.1, $WT_{G\circ
H}(h_{1}^{1},h_{2}^{1})=V(G\circ H)\setminus X$, where

$X=\\{x\in V(H^{i})~{}|~{}x\notin WT_{H^{1}}(h_{1}^{i},h_{2}^{1})\text{ and
}x\text{ is adjacent to exactly one of }h_{1}^{i}\text{ and }h_{2}^{i}\\}.$

Now, consider a set $\\{h_{1}^{1},h_{2}^{1},g_{2}\\}$, where $g_{1}g_{2}\in
E(G)$. Let $x\in V(H^{1})$ such that $xh_{1}^{1}\in E(H^{1})$ and
$xh_{2}^{1}\notin E(H^{1})$. Then $W:g_{2},g_{1},x,g_{1},h_{2}^{1}$ is a
weakly toll walk in $G\circ H$ that contains $x$. If $x\in V(H^{1})$ is such a
vertex that $xh_{1}^{1}\notin E(H^{1})$ and $xh_{2}^{1}\in E(H^{1})$, then
$W^{\prime}:g_{2},g_{1},x,g_{1},h_{1}^{1}$ is a weakly toll walk in $G\circ H$
that contains $x$. Therefore $\\{h_{1}^{1},h_{2}^{1},g_{2}\\}$ is a weakly
toll set and $wtn(G\circ H)\leq 3.$ $\square$

Even more, investigating Lemma 4.1, Lemma 4.2, Lemma 4.4 and Lemma 4.6 we
observe that for given graphs $G$ and $H$, maximum weakly toll intervals
arrise when the weakly toll interval is taken between two non adjacent
vertices of one copy of $H$ (as described in Lemma 4.1). Such a weakly toll
interval is maximum iff a set

$X=\\{x\in V(H^{i})~{}|~{}x\notin WT_{H^{i}}(h_{1}^{i},h_{2}^{i})\text{ and
}x\text{ is adjacent to exactly one of }h_{1}^{i}\text{ and }h_{2}^{i}\\}.$

is minimum, i.e. an empty set. By the notation, used in Lemma 2.4, observe
that $X=X_{h^{i}_{1}}\cup X_{h^{i}_{2}}$. Moreover, applying Corolarry 2.5
leads to $X_{h^{i}_{1}}\cup X_{h^{i}_{2}}=\emptyset$ if and only if
$wtn(H)=2.$

Therefore we have the following:

###### Theorem 4.9

Let $G$ and $H$ be connected non complete graphs. Then

$wtn(G\circ H)=\left\\{\begin{array}[]{cl}2;&wtn(H)=2,\\\
3;&\text{otherwise.}\end{array}\right.$

Even more:

###### Theorem 4.10

Let $G$ and $H$ be connected non complete graphs. Then $wth(G\circ H)=2.$

Proof.  Note that $wth(G\circ H)\leq wtn(G\circ H)\leq 3.$ Recall the proof of
the Proposition 4.8. Let $S=\\{h_{1}^{1},h_{2}^{1}\\}$. Then
$\left[S\right]]_{WT}=V(G\circ H)$ as the vertex $g_{2}\in
WT(h_{1}^{1},h_{2}^{1})$. $\square$

In addition, recall the definition of the generalized corona product graph.
Given simple graphs $G,H_{1},\ldots,H_{n}$, where $n=|V(G)|$, the generalized
corona, denoted $G\circ\wedge_{i=1}^{n}H_{i}$, is the graph, obtained by
taking one copy of graphs $G,H_{1},\ldots,H_{n}$, and joining the $i-th$
vertex of $G$ to every vertex of $H_{i}$. Summing up the results, obtained for
the corona product graph, it follows immidiately that
$wtn(G\circ\wedge_{i=1}^{n}H_{i})\leq 3$ if at least one of $H_{i}$ is not a
complete graph. Even more, if there is one of $H_{i}$, for which
$wtn(H_{i})=2$, then $wtn(G\circ\wedge_{i=1}^{n}H_{i})=2$. Obviously, by
Theroem 4.10, $wth(G\circ\wedge_{i=1}^{n}H_{i})=2$.

##  5 Acknowledgements

This research was supported by Slovenian Research Agency under the grants
P1-0383, J1-2452 and J1-1693.

## References

  * [1] L. Alcón, A note on path domination, Discuss. Math. Graph Theory. 36 (2016) 1021–1034.
  * [2] L. Alcón, B. Brešar, T. Gologranc, M. Gutierrez, T. Kraner, I. Peterin, A. Tepeh, Toll convexity, European J. Combin. 46 (2015) 161–175.
  * [3] B. Brešar, S. Klavžar, A. Tepeh Horvat, On the geodetic number and related metric sets in Cartesian product graphs, Discrete Math. 308 (2008) 5555–5561.
  * [4] B. Brešar, T. Kraner Šumenjak, A. Tepeh, The geodetic number of the lexicographic product of graphs, Discrete Math. 311 (2011) 1693–1698.
  * [5] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl., 60 (11) (2010) 3020–3031.
  * [6] G. B. Cagaanan, S. R. Canoy Jr., On the hull sets and hull number of the Cartesian product of graphs, Discrete Math. 287 (2004) 141–144.
  * [7] M. C. Dourado, Computing the hull number in toll convexity, Ann. Oper. Res. 315 (2022) 121–140.
  * [8] M. C. Dourado, M. Gutierrez, F. Protti, S. Tondato, Weakly toll convexity and proper interval graphs, arXiv:2203.17056v6.
  * [9] M. C. Dourado, M. Gutierrez, F. Protti, S. Tondato, Computing the hull and interval numbers in the weakly toll convexity, arXiv:2303.07414v1.
  * [10] T. Dravec, On the toll number of a graph, Disc. Appl. Math 321 (2022) 250–257.
  * [11] M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Alg. Discrete Math. 7 (1986) 433–444.
  * [12] T. Gologranc, P. Repolusk, Toll number of the Cartesian and the lexicographic product of graphs, Discrete Math. 340 (2017) 2488–2498.
  * [13] T. Gologranc, P. Repolusk, Toll number of the strong product of graphs, Discrete Math. 342 (2019) 807–814.
  * [14] R. Hammack, W. Imrich, S. Klavžar, _Handbook of Product Graphs, Second Edition_ , CRC Press, Boca Raton, FL, 2011.
  * [15] I. M. Pelayo, Geodesic Convexity in Graphs, Springer, New York, 2013.
  * [16] A. P. Santhakumaran, P. Titus, K. Ganesamoorthy, On the monophonic number of a graph, J. Appl. Math. Informatics 32 (2014) 255–266.


# Emerging vaccine-breakthrough SARS-CoV-2 variants

Rui Wang1, Jiahui Chen1, Yuta Hozumi1, Changchuan Yin2, and Guo-Wei
Wei1,3,4111 Corresponding author. Email<EMAIL_ADDRESS>
1 Department of Mathematics,
Michigan State University, MI 48824, USA.
2 Department of Mathematics, Statistics, and Computer Science,
University of Illinois at Chicago, Chicago, IL 60607, USA
3 Department of Electrical and Computer Engineering,
Michigan State University, MI 48824, USA.
4 Department of Biochemistry and Molecular Biology,
Michigan State University, MI 48824, USA.

###### Abstract

The recent global surge in coronavirus disease 2019 (COVID-19) infections have
been fueled by new severe acute respiratory syndrome coronavirus 2 (SARS-
CoV-2) variants, namely Alpha, Beta, Gamma, Delta, etc. The molecular
mechanism underlying such surge is elusive due to the existence of 28,554,
including 4,653 non-degenerate mutations on the spike (S) protein, which is
the target of most COVID-19 vaccines. The understanding of the molecular
mechanism of SARS-CoV-2 transmission and evolution is a prerequisite to
foresee the global trend of emerging vaccine-breakthrough SARS-CoV-2 variants
and the design of mutation-proof vaccines and monoclonal antibodies (mAbs). We
integrate the genotyping of 1,489,884 SARS-CoV-2 genomes isolated from
patients, a library collection of 130 human antibodies, tens of thousands of
mutational data points, topological data analysis (TDA), and deep learning to
reveal SARS-CoV-2 evolution mechanism and forecast emerging vaccine-escape
variants. We show that infectivity-strengthening and antibody-disruptive co-
mutations on the S protein receptor-binding domain (RBD) can quantitatively
explain the infectivity and virulence of all prevailing variants. We
demonstrate that Lambda is as infectious as Delta but is more vaccine-
resistant. We analyze emerging vaccine-breakthrough co-mutations in 20
COVID-19 devastated countries, including the United Kingdom (UK), the United
States (US), Denmark (DK), Brazil (BR), Germany (DE), Netherlands (NL), Sweden
(SE), Italy (IT), Canada (CA), France (FR), India (IN), and Belgium (BE), etc.
We envision that natural selection through infectivity will continue to be a
main mechanism for viral evolution among unvaccinated populations, while
antibody disruptive co-mutations will fuel the future growth of vaccine-
breakthrough variants among fully vaccinated populations. Finally, we have
identified the following sets of co-mutations that have the great likelihood
of becoming dominant: [A411S, L452R, T478K], [L452R, T478K, N501Y], [V401L,
L452R, T478K], [K417N, L452R, T478K], [L452R, T478K, E484K, N501Y], and
[P384L, K417N, E484K, N501Y]. We predict they, particularly the last four,
will break through existing vaccines. We foresee an urgent need to develop new
vaccines that target these co-mutations.

Keywords: COVID-19, SARS-CoV-2, receptor-binding domain, co-mutations,
variants, vaccine-breakthrough, vaccine-escape, vaccine-resistant, infectivity

##  1 Introduction

The death toll of coronavirus disease 2019 (COVID-19) caused by severe acute
respiratory syndrome coronavirus 2 (SARS-CoV-2) has exceeded 4.4 million in
August 2021. Tremendous efforts in combating SARS-CoV-2 have led to several
authorized vaccines, which mainly target the viral spike (S) proteins.
However, the emergence of mutations on the S gene has resulted in more
infectious variants and vaccine breakthrough infections. Emerging vaccine
breakthrough SARS-CoV-2 variants pose a grand challenge to the long-term
control and prevention of the COVID-19 pandemic. Therefore, forecasting
emerging breakthrough SARS-CoV-2 variants is of paramount importance for the
design of new mutation-proof vaccines and monoclonal antibodies (mABs).

To predict emerging breakthrough SARS-CoV-2 variants, one must understand the
molecular mechanism of viral transmission and evolution, which is one of the
greatest challenges of our time. SARS-CoV-2 entry of a host cell depends on
the binding between S protein and the host angiotensin-converting enzyme 2
(ACE2), primed by host transmembrane protease, serine 2 (TMPRSS2) [1]. Such a
process inaugurates the host’s adaptive immune response, and consequently,
antibodies are generated to combat the invading virus either through direct
neutralization or non-neutralizing binding [2, 3]. S protein receptor-binding
domain (RBD) is a short immunogenic fragment that facilitates the S protein
binding with ACE2. Epidemiological and biochemical studies have suggested that
the binding free energy (BFE) between the S RBD and the ACE2 is proportional
to the infectivity [4, 5, 6, 1, 7]. Additionally, the strong binding between
the RBD and mAbs leads to effective direct neutralization [8, 9, 10].
Therefore, RBD mutations have dominating impacts on viral infectivity, mAb
efficacy, and vaccine protection rates. Mutations may occur for various
reasons, including random genetic drift, replication error, polymerase error,
host immune responses, gene editing, and recombinations [11, 12, 13, 14, 15].
Being beneficial from the genetic proofreading mechanism regulated by NSP12
(a.k.a RNA-dependent RNA polymerase) and NSP14 [16, 17], SARS-CoV-2 has a
higher fidelity in its replication process than the other RNA viruses such as
influenza. Nonetheless, near 700 non-degenerate mutations are observed on RBD,
contributing many key mutations in emerging variants, i.e., N501Y for Alpha,
K417N, E484K, and N501Y for Beta, K417T, E484K, and N501Y for Gamma, L452R and
T478K for Delta, L452Q and F490S for Lambda, etc [18]. Given the importance of
the RBD for SARS-CoV-2 infectivity, vaccine efficacy, and mAb effectiveness,
it is imperative to understand the mechanism governing RBD mutations.

In June 2020, when there were only 89 non-degenerated mutations on the RBD,
and the highest observed mutational frequency was only around 50 globally, we
were able to show that natural selection underpins SARS-CoV-2 evolution, based
on the genotyping of 24,715 SARS-CoV-2 sequences isolated patients and a
topology-based deep learning model for RBD-ACE2 binding analysis [19]. In the
same work, we predicted that RBD residues 452 and 501 “have high chances to
mutate into significantly more infectious COVID-19 strains” [19]. Currently,
these residues are the key mutational sites of all prevailing SARS-CoV-2
variants. We further foresaw a list of 1,149 most likely RBD mutations among
3686 possible RBD mutations [19]. Up to date, every one of the observed 683
RBD mutations belongs to the list. In April 2021, we demonstrated that all the
100 most observed RBD mutations of 651 existing RBD mutations from 506,768
viral genomes had enhanced the binding between RBD and ACE2, resulting in more
infectious variants [18]. The odd for these 100 most observed mutations to be
there accidentally is smaller than one chance in 1.2 nonillions
($2^{100}\approx$ 1.2$\times 10^{30}$)222The average BFE changes of 1149 RBD
mutations for the RBD-ACE2 complex is -0.28kcal/mol. Randomly, each RBD
mutation has a 50% chance to assume a BFE change above or below -0.28kcal/mol,
which leads to $2^{100}=1.276506\times 10^{30}$ possible states for 100
mutations.. There is no double that natural selection via viral infectivity,
rather than any other competing theories [11, 12, 13, 14, 15], is the
dominating mechanism for SARS-CoV-2 transmission and evolution. This
mechanistic discovery lays the foundation for forecasting future emerging
SASR-CoV-2 variants.

Understanding SARS-CoV-2 variant threats to current vaccines and mAbs is
another urgent issue facing the scientific community [20]. The World Health
Organization (WHO) identified variants of concern (VOCs) and variants of
interest (VOIs). The former describes variants that have an increment in the
transmissibility and virulence, or adversely affect the effectiveness of
vaccines, therapeutics, and diagnostics with clear clinical correlation
evidence. The latter describes variants that carry genetic changes, which are
predicted or known to reduce neutralization by antibodies generated against
vaccination, the efficacy of treatments, and affect transmissibility,
virulence, disease severity, immune escape, diagnostics, etc., which cause
significant community transmission and suggest an emerging risk to the public.
Currently, WHO listed four VOCs, i.e., variants B.1.1.7 (Alpha) [21, 22, 23],
B.1.351 (Beta) [22, 24], P.1 (Gamma)[22], and B.1.617.2 (Delta) [25]), and
four VOIs, i.e., variants B.1.525 (Eta)[26], B.1.526 (Iota) [26, 27],
B.1.617.1 (Kappa) [28], C.37 (Lambda)[29], and B.1.621 (Mu) (A general
introduction about the prevailing and emerging variants is given in Section S1
of the Supporting Information.). Our hypothesis is that the severity of
variants to infectivity, vaccine efficacy, and mAbs effectiveness depends
mainly on how the associated RBD mutations impact the binding with ACE2 and
antibodies. Based on this hypothesis, we collected and analyzed a library of
antibodies and unveiled that most of the RBD mutations would weaken the
binding of S protein and antibodies and disrupt the efficacy and reliability
of antibody therapies and vaccines [20]. We predicted “the urgent need to
develop new mutation-resistant vaccines and antibodies and prepare for
seasonal vaccination” in early 2021 [20]. We further identified vaccine-escape
(i.e., vaccine-breakthrough) mutations and fast-growing mutations [18]. Our
predictions of the threats from VOCs and VOIs were in great agreement with
experimental data [30].

The objective of this work is to forecast emerging SARS-CoV-2 variants that
pose an imminent threat to combating COVID-19 and long-term public health. To
this end, we carry out an RBD-specific analysis of SARS-CoV-2 co-mutations
involving a wide variety of combinations of 683 unique single mutations on the
RBD. We take a unique approach that integrates viral genotyping of 1,489,884
complete genome sequences isolated from patients, algebraic topology
algorithms that won the worldwide competition in computer-aided drug discovery
[31], deep learning models trained with tens of thousands of mutational data
points [30, 20], and a library of 130 SARS-CoV-2 antibody structures. By
analyzing the frequency, binding free energy (BFE) changes, and antibody
disruption counts of RBD co-mutations, we reveal that nine RBD co-mutation
sets, namely [L452R, T478K], [L452Q, F490S], [E484K, N501Y], [F490S, N501Y],
[S494P, N501Y], [K417T, E484K, N501Y], [K417N, L452R, T478K], [K417N, E484K,
N501Y], and [P384L, K417N, E484K, N501Y], may strongly disrupt existing
vaccines and mAbs with relatively high infectivity and transmissibility among
the populations. We predict that low-frequency co-mutation sets [A411S, L452R,
T478K], [L452R, T478K, N501Y], [V401L, L452R, T478K], and [L452R, T478K,
E484K, N501Y] are on the path to become dangerous new variants. The associated
new mutations, P384L, V401L, and A411S, call for the new design of boosting
vaccines and mAbs.

##  2 Results

###  2.1 Vaccine-breakthrough S protein RBD mutations

Figure 1: Most significant RBD mutations. a The 3D structure of SARS-CoV-2 S
protein RBD and ACE2 complex (PDB ID: 6M0J). The RBD mutations in ten variants
are marked with color. b Illustration of the time evolution of 455 ACE2
binding-strengthening RBD mutations (blue) and 228 ACE2 binding-weakening RBD
mutations (red). The $x$-axis represents the date and the $y$-axis represents
the natural log of frequency. There has been a surge in the number of
infections since early 2021. c BFE changes of RBD complexes with ACE2 and 130
antibodies induced by 75 significant RBD mutations. A positive BFE change
(blue) means the mutation strengthens the binding, while a negative BFE change
(red) means the mutation weakens the binding. Most mutations, except for
vaccine-resistant Y449H and Y449S, strengthen the RBD binding with ACE2. Y449S
and K417N are highly disruptive to antibodies.

To understand the molecular mechanisms of vaccine-escape mutations, we analyze
single nucleotide polymorphisms (SNPs) of 1,489,884 complete SARS-CoV-2 genome
sequences, resulting in 683 non-degenerate RBD mutations and their associated
frequencies. A full set of mutation information is available on our
interactive web page Mutation Tracker. The infectivity of each mutation is
mainly determined by the mutation-induced BFE change to the binding complex of
RBD and ACE2. To estimate the impact of each mutation on vaccines, we collect
a library of 130 antibody structures (Supporting Information S2.1.2),
including Food and Drug Administration (FDA)-approved mAbs from Eli Lilly and
Regeneron. For a given RBD mutation, its number of antibody disruptions is
given by the number of antibodies whose mutation-induced antibody-RBD BFE
changes are smaller than -0.3kcal/mol (A list of names for antibodies that are
disrupted by mutations can be found in the Supporting Information S2.1.1.).
BFE changes following mutations are predicted by our deep learning model,
TopNetTree [32]. We have created an interactive web page, Mutation Analyzer,
to list all RBD mutations, their observed frequencies, their RBD-ACE2 BFE
changes following mutations, their number of antibody disruptions, and various
ranks. Figure 1 illustrates RBD mutations associated with prevailing SARS-
CoV-2 variants, time evolution trajectories of all RBD mutations, and the BFE
changes of RBD-ACE2 and 130 RBD-antibodies induced by 75 significant
mutations. A summary of our analysis is given in Table 1.

Table 1: Top 25 most observed S protein RBD mutations. Here, BFE change refers to the BFE change for the S protein and human ACE2 complex induced by a single-site S protein RBD mutation. A positive mutation-induced BFE change strengthens the binding between S protein and ACE2, which results in more infectious variants. Counts of antibody disruption represent the number of antibody and S protein complexes disrupted by a specific RBD mutation. Here, an antibody and S protein complex is to be disrupted if its binding affinity is reduced by more than 0.3 kcal/mol [18]. In addition, we calculate the antibody disruption ratio (%), which is the ratio of the number of disrupted antibody and S protein complexes over 130 known complexes. Ranks are computed from 683 observed RBD mutations. Mutation | Worldwide | BFE change | Antibody disruption
---|---|---|---
Count | Rank | Change | Rank | Count | Ratio | Rank
N501Y | 744354 | 1 | 0.5499 | 30 | 24 | 18.46 | 160
L452R | 259345 | 2 | 0.5752 | 28 | 39 | 30.0 | 98
T478K | 239619 | 3 | 0.9994 | 2 | 2 | 1.54 | 557
E484K | 84167 | 4 | 0.0946 | 272 | 38 | 29.23 | 104
K417T | 37748 | 5 | 0.0116 | 433 | 37 | 28.46 | 107
S477N | 32673 | 6 | 0.0180 | 422 | 0 | 0.0 | 650
N439K | 16154 | 7 | 0.1792 | 159 | 11 | 8.46 | 272
K417N | 8399 | 8 | 0.1661 | 176 | 53 | 40.77 | 61
F490S | 5617 | 9 | 0.4406 | 52 | 51 | 39.23 | 67
S494P | 5119 | 10 | 0.0902 | 282 | 62 | 47.69 | 46
N440K | 3379 | 11 | 0.6161 | 22 | 0 | 0.0 | 645
E484Q | 3229 | 12 | 0.0057 | 442 | 30 | 23.08 | 130
L452Q | 2858 | 13 | 0.9802 | 3 | 27 | 20.77 | 144
A520S | 2727 | 14 | 0.1495 | 199 | 3 | 2.31 | 497
N501T | 2054 | 15 | 0.4514 | 48 | 17 | 13.08 | 202
R357K | 1973 | 16 | 0.1393 | 208 | 5 | 3.85 | 388
A522S | 1959 | 17 | 0.1283 | 221 | 2 | 1.54 | 543
R346K | 1686 | 18 | 0.1234 | 229 | 6 | 4.62 | 380
V367F | 1395 | 19 | 0.1764 | 161 | 0 | 0.0 | 637
N440S | 1361 | 20 | 0.1499 | 197 | 2 | 1.54 | 542
P384L | 1155 | 21 | 0.2681 | 105 | 18 | 13.85 | 199
Y449S | 1146 | 22 | -0.8112 | 632 | 85 | 65.38 | 16
D427N | 1106 | 23 | -0.1133 | 558 | 1 | 0.77 | 589
R346S | 1037 | 24 | 0.0374 | 386 | 20 | 15.38 | 182
A475V | 891 | 25 | 0.3069 | 94 | 10 | 7.69 | 289

First, the 10 most observed or fast-growing RBD mutations are N501Y, L452R,
T478K, E484K, K417T, S477N, N439K, K417N, F490S, and S494P, as shown in Table
1. Inclusively, these top mutations strengthen their BFEs and become more
infectious, following the natural selection mechanism [19]. Figure 1b shows
that the frequencies of the top three mutations increased dramatically since
2021 due to Alpha, Beta, Gamma, Delta, and other variants. Second, among the
top 25 most observed RBD mutations, T478K, L452Q N440K, L452R, N501Y, N501T,
F490S, A475V, and P384L are the 8 most infectious ones judged by their ability
to strengthen the binding with ACE2, as shown in Figure 1c . The BFE changes
of S protein and ACE2 for mutation T478K is nearly 1.00 kcal/mol, which
strongly enhances the binding of the RBD–ACE2 complex [33]. Together with
L452R (BFE change: 0.58kcal/mol), T478K makes Delta the most infectious
variant in VOCs. Third, among the top 25 most observed RBD mutations, Y449S,
S494P, K417N, F490S, L452R, E484K, K417T, E484Q, L452Q, and N501Y are the 10
most antibody disruptive ones, judged by their interactions with 130
antibodies shown in Figure 1c. It can be seen that mutations L452R, E484K,
K417T, K417N, F490S, and S494P disrupt more than 30% of antibody-RBD
complexes, while mutations E484K and K417T may disrupt nearly 30% antibody-RBD
complexes, indicating their disruptive ability to the efficacy and reliability
of antibody therapies and vaccines. The most dangerous mutations are the ones
that are both infectivity-strengthening and antibody disruptive. Four RBD
mutations, N501Y, L452R, F490S, and L452Q, appear in both lists and are key
mutations in WHO’s VOC and VOI lists. Among them, F490S and L452Q are the key
RBD mutations in Lambda, making Lambda a more dangerous emerging variant than
Delta. Note that high-frequency mutation S477N does not significantly weaken
any antibody and RBD binding, and thus does not appear in any prevailing
variants.

###  2.2 Vaccine-breakthrough S protein RBD co-mutations

Figure 2: Properties of RBD co-mutations. a Illustration of RBD 2 co-mutations
with a frequency greater than 90. b Illustration of RBD 3 co-mutations with a
frequency greater than 30. c Illustration of RBD 2 co-mutations with a
frequency greater than 20. Here, the $x$-axis lists RBD co-mutations and the
$y$-axis represents the predicted total BFE change of each set of RBD co-
mutations. The number on the top of each bar is the AI-predicted number of
antibody and RBD complexes that may be significantly disrupted by the set of
RBD co-mutations, and the color of each bar represents the natural log of
frequency for each set of RBD co-mutations. (Please check the interactive HTML
files in the Supporting Information S2.2.4 for a better view of these plots.)

The recent surge in COVID-19 infections is due to the occurrence of RBD co-
mutations that combine two or more infectivity-strengthening mutations. The
most dangerous future SARS-CoV-2 variants must be RBD co-mutations that
combine infectivity-strengthening mutation(s) with antibody disruptive
mutation(s). A list of 1,139,244 RBD co-mutations that are decoded from
1,489,884 complete SARS-CoV-2 genome sequences can be found in Section S2.1.3
of the Supporting Information, and all of the non-degenerate RBD co-mutations
with their frequencies, antibody disruption counts, total BFE changes, and the
first detection dates and countries can be found in Section S2.1.4 of the
Supporting Information. Figure 2 illustrates the properties of S protein RBD
2, 3, and 4 co-mutations. The height of each bar shows the predicted total BFE
change of each set of co-mutations on RBD, the color represents the natural
log of frequency for each set of RBD co-mutations, and the number at the top
of each bar is the AI-predicted number of antibody-RBD complexes that each set
of RBD co-mutations may disrupt based on a total of 130 RBD and antibody
complexes. Notably, for a specific set of co-mutations, the higher the number
at the top of the bar is, the stronger ability to break through vaccines will
be. From Figure 2, RBD 2 co-mutation set [L452R, T478K] (Delta variant) has
the highest frequency (219,362) and the highest BFE change (1.575 kcal/mol).
Moreover, the Delta variant would disrupt 40 antibody-RBD complexes,
suggesting that Delta would not only enhance the infectivity but also be a
vaccine breakthrough variant. Moreover, [L452Q, F490S] (Lambda) is another co-
mutation with high frequency, high BFE changes (1.421 kcal/mol), and high
antibody disruption count (59). In addition, Lambda is considered to be more
dangerous than Delta due to its higher antibody disruption count. Further,
[R346K, E484K, N501Y] (Mu variant) has a BFE change of 0.768 kcal/mol and high
antibody disruption count (60). It is not as infectious as Delta and Lambda,
but has a similar ability as Lambda in escaping vaccines. Note that among all
VOCs and VOIs, Beta has the highest ability to break through vaccines, but its
infectivity is relatively low (BFE change: 0.656 kcal/mol). Furthermore, high-
frequency 2 co-mutation sets [E484K, N501Y], [F490S, N501Y], and [S494P,
N501Y] are all considered to be the emerging variants that have the potential
to escape vaccines. From Figure 2, three 3 co-mutation sets [R345K, E484K,
N501Y] (Mu), [K417T, E484K, N501Y] (Gamma), and [K417N, E484K, N501Y] (Beta)
draw our attention. They are all the prevailing three co-mutations with
moderate BFE changes but very high antibody disruption count (more than 60).
With a BFE change of 1.4 kcal/mol and antibody disruption count of 82, co-
mutation set [K417N, L452R, T478K] (Delta plus) appears to be more dangerous
than all of the current VOCs and VOIs. For 4 co-mutations in Figure 2 c,
[P384L, K417N, E484K, N501Y] (Beta plus) could penetrate all vaccines due to
its highest antibody disruption count of 101. We would like to address that
all of the co-mutations sets, except for [Y449S, N501Y] in Figure 2 have
positive BFE changes, following the natural selection. We anticipate that
although co-mutation sets [V401L, L452R, T478K], [L452R, T478K, N501Y],
[A411S, L452R, T478K], and [L452R, T478K, E484K, N501Y] have relatively low
frequencies at this point, they may become dangerous variants soon due to
their large BFE changes and antibody disruption counts.

Figure 3: a 2D histograms of antibody disruption count and total BFE changes
for RBD 2 co-mutations. b 2D histograms of antibody disruption count and total
BFE changes for RBD 3 co-mutations. c 2D histograms of antibody disruption
count and total BFE changes for RBD 4 co-mutations. d The histograms of total
BFE changes for RBD co-mutations. e The histograms of the natural log of
frequency for RBD co-mutations. f The histograms of antibody disruption count
for RBD co-mutations. In figures a, b, and c, the color bar represents the
number of co-mutations that fall into the restriction of $x$-axis and
$y$-axis. The reader is referred to the web version of these plots in the
Supporting Information S2.2.2 and S2.2.3.

It is important to understand the general trend of SARS-CoV-2 evolution. To
this end, we carry out the statistical analysis of RBD co-mutations. Among
1,489,884 SARS-CoV-2 genome isolates, a total of 1,113 distinctive 2 co-
mutations, 612 distinctive 3 co-mutations, and 217 distinctive 4 co-mutations
are found. Figures 3 a, b, and c illustrate the 2D histograms of 2, 3, and 4
co-mutations, respectively. The $x$-axis is the number of antibody disruption
counts, and the $y$-axis shows the total BFE change. Figure 3 a shows that
there are 82 RBD 2 co-mutations that have BFE changes in the range of [0.600,
0.799] kcal/mol and will disruptive 40 to 49 antibodies. According to Figure 3
b, there are 170 unique 3 co-mutations that have large BFE changes of S
protein and ACE2 in the range of [1.500, 1.999] kcal/mol. In Figure 3 c, it is
seen that almost all of the 4 co-mutations on RBD have the BFE changes greater
than 0.5 kcal/mol and weaken the binding of S protein with at least 60
antibodies. Figures 3d, e, and f are the histograms of total BFE changes,
natural log of frequencies, and antibody disruption counts for RBD 2, 3, and 4
co-mutations. It can be found that most of the 2, 3, and 4 RBD co-mutations
have positive total BFE changes, and the larger number of RBD co-mutations is,
the higher number of antibody disruption count will be. In summary, co-
mutations with a larger number of antibody disruptive counts and high BFE
changes will grow faster. We anticipate that when most of the population is
vaccinated, vaccine-resistant mutations will become a more viable mechanism
for viral evolution.

###  2.3 Emerging breakthrough variants in COVID-19 devastated countries

Figure 4:  Illustration of the time evolution of 2, 3, and 4 co-mutations on
the S protein RBD of SARS-CoV-2 from January 01, 2021, to July 31, 2021, in 12
COVID-19 devastated countries: the United Kingdom (UK), the United States
(US), Denmark (DK), Brazil (BR), Germany (DE), Netherlands (NL), Sweden (SE),
Italy (IT), Canada (CA), France (FR), India (IN), and Belgium (BE). The
$y$-axis represents the natural log frequency of each RBD co-mutation. The top
5 high-frequency co-mutations in each country are marked by red, blue, green,
yellow, and pink lines. The cyan line is for the RBD co-mutation [L452Q,
F490S] on the Lambda variant, and the other co-mutations are marked by light
grey lines. Notably, there are two blues lines in the panel of FR due to the
same frequency of [K417N, E484K, N501Y] and [E484K, N501Y]. (Please check the
interactive HTML files in the Supporting Information S2.2.1 for a better view
of these plots.)

Our analysis of RBD mutations reveals the recent global surge of infections
due to RBD co-mutations. However, due to the difference in the rate of
vaccination, COVID-19 control and prevention measures, medical infrastructure,
population structures, etc., each country may have a different pattern of RBD
co-mutations and follow a different trajectory of SARS-CoV-2 transmission and
evolution. Therefore, we analyze the RBD 2, 3, and 4 co-mutations in 20
countries that have the high frequency of SARS-CoV-2 genome isolates,
including the United Kingdom (UK), the United States (US), Denmark (DK),
Brazil (BR), Germany (DE), Netherlands (NL), Sweden (SE), Italy (IT), Canada
(CA), France (FR), India (IN), and Belgium (BE), as well as Ireland (IE),
Spain (ES), Chile (CL), Portugal (PT), Mexico (MX), Singapore (SG), Turkey
(TR), and Finland (FL). Figure 4 shows the time evolution of 2, 3, and 4 co-
mutations on the S protein RBD of SARS-CoV-2 from January 01, 2021, to July
31, 2021, in 12 COVID-19 devastated countries. The plots of the other 8
countries can be found in the Supporting Information S3. The top 5 high-
frequency co-mutations in each country are marked by red, blue, green, yellow,
and pink lines. The cyan line is for the RBD co-mutation set [L452Q, F490S] on
the Lambda variant, which is more penetrative to vaccines than the Delta.
Light grey lines mark the other co-mutations. The RBD co-mutation set [L452R,
T478K] (Delta) with 1.575 kcal/mol BFE change was first found in IN in early
January 2021, and the number of this variant increases rapidly around the
world in a short period. Later on, in early March 2021, the UK, US, DK, DE,
NL, SE, IT, FR, BE reported the appearance of [L452R, T478K] in early March
2021, and eventually [L452R, T478K] became a dominated co-mutation, which is
consistent to the finding that Delta variant remains largely susceptible to
infection. The co-mutation set [K417T, E484K, N501Y] (Gamma) with BFE change
of 0.656 kcal/mol was first found in Brazil in early January 2021, and then it
became the most dominated co-mutation in Brazil and Canada, and the second
dominated co-mutation in the US, NL, SE, IT, FR, IN, and BE. Notably, co-
mutaion set [G446V, L452R, T478K] in the UK with BFE change of 1.733 kcal/mol
and 46 antibody disruption counts appears to be a dangerous set of co-
mutations that may affect the infectivity and vaccine/antibodies efficacy
shortly. Moreover, co-mutation set [N501Y, A520S] has quickly increased IN and
BE since April 16, 2021. Considering the BFE change and antibody disruptive
count of co-mutation set [N501Y, A520S] is 0.699 and 27, we suggest monitoring
this variant in IN and BE. Furthermore, the co-mutation set [K417N, T470N,
E484K, N501T] that was first found in BR on April 06, 2020, has a BFE change
of 0.625 kcal/mol and antibody disruption count 84, is an emerging vaccine
breakthrough co-mutation in Brazil. In addition, co-mutation set [L452Q,
F490S] (cyan lines) on Lambda variant was recently drawing much attention due
to its potential ability to resist vaccines and enhance the infectivity, which
is consistent with our predictions that co-mutation set [L452Q, F490S] has a
relatively significant BFE change of S protein and ACE2 (1.421kcal/mol) and
would reduce the RBD binding with 59 antibodies. Lambda has already spread out
in every country in Figure 4.

##  3 Methodology and validation

In this section, the work flow of deep learning-based BFE change predictions
of protein-protein interactions induced by mutations for the present SARS-
CoV-2 variant analysis and prediction will be firstly introduced, which
includes four steps as shown in Figure 5: (1) Data pre-processing; (2)
training data preparation; (3) feature generations of protein-protein
interaction complexes; (4) prediction of protein-protein interactions by deep
neural networks (check Section S5 in Supporting information). Next, the
validation of our machine learning-based model will be demonstrated,
suggesting consistent and reliable results compared to the experimental deep
mutations data.

Figure 5: a Illustration of genome sequence data pre-processing and BFE change
predictions. b Comparison of experimental CT-P59 IC50 fold change (reduction)
and predicted BFE changes induced by mutations L452R and T478K. c Comparison
of predicted BFE changes and relative luciferase units [25] for pseudovirus
infection changes of ACE2 and S protein complex induced by mutations L452R and
N501Y.

###  3.1 Data pre-processing and SNP genotyping

The first step is to pre-process the original SARS-CoV-2 sequences data. In
this step, a total of 1,489,884 complete SARS-CoV-2 genome sequences with high
coverage and exact collection date are downloaded from the GISAID database
[34] (https://www.gisaid.org/) as of August 05, 2021. Complete SARS-CoV-2
genome sequences are available from the GISAID database [34]. Next, the
1,489,884 complete SARS-CoV-2 genome sequences were rearranged according to
the reference genome downloaded from the GenBank (NC_045512.2)[35], and
multiple sequence alignment (MSA) is applied by using Cluster Omega with
default parameters. Then, single nucleotide polymorphism (SNP) genotyping is
applied to measure the genetic variations between different isolates of SARS-
CoV-2 by analyzing the rearranged sequences [36, 37], which is be of paramount
importance for tracking the genotype changes during the pandemic. The SNP
genotyping captures all of the differences between patients’ sequences and the
reference genome, which decodes a total of 28,478 unique single mutations from
1,489,884 complete SARS-CoV-2 genome sequences. Among them, 4,653 non-
degenerate mutations on S protein and 683 non-degenerate mutations on the S
protein RBD (S protein residues from 329 to 530) are detected. In this work,
the co-mutation analysis is more crucial than the unique single mutation
analysis. Therefore, for each SARS-CoV-2 isolate, we extract the all of the
mutations on S protein RBD, which is called a RBD co-mutation for a specific
isolates. By doing this, a total of 1,139,244 RBD co-mutations are captured.
Notably, the SARS-CoV-2 unique single mutations in the world is available at
Mutation Tracker. The analysis of RBD mutations is available at Mutation
Analyzer.

###  3.2 Methods for BFE change predictions

In this section, the process of the machine learning-based BFE change
predictions is introduced. Once the data pre-processing and SNP genotyping is
carried out, we will firstly proceed with the training data preparation
process, which plays a key role in reliability and accuracy. A library of 130
antibodies and RBD complexes as well as an ACE2-RBD complex are obtained from
Protein Data Bank (PDB). RBD mutation-induced BFE changes of these complexes
are evaluated by the following machine learning model. According to the
emergency and the rapid change of RNA virus, it is rare to have massive
experimental BFE change data of SARS-CoV-2, while, on the other hand, next-
generation sequencing data is relatively easy to collect. In the training
process, the dataset of BFE changes induced by mutations of the SKEMPI 2.0
dataset [38] is used as the basic training set, while next-generation
sequencing datasets are added as assistant training sets. The SKEMPI 2.0
contains 7,085 single- and multi-point mutations and 4,169 elements of that in
319 different protein complexes used for the machine learning model training.
The mutational scanning data consists of experimental data of the binding of
ACE2 and RBD induced mutations on ACE2[39] and RBD[40, 41], and the binding of
CTC-445.2 and RBD with mutations on both protein[41].

Next, the feature generations of protein-protein interaction complexes is
performed. The element-specific algebraic topological analysis on complex
structures is implemented to generate topological bar codes [30, 42, 43, 44].
In addition, biochemistry and biophysics features such as Coulomb
interactions, surface areas, electrostatics, et al., are combined with
topological features [20]. The detailed information about the topology-based
models will be demonstrated in subsection 3.3. Lastly, deep neural networks
for SARS-CoV-2 are constructed for the BFE change prediction of protein-
protein interactions [30]. The detailed descriptions of dataset and machine
learning model are found in the literature [19, 45, 30] and are available at
TopNetmAb.

###  3.3 Feature generation for machine learning model

Among all features generated for machine learning prediction, the application
of topology theory makes the model to a whole new level. Those summarized as
other inputs are called as auxiliary features and are described in Section S4
of the Supporting Information. In this section, a brief introduction about the
theory of topology will be discussed. Algebraic topology [42, 43] has achieved
tremendous success in many fields including biochemical and biophysical
properties[44]. Special treatment should be implemented for biology
applications to describe element types and amino acids in poly-peptide
mathematically, which element-specific and site-specific persistent homology
[32, 19]. To construct the algebraic topological features on protein-protein
interaction model, a series of element subsets for complex structures should
be defined, which considers atoms from the mutation sites, atoms in the
neighborhood of the mutation site within a certain distance, atoms from
antibody binding site, atoms from antigen binding site, and atoms in the
system that belong to type of {C, N, O}, $\mathcal{A}_{\text{ele}}(\text{E})$.
Under the element/site-specific construction, simplicial complexes is
constructed on point clouds formed by atoms. For example, a set of independent
$k\\!+\\!1$ points is from one element/site-specific set
$U=\\{u_{0},u_{1},...,u_{k}\\}$. The $k$-simplex $\sigma$ is a convex hull of
$k\\!+\\!1$ independent points $U$, which is a convex combination of
independent points. For example, a $0$-simplex is a point and a $1$-simplex is
an edge. Thus, a $m$-face of the $k$-simplex with $m\\!+\\!1$ vertices forms a
convex hull in a lower dimension $m<k$ and is a subset of the $k\\!+\\!1$
vertices of a $k$-simplex, so that a sum of all its $(k\\!-\\!1)$–faces is the
boundary of a $k$–simplex $\sigma$ as

$\partial_{k}\sigma=\sum_{i=1}^{k}(-1)^{i}\langle
u_{0},...,\hat{u}_{i},...,u_{k}\rangle,$ (1)

where $\langle u_{0},...,\hat{u}_{i},...,u_{k}\rangle$ consists of all
vertices of $\sigma$ excluding $u_{i}$. The collection of finitely many
simplices is a simplicial complex. In the model, the Vietoris-Rips (VR)
complex (if and only if
$\mathbb{B}(u_{i_{j}},r)\cap\mathbb{B}(u_{i_{j^{\prime}}},r)\neq\emptyset$ for
${j},{j^{\prime}}\in[0,k]$) is for dimension 0 topology, and alpha complex (if
and only if $\cap_{u_{i_{j}}\in\sigma}\mathbb{B}(u_{i_{j}},r)\neq\emptyset$)
is for point cloud of dimensions 1 and 2 topology [44].

The $k$-chain $c_{k}$ of a simplicial complex $K$ is a formal sum of the
$k$-simplices in $K$, which is $c_{k}=\sum\alpha_{i}\sigma_{i}$, where
$\alpha_{i}$ is coefficients and is chosen to be $\mathbb{Z}_{2}$. Thus, the
boundary operator on a $k$-chain $c_{k}$ is

$\partial_{k}c_{k}=\sum\alpha_{i}\partial_{k}\sigma_{i},$ (2)

such that $\partial_{k}:C_{k}\rightarrow C_{k-1}$ and follows from that
boundaries are boundaryless $\partial_{k-1}\partial_{k}=\emptyset$. A chain
complex is

$\cdots\stackrel{{\scriptstyle\partial_{i+1}}}{{\longrightarrow}}C_{i}(K)\stackrel{{\scriptstyle\partial_{i}}}{{\longrightarrow}}C_{i-1}(K)\stackrel{{\scriptstyle\partial_{i-1}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle\partial_{2}}}{{\longrightarrow}}C_{1}(K)\stackrel{{\scriptstyle\partial_{1}}}{{\longrightarrow}}C_{0}(K)\stackrel{{\scriptstyle\partial_{0}}}{{\longrightarrow}}0,$
(3)

as a sequence of complexes by boundary maps. Therefore, the Betti numbers are
given as the ranks of $k$th homology group $H_{k}$ as
$\beta_{k}=\text{rank}(H_{k})$, where $H_{k}=Z_{k}/B_{k}$, $k$-cycle group
$Z_{k}$ and the $k$-boundary group $B_{k}$. The Betti numbers are the key for
topological features, where $\beta_{0}$ gives the number of connected
components, such as number of atoms, $\beta_{1}$ is the number of cycles in
the complex structure, and $\beta_{2}$ illustrates the number of cavities.
This presents abstract properties of the 3D structure.

Finally, only one simplicial complex couldn’t give the whole picture of the
protein-protein interaction structure. A filtration of a topology space is
needed to extract more properties. A filtration is a nested sequence such that

$\emptyset=K_{0}\subseteq K_{1}\subseteq\cdots\subseteq K_{m}=K.$ (4)

Each element of the sequence could generate the Betti numbers
$\\{\beta_{0},\beta_{1},\beta_{2}\\}$ and consequentially, a series of Betti
numbers in three dimensions is constructed and applied to be the topological
fingerprints in Figure 5a.

###  3.4 Validation

The validation of our machine learning predictions for mutation-induced BFE
changes compared to experimental data has been demonstrated in recently
published papers [20, 30]. Firstly, we showed high correlations of
experimental deep mutational enrichment data and predictions for the binding
complex of SARS-CoV-2 S protein RBD and protein CTC-445.2 [20] and the binding
complex of SARS-CoV-2 RBD and ACE2 [30]. In comparison with experimental data
on antibody therapies in clinical trials of emerging mutations, our
predictions achieve a Pearson correlation at 0.80 [30]. Considering the BFE
changes induced by RBD mutations for ACE2 and RBD complex, predictions on
mutations L452R and N501Y have a highly similar trend with experimental data
[30]. Meanwhile, as we presented in [18], high-frequency mutations are all
having positive BFE changes. Moreover, for multi-mutation tests, our BFE
change predictions have the same pattern with experimental data of the impact
of SARS-CoV-2 variants on major antibody therapeutic candidates, where the BFE
changes are accumulative for co-mutations [30].

Recent studies on potency of mAb CT-P59 in vitro and in vivo against Delta
variants[46] show that the neutralization of CT-P59 is reduced by L452R (13.22
ng/mL) and is retained against T478K (0.213 ng/mL). In our predictions [30],
L452R induces a negative BFE change (-2.39 kcal/mol), and T478K produces a
positive BFE change (0.36 kcal/mol). In Figure 5b, the fold changes for
experimental and predicted values are presented. Additional, in Figure 5c, a
comparison of the experimental pseudovirus infection changes and predicted BFE
change of ACE2 and S protein complex induced by mutations L452R and N501Y,
where the experimental data is obtained in a reference to D614G and reported
in relative luciferase units [25]. It indicates that the binding of RBD and
ACE2 dominates the infectivity of SARS-CoV-2. More details can be found in
Section S6 of Supporting information.

## Data and model availability

The SARS-CoV-2 SNP data in the world is available at Mutation Tracker. The
most observed SARS-CoV-2 RBD mutations are available at Mutaton Analyzer. The
information of 130 antibodies with their corresponding PDB IDs can be found in
the Supplementary Data. The SARS-CoV-2 S protein RBD SNP and non-degenerate
co-mutations data can be found in Section S2.1.4 of the Supporting
Information. The TopNetTree model is available at TopNetmAb.

## Supporting information

The supporting information is available for

  1. S1

Overview of SARS-CoV-2 prevailing and emerging variants

  2. S2

Supplementary data: The Supplementary_Data.zip contains two folders: S2.1:
Excel folder: A total of 4 files are in this folder: S2.1.1:
antibodies_disruptmutation.csv shows the name of antibodies disrupted by
mutations. S2.1.2: antibodies.csv lists the PDB IDs for all of the 130 SARS-
CoV-2 antibodies. S2.1.3: RBD_comutation_residue_08052021.csv lists all of the
SNPs of RBD co-mutations up to August 05, 2021. S2.1.4:
Track_Comutation_08052021.xlsx preserves all of the non-degenerate RBD co-
mutations with their frequencies, antibody disruption counts, total BFE
changes, and the first detection dates and countries. S2.2:  HTML folder: A
total of 29 HTML files containing: S2.2.1: 20 HTML files for the for the time
evolution of 2, 3, and 4 co-mutations on the S protein RBD of SARS-CoV-2 from
January 01, 2021 to July 31, 2021, in 12 COVID-19 devastated countries.
S2.2.2: Three 2D histograms are given for antibody disruption counts and total
BFE changes for RBD 2 co-mutations, 3 co-mutations, and 4 co-mutations.
S2.2.4: Three histograms of total BFE changes, antibody disruption count, and
natural log of frequencies for RBD 2 co-mutations, 3 co-mutations, and 4 co-
mutations. S2.2.4: Three barplots for RBD 2, 3, 4 co-mutations with a
frequency greater than 90, 30, and 20, respectively.

  3. S3

Supplementary figures: the line plot of the time evolution of 2, 3, and 4 co-
mutations on the S protein RBD of SARS-CoV-2 from January 01, 2021, to July
31, 2021, in 8 COVID-19 devastated countries.

  4. S4

Supplementary feature generation: detailed description of feature generations.

  5. S5

Supplementary machine learning methods: detailed description of machine
learning method implemented in this work

  6. S6

Supplementary validation: validations of our machine learning predictions with
experimental data.

## Acknowledgment

This work was supported in part by NIH grant GM126189, NSF grants DMS-2052983,
DMS-1761320, and IIS-1900473, NASA grant 80NSSC21M0023, Michigan Economic
Development Corporation, MSU Foundation, Bristol-Myers Squibb 65109, and
Pfizer. GWW thanks the discussion with Dr. Peter Lyster which inspired this
work.

## References

  * [1] Markus Hoffmann, Hannah Kleine-Weber, Simon Schroeder, Nadine Krüger, Tanja Herrler, Sandra Erichsen, Tobias S Schiergens, Georg Herrler, Nai-Huei Wu, Andreas Nitsche, et al.  SARS-CoV-2 cell entry depends on ACE2 and TMPRSS2 and is blocked by a clinically proven protease inhibitor.  Cell, 181(2):271–280, 2020.
  * [2] Jiahui Chen, Kaifu Gao, Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei.  Review of COVID-19 antibody therapies.  Annual Review of Biophysics, 50:1–30, 2020.
  * [3] Peter Chen, Ajay Nirula, Barry Heller, Robert L Gottlieb, Joseph Boscia, Jason Morris, Gregory Huhn, Jose Cardona, Bharat Mocherla, Valentina Stosor, et al.  SARS-CoV-2 neutralizing antibody LY-CoV555 in outpatients with COVID-19.  New England Journal of Medicine, 384(3):229–237, 2021.
  * [4] Wendong Li, Zhengli Shi, Meng Yu, Wuze Ren, Craig Smith, Jonathan H Epstein, Hanzhong Wang, Gary Crameri, Zhihong Hu, Huajun Zhang, et al.  Bats are natural reservoirs of SARS-like coronaviruses.  Science, 310(5748):676–679, 2005.
  * [5] Xiu-Xia Qu, Pei Hao, Xi-Jun Song, Si-Ming Jiang, Yan-Xia Liu, Pei-Gang Wang, Xi Rao, Huai-Dong Song, Sheng-Yue Wang, Yu Zuo, et al.  Identification of two critical amino acid residues of the severe acute respiratory syndrome coronavirus spike protein for its variation in zoonotic tropism transition via a double substitution strategy.  Journal of Biological Chemistry, 280(33):29588–29595, 2005.
  * [6] Huai-Dong Song, Chang-Chun Tu, Guo-Wei Zhang, Sheng-Yue Wang, Kui Zheng, Lian-Cheng Lei, Qiu-Xia Chen, Yu-Wei Gao, Hui-Qiong Zhou, Hua Xiang, et al.  Cross-host evolution of severe acute respiratory syndrome coronavirus in palm civet and human.  Proceedings of the National Academy of Sciences, 102(7):2430–2435, 2005.
  * [7] Alexandra C Walls, Young-Jun Park, M Alejandra Tortorici, Abigail Wall, Andrew T McGuire, and David Veesler.  Structure, function, and antigenicity of the SARS-CoV-2 spike glycoprotein.  Cell, 2020.
  * [8] Chunyan Wang, Wentao Li, Dubravka Drabek, Nisreen MA Okba, Rien van Haperen, Albert DME Osterhaus, Frank JM van Kuppeveld, Bart L Haagmans, Frank Grosveld, and Berend-Jan Bosch.  A human monoclonal antibody blocking SARS-CoV-2 infection.  Nature communications, 11(1):1–6, 2020.
  * [9] Fei Yu, Rong Xiang, Xiaoqian Deng, Lili Wang, Zhengsen Yu, Shijun Tian, Ruiying Liang, Yanbai Li, Tianlei Ying, and Shibo Jiang.  Receptor-binding domain-specific human neutralizing monoclonal antibodies against SARS-CoV and SARS-CoV-2.  Signal Transduction and Targeted Therapy, 5(1):1–12, 2020.
  * [10] Cheng Li, Xiaolong Tian, Xiaodong Jia, Jinkai Wan, Lu Lu, Shibo Jiang, Fei Lan, Yinying Lu, Yanling Wu, and Tianlei Ying.  The impact of receptor-binding domain natural mutations on antibody recognition of SARS-CoV-2.  Signal Transduction and Targeted Therapy, 6(1):1–3, 2021.
  * [11] Rafael Sanjuán and Pilar Domingo-Calap.  Mechanisms of viral mutation.  Cellular and Molecular Life Sciences, 73(23):4433–4448, 2016.
  * [12] Nathan D Grubaugh, William P Hanage, and Angela L Rasmussen.  Making sense of mutation: what D614G means for the COVID-19 pandemic remains unclear.  Cell, 182(4):794–795, 2020.
  * [13] Tugba G Kucukkal, Marharyta Petukh, Lin Li, and Emil Alexov.  Structural and physico-chemical effects of disease and non-disease nsSNPs on proteins.  Current Opinion in Structural Biology, 32:18–24, 2015.
  * [14] Peng Yue, Zhaolong Li, and John Moult.  Loss of protein structure stability as a major causative factor in monogenic disease.  Journal of molecular biology, 353(2):459–473, 2005.
  * [15] Rui Wang, Yuta Hozumi, Yong-Hui Zheng, Changchuan Yin, and Guo-Wei Wei.  Host immune response driving SARS-CoV-2 evolution.  Viruses, 12(10):1095, 2020.
  * [16] Marion Sevajol, Lorenzo Subissi, Etienne Decroly, Bruno Canard, and Isabelle Imbert.  Insights into RNA synthesis, capping, and proofreading mechanisms of SARS-coronavirus.  Virus Research, 194:90–99, 2014.
  * [17] François Ferron, Lorenzo Subissi, Ana Theresa Silveira De Morais, Nhung Thi Tuyet Le, Marion Sevajol, Laure Gluais, Etienne Decroly, Clemens Vonrhein, Gérard Bricogne, Bruno Canard, et al.  Structural and molecular basis of mismatch correction and ribavirin excision from coronavirus RNA.  Proceedings of the National Academy of Sciences, 115(2):E162–E171, 2018.
  * [18] Rui Wang, Jiahui Chen, Kaifu Gao, and Guo-Wei Wei.  Vaccine-escape and fast-growing mutations in the United Kingdom, the United States, Singapore, Spain, India, and other COVID-19-devastated countries.  Genomics, 113(4):2158–2170, 2021.
  * [19] Jiahui Chen, Rui Wang, Menglun Wang, and Guo-Wei Wei.  Mutations strengthened SARS-CoV-2 infectivity.  Journal of molecular biology, 432(19):5212–5226, 2020.
  * [20] Jiahui Chen, Kaifu Gao, Rui Wang, and Guo-Wei Wei.  Prediction and mitigation of mutation threats to COVID-19 vaccines and antibody therapies.  Chemical Science, 12(20):6929–6948, 2021.
  * [21] Nicholas G Davies, Sam Abbott, Rosanna C Barnard, Christopher I Jarvis, Adam J Kucharski, James D Munday, Carl AB Pearson, Timothy W Russell, Damien C Tully, Alex D Washburne, et al.  Estimated transmissibility and impact of SARS-CoV-2 lineage B. 1.1. 7 in England.  Science, 372(6538), 2021.
  * [22] Pengfei Wang, Ryan G Casner, Manoj S Nair, Maple Wang, Jian Yu, Gabriele Cerutti, Lihong Liu, Peter D Kwong, Yaoxing Huang, Lawrence Shapiro, et al.  Increased resistance of SARS-CoV-2 variant P. 1 to antibody neutralization.  Cell host & microbe, 29(5):747–751, 2021.
  * [23] Katherine RW Emary, Tanya Golubchik, Parvinder K Aley, Cristina V Ariani, Brian Angus, Sagida Bibi, Beth Blane, David Bonsall, Paola Cicconi, Sue Charlton, et al.  Efficacy of ChAdOx1 nCoV-19 (AZD1222) vaccine against SARS-CoV-2 variant of concern 202012/01 (B. 1.1. 7): an exploratory analysis of a randomised controlled trial.  The Lancet, 397(10282):1351–1362, 2021.
  * [24] Shabir A Madhi, Vicky Baillie, Clare L Cutland, Merryn Voysey, Anthonet L Koen, Lee Fairlie, Sherman D Padayachee, Keertan Dheda, Shaun L Barnabas, Qasim E Bhorat, et al.  Efficacy of the ChAdOx1 nCoV-19 COVID-19 vaccine against the B. 1.351 variant.  New England Journal of Medicine, 384(20):1885–1898, 2021.
  * [25] Xianding Deng, Miguel A Garcia-Knight, Mir M Khalid, Venice Servellita, Candace Wang, Mary Kate Morris, Alicia Sotomayor-González, Dustin R Glasner, Kevin R Reyes, Amelia S Gliwa, et al.  Transmission, infectivity, and antibody neutralization of an emerging SARS-CoV-2 variant in California carrying a L452R spike protein mutation.  MedRxiv, 2021.
  * [26] Sonia Jangra, Chengjin Ye, Raveen Rathnasinghe, Daniel Stadlbauer, Hala Alshammary, Angela A Amoako, Mahmoud H Awawda, Katherine F Beach, Maria C Bermúdez-González, Rachel L Chernet, et al.  SARS-CoV-2 spike E484K mutation reduces antibody neutralisation.  The Lancet Microbe, 2021.
  * [27] Medini K Annavajhala, Hiroshi Mohri, Jason E Zucker, Zizhang Sheng, Pengfei Wang, Angela Gomez-Simmonds, David D Ho, and Anne-Catrin Uhlemann.  A novel SARS-CoV-2 variant of concern, B. 1.526, identified in New York.  medRxiv, 2021.
  * [28] Allison J Greaney, Andrea N Loes, Katharine HD Crawford, Tyler N Starr, Keara D Malone, Helen Y Chu, and Jesse D Bloom.  Comprehensive mapping of mutations in the SARS-CoV-2 receptor-binding domain that affect recognition by polyclonal human plasma antibodies.  Cell host & microbe, 29(3):463–476, 2021.
  * [29] Izumi Kimura, Yusuke Kosugi, Jiaqi Wu, Daichi Yamasoba, Erika P Butlertanaka, Yuri L Tanaka, Yafei Liu, Kotaro Shirakawa, Yasuhiro Kazuma, Ryosuke Nomura, et al.  SARS-CoV-2 Lambda variant exhibits higher infectivity and immune resistance.  bioRxiv, 2021.
  * [30] Jiahui Chen, Kaifu Gao, Rui Wang, and Guo-Wei Wei.  Revealing the threat of emerging SARS-CoV-2 mutations to antibody therapies.  Journal of Molecular Biology, 433(7744), 2021.
  * [31] Duc Duy Nguyen, Zixuan Cang, Kedi Wu, Menglun Wang, Yin Cao, and Guo-Wei Wei.  Mathematical deep learning for pose and binding affinity prediction and ranking in D3R Grand Challenges.  Journal of Computer-aided Molecular Design, 33(1):71–82, 2019.
  * [32] Menglun Wang, Zixuan Cang, and Guo-Wei Wei.  A topology-based network tree for the prediction of protein–protein binding affinity changes following mutation.  Nature Machine Intelligence, 2(2):116–123, 2020.
  * [33] Sarah Cherian, Varsha Potdar, Santosh Jadhav, Pragya Yadav, Nivedita Gupta, Mousumi Das, Partha Rakshit, Sujeet Singh, Priya Abraham, Samiran Panda, et al.  SARS-CoV-2 Spike Mutations, L452R, T478K, E484Q and P681R, in the Second Wave of COVID-19 in Maharashtra, India.  Microorganisms, 9(7):1542, 2021.
  * [34] Yuelong Shu and John McCauley.  GISAID: Global initiative on sharing all influenza data–from vision to reality.  Eurosurveillance, 22(13):30494, 2017.
  * [35] Fan Wu, Su Zhao, Bin Yu, Yan-Mei Chen, Wen Wang, Zhi-Gang Song, Yi Hu, Zhao-Wu Tao, Jun-Hua Tian, Yuan-Yuan Pei, et al.  A new coronavirus associated with human respiratory disease in China.  Nature, 579(7798):265–269, 2020.
  * [36] Changchuan Yin.  Genotyping coronavirus SARS-CoV-2: methods and implications.  Genomics, 112(5):3588–3596, 2020.
  * [37] Sobin Kim and Ashish Misra.  Snp genotyping: technologies and biomedical applications.  Annu. Rev. Biomed. Eng., 9:289–320, 2007.
  * [38] Justina Jankauskaitė, Brian Jiménez-García, Justas Dapkūnas, Juan Fernández-Recio, and Iain H Moal.  SKEMPI 2.0: an updated benchmark of changes in protein–protein binding energy, kinetics and thermodynamics upon mutation.  Bioinformatics, 35(3):462–469, 2019.
  * [39] Erik Procko.  The sequence of human ace2 is suboptimal for binding the s spike protein of sars coronavirus 2.  BioRxiv, 2020.
  * [40] Tyler N Starr, Allison J Greaney, Sarah K Hilton, Daniel Ellis, Katharine HD Crawford, Adam S Dingens, Mary Jane Navarro, John E Bowen, M Alejandra Tortorici, Alexandra C Walls, et al.  Deep mutational scanning of SARS-CoV-2 receptor binding domain reveals constraints on folding and ACE2 binding.  Cell, 182(5):1295–1310, 2020.
  * [41] Thomas W Linsky, Renan Vergara, Nuria Codina, Jorgen W Nelson, Matthew J Walker, Wen Su, Christopher O Barnes, Tien-Ying Hsiang, Katharina Esser-Nobis, Kevin Yu, et al.  De novo design of potent and resilient hACE2 decoys to neutralize SARS-CoV-2.  Science, 370(6521):1208–1214, 2020.
  * [42] Gunnar Carlsson.  Topology and data.  Bulletin of the American Mathematical Society, 46(2):255–308, 2009\.
  * [43] Herbert Edelsbrunner, David Letscher, and Afra Zomorodian.  Topological persistence and simplification.  In Proceedings 41st annual symposium on foundations of computer science, pages 454–463. IEEE, 2000.
  * [44] Kelin Xia and Guo-Wei Wei.  Persistent homology analysis of protein structure, flexibility, and folding.  International journal for numerical methods in biomedical engineering, 30(8):814–844, 2014.
  * [45] Rui Wang, Yuta Hozumi, Changchuan Yin, and Guo-Wei Wei.  Mutations on COVID-19 diagnostic targets.  Genomics, 112(6):5204–5213, 2020.
  * [46] Soo-Young Lee, Dong-Kyun Ryu, Hanmi Noh, Jongin Kim, Ji-Min Seo, Cheolmin Kim, Carel van Baalen, Aloys SL Tijsma, Hyo-Young Chung, Min-Ho Lee, et al.  Therapeutic efficacy of CT-p59 against P. 1 variant of SARS-CoV-2.  bioRxiv, 2021.