# A continuous generalization of domination-like invariants

Michitaka<EMAIL_ADDRESS>
College of Liberal Arts and Science,
Kitasato University,
1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan

###### Abstract

In this paper, we define a new domination-like invariant of graphs. Let
$\mathbb{R}^{+}$ be the set of non-negative numbers. Let
$c\in\mathbb{R}^{+}-\\{0\\}$ be a number, and let $G$ be a graph. A function
$f:V(G)\rightarrow\mathbb{R}^{+}$ is a $c$-self-dominating function of $G$ if
for every $u\in V(G)$, $f(u)\geq c$ or $\max\\{f(v):v\in N_{G}(u)\\}\geq 1$.
The $c$-self-domination number $\gamma^{c}(G)$ of $G$ is defined as
$\gamma^{c}(G):=\min\\{\sum_{u\in V(G)}f(u):f$ is a $c$-self-dominating
function of $G\\}$. Then $\gamma^{1}(G)$, $\gamma^{\infty}(G)$ and
$\gamma^{\frac{1}{2}}(G)$ are equal to the domination number, the total
domination number and the half of the Roman domination number of $G$,
respectively. Our main aim is to continuously fill in the gaps among such
three invariants. In this paper, we give a sharp upper bound of the $c$-self-
domination number for all $c\geq\frac{1}{2}$.

Key words and phrases. self-domination, domination, total domination, Roman
domination.

AMS 2010 Mathematics Subject Classification. 05C69.

##  1 Introduction

###  1.1 Definitions and notations

All graphs considered in this paper are finite, simple, and undirected. Let
$G$ be a graph. We let $V(G)$ and $E(G)$ denote the vertex set and the edge
set of $G$, respectively. For a vertex $u\in V(G)$, we let $N_{G}(u)$ and
$d_{G}(u)$ denote the neighborhood and the degree of $u$, respectively; thus
$N_{G}(u)=\\{v\in V(G):uv\in E(G)\\}$ and $d_{G}(u)=|N_{G}(u)|$. For a subset
$U$ of $V(G)$, we let $G[U]$ denote the subgraph of $G$ induced by $U$. We let
$P_{n}$ denote the path of order $n$. For terms and symbols not defined in
this paper, we refer the reader to [4].

We let $\mathbb{R}^{+}$ denote the set of non-negative numbers. Here we regard
$\infty$ as a non-negative number (i.e., $\infty\in\mathbb{R}^{+}$). For a
graph $G$ and a function $f:V(G)\rightarrow\mathbb{R}^{+}$, the weight $w(f)$
of $f$ is defined by $w(f)=\sum_{u\in V(G)}f(u)$.

Let $G$ be a graph. A set $S\subseteq V(G)$ is a dominating set of $G$ if each
vertex in $V(G)-S$ is adjacent to a vertex in $S$. The minimum cardinality of
a dominating set of $G$, denoted by $\gamma(G)$, is called the domination
number of $G$. The domination number is one of the most important invariants
in Graph Theory, and it can be widely applied to real problems, for example,
school bus routing problem, social network theory and location of radio
stations (see [8, 9]). To meet various additional requirements for above
problems, many domination-like invariants were defined and studied.

A set $S\subseteq V(G)$ is a total dominating set of $G$ if each vertex of $G$
is adjacent to a vertex in $S$. Note that if $G$ has no isolated vertices,
then there exists a total dominating set of $G$. For a graph $G$ without
isolated vertices, the minimum cardinality of a total dominating set of $G$,
denoted by $\gamma_{t}(G)$, is called the total domination number of $G$. The
total domination number is typically defined for only graphs without isolated
vertices. However, in this paper, we define $\gamma_{t}(G)$ as
$\gamma_{t}(G)=\infty$ if $G$ has an isolated vertex for convenience. The
concept of total domination was introduced in [2], and has been actively
studied (see a book [10]).

A function $f:V(G)\rightarrow\\{0,1,2\\}$ is a Roman dominating function of
$G$ if each vertex $u\in V(G)$ with $f(u)=0$ is adjacent to a vertex $v\in
V(G)$ with $f(v)=2$. The minimum weight of a Roman dominating function of $G$,
denoted by $\gamma_{R}(G)$, is called the Roman domination number of $G$. The
Roman domination number was introduced by Stewart [15], and was studied by
Cockayne et al. [3] in earnest. Roman domination derives from the strategy to
defend the Roman Empire against the enemies. Recently, various properties on
the Roman domination number have been explored in, for example, [6, 11, 12].

From a mathematical point of view, Roman domination concept seems to be more
artificial than original domination and total domination. However, by the
following reasons, we can interpret Roman domination as a natural extension of
domination and total domination.

We define a new domination-like invariant. Let $c\in\mathbb{R}^{+}-\\{0\\}$ be
a number, and let $G$ be a graph. A function $f:V(G)\rightarrow\mathbb{R}^{+}$
is a $c$-self-dominating function (or $c$-SDF) of $G$ if for each $u\in V(G)$,
$f(u)\geq c$ or $\max\\{f(v):v\in N_{G}(u)\\}\geq 1$.

###### Remark 1

We choose a $c$-SDF $f$ of $G$ so that $w(f)$ is as small as possible. Suppose
that there exists a vertex $x\in V(G)$ with $f(x)\notin\\{0,1,c\\}$. Now we
construct a function $f^{\prime}:V(G)\rightarrow\mathbb{R}^{+}$ as follows:
For $u\in V(G)-\\{x\\}$, let $f^{\prime}(u)=f(u)$. If $0<f(x)<\min\\{1,c\\}$,
let $f^{\prime}(x)=0$; if $\min\\{1,c\\}<f(x)<\max\\{1,c\\}$, let
$f^{\prime}(x)=\min\\{1,c\\}$; if $f(x)>\max\\{1,c\\}$, let
$f^{\prime}(x)=\max\\{1,c\\}$ (for example, if $c=\infty$, then
$f^{\prime}(x)=0$ or $f^{\prime}(x)=1$ according as $0<f(x)<1$ or
$1<f(x)<\infty$). Then we can easily verify that $f^{\prime}$ is a $c$-SDF of
$G$ with $w(f^{\prime})<w(f)$, which contradicts the choice of $f$. Thus
$\\{f(u):u\in V(G)\\}\subseteq\\{0,1,c\\}$. In particular, the minimum weight
of $c$-SDF of $G$ is well-defined.

The minimum weight of a $c$-SDF of $G$, denoted by $\gamma^{c}(G)$, is called
the $c$-self-domination number of $G$. A $c$-SDF $f$ of $G$ with
$w(f)=\gamma^{c}(G)$ is called a $\gamma^{c}$-function of $G$. Considering
Remark 1,

$\\{f(u):u\in V(G)\\}\subseteq\\{0,1,c\\}$ for a $\gamma^{c}$-function $f$ of
a graph $G$. (1.1)

We show that $c$-self-domination is a common generalization of domination,
total domination and Roman domination.

###### Proposition 1.1

Let $G$ be a graph. Then the following hold.

  1. (i)

$\gamma^{1}(G)=\gamma(G)$,

  2. (ii)

$\gamma^{\infty}(G)=\gamma_{t}(G)$, and

  3. (iii)

$\gamma^{\frac{1}{2}}(G)=\frac{1}{2}\gamma_{R}(G)$.

###### Proof.

  1. (i)

For a dominating set $S$ of $G$ with $|S|=\gamma(G)$, the function
$f_{1}:V(G)\rightarrow\mathbb{R}^{+}$ with

$f_{1}(u)=\begin{cases}1,&u\in S;\\\ 0,&u\notin S\end{cases}$

is a $1$-SDF of $G$ with $w(f_{1})=|S|$, and hence $\gamma^{1}(G)\leq
w(f_{1})=|S|=\gamma(G)$.

Let $f$ be a $\gamma^{1}$-function of $G$. Then by (1.1), $\\{f(u):u\in
V(G)\\}\subseteq\\{0,1\\}$. Hence the set $S_{1}:=\\{u\in V(G):f(u)=1\\}$ is a
dominating set of $G$ with $|S_{1}|=w(f)$. Thus
$\gamma(G)\leq|S_{1}|=w(f)=\gamma^{1}(G)$.

Consequently, $\gamma^{1}(G)=\gamma(G)$.

  2. (ii)

If $G$ has an isolated vertex, then it is clear that
$\gamma^{\infty}(G)=\infty=\gamma_{t}(G)$. Thus we may assume that $G$ has no
isolated vertices. For a total dominating set $S$ of $G$ with
$|S|=\gamma_{t}(G)$, the function $f_{2}:V(G)\rightarrow\mathbb{R}^{+}$ with

$f_{2}(u)=\begin{cases}1,&u\in S;\\\ 0,&u\notin S\end{cases}$

is an $\infty$-SDF of $G$ with $w(f_{2})=|S|$, and hence
$\gamma^{\infty}(G)\leq w(f_{2})=|S|=\gamma_{t}(G)$.

Let $f$ be a $\gamma^{\infty}$-function of $G$. Since the function assigning
$1$ to all vertices of $G$ is an $\infty$-SDF of $G$, we have
$\gamma^{\infty}(G)<\infty$, and hence $f$ does not use $\infty$. This
together with (1.1) implies that $\\{f(u):u\in V(G)\\}\subseteq\\{0,1\\}$.
Hence the set $S_{2}:=\\{u\in V(G):f(u)=1\\}$ is a total dominating set of $G$
with $|S_{2}|=w(f)$. Thus $\gamma_{t}(G)\leq|S_{2}|=w(f)=\gamma^{\infty}(G)$.

Consequently, $\gamma^{\infty}(G)=\gamma_{t}(G)$.

  3. (iii)

For a Roman dominating function $f$ of $G$ with $w(f)=\gamma_{R}(G)$, the
function $f_{3}:V(G)\rightarrow\mathbb{R}^{+}$ with
$f_{3}(u)=\frac{1}{2}f(u)~{}(u\in V(G))$ is a $\frac{1}{2}$-SDF of $G$ with
$w(f_{3})=\frac{1}{2}w(f)$, and hence $\gamma^{\frac{1}{2}}(G)\leq
w(f_{3})=\frac{1}{2}w(f)=\frac{1}{2}\gamma_{R}(G)$.

Let $f^{\prime}$ be a $\gamma^{\frac{1}{2}}$-function of $G$. Then by (1.1),
$\\{f^{\prime}(u):u\in V(G)\\}\subseteq\\{0,1,\frac{1}{2}\\}$. Hence the
function $f^{\prime}_{3}:V(G)\rightarrow\\{0,1,2\\}$ with
$f^{\prime}_{3}(u)=2f^{\prime}(u)~{}(u\in V(G))$ is a Roman dominating
function of $G$ with $w(f^{\prime}_{3})=2w(f^{\prime})$. Thus
$\gamma_{R}(G)\leq w(f^{\prime}_{3})=2w(f^{\prime})=2\gamma^{\frac{1}{2}}(G)$.

Consequently, $\gamma^{\frac{1}{2}}(G)=\frac{1}{2}\gamma_{R}(G)$. ∎

###  1.2 Main results

By Proposition 1.1, $c$-self-domination can continuously fill in the gaps
among three invariants: domination, total domination and Roman domination. On
the other hand, some results concerning such invariants have been proved via
different techniques. Thus the study of $c$-self-domination for
$c\geq\frac{1}{2}$ may give essential boundaries of them. As the initial
research for the goal, we focus on the following known upper bounds.

######  Theorem A (Ore [13])

Let $G$ be a connected graph of order $n\geq 2$. Then
$\gamma(G)\leq\frac{1}{2}n$.

######  Theorem B (Cockayne et al. [2])

Let $G$ be a connected graph of order $n\geq 3$. Then
$\gamma_{t}(G)\leq\frac{2}{3}n$.

######  Theorem C (Chambers et al. [1])

Let $G$ be a connected graph of order $n\geq 3$. Then
$\gamma_{R}(G)\leq\frac{4}{5}n$.

In this paper, we generalize Theorems A–C as follows.

###### Theorem 1.2

Let $c\in\mathbb{R}^{+}$ be a number with $c\geq\frac{1}{2}$. Let $G$ be a
connected graph of order $n\geq 3$. Then

$\gamma^{c}(G)\leq\begin{cases}\frac{m+1}{2m+3}n,&\frac{m}{m+1}\leq
c<\frac{2m+1}{2m+3},~{}m\in\mathbb{N};\\\
\frac{cm+2c+1}{2m+5}n,&\frac{2m+1}{2m+3}\leq
c<\frac{m+1}{m+2},~{}m\in\mathbb{N};\\\ \frac{1}{2}n,&c=1;\\\
\frac{m+2}{2m+3}n,&\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m},~{}m\in\mathbb{N};\\\
\frac{cm}{2m+1}n,&\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m},~{}m\in\mathbb{N};\\\
\frac{2}{3}n,&c>2.\end{cases}$

###### Remark 2

  1. (i)

Since the function $h(m):=\frac{m}{m+1}$ is a monotonically increasing
function and $\lim_{m\rightarrow\infty}h(m)=1$, the interval $[\frac{1}{2},1)$
can be partitioned by intervals $[\frac{m}{m+1},\frac{m+1}{m+2})$
$(m\in\mathbb{N})$. In particular, for a number $c~{}(\frac{1}{2}\leq c<1)$,
there is only one positive integer $m$ such that $\frac{m}{m+1}\leq
c<\frac{m+1}{m+2}$. Furthermore, since
$\frac{m}{m+1}<\frac{2m+1}{2m+3}<\frac{m+1}{m+2}$, the interval
$[\frac{m}{m+1},\frac{m+1}{m+2})$ can be partitioned by two intervals
$[\frac{m}{m+1},\frac{2m+1}{2m+3})$ and $[\frac{2m+1}{2m+3},\frac{m+1}{m+2})$.

  2. (ii)

Since the function $h^{\prime}(m):=\frac{m+1}{m}$ is a monotonically
decreasing function and $\lim_{m\rightarrow\infty}h^{\prime}(m)=1$, the
interval $(1,2]$ can be partitioned by intervals
$(\frac{m+2}{m+1},\frac{m+1}{m}]$ $(m\in\mathbb{N})$. In particular, for a
number $c~{}(1<c\leq 2)$, there is only one positive integer $m$ such that
$\frac{m+2}{m+1}<c\leq\frac{m+1}{m}$. Furthermore, since
$\frac{m+2}{m+1}<\frac{(2m+1)(m+2)}{(2m+3)m}<\frac{m+1}{m}$, the interval
$(\frac{m+2}{m+1},\frac{m+1}{m}]$ can be partitioned by two intervals
$(\frac{m+2}{m+1},\frac{(2m+1)(m+2)}{(2m+3)m}]$ and
$(\frac{(2m+1)(m+2)}{(2m+3)m},\frac{m+1}{m}]$.

By (i) and (ii), for each $c~{}(c\geq\frac{1}{2})$, Theorem 1.2 gives exactly
one upper bound on $\gamma^{c}$.

It follows from Proposition 1.1(i) and Theorem A that
$\gamma^{1}(G)\leq\frac{1}{2}n$ for every connected graph $G$ of order $n\geq
2$. (Indeed, since a maximal independent set $S$ of $G$ and the set
$S^{\prime}:=V(G)-S$ are dominating sets of $G$, we obtain the upper bound.)
Thus it suffices to focus on Theorem 1.2 for the case where $c\neq 1$. We
divide the proof of Theorem 1.2 into three cases. We consider the case where
$\frac{1}{2}\leq c<1$ in Section 3, the case where $1<c\leq 2$ in Section 4,
the case where $c>2$ in Section 5. In Section 6, we discuss the sharpness of
Theorem 1.2.

##  2 Trees without good edges

Let $T$ be a tree. For an edge $x_{1}x_{2}$ of $T$, let
$T_{x_{1}x_{2}}^{x_{1}}$ be the component of $T-x_{1}x_{2}$ containing
$x_{1}$. An edge $x_{1}x_{2}$ of $T$ is good if
$|V(T_{x_{1}x_{2}}^{x_{i}})|\geq 3$ for each $i\in\\{1,2\\}$.

For non-negative integers $p$ and $q$, we let $T_{p,q}$ denote the tree with

$V(T_{p,q})=\\{x\\}\cup\\{y_{i,j}:1\leq i\leq
p,j\in\\{1,2\\}\\}\cup\\{z_{i}:1\leq i\leq q\\}$

and

$E(T_{p,q})=\\{xy_{i,1},y_{i,1}y_{i,2}:1\leq i\leq p\\}\cup\\{xz_{i}:1\leq
i\leq q\\}$

(see Figure 1).

$x$$y_{1,1}$$y_{1,2}$$y_{p,2}$$y_{p,1}$$z_{q}$$z_{1}$ Figure 1: Tree $T_{p,q}$

The following lemma might be known. However, to keep the paper self-contained,
we give its proof.

###### Lemma 2.1

Let $T$ be a tree of order at least $3$. Then $T$ has no good edge if and only
if $T$ is isomorphic to $T_{p,q}$ for some $p\geq 0$ and $q\geq 0$ with
$2p+q\geq 2$.

###### Proof.

For integers $p\geq 0$ and $q\geq 0$ with $2p+q\geq 2$, it is clear that
$T_{p,q}$ has no good edge. Thus it suffices to show that the “only if” part
of the lemma.

Let $P=x_{0}x_{1}\cdots x_{d}$ be a longest path of $T$. Then $d$ is equal to
the diameter of $T$. In particular, $d_{T}(x_{1})\geq 2$ because $d\geq 2$. By
the maximality of $P$, every vertex in $N_{T}(x_{1})-\\{x_{0},x_{2}\\}$ is a
leaf of $T$.

Suppose that $d_{T}(x_{1})\geq 3$. Since $x_{1}x_{2}$ is not a good edge of
$T$, $|V(T_{x_{1}x_{2}}^{x_{2}})|\leq 2$. In particular, either $d=2$ and
$V(T_{x_{1}x_{2}}^{x_{2}})=\\{x_{2}\\}$ or $d=3$ and
$V(T_{x_{1}x_{2}}^{x_{2}})=\\{x_{2},x_{3}\\}$. Let $k=d_{T}(x_{1})$. If $d=2$
and $V(T_{x_{1}x_{2}}^{x_{2}})=\\{x_{2}\\}$, then $T$ is isomorphic to
$T_{0,k}$; if $d=3$ and $V(T_{x_{1}x_{2}}^{x_{2}})=\\{x_{2},x_{3}\\}$, then
$T$ is isomorphic to $T_{1,k-1}$. In either case, we obtain the desired
conclusion. Thus we may assume that $d_{T}(x_{1})=2$ (i.e.,
$N_{T}(x_{1})=\\{x_{0},x_{2}\\}$).

For each vertex $u\in N_{T}(x_{2})-\\{x_{1}\\}$, since $x_{2}u$ is not a good
edge and $|V(T_{x_{2}u}^{x_{2}})|\geq 3$, $|V(T_{x_{2}u}^{u})|\leq 2$. Let
$p=|\\{u\in N_{T}(x_{2})-\\{x_{1}\\}:|V(T_{x_{2}u}^{u})|=2\\}|$ and
$q=|\\{u\in N_{T}(x_{2})-\\{x_{1}\\}:|V(T_{x_{2}u}^{u})|=1\\}|$. Then $T$ is
isomorphic to $T_{p+1,q}$, as desired. ∎

##  3 Upper bound on $\gamma^{c}$ for $\frac{1}{2}\leq c<1$

In this section, we prove the following theorem.

###### Theorem 3.1

Let $c\in\mathbb{R}^{+}$ be a number with $\frac{1}{2}\leq c<1$, and let
$m\geq 1$ be the integer such that $\frac{m}{m+1}\leq c<\frac{m+1}{m+2}$. Let
$T$ be a tree of order $n\geq 3$. Then the conclusion of Theorem 1.2 holds for
$G=T$.

###### Remark 3

Since the deletion of edges cannot decrease the $c$-self-domination number of
a graph, we obtain Theorem 1.2 for the case where $\frac{1}{2}\leq c<1$ as a
corollary of Theorem 3.1.

We first show the following lemma.

###### Lemma 3.2

Let $c$ and $m$ be as in Theorem 3.1. If $T=T_{p,q}$ for integers $p\geq 0$
and $q\geq 0$ with $2p+q\geq 2$, then the conclusion of Theorem 3.1 holds.

###### Proof.

The function $f_{1}:V(T_{p,q})\rightarrow\mathbb{R}^{+}$ with

$f_{1}(u)=\begin{cases}1,&u=x;\\\ c,&u\in\\{y_{i,2}:1\leq i\leq p\\};\\\
0,&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $T_{p,q}$ with $w(f_{1})=cp+1$. Hence

$\displaystyle\gamma^{c}(T_{p,q})\leq
w(f_{1})=cp+1=\frac{cp+1}{2p+q+1}|V(T_{p,q})|.$ (3.1)

If $p\geq 1$, then the function $f_{2}:V(T_{p,q})\rightarrow\mathbb{R}^{+}$
with

$f_{2}(u)=\begin{cases}1,&u\in\\{y_{i,1}:1\leq i\leq p\\};\\\
c,&u\in\\{z_{i}:1\leq i\leq q\\};\\\ 0,&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $T_{p,q}$ with $w(f_{2})=p+cq$. Hence

$\displaystyle\gamma^{c}(T_{p,q})\leq
w(f_{2})=p+cq=\frac{p+cq}{2p+q+1}|V(T_{p,q})|\mbox{~{}~{}~{}~{}if }p\geq 1.$
(3.2)

Furthermore, we have

$\displaystyle\frac{m+1}{2m+3}=\frac{\frac{(2m+1)(m+2)}{2m+3}+1}{2m+5}\leq\frac{c(m+2)+1}{2m+5}\mbox{~{}~{}~{}~{}if
}c\geq\frac{2m+1}{2m+3}.$ (3.3)

We divide the proof into four cases.

Case 1: Either $p=0$ or $(p,q)=(1,0)$.

Note that if $p=0$, then $q=2p+q\geq 2$. Hence it follows from (3.1) and (3.2)
that

$\displaystyle\gamma^{c}(T_{p,q})\leq\frac{1}{3}|V(T_{p,q})|<\frac{m+1}{2m+3}|V(T_{p,q})|.$
(3.4)

In particular, we obtain the desired conclusion for the case where
$\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$. If $\frac{2m+1}{2m+3}\leq
c<\frac{m+1}{m+2}$, then it follows from (3.3) and (3.4) that

$\gamma^{c}(T_{p,q})<\frac{m+1}{2m+3}|V(T_{p,q})|\leq\frac{c(m+2)+1}{2m+5}|V(T_{p,q})|,$

which follows the desired conclusion for the remaining case.

Case 2: $p=1$ and $q\geq 1$.

If $\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$, then by (3.1) and the assumption
that $q\geq 1$,

$\gamma^{c}(T_{p,q})\leq\frac{cp+1}{2p+q+1}|V(T_{p,q})|<\frac{\frac{2m+1}{2m+3}+1}{4}|V(T_{p,q})|=\frac{m+1}{2m+3}|V(T_{p,q})|,$

as desired.

Next we suppose that $\frac{2m+1}{2m+3}\leq c<\frac{m+1}{m+2}$. Since

$\displaystyle 4(cm+2c+1)-(c+1)(2m+5)$ $\displaystyle=c(2m+3)-(2m+1)$
$\displaystyle\geq\frac{(2m+1)(2m+3)}{2m+3}-(2m+1)$ $\displaystyle=0,$

we have

$\frac{cp+1}{2p+q+1}\leq\frac{c+1}{4}\leq\frac{cm+2c+1}{2m+5}.$

This together with (3.1) leads to the desired conclusion for the case where
$\frac{2m+1}{2m+3}\leq c<\frac{m+1}{m+2}$.

Case 3: $p\geq 2$ and $q\geq 1$.

Since $p\geq 2$,

$2(m+1)(m+2)(p+1)-((m+1)p+m+2)(2m+3)=m(p-1)+p-2>0,$

and hence

$\frac{(m+1)p+m+2}{2(m+2)(p+1)}<\frac{m+1}{2m+3}.$

This together with (3.1) implies

$\displaystyle\gamma^{c}(T_{p,q})$
$\displaystyle\leq\frac{cp+1}{2p+q+1}|V(T_{p,q})|$
$\displaystyle<\frac{\frac{(m+1)p}{m+2}+1}{2p+2}|V(T_{p,q})|$
$\displaystyle=\frac{(m+1)p+m+2}{2(m+2)(p+1)}|V(T_{p,q})|$
$\displaystyle<\frac{m+1}{2m+3}|V(T_{p,q})|.$ (3.5)

In particular, we obtain the desired conclusion for the case where
$\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$. If $\frac{2m+1}{2m+3}\leq
c<\frac{m+1}{m+2}$, then it follows from (3.3) and (3.5) that

$\gamma^{c}(T_{p,q})\leq\frac{m+1}{2m+3}|V(T_{p,q})|\leq\frac{c(m+2)+1}{2m+5}|V(T_{p,q})|,$

which follows the desired conclusion for the remaining case.

Case 4: $p\geq 2$ and $q=0$.

Suppose that $p\leq m+1$. Then it follows from (3.2) that

$\displaystyle\gamma^{c}(T_{p,q})\leq\frac{p}{2p+1}|V(T_{p,q})|\leq\frac{m+1}{2m+3}|V(T_{p,q})|.$
(3.6)

In particular, we obtain the desired conclusion for the case where
$\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$. If $\frac{2m+1}{2m+3}\leq
c<\frac{m+1}{m+2}$, then it follows from (3.3) and (3.6) that

$\gamma^{c}(T_{p,q})\leq\frac{m+1}{2m+3}|V(T_{p,q})|\leq\frac{c(m+2)+1}{2m+5}|V(T_{p,q})|,$

as desired. Thus we may assume that $p\geq m+2$.

We first suppose that $\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$. Then

$(m+1)(2p+1)-((2m+1)p+2m+3)=p-m-2\geq 0,$

and hence

$\frac{(2m+1)p+2m+3}{2p+1}\leq m+1.$

This together with (3.1) leads to

$\displaystyle\gamma^{c}(T_{p,q})$
$\displaystyle\leq\frac{cp+1}{2p+1}|V(T_{p,q})|$
$\displaystyle<\frac{\frac{(2m+1)p}{2m+3}+1}{2p+1}|V(T_{p,q})|$
$\displaystyle=\frac{(2m+1)p+2m+3}{(2p+1)(2m+3)}|V(T_{p,q})|$
$\displaystyle\leq\frac{m+1}{2m+3}|V(T_{p,q})|,$

which leads to the desired conclusion for the case where $\frac{m}{m+1}\leq
c<\frac{2m+1}{2m+3}$.

Next we suppose that $\frac{2m+1}{2m+3}\leq c<\frac{m+1}{m+2}$. Then

$(c(m+2)+1)(2p+1)-(cp+1)(2m+5)=(p-m-2)(2-c)\geq 0,$

and hence

$\frac{cp+1}{2p+1}\leq\frac{c(m+2)+1}{2m+5}.$

This together with (3.1) leads to

$\gamma^{c}(T_{p,q})\leq\frac{cp+1}{2p+1}|V(T_{p,q})|\leq\frac{c(m+2)+1}{2m+5}|V(T_{p,q})|,$

which leads to the desired conclusion for the case where
$\frac{2m+1}{2m+3}\leq c<\frac{m+1}{m+2}$.

This completes the proof of Lemma 3.2. ∎

Proof of Theorem 3.1. We proceed by induction on $n$. If $T$ has no good edge,
then by Lemma 2.1 and Lemma 3.2, the desired conclusion holds. Thus we may
assume that $T$ has a good edge $x_{1}x_{2}$. Then by the induction
hypothesis, for each $i\in\\{1,2\\}$,

$\gamma^{c}(T_{x_{1}x_{2}}^{x_{i}})\leq\begin{cases}\frac{m+1}{2m+3}|V(T_{x_{1}x_{2}}^{x_{i}})|,&\frac{m}{m+1}\leq
c<\frac{2m+1}{2m+3};\\\
\frac{cm+2c+1}{2m+5}|V(T_{x_{1}x_{2}}^{x_{i}})|,&\frac{2m+1}{2m+3}\leq
c<\frac{m+1}{m+2}.\end{cases}$

Since
$\gamma^{c}(T)\leq\gamma^{c}(T_{x_{1}x_{2}}^{x_{1}})+\gamma^{c}(T_{x_{1}x_{2}}^{x_{2}})$
and $|V(T_{x_{1}x_{2}}^{x_{1}})|+|V(T_{x_{1}x_{2}}^{x_{2}})|=n$, this leads to
the desired conclusion. ∎

##  4 Upper bound on $\gamma^{c}$ for $1<c\leq 2$

In this section, we prove the following theorem.

###### Theorem 4.1

Let $c\in\mathbb{R}^{+}$ be a number with $1<c\leq 2$, and let $m\geq 1$ be
the integer such that $\frac{m+2}{m+1}<c\leq\frac{m+1}{m}$. Let $T$ be a tree
of order $n\geq 3$. Then the conclusion of Theorem 1.2 holds for $G=T$.

###### Remark 4

Since the deletion of edges cannot decrease the $c$-self-domination number of
a graph, we obtain Theorem 1.2 for the case where $1<c\leq 2$ as a corollary
of Theorem 4.1.

We first show the following lemma.

###### Lemma 4.2

Let $c$ and $m$ be as in Theorem 4.1. If $T=T_{p,q}$ for integers $p\geq 0$
and $q\geq 0$ with $2p+q\geq 2$, then the conclusion of Theorem 4.1 holds.

###### Proof.

If $p=0$, then the function $f_{1}:$ The function
$f_{1}:V(T_{p,q})\rightarrow\mathbb{R}^{+}$ with

$f_{1}(u)=\begin{cases}c,&u=x;\\\ 0,&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $T_{p,q}$ with $w(f_{1})=c$. Hence

$\displaystyle\gamma^{c}(T_{p,q})\leq
w(f_{1})=c=\frac{c}{q+1}|V(T_{p,q})|\mbox{~{}~{}~{}~{}if }p=0.$ (4.1)

If $p\geq 1$, then the function $f_{2}:V(T_{p,q})\rightarrow\mathbb{R}^{+}$
with

$f_{2}(u)=\begin{cases}1,&u\in\\{x,y_{i,1}:1\leq i\leq p\\};\\\
0,&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $T_{p,q}$ with $w(f_{2})=p+1$. Hence

$\displaystyle\gamma^{c}(T_{p,q})\leq
w(f_{2})=p+1=\frac{p+1}{2p+q+1}|V(T_{p,q})|\mbox{~{}~{}~{}~{}if }p\geq 1.$
(4.2)

If $q=0$ (i.e., $p\geq 1$), then the function
$f_{3}:V(T_{p,q})\rightarrow\mathbb{R}^{+}$ with

$f_{3}(u)=\begin{cases}c,&u\in\\{y_{i,1}:1\leq i\leq p\\};\\\
0,&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $T_{p,q}$ with $w(f_{3})=cp$. Hence

$\displaystyle\gamma^{c}(T_{p,q})\leq
w(f_{3})=cp=\frac{cp}{2p+1}|V(T_{p,q})|\mbox{~{}~{}~{}~{}if }q=0.$ (4.3)

Furthermore, we have

$\displaystyle\frac{cm}{2m+1}\leq\frac{\frac{(2m+1)(m+2)m}{(2m+3)m}}{2m+1}=\frac{m+2}{2m+3}\mbox{~{}~{}~{}~{}if
}c\leq\frac{(2m+1)(m+2)}{(2m+3)m}.$ (4.4)

We divide the proof into three cases.

Case 1: Either $p=0$ or $(p,q)=(1,0)$.

Note that if $p=0$, then $q=2p+q\geq 2$. Hence it follows from (4.1) and (4.3)
that

$\displaystyle\gamma^{c}(T_{p,q})\leq\frac{c}{3}|V(T_{p,q})|\leq\frac{cm}{2m+1}|V(T_{p,q})|.$
(4.5)

In particular, we obtain the desired conclusion for the case where
$\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}$. If
$\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$, then it follows from (4.4)
and (4.5) that

$\gamma^{c}(T_{p,q})\leq\frac{cm}{2m+1}|V(T_{p,q})|\leq\frac{m+2}{2m+3}|V(T_{p,q})|,$

which follows the desired conclusion for the remaining case.

Case 2: $p\geq 1$ and $q\geq 1$.

By (4.2),

$\displaystyle\gamma^{c}(T_{p,q})$
$\displaystyle\leq\frac{p+1}{2p+q+1}|V(T_{p,q})|$
$\displaystyle\leq\frac{p+1}{2p+2}|V(T_{p,q})|$
$\displaystyle=\frac{1}{2}|V(T_{p,q})|$
$\displaystyle\leq\frac{(m+2)m}{(m+1)(2m+1)}|V(T_{p,q})|$
$\displaystyle<\frac{cm}{2m+1}|V(T_{p,q})|.$ (4.6)

In particular, we obtain the desired conclusion for the case where
$\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}$. If
$\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$, then it follows from (4.4)
and (4.6) that

$\gamma^{c}(T_{p,q})<\frac{cm}{2m+1}|V(T_{p,q})|\leq\frac{m+2}{2m+3}|V(T_{p,q})|,$

which follows the desired conclusion for the remaining case.

Case 3: $p\geq 2$ and $q=0$.

Suppose that $p\leq m$. Then it follows from (4.3) that

$\displaystyle\gamma^{c}(T_{p,q})\leq\frac{cp}{2p+1}|V(T_{p,q})|\leq\frac{cm}{2m+1}|V(T_{p,q})|.$
(4.7)

In particular, we obtain the desired conclusion for the case where
$\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}$. If
$\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$, then it follows from (4.4)
and (4.7) that

$\gamma^{c}(T_{p,q})\leq\frac{cm}{2m+1}|V(T_{p,q})|\leq\frac{m+2}{2m+3}|V(T_{p,q})|,$

which follows the desired conclusion for the case where
$\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$. Thus we may assume that
$p\geq m+1$.

We first suppose that $\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$. Then
$\frac{p+1}{2p+1}\leq\frac{m+2}{2m+3}$. This together with (4.2) leads to

$\gamma^{c}(T_{p,q})\leq\frac{p+1}{2p+1}|V(T_{p,q})|\leq\frac{m+2}{2m+3}|V(T_{p,q})|,$

as desired.

Next we suppose that $\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}$. Then

$\frac{p+1}{2p+1}\leq\frac{m+2}{2m+3}=\frac{\frac{(2m+1)(m+2)m}{(2m+3)m}}{2m+1}<\frac{cm}{2m+1}.$

This together with (4.2) leads to

$\gamma^{c}(T_{p,q})\leq\frac{p+1}{2p+1}|V(T_{p,q})|<\frac{cm}{2m+1}|V(T_{p,q})|,$

as desired.

This completes the proof of Lemma 4.2. ∎

Proof of Theorem 4.1. We proceed by induction on $n$. If $T$ has no good edge,
then by Lemma 2.1 and Lemma 4.2, the desired conclusion holds. Thus we may
assume that $T$ has a good edge $x_{1}x_{2}$. Then by the induction
hypothesis, for each $i\in\\{1,2\\}$,

$\gamma^{c}(T_{x_{1}x_{2}}^{x_{i}})\leq\begin{cases}\frac{m+2}{2m+3}|V(T_{x_{1}x_{2}}^{x_{i}})|,&\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m};\\\
\frac{cm}{2m+1}|V(T_{x_{1}x_{2}}^{x_{i}})|,&\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}.\end{cases}$

Since
$\gamma^{c}(T)\leq\gamma^{c}(T_{x_{1}x_{2}}^{x_{1}})+\gamma^{c}(T_{x_{1}x_{2}}^{x_{2}})$
and $|V(T_{x_{1}x_{2}}^{x_{1}})|+|V(T_{x_{1}x_{2}}^{x_{2}})|=n$, this leads to
the desired conclusion. ∎

##  5 Upper bound on $\gamma^{c}$ for $c>2$

###### Lemma 5.1

Let $c\in\mathbb{R}^{+}$ be a number with $c\geq 2$. Let $G$ be a connected
graph of order at least $2$. Then $\gamma^{c}(G)=\gamma_{t}(G)$.

###### Proof.

Let $f$ be a $\gamma^{c}$-function of $G$. By (1.1), we have $\\{f(u):u\in
V(G)\\}\subseteq\\{0,1,c\\}$. Choose $f$ so that $|\\{u\in V(G):f(u)=1\\}|$ is
as large as possible.

Suppose that $f(x)=c$ for some $x\in V(G)$, and let $y\in N_{G}(x)$. Then the
function $f^{\prime}:V(G)\rightarrow\mathbb{R}^{+}$ with

$f^{\prime}(u)=\begin{cases}1,&u\in\\{x,y\\};\\\
f(u),&\mbox{otherwise}\end{cases}$

is a $c$-SDF of $G$ with $w(f^{\prime})=w(f)-c-f(y)+2\leq w(f)$ and $|\\{u\in
V(G):f^{\prime}(u)=1\\}|>|\\{u\in V(G):f(u)=1\\}|$, which contradicts the
choice of $f$. Thus $\\{f(u):u\in V(G)\\}\subseteq\\{0,1\\}$.

Since the set $S:=\\{u\in V(G):f(u)=1\\}$ is a total dominating set of $G$
with $|S|=w(f)$, $\gamma_{t}(G)\leq|S|=w(f)=\gamma^{c}(G)$. Since every
$\infty$-SDF of $G$ is also a $c$-SDF of $G$, we have
$\gamma^{c}(G)\leq\gamma^{\infty}(G)$. This together with Proposition 1.1
leads to $\gamma^{c}(G)\leq\gamma^{\infty}(G)=\gamma_{t}(G)$, we obtain the
desired conclusion. ∎

By Lemma 5.1 and Theorem 4.1 for the case where $c\geq 2$, we obtain the
following proposition.

###### Proposition 5.2

Let $c\in\mathbb{R}^{+}$ be a number with $c\geq 2$. Let $G$ be a connected
graph of order $n\geq 3$. Then $\gamma^{c}(G)\leq\frac{2}{3}n$.

###### Remark 5

We obtain Theorem 1.2 for the case where $c>2$ as a corollary of Proposition
5.2.

##  6 Examples

In this section, we show that Theorem 1.2 is best possible.

Let $p\geq 1$ and $s\geq 1$ be integers, and let $T_{p,0}$ be the tree defined
in Section 2. Let $L_{p}^{1},\ldots,L_{p}^{s}$ be vertex-disjoint copies of
$T_{p,0}$. For $l~{}(1\leq l\leq s)$, let $x^{l}$ and $y_{i,j}^{l}~{}(1\leq
i\leq p,j\in\\{1,2\\})$ be the vertices of $L_{p}^{l}$ corresponding to $x$
and $y_{i,j}$, respectively. Let $T_{p}^{s}$ be the tree obtained from
$L_{p}^{1},\ldots,L_{p}^{s}$ by adding edges $x^{l}x^{l+1}~{}(1\leq l\leq
s-1)$.

###  6.1 The case $\frac{1}{2}\leq c<1$

Throughout this subsection, fix a number $c$ with $\frac{1}{2}\leq c<1$, and
let $m\geq 1$ be the integer such that $\frac{m}{m+1}\leq c<\frac{m+1}{m+2}$.

###### Lemma 6.1

Let $p\geq 1$ and $s\geq 1$ be integers. Let
$f:V(T_{p}^{s})\rightarrow\mathbb{R}^{+}$ be a $\gamma^{c}$-function of
$T_{p}^{s}$. Then for $l~{}(1\leq l\leq s)$, $\sum_{u\in
V(L_{p}^{l})}f(u)\geq\min\\{cp+1,p\\}$.

###### Proof.

If $f(x^{l})\geq 1$, then $f(y_{i,2}^{l})\geq c$ or $f(y_{i,1}^{l})\geq 1$ for
each $i~{}(1\leq i\leq p)$, and hence

$\sum_{u\in V(L_{p}^{l})}f(u)=f(x^{l})+\sum_{1\leq i\leq
p}(f(y_{i,1}^{l})+f(y_{i,2}^{l}))\geq 1+\sum_{1\leq i\leq p}c=1+cp,$

as desired. Thus we may assume that $f(x^{l})<1$. For each $i~{}(1\leq i\leq
p)$, since the restriction of $f$ on $\\{y_{i,1},y_{i,2}\\}$ is a $c$-SDF of
$G[\\{y_{i,1},y_{i,2}\\}]~{}(\simeq P_{2})$, we have
$f(y_{i,1})+f(y_{i,2})\geq\gamma^{c}(P_{2})=1$. It follows that

$\sum_{u\in V(L_{p}^{l})}f(u)=f(x^{l})+\sum_{1\leq i\leq
p}(f(y_{i,1}^{l})+f(y_{i,2}^{l}))\geq\sum_{1\leq i\leq p}1=p,$

as desired. ∎

Now we show that Theorem 1.2 for the case where $\frac{1}{2}\leq c<1$ is best
possible. We assume that $\frac{m}{m+1}\leq c<\frac{2m+1}{2m+3}$. Let $f$ be a
$\gamma^{c}$-function of $T_{m+1}^{s}$. Since
$c(m+1)+1\geq\frac{m(m+1)}{m+1}+1=m+1$ and $|V(T_{m+1}^{s})|=s(2m+3)$, it
follows from Lemma 6.1 that

$\displaystyle\gamma^{c}(T_{m+1}^{s})$ $\displaystyle=w(f)$
$\displaystyle=\sum_{1\leq l\leq s}\left(\sum_{u\in
V(L_{m+1}^{l})}f(u)\right)$ $\displaystyle\geq\sum_{1\leq l\leq
s}\min\\{c(m+1)+1,m+1\\}$ $\displaystyle=s(m+1)$
$\displaystyle=\frac{m+1}{2m+3}|V(T_{m+1}^{s})|.$

This together with Theorem 1.2 implies that
$\gamma^{c}(T_{m+1}^{s})=\frac{m+1}{2m+3}|V(T_{m+1}^{s})|$. Since $s\geq 1$ is
arbitrary, there exist infinitely many connected graphs $G$ with
$\gamma^{c}(G)=\frac{m+1}{2m+3}|V(G)|$.

Next we assume that $\frac{2m+1}{2m+3}\leq c<\frac{m+1}{m+2}$. Let
$f^{\prime}$ be a $\gamma^{c}$-function of $T_{m+2}^{s}$. Since
$c(m+2)+1<\frac{(m+1)(m+2)}{m+2}+1=m+2$ and $|V(T_{m+2}^{s})|=s(2m+5)$, it
follows from Lemma 6.1 that

$\displaystyle\gamma^{c}(T_{m+2}^{s})$ $\displaystyle=w(f^{\prime})$
$\displaystyle=\sum_{1\leq l\leq s}\left(\sum_{u\in
V(L_{m+2}^{l})}f^{\prime}(u)\right)$ $\displaystyle\geq\sum_{1\leq l\leq
s}\min\\{c(m+2)+1,m+2\\}$ $\displaystyle=s(c(m+2)+1)$
$\displaystyle=\frac{cm+2c+1}{2m+5}|V(T_{m+2}^{s})|.$

This together with Theorem 1.2 implies that
$\gamma^{c}(T_{m+2}^{s})=\frac{cm+2c+1}{2m+5}|V(T_{m+2}^{s})|$. Since $s\geq
1$ is arbitrary, there exist infinitely many connected graphs $G$ with
$\gamma^{c}(G)=\frac{cm+2c+1}{2m+5}|V(G)|$.

Therefore, Theorem 1.2 for the case where $\frac{1}{2}\leq c<1$ is best
possible.

###  6.2 The case $c=1$

Fink et al. [5] and Payan and Xuong [14] proved that a connected graph $G$
satisfies $\gamma(G)=\frac{1}{2}|V(G)|$ if and only if $G$ is isomorphic to
either a cycle of order $4$ or the graph obtained from a connected graph $H$
by adding a pendant edge to each vertex of $H$. This together with Proposition
1.1(i) implies that there exist infinitely many connected graphs $G$ with
$\gamma^{1}(G)=\frac{1}{2}|V(G)|$. Consequently Theorem 1.2 for the case where
$c=1$ is best possible.

###  6.3 The case $1<c\leq 2$

Throughout this subsection, fix a number $c$ with $1<c\leq 2$, and let $m\geq
1$ be the integer such that $\frac{m+2}{m+1}<c\leq\frac{m+1}{m}$.

###### Lemma 6.2

Let $p\geq 1$ and $s\geq 1$ be integers. Let
$f:V(T_{p}^{s})\rightarrow\mathbb{R}^{+}$ be a $\gamma^{c}$-function of
$T_{p}^{s}$. Then for $l~{}(1\leq l\leq s)$, $\sum_{u\in
V(L_{p}^{l})}f(u)\geq\min\\{p+1,cp\\}$.

###### Proof.

If $f(x^{l})\geq 1$, then $f(y_{i,2}^{l})\geq c$ or $f(y_{i,1}^{l})\geq 1$ for
each $i~{}(1\leq i\leq p)$, and hence

$\sum_{u\in V(L_{p}^{l})}f(u)=f(x^{l})+\sum_{1\leq i\leq
p}(f(y_{i,1}^{l})+f(y_{i,2}^{l}))\geq 1+\sum_{1\leq i\leq p}1=1+p,$

as desired. Thus we may assume that $f(x^{l})<1$. For each $i~{}(1\leq i\leq
p)$, since the restriction of $f$ on $\\{y_{i,1},y_{i,2}\\}$ is a $c$-SDF of
$G[\\{y_{i,1},y_{i,2}\\}]~{}(\simeq P_{2})$, we have
$f(y_{i,1})+f(y_{i,2})\geq\gamma^{c}(P_{2})=c$. It follows that

$\sum_{u\in V(L_{p}^{l})}f(u)=f(x^{l})+\sum_{1\leq i\leq
p}(f(y_{i,1}^{l})+f(y_{i,2}^{l}))\geq\sum_{1\leq i\leq p}c=cp,$

as desired. ∎

Now we show that Theorem 1.2 for the case where $1<c\leq 2$ is best possible.
We assume that $\frac{m+2}{m+1}<c\leq\frac{(2m+1)(m+2)}{(2m+3)m}$. Let $f$ be
a $\gamma^{c}$-function of $T_{m+1}^{s}$. Since
$c(m+1)\geq\frac{(m+2)(m+1)}{m+1}=m+2$ and $|V(T_{m+1}^{s})|=s(2m+3)$, it
follows from Lemma 6.2 that

$\displaystyle\gamma^{c}(T_{m+1}^{s})$ $\displaystyle=w(f)$
$\displaystyle=\sum_{1\leq l\leq s}\left(\sum_{u\in
V(L_{m+1}^{l})}f(u)\right)$ $\displaystyle\geq\sum_{1\leq l\leq
s}\min\\{(m+1)+1,c(m+1)\\}$ $\displaystyle=s(m+2)$
$\displaystyle=\frac{m+2}{2m+3}|V(T_{m+1}^{s})|.$

This together with Theorem 1.2 implies that
$\gamma^{c}(T_{m+1}^{s})=\frac{m+2}{2m+3}|V(T_{m+1}^{s})|$. Since $s\geq 1$ is
arbitrary, there exist infinitely many connected graphs $G$ with
$\gamma^{c}(G)=\frac{m+2}{2m+3}|V(G)|$.

Next we assume that $\frac{(2m+1)(m+2)}{(2m+3)m}<c\leq\frac{m+1}{m}$. Let
$f^{\prime}$ be a $\gamma^{c}$-function of $T_{m}^{s}$. Since
$cm\leq\frac{(m+1)m}{m}=m+1$ and $|V(T_{m}^{s})|=s(2m+1)$, it follows from
Lemma 6.2 that

$\displaystyle\gamma^{c}(T_{m}^{s})$ $\displaystyle=w(f^{\prime})$
$\displaystyle=\sum_{1\leq l\leq s}\left(\sum_{u\in
V(L_{m}^{l})}f^{\prime}(u)\right)$ $\displaystyle\geq\sum_{1\leq l\leq
s}\min\\{m+1,cm\\}$ $\displaystyle=scm$
$\displaystyle=\frac{cm}{2m+1}|V(T_{m}^{s})|.$

This together with Theorem 1.2 implies that
$\gamma^{c}(T_{m}^{s})=\frac{cm}{2m+1}|V(T_{m}^{s})|$. Since $s\geq 1$ is
arbitrary, there exist infinitely many connected graphs $G$ with
$\gamma^{c}(G)=\frac{cm}{2m+1}|V(G)|$.

Therefore, Theorem 1.2 for the case where $1<c\leq 2$ is best possible.

###  6.4 The case $c>2$

In Subsection 6.3, we show that there exist infinitely many connected graphs
$G$ with $\gamma^{2}(G)=\frac{2}{3}|V(G)|$. On the other hand, it follows from
Lemma 5.1 that for a number $c>2$ and a connected graph $G$ of order at least
$2$, $\gamma^{c}(G)=\gamma^{2}(G)$. Hence for $c>2$, there exist infinitely
many connected graphs $G$ with $\gamma^{c}(G)=\frac{2}{3}|V(G)|$. Consequently
Theorem 1.2 for the case where $c>2$ is best possible.

##  7 Concluding remarks

In this paper, our aim is to find essential boundaries among domination, total
domination and Roman domination. Thus we focused on $c$-self-domination for
$c\geq\frac{1}{2}$. As far as we check Theorem 1.2 and its proof, the
essential parts are roughly divided into $\frac{1}{2}\leq c<1$, $c=1$ and
$c>1$. Hence, for example, we expect that some results on Roman domination can
be extended to $c$-self-domination for $\frac{1}{2}<c<1$.

Here one might be interested in upper bounds on $c$-self-domination for
$c<\frac{1}{2}$. As a general upper bound on $c$-self-domination, we obtain
the following proposition.

###### Proposition 7.1

Let $0<c\leq 1$ be a number, and let $G$ be a graph of order $n$. Then
$\gamma^{c}(G)\leq cn$.

###### Proof.

Since the function $f:V(G)\rightarrow\mathbb{R}^{+}$ with $f(u)=c~{}(u\in
V(G))$ is a $c$-SDF of $G$ with $w(f)=cn$, we get the desired conclusion. ∎

Proposition 7.1 is best possible for the case where $0<c\leq\frac{1}{3}$. It
suffices to show that $\gamma^{c}(P_{n})\geq cn$ for all $n\geq 1$. Let $f$ be
a $\gamma^{c}$-function of $P_{n}$. By (1.1), we have $\\{f(u):u\in
V(P_{n})\\}\subseteq\\{0,1,c\\}$. Choose $f$ so that $|\\{u\in
V(P_{n}):f(u)=c\\}|$ is as large as possible. Suppose that $\\{f(u):u\in
V(P_{n})\\}\cap\\{0,1\\}\neq\emptyset$. Then there exists a vertex $x\in
V(P_{n})$ with $f(x)=1$. Let $f^{\prime}:V(P_{n})\rightarrow\mathbb{R}^{+}$ be
the function with

$f^{\prime}(u)=\begin{cases}c,&u=x;\\\ \max\\{f(u),c\\},&u\in N_{P_{n}}(x);\\\
f(u),&\mbox{otherwise}.\end{cases}$

Then $f^{\prime}$ is a $c$-SDF of $P_{n}$ with $w(f^{\prime})\leq
w(f)-1+3c\leq w(f)$ and $|\\{u\in V(P_{n}):f^{\prime}(u)=c\\}|>|\\{u\in
V(P_{n}):f(u)=c\\}|$, which contradicts the choice of $f$. Thus $f(u)=c$ for
all $u\in V(P_{n})$. Consequently, $\gamma^{c}(P_{n})=cn$, and so Proposition
7.1 is best possible for the case where $0<c\leq\frac{1}{3}$.

The author recently settled the remaining case in the following paper [7],
i.e., for a number $c\in\mathbb{R}^{+}$ with $\frac{1}{3}<c<\frac{1}{2}$, a
sharp upper bound on $\gamma^{c}(G)$ for a connected graph $G$ is given.

## Acknowledgment

The author would like to thank anonymous referees for careful reading and
helpful comments. This work was supported by JSPS KAKENHI Grant number
18K13449.

## References

  * [1] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575–1586.
  * [2] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
  * [3] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22.
  * [4] R. Diestel, “Graph Theory” (5th edition), Graduate Texts in Mathematics 173, Springer (2016).
  * [5] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287–293.
  * [6] X. Fu, Y. Yang and B. Jiang, Roman domination in regular graphs, Discrete Math. 309 (2009) 1528–1537.
  * [7] M. Furuya, A characterization of trees based on edge-deletion and its applications for domination-type invariants, preprint.
  * [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York (1998).
  * [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination inn Graphs: Advanced Topics, Marcel Dekker, Inc. New York (1998).
  * [10] M.A. Henning and A. Yeo, Total domination in graphs, Springer Monographs in Mathematics. Springer, New York, (2013).
  * [11] M. Liedloff, T. Kloks, J. Liu and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008) 3400–3415.
  * [12] C.H. Liu and G.J. Chang, Roman domination on $2$-connected graphs, SIAM J. Discrete Math. 26 (2012) 193–205.
  * [13] O. Ore, Theory of graphs, American Mathematical Society Colloquium Publications Vol.38 American Mathematics Society, Providence, RI (1962).
  * [14] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23–32.
  * [15] I. Stewart, Defend the Roman Empire!, Sci. Am. 281 (1999) 136–139.


Trade-offs and thermodynamics of energy-relay proofreading

Jonas Berx 0000-0003-1904-8103
Niels Bohr International Academy, Niels Bohr Institute, University of Copenhagen, Blegdamsvej 17, 2100 Copenhagen, Denmark
Karel Proesmans 0000-0001-9051-4205
Niels Bohr International Academy, Niels Bohr Institute, University of Copenhagen, Blegdamsvej 17, 2100 Copenhagen, Denmark

Biological processes that are able to discriminate between different molecules consume energy and dissipate heat. They operate at different levels of fidelity and speed, and as a consequence there exist fundamental trade-offs between these quantities and the entropy production rate. Usually, the energy source required to operate in a high-fidelity regime comes from the consumption of external energetic molecules, e.g., GTP hydrolysis in protein translation . In this work, we study trade-offs between several kinetic and thermodynamic observables for Hopfield's energy-relay mechanism, which does not consume external molecules and is able to operate in depleted regions, at the cost of a higher error rate. The trade-offs are obtained both analytically and numerically via Pareto optimal fronts. We find that the scheme is able to operate in three distinct regimes: an energy relay regime, a mixed relay-Michaelis-Menten regime, and a Michaelis-Menten regime, depending on the kinetic and energetic parameters that tune transitions between states. The mixed regime features a dynamical phase transition in the error-entropy production Pareto trade-off, while the pure energy relay regime contains a region where this type of proofreading energetically outperforms standard kinetic proofreading.

§ INTRODUCTION

Life is a remarkable manifestation of non-equilibrium processes that rely on the precise handling of information. The intricate mechanisms involved in information processing within organisms are of seminal importance in the study of the physics of life. Among these mechanisms, the concept of kinetic proofreading (KPR), as introduced in the pioneering works of Hopfield and Ninio <cit.>, emerged as a fundamental principle for achieving unexpected fidelity in, e.g., nucleic acid transcription and protein synthesis <cit.>. By cyclically resetting the chemical reaction system instead of proceeding to product formation, mistakes arising from the incorporation of wrong substrates can be rectified, leading to high accuracy. KPR achieves this goal by introducing a strongly irreversible step in these processes that relies on the hydrolysis of external molecules such as GTP.

One underlying assumption in the KPR scheme is that different production cycles are independent; the enzyme is reset to its unbound starting conformation after every product formation. When there are correlations present in the assembly process, as is the case in, e.g., enzymes that possess a single binding site with multiple internal states, proofreading properties can depend on the state of the enzyme after a previous production step was completed. Such time-dependent functionality is termed dynamic cooperativity, contrasting with allosteric cooperativity <cit.>. Systems exhibiting dynamic cooperativity possess a mnemonic functionality; they can remember their history <cit.>. Such memory effects are relatively well-known in enzymology <cit.>, but rarely in conjunction with the thermodynamics of accuracy <cit.>.

In this work, we study a particular proofreading scheme that utilises such dynamic cooperativity: Hopfield's energy-relay proofreading (ERPR) <cit.>. ERPR offers an alternative approach to classical proofreading systems by eliminating the need to hydrolyse external molecules. For instance, in DNA replication, the initial formation of a new phosphodiester bond in the processive synthesis process liberates energy, transforming the enzyme into a high-energy, metastable state. This high-energy state is crucial for ensuring that the error-rejecting mechanism is irreversible. If errors had the potential to re-enter through the reverse of the pathway that initially rejected them, effective proofreading would be impossible. The correlations between consecutive assembly phases are thus inherently integrated into the internal chemical network. It has been established that free enzyme conformational fluctuations yield non-Michaelis-Menten (MM) kinetics and can lead to dynamic cooperativity <cit.>.

Currently, there is evidence pointing to the possible existence of ERPR in concrete biochemical systems. For instance, DNA polymerases exhibit both static and dynamic cooperativity <cit.>, further implying that they can exist in multiple functional (and presumably, conformational) states. In Ref. <cit.>, the authors consider a variant of the energy relay scheme to model the cavity system of myoglobin which protects it from carbon monoxide poisoning. More recently, it was suggested that RNA compression after the first CCA cycle of the CCA-adding enzyme is an example of proofreading via an energy relay mechanism <cit.>, where the potential energy stored in the enzyme due to compression provides the energy relay mechanism for proofreading in this case. This mechanism enables the enzyme to label structurally deficient tRNAs with a CCACCA-end, tagging them for subsequent degradation by exonuclease <cit.>.

Lastly, for DNA replication the initial insertion of nucleotides within each processive replication segment occurs with a notable propensity for errors in the energy relay mechanism <cit.>, as a result of elevating the enzyme from a low-energy to a high-energy state, induced by the incorporation of a nucleotide through regular MM kinetics. This distinctive feature serves as a hallmark of the ERPR mechanism, providing a pathway for experimental validation.

In this paper, we study the ERPR scheme in the setting of stochastic thermodynamics, to investigate the trade-off between speed, accuracy, proofreading cost and entropy production. Since the need for enhanced fidelity necessarily implies that living processes take place far from equilibrium, the trade-off between the error rate and entropy production rate will play a crucial role in our analysis. The KPR mechanism is one of the most extensively studied models in stochastic thermodynamics <cit.>, since it offers a relatively simple testbed in which to compute analytically and validate experimentally different trade-offs <cit.> and bounds, such as the thermodynamic uncertainty relation <cit.>. In contrast, ERPR has not been studied within this setting, although both schemes offer a conducive way of proofreading. We consider in this work for simplicity a single-step scheme, although multi-step extensions have been studied as well <cit.>.

The setup of this work is as follows. In Sec. <ref> we set the stage for the energy relay mechanism and the associated observables, and briefly discuss the concept of Pareto optimal fronts. In Sec. <ref>, we show that the ERPR scheme is able to operate in three distinct regimes, based on both the error rate and the cost of proofreading. We discuss these regimes in more detail in Sec. <ref> and perform a scaling analysis of the pairwise Pareto optimal fronts. In Sec. <ref>, we directly compare the ERPR scheme with KPR in a model where the proofreading discrimination can also be varied by the Pareto optimisation, and finally we conclude in Sec. <ref>.

§ ENERGY RELAY PROOFREADING AND PARETO FRONTS

We start by setting the stage for the energy relay proofreading mechanism <cit.>. Consider an enzyme that can access energy states $E$ and $E'$, in order of increasing energy. We call henceforth $E$ the ground state and $E'$ the high-energy, metastable state. The enzyme can bind substrates $S \in\{R,W\}$, where we consider right ($R$) and wrong ($W$) substrates. The reaction pathways are given by the reaction scheme in Fig. <ref>. Starting from its ground state, the enzyme $E$ can bind a substrate $S$ to form the complex $ES$, which can in turn produce the corresponding product $P_S$ by means of regular MM kinetics through pathway $\#3$. However, the energy released in the production process is used to elevate the enzyme to its high-energy state $E'$. This high-energy conformation can once again bind a substrate to form the complex $E'S$, which can either undergo proofreading by unbinding the substrate to form $E+S$ through pathway $\#2$, or can continue through the production pathway $\#1$.
In this scheme, the side branch $E'S \rightarrow E+S$ can be used to effectively proofread the complex. This is in stark contrast with KPR where only a single unbound enzymatic conformational state is considered and effective discrimination occurs by hydrolysing energetic molecules to irreversibly change the bound complex $ES$ to a state $ES^*$. From this state, the enzyme either unbinds the substrate, or proceeds to create product $P_S$. Both processes reset the enzyme to the unbound state, restarting the cycle. The probability of unbinding a wrong substrate is slightly higher than unbinding a right one, which is amplified through the resetting of the cycle, and therefore leads to effective proofreading

Reaction pathways for an enzyme $E$ and substrate $S\in\{R,W\}$ in the energy relay proofreading scheme. Branching pathways are indicated by different colours and numbers, where the arrows point in the preferential direction of the average flux.

The full reaction network of both of these schemes, together with a standard MM network is shown in Fig. <ref>. There are some important differences between ERPR and other proofreading schemes such as KPR. Firstly, ERPR generally works without consuming energy in, e.g., NTP hydrolysis. Secondly, the presence of multiple unbound enzymatic states in ERPR allows for correlations between subsequent cycles.

Discriminatory networks for the MM, KPR and ERPR schemes. Black edges in the networks are bidirectional, with the average direction of the flux indicated by arrows. Red/blue edges are unidirectional with catalysis rate $F$.

§.§ Kinetic and thermodynamic observables

To continue, we chemostat the substrate and product concentrations $[R],[W],[P_R]$ and $[P_W]$, such that the time evolution of the concentrations $[\xi]$ of the different enzymatic configurations $\xi\in\{E',E,E'R,E'W,ER,EW\}$ is given by the chemical master equation (CME):

\begin{equation}
\label{eq:master_eq_concentrations}
\dv[]{\Xi}{t} = {\bf \Gamma}\,\Xi\,,
\end{equation}

where $\Xi(t)$ denotes a vector of concentrations of the different states $\xi$ at time $t$, and the matrix ${\bf \Gamma}$ contains the transitions between states. In particular, for the ERPR the master equation is given by a set of six coupled differential equations, c.f., Eqs. (<ref>) below.

Additionally, we require that the total concentration of enzymes is fixed and normalised to one, i.e., $[E']+[E] + [E'R] + [E'W] + [ER] + [EW] = 1$. Consequently, we can interpret all of our results as if a single enzyme cycles through the different states. The master equation then becomes

\begin{equation}
\label{eq:master_eq_general}
\dv[]{\mathbb{P}}{t} = {\bf \Gamma}\,\mathbb{P}\,,
\end{equation}

where $\mathbb{P}(t)$ denotes now the vector of probabilities $P_\xi(t)$ to find the enzyme in state $\xi$ at time $t$. The steady state probabilities $P_\xi^s$ of the system are obtained by setting the left-hand side of equation (<ref>) to zero. The final catalysis step, whereby the products are formed and the enzyme is brought back to its high-energy state $E'$, is chosen to be unidirectional with rate $F$, which is equal for both right and wrong product formation. This last assumption is made for mathematical simplicity and because this process is highly irreversible in practice. Consequently, we can depict consecutive occurrences of the process by disregarding their final product state and treating this reaction as an irreversible pathway leading back to the high-energy free-enzyme state.

The kinetic quantities that we are interested in are the error rate $\eta$, proofreading cost $C$ and production speed $v$. We first consider the error rate $\eta$, defined as the ratio of the wrong production flux $\mathcal{J}_W$ and the total production flux $\mathcal{J}_p \equiv \mathcal{J}_W + \mathcal{J}_R$,

\begin{equation}
\label{eq:error_rate}
\eta = \frac{\mathcal{J}_W}{\mathcal{J}_R + \mathcal{J}_W}\,,
\end{equation}

where the steady-state production fluxes are defined as $\mathcal{J}_{S} \equiv F\,P_{ES}^s$, $S\in\{R,\,W\}$.

We next consider the cost of proofreading $C_j$ via either pathway $j=2$ or $j=3$ (see the red and green lines in Fig. <ref>, respectively), where a bound enzyme, either $E'S$ or $ES$, releases its substrate $S$ and changes to the ground state $E$. These costs of proofreading are defined as

\begin{equation}
\label{eq:proofreading_cost_2}
\begin{split}
C_2 &= \frac{\mathcal{J}_{\ell,R}+\mathcal{J}_{\ell,W}}{\mathcal{J}_p}\,, \\
C_3 &= -\frac{\mathcal{J}_{m,R}+\mathcal{J}_{m,W}}{\mathcal{J}_p}\,,
\end{split}
\end{equation}

with $\mathcal{J}_{\ell,S} = \ell_S^+ P_{E'S}^s - \ell_S^- P_E^s$ and $\mathcal{J}_{m,S} = m_S^+ P_{E}^s - m_S^- P_{ES}^s$ for $S\in\{R,\,W\}$. The reason for calling this quantity a `cost' derives from the equivalent nomenclature used in studies on KPR <cit.>, where the number of times the proofreading side reaction is used is related to the amount of NTP that is hydrolysed. Therefore, in studies on ERPR <cit.> and hence also in this work, this quantity is referred to as a cost. Despite no longer directly being related to the dissipated energy for ERPR, $C_j$ can still provide important insights. Indeed, it can be seen as the number of times the proofreading pathways $\#2$ or $\#3$ are used per product molecule formed, and this is crucial to determine the different operating regimes of ERPR as we will see below.

In the steady state, the fluxes into state $E$ balance and the total proofreading cost becomes zero, $C = C_2 + C_3 = 0$. It can be shown that the individual pathway costs are bounded by $|C_i|\leq 1$, with $i=2,3$, when $\mathcal{J}_{h,R}+\mathcal{J}_{h,W} \geq 0$, with $\mathcal{J}_{h,S} \equiv h_S^+ P_{E'S}^s - h_S^- P_{ES}^s$. Since this step is usually assumed to be irreversible for high fidelity regimes <cit.>, as is also done for KPR schemes <cit.>, we assume that this condition is fulfilled as well in the regimes of the trade-offs we will study. While the total cost may be zero, it is instructive to study the partial proofreading costs themselves, i.e., equation (<ref>). Since these quantities can in principle both take on either positive or negative values, they can be used to study the fraction of products that have passed through the proofreading cycle, either in the forward or backward direction. Following the definition of the cost in KPR, we consider here only the partial cost associated with pathway $\#2$, i.e., $C_2$, which we will henceforth just call the cost $C$.

The last kinetic quantity we are interested in is the production speed $v$, which is defined as the dimensionless ratio of the production flux and the catalysis rate, i.e.,

\begin{equation}
\label{eq:speed}
v = \mathcal{J}_p/F\,.
\end{equation}

where we divide by $F$ to make the speed dimensionless.

Finally, following <cit.> we consider the thermodynamics of proofreading through the entropy production

\begin{equation}
\label{eq:entropy_production}
\sigma = \frac{1}{2}\sum_{i,j}\,'\left(k_{ij}P_i^s-k_{ji}P_j^s\right) \ln\frac{k_{ij}P_i^s}{k_{ji}P_j^s}\,,
\end{equation}

where the primed sum runs over all pairs of states, not taking the catalysis transitions into account, and the $k_{ij}$ indicate the transition rates from state $i$ to $j$. The term between brackets can be seen as the probability flux between two states, while the logarithm is the affinity. It is clear that the catalysis transitions merely describe the succession of subsequent production steps and do not constitute any discrimination. It can be thought of as a separately optimised process. Therefore we do not take these steps into account for the entropy production. The entropy production per catalysis step is then given by $\Delta\sigma = \tau\sigma = \sigma/\mathcal{J}_p$, which is proportional to the free energy irreversibly lost during product formation.

§.§ Pareto optimal fronts

By tuning the kinetic rates within a feasible solution space, observables that depend directly on these rates become indirectly coupled to each other. As a result, optimisation of a single objective cannot generally be performed independently of the others. For the ERPR, we consider the set of feasible combinations $\mathcal{F} = (v, \Delta\sigma,C,\eta)$ of the observables defined earlier: speed $v$, entropy production rate per product $\Delta\sigma$, proofreading cost $C$ and error rate $\eta$). The goal is to improve these observables (or objectives), where improving an objective in our system corresponds to increasing the speed and decreasing the entropy production rate, cost and error. By means of multi-objective optimisation, the Pareto front $\mathcal{P}\subset \mathcal{F}$ can be computed, which represents the most optimal trade-off between the different targets. In essence, the Pareto front $\mathcal{P}$ defines a set of solutions where improving one objective necessarily comes at the detriment of another. Pairwise trade-offs between two objectives can then be determined by marginalising the concomitant four-dimensional Pareto optimal front.

§ ENERGETIC VS. KINETIC DISCRIMINATION

The Gibbs free energy ($G$) landscape as a function of the reaction coordinate for the MM, KPR and ERPR discriminatory mechanisms. Full red (blue) curves indicate the free energy landscape for the right (wrong) production pathways. Dashed lines indicate side reaction pathways, if any. For the ERPR scheme, two side reaction pathways (proofreading and upcycling) are drawn.

To continue, we will make a particular choice for the kinetic rates based on the free energy landscape shown in the right panel of Fig. <ref>. For comparison, the free energy landscapes for the MM and KPR schemes are also shown <cit.>. These rates offer the possibility of energetic or kinetic discrimination <cit.>. The former indicates that discrimination results from an intrinsic difference in affinity of the right and wrong substrates, i.e., it is a result of the energy difference between the different enzymatic states. The latter mechanism pertains to kinetic barriers between different enzymatic states. This can be separated into two types of discrimination: i) initial kinetic discrimination, where the kinetic barrier  occurs in the binding transitions from the high-energy free enzyme $E'+S$ to the $E'S$ states, or ii) proofreading kinetic discrimination, which occurs between transitions from the bound $E'S$ states to the free enzymatic ground state $E$. For initial discrimination, the activation energy difference between the wrong and right pathways is given by $\delta \geq 0$, which we call the initial discrimination parameter. Similarly, for proofreading discrimination, the difference between the right and wrong activation energy is given by $\delta_p \geq 0$, which we name the proofreading parameter. Finally, the difference in binding energies between the two final bound states $ER$ and $EW$ is given by $\gamma$, the energetic discrimination parameter.

The kinetic rates for the ERPR are given by the following Kramers rates,

k_R^+    = ω^ϵ+δ,         k_R^-    = ω^δ,
k_W^+    = ω^ϵ,        k_W^-    = ω^γ,

h_R^+    = ω_i ^ϵ_i,         h_R^-    = ω_i,
h_W^+    = ω_i ^ϵ_i,        h_W^-    = ω_i,

ℓ_R^+    = ω_ℓ^ϵ_i-ϵ_p-δ_p,         ℓ_R^-    = ω_ℓ^-δ_p,
ℓ_W^+    = ω_ℓ^ϵ_i-ϵ_p+γ,        ℓ_W^-    = ω_ℓ,

m_R^+    = ω_m ^ϵ_p,         m_R^-    = ω_m,
m_W^+    = ω_m ^ϵ_p-γ,        m_W^-    = ω_m .

It is straightforward to check that with this choice of kinetic rates, the Gibbs free energy difference between the right and wrong pathways is given by $\Delta G = \Delta \mu_R - \Delta \mu_W = \gamma$, with $\Delta\mu_R \equiv \mu_{P_R} - \mu_R$ and $\Delta\mu_W \equiv \mu_{P_W} - \mu_W$. Moreover, the chemical potential difference in the proofreading and upcycling cycles is equal to zero.

Motivated by experiments showing that tRNA discrimination of the CCA-adding enzyme is kinetically controlled <cit.>, we focus here on a forward discrimination strategy, where the kinetic differences are present in the forward rates. This is a choice that pertains in particular to error correction mechanisms used by, e.g., ribosomes <cit.>, where discrimination of cognate and non-cognate aa-tRNA occurs in two phases: initial selection and proofreading. In both ribosomal selection steps, discrimination is based on different stabilities of correct and incorrect codon–anticodon duplexes, which manifests itself in a difference of forward kinetic rates <cit.>.

Similarly, one can opt for discrimination in the reverse rates <cit.>, which leads to qualitatively similar results.

With this choice of rates, the discrimination error achieved simply by binding substrates and creating products is given by the ratio of the Boltzmann weights of the states of the bound enzyme, which simplifies to

\begin{equation}
\label{eq:error_eq}
\eta_{\rm eq} = \frac{1}{1+\me^\gamma}\,.
\end{equation}

We now introduce the shorthand notation $f(x) = 1/(1+\me^x)$, in order to ease notation where necessary. Hence, the error becomes $\eta_{\rm eq} = f(\gamma)$. Solving the master equation,

\begin{equation}
\label{eq:master_eq_ERPR}
\begin{split}
\dv[]{[E']}{t} &= k_R^- [E'R] + k_W^- [E'W] + F ([ER]+[EW])-(k_R^+[R]+k_W^+[W])[E']\\
\dv[]{[E'S]}{t} &= k_S^+[S] [E'] + h_S^- [ES] + \ell_S^-[S][E] - (k_S^- + h_S^+ + \ell_S^+)[E'S]\,,\\
\dv[]{[ES]}{t} &= h_S^+ [E'S] + m_S^+ [S][E] -(F+h_S^- +m_S^-) [ES]\,, \\
\dv[]{[E]}{t} &= \ell_R^+ [E'R] + \ell_W^+ [E'W] + m_R^- [ER] + m_W^- [EW] - \{(\ell_R^- + m_R^+) [R] + (\ell_W^- +m_W^+) [W]\}\, [E]\,,
\end{split}
\end{equation}

for $S\in\{R,\,W\}$ and subsequently normalising yields the steady-state distribution for the occupation probabilities, from which all of the observables can be calculated. While the system (<ref>) is exactly solvable, the complete solution is long and unwieldy and hence we will not give the full expressions for the steady-state solution. However, analytical progress can be made when considering the limit in which the production cycles for both $R$ and $W$ are strongly driven in the forward direction, following pathway $\#1$ in Fig. <ref>. Additionally, we expect that effective proofreading is possible whenever the proofreading cycles are driven in the direction $E'S\rightarrow E+S\rightarrow ES$.

Solving the master equation (<ref>), inserting the steady-state probabilities into (<ref>) and subsequently taking the limit of all the reverse kinetic rates to zero, yields the following expression for the error in the forward driven limit,

\begin{equation}
\label{eq:error_forward_full}
\eta = \frac{(\mathcal{M}-1) \Gamma_R +\Gamma_W \left(1+\mathcal{K} (\Gamma_R -1)\right)}{\mathcal{K} \mathcal{M} \Gamma_R \Gamma_W}\,,
\end{equation}

with $\Gamma_S = 1+\ell_S^+/h_S^+$, $\mathcal{K} = 1+k_R^+/k_W^+$ and $\mathcal{M} = 1+m_R^+/m_W^+$. Substituting the rates (<ref>), the error in this forward driven limit reduces to

\begin{equation}
\label{eq:error_forward}
\eta = f(\delta)f(\gamma)\left\{1+\frac{\me^{\delta-\delta_p}}{\frac{\omega_i}{\omega_\ell} \me^{\epsilon_p} + \me^{-\delta_p}} + \frac{\frac{\omega_i}{\omega_\ell}\me^{\epsilon_p +\gamma}}{\frac{\omega_i}{\omega_\ell} \me^{\epsilon_p} + \me^\gamma}\right\}\,.
\end{equation}

The free parameters that can be optimised are $\omega_i,\,\omega_\ell$ and $\epsilon_p$, so we introduce the (degenerate) variable $x\equiv \frac{\omega_i}{\omega_\ell}\me^{\epsilon_p}$. Essentially, $x$ is the ratio of the forward right transition rate through pathway $\#1$ and the proofreading pathway $\#2$ for a given value of $\delta_p$, i.e., $x=\frac{h_R^+}{\ell_R^+}\me^{-\delta_p}$. The minimal proofreading error $\eta_{\rm min,ERPR}$ can be found by minimising (<ref>) with respect to $x$. This yields

\begin{equation}
\label{eq:error_minimal}
\eta_{\rm min,ERPR} = f(\gamma)f(\delta)\frac{\me^{\gamma+\delta_p} + 2\me^{\gamma + \frac{\delta+\delta_p}{2}}-(1+\me^\gamma + \me^\delta) }{\me^{\gamma+\delta_p}-1}\,,
\end{equation}

which is achieved when $x = x^* \equiv (\me^{\delta/2} - \me^{-\delta_p/2})/(\me^{\delta_p/2} - \me^{\delta/2-\gamma})$. It can be proven (see appendix <ref>) that the minimal error of the energy relay is always smaller than or equal to the minimal MM error <cit.>,

\begin{equation}
\label{eq:error_minimal_MM}
\eta_{\rm min,MM} = f(\max\{\delta,\gamma\})=\frac{1}{1+\me^{\max\{\delta,\gamma\}}}\,.
\end{equation}

To simplify notation, we will define $\eta_E \equiv \eta_{\rm min,\,ERPR}$ and $\eta_M \equiv \eta_{\rm min,\,MM}$ as the minimum error rates in both models. For the sake of completeness, we also give the minimal error in the KPR scheme, i.e.,

\begin{equation}
\label{eq:error_minimal_KPR}
\eta_{K} = f(\max\{\delta,\gamma\}+\gamma+\delta_p)=\frac{1}{1+\me^{\max\{\delta,\gamma\}+\gamma+\delta_p}}\,,
\end{equation}

although care should be taken when directly comparing the minimal errors of KPR and ERPR; the former possesses a proofreading step with the same kinetic discrimination parameter $\delta_p$ as the ERPR but the proofreading occurs from the bound states $ES^*$ and subsequently resets the enzyme to its unbound state, while for the ERPR scheme proofreading occurs from the high-energy bound states $E'S$ and then accesses the free enzyme ground state instead of resetting the system. We make a comparison between the ERPR and KPR in sec. <ref>.

By inspecting the expression for $x^*$, one can show that when $x^* \rightarrow\infty$, the minimal ERPR error becomes equal to the minimal MM error in the kinetic regime $\eta_M = f(\delta)$. For $x^*$, this means that when

\begin{equation}
\label{eq:condition_zero_cost}
\delta = 2\gamma+\delta_p\,,
\end{equation}

the discriminatory mechanism corresponds to pure MM kinetics.

Indeed one can verify that $\gamma = (\delta - \delta_p)/2$ into equation (<ref>), leads to $\eta_{E} = f(\delta) = \eta_M$. The proofreading scheme stops using pathways $\#2$ and $\#3$ altogether for minimal $\eta$, but creates products only through pathway $\#1$, where only the high-energy free enzymatic state $E'$ is used. This can be seen by inspecting $x$, which can only diverge when the ratio of kinetic rates $h_R^+/\ell_R^+$ diverges. At the transition characterised by (<ref>), this divergence is associated with the limits $\ell_R^+\downarrow 0$ and $h_R^+\uparrow \infty$, effectively reducing the scheme to MM kinetics.

To illustrate this transition between proofreading regimes in more detail, let us now turn to the proofreading cost $C$ in the forward limit, using the same rates as before, i.e.,

\begin{equation}
\label{eq:cost_forward}
C = f(\delta)\frac{1+\me^\delta + x(\me^{\delta-\gamma}+\me^{\delta_p})}{\left(1+x\me^{\delta_p}\right)\left(1+x\me^{-\gamma}\right)}\,.
\end{equation}

By eliminating $x$ in equations (<ref>) and (<ref>), it is possible to compute the relationship between the cost and the error in the forward driven system; this calculation is done in the appendix <ref>, resulting in (<ref>). It will turn out that this expression constitutes the optimal trade-off between those two quantities.

For $\eta = \eta_{\rm eq}$, the proofreading cost becomes

\begin{equation}
\label{eq:cost_forward_eq}
C(\eta_{\rm eq}) = \frac{f(\delta)}{f(\delta_p)}\,\frac{(\me^\gamma - \me^\delta)}{(\me^{\gamma+\delta_p}-1)}\,.
\end{equation}

Note that the proofreading cost at $\eta_{\rm eq}$ becomes zero at $\delta=\gamma$, i.e., on the transition to the kinetic discrimination regime <cit.>. When the error is minimal at $x=x^*$, the corresponding proofreading cost becomes

\begin{equation}
\label{eq:cost_forward_minimal}
C(\eta_{E}) = f(\delta)\frac{(\me^{\gamma+\delta_p/2}-\me^{\delta/2}) \left(\me^{\delta/2} + \me^{\delta_p/2}\right) }{\me^{\gamma+\delta_p}-1}\,.
\end{equation}

This minimal proofreading cost can also become zero or negative, the latter of which indicates that the proofreading cycle is being operated in reverse; substrate $S$ is bound to the enzyme $E$ in the ground state and forms a high-energy complex $E'S$. This particular transition will essentially never occur, but nevertheless we have taken the possibility into account by choosing $\ell^\pm_S$ to obey local detailed balance, contrary to the original definition of Hopfield <cit.> and others <cit.>. The minimal cost is smaller than or equal to zero when the bound (<ref>) is fulfilled.

The minimal discrimination errors, $\eta_M$ (red), $\eta_E$ (black) and $\eta_K$ (blue), as a function of the discrimination parameter $\delta$, with $\gamma=2$ and $\delta_p=1$. The three discrimination regimes, ERPR, ERPR+MM and MM, are shown as grey, red and blue shaded areas, respectively. The black dashed line indicates the continuation of $\eta_E$ in the MM region.

In Fig. <ref>, we compare the minimal errors $\eta_E$, $\eta_M$ and $\eta_K$ as functions of $\delta$, with fixed $\gamma=2,\,\delta_p=1$. It can  be seen that increasing $\delta$ heralds a first transition at $\delta = \gamma$, to a proofreading mode where the system can initially make use of MM kinetics in the kinetic discrimination regime, for errors that are higher than the minimal MM error rate. For errors smaller than the minimal MM error rate, the proofreading side chains are used. Therefore, the minimal error rate in this mixed regime is set by the minimal ERPR error rate. A more detailed analysis of this mixed proofreading regime will be performed in Sec. <ref>. The second transition at $\delta = 2\gamma + \delta_p$, set by (<ref>) effectively equates the minimal MM and ERPR errors, after which the MM error is preferred, as a result of $x$ becoming zero and the scheme transitioning fully into the MM regime.

The three minimal errors obey a particular ordering, i.e., $\eta_K \leq \eta_E \leq \eta_M$, see Fig. <ref>. We prove this in the appendix <ref>.

§ PARETO OPTIMAL TRADE-OFFS AND SCALING LAWS

We now study the trade-offs between the different quantities, i.e, $\eta,\,v,\,\Delta\sigma$ and $C$, as a function of the discrimination constants $(\gamma,\delta,\delta_p)$, by means of Pareto optimal fronts. For simplicity, we fix $\gamma=2$, $\epsilon=5$ (in units of $k_B T$) and $\omega = 1$. After choosing particular values for $\delta,\,\delta_p$, the number of remaining variables with respect to which needs to be optimised is equal to six.

To discover the Pareto optimal solutions, we employ a computational approach rooted in multifunction optimisation. Specifically, our methodology involves a thorough traversal of parameter space utilising genetic algorithms, using Matlab's  function <cit.>. We complement the optimisation algorithm with the constraint $\epsilon_p \leq \epsilon_i$, in order to maintain the ordering of the energy states as shown in Fig. <ref>.

Based on the condition (<ref>), we can draw the general proofreading behaviour in the $(\delta,\delta_p)$ plane, see Fig. <ref>(a). For an initial discrimination factor $\delta\leq\gamma$ and $\delta_p\geq0$, i.e., the energetic discrimination regime, the system favours the energy relay to decrease the error fraction (grey shaded area). When $\delta\geq\gamma$, however, the system uses MM kinetics for error rates that are higher than the minimal MM error rate.

When the minimal MM error rate is reached in this regime (red shaded area), the energy relay side chain is activated to achieve an even lower minimal error, given by equation (<ref>). This dual mechanism completely reduces to MM discrimination when $\delta\geq2\gamma+\delta_p$ (blue shaded area).

(a) $(\delta,\delta_p)$ phase space for the ERPR scheme with $\gamma=2$. The three proofreading regimes are shown, together with the $(\delta,\,\delta_p)$ combinations (coloured points) that are studied in more detail in the other panels. (b-f) Projected Pareto fronts onto the $(\Delta\sigma,\eta)$ and $(C,\eta)$ subspaces, for $\delta=1$ (blue), $\delta=\gamma=2$ (purple), $\delta=4$ (orange), $\delta=5$ (green) and $\delta=6$ (gray). The grey full, grey dashed, and red dashed vertical lines indicate respectively analytical predictions for $\eta_{\rm eq}$, $\eta_E$ and $\eta_M$. Orange dashed lines indicate a parametric plot of $C(\eta_E)$ vs. $\eta_E$, where $\delta$ is varied; corresponding orange dots are the $(\eta_E,C(\eta_E))$ values for the chosen parameters.

To find trade-offs between pairs of variables, we numerically marginalise the full four-dimensional objective space of the Pareto front, projecting onto the subspace under scrutiny. We will consider the different trade-offs in the three aforementioned regimes separately. We find that the production speed $v$ in all regimes remains equal to its value of $v=1$ at $\eta_{\rm eq}$, for error values far below $\eta_{\rm eq}$. This signifies that the relation $P_{\rm ER}^s + P_{\rm EW}^s =1$ holds for the optimal trade-off between speed and error. Only close to the minimum error, $\eta_E$, does it drop very sharply to zero, see Fig. <ref> in appendix <ref>. In a non-equilibrium steady state, flux magnitudes, and consequently also the speed, are determined by both maxima and minima in the free energy landscape, corresponding respectively to energy barriers and discrete states <cit.>. Conversely, the error rate, cost and entropy production rate per product are set by ratios of fluxes, which only depend on the energy barriers (kinetic control). As a result, the speed can be decoupled from the trade-off and varied independently by tuning the energy minima, which is, in fact, what the Pareto optimisation achieves. Such decoupling has, e.g., been observed in Escherichia coli isoleucyl-tRNA synthetase <cit.>. Henceforth, we will not consider marginalised trade-offs involving the speed directly, but instead focus on the error-entropy production and error-cost trade-offs in the different regimes, which are shown in Fig. <ref>. We discuss the different regimes and associated trade-offs in the following subsections.

§.§ ERPR regime

Considering now only the marginalised Pareto fronts onto the $(\eta,\Delta\sigma)$ and $(\eta,C)$ subspaces, it becomes clear that the discrimination regime influences the details of those trade-offs, as shown in Fig. <ref>(b-c) for the ERPR regime where $\delta \leq \gamma$. The net preferred flow in the ERPR regime is shown in the inset in Fig. <ref>(a).

For this regime, the proofreading cost $C$ jumps discontinuously from zero to a finite positive value at $\eta_{\rm eq}$. It signifies an abrupt shift in the optimal rate configuration when transitioning from the $\eta \gtrsim \eta_{\rm eq}$ regime to the $\eta \lesssim \eta_{\rm eq}$ regime. Similar behaviour is seen in a model of MM discrimination with dissipative resetting <cit.>, where a resetting cycle is driven by the cycle chemical potential difference, at the cost of increased entropy production. When $\delta$ increases to $\delta=\gamma$, the transition in proofreading cost becomes continuous at $\eta=\eta_{\rm eq}$, see Fig. <ref>(b).

The entropy production rate per product formed increases sharply from zero at $\eta = \eta_{\rm eq}$, where effective discrimination requires no free energy dissipation but relies solely on the difference in Gibbs free energy between the products, to infinity for small errors at $\eta\downarrow\eta_E$, where an infinite amount of free energy dissipation is required to maintain the minimal error rate. At a fixed error rate, increasing the proofreading parameter $\delta_p$ progressively lowers the minimal required proofreading cost. Concomitantly, the minimal entropy production rate is also lowered; a system with a better proofreading discrimination mechanisms requires less free energy to operate.

Based on the expression derived for MM discrimination (see appendix <ref>), we find that close to the minimal error rate $\eta_E$, the entropy production-error trade-off follows a logarithmic scaling law,

\begin{equation}
\label{eq:sigma_eta_scaling}
\Delta\sigma\sim \alpha\,\ln{\left(\frac{1}{\eta-\eta_E}\right)}\,.
\end{equation}

Conversely, the cost-error trade-off is given by the exact relation (<ref>), which asymptotically for $\eta\downarrow\eta_E$ exhibits a square root scaling, i.e.,

\begin{equation}
\label{eq:cost_scaling}
C - C(\eta_E)\sim  - (\eta - \eta_E)^\frac{1}{2}
\end{equation}

In Fig. <ref>, we show the marginalised entropy production-error and cost-error trade-offs (red lines in (a,b)), along with the rescaled marginalised Pareto fronts for some parameter combinations according to equations (<ref>) and (<ref>). Good data collapse is observed for both trade-offs according to the above scaling laws. Linear fits show that in the ERPR regime $\alpha = 3.01\pm0.01$ close to $\eta_{E}$, and that the square root scaling of equation (<ref>) can be retrieved numerically.

(a, b) Projected Pareto fronts onto the $(\eta,\Delta\sigma)$ and $(\eta,C)$ subspaces for the $\gamma =2$, $\delta = 1$ ERPR regime shown in Fig. <ref>, together with the marginalised trade-offs (red lines). Inset in (a): the preferred flow direction (red arrows) of the ERPR regime. In (b), the dashed black lines show the exact expression (<ref>), which coincide perfectly with the numerically marginalised fronts. (c) Entropy production according to the scaling law (<ref>). (d) Cost as a function of $\eta-\eta_E$, showing that for $\eta \gtrsim \eta_E$ the cost scales as $C\sim-(\eta-\eta_E)^\frac{1}{2}$.

Furthermore, in Fig. <ref>(b), we show that the marginalised cost-error trade-off obtained numerically from the Pareto front (red lines) coincides exactly with the analytically computed cost function (<ref>) (dashed black line, see appendix <ref>), where the cost at $\eta_{\rm eq}$ and the cost at the minimal error $\eta_{E}$ are given by respectively equation (<ref>) and (<ref>).

From this analysis, it becomes clear that the scaling behaviour of the entropy production as a function of the error rate is universal for the ERPR regime. The only effect of the parameters $\gamma,\,\delta,\,\delta_p$ is to tune the cut-off of the scaling laws.

§.§ ERPR + MM regime

When $\gamma < \delta\leq2\gamma+\delta_p$, a new region emerges on the Pareto front: for $\eta\geq\eta_M$, the scheme does not use the proofreading side reactions for errors in the range $[\eta_M,\,\eta_{\rm eq}]$, since discrimination only occurs at the MM error rate. When the minimal MM error rate $\eta_M$ is reached, however, the proofreading cycle is used to push the error rate even lower. At this instance, the minimal cost required continuously increases from $C = 0$ at $\eta = \eta_{M}$ to $C = C(\eta_E)$ at $\eta = \eta_{E}$. A similar switching exists between different mechanisms for conformationally fluctuating enzymes with multiple parallel reaction pathways <cit.>. For error rates lower than $\eta_M$, the entropy production again decreases with increasing $\delta_p$. Conversely, for error rates higher than $\eta_M$, increasing $\delta_p$ in fact increases the entropy production, see Fig. <ref>(d).

(a, b) Projected Pareto fronts onto the $(\eta,\Delta\sigma)$ and $(\eta,C)$ subspaces for the $(\delta,\delta_p) = (4,2)$ and $(5,2)$ discrimination parameters in the ERPR + MM regime shown in Fig. <ref>, together with the marginalised trade-offs (red lines). Red dashed vertical lines indicate $\eta_{\rm M}$. In (b), the dashed black lines show the exact expression (<ref>), which coincide perfectly with the numerically marginalised fronts. (c) Entropy production according to the scaling law (<ref>). The cusps in the fronts indicate the transition from MM kinetics to ERPR. (d) Cost as a function of $\eta-\eta_E$, showing that for $\eta \gtrsim \eta_E$ the cost scales as $C\sim-(\eta-\eta_E)^\frac{1}{2}$.

The entropy production-error and cost-error trade-offs follow the same scaling laws as before, i.e., equation (<ref>) and (<ref>), with $\alpha$ ranging from $\alpha \approx 1$ for $\eta \lesssim \eta_{\rm eq}$ to $\alpha \approx 3$ for $\eta\downarrow\eta_E$. Details are shown in Fig. <ref>. The entropy production-error trade-off exhibits a phase transition at $\eta = \eta_{\rm M}$, where the optimal proofreading protocol changes <cit.>.
Similar phase transitions were observed for the Pareto optimal trade-off between the standard deviation and the mean of the dissipated work in a quantum dot <cit.> and for the error-dissipation trade-off for a discriminatory network with correlations <cit.>.

§.§ MM regime

Increasing $\delta$ or lowering $\delta_p$ to cross the boundary where $\delta = 2\gamma+\delta_p$ induces a transition to a fully MM discriminatory regime, where the proofreading kinetic parameter $\delta_p$ plays no role anymore in setting the minimal error rate. It is now fully determined by $\eta_M$ in the kinetic regime, which is a function of $\delta$ only. The proofreading side reaction is now never used in a useful fashion, since it cannot decrease the error any further. Increasing $\delta_p$ now has the adverse effect of raising the entropy production for a fixed error rate. In this regime, the entropy production per product increases smoothly from $\Delta\sigma = 0$ at $\eta=\eta_{\rm eq}$ to infinity at $\eta = \eta_{M}$, as is shown in Fig. <ref>(d-e-f). The average flow direction in the MM regime is shown in the inset in Fig. <ref>(a), where red arrows indicate pairs of transitions that occur more frequently.

The entropy production-error trade-off once again follows the same scaling laws as before, i.e., equation (<ref>), with $\alpha$ decreasing from $\alpha \approx 1$ close to $\eta \approx \eta_{\rm eq}$. For $\eta \downarrow \eta_{M}$, $\alpha$ increases again to $\alpha\approx 1$. The proofreading side chain is not used and the minimal cost is zero everywhere, so we do not show the cost-error trade-off.

Relation between the entropy production per product $\Delta\sigma$ and the error rate $\eta$ in the MM regime, with $\delta = 6$ in (a). Red lines in (a) are numerically marginalised trade-off curves, which are replicated in (b) to show data scaling following equation (<ref>). Inset in (a): the preferred flow direction (red arrows) of the MM regime.

§ ERPR VERSUS KPR

Considering the mechanisms of the KPR and the ERPR, one can wonder about the realm of applicability of both discriminatory schemes. Comparing eq. (<ref>) and eq. (<ref>) for ERPR and KPR, respectively, it is clear that KPR always achieves the lowest minimal error rate for equal $\delta$, $\delta_p$ and $\gamma$. However, in order to make a fair comparison between the two schemes, we implement the KPR network as illustrated in Fig. <ref>(b) with the associated free energy landscape shown in Fig. <ref>. The proofreading rates $K_S^\pm$ in KPR are taken to be similar to the rates $\ell_S^\pm$ in the ERPR network, i.e.,

K_R^+    = ω_ℓ^ϵ_p-δ_p        K_R^-    = ω_ℓ^-δ_p

K_W^+    = ω_ℓ^ϵ_p+γ        K_W^-    = ω_ℓ .
We also remove the constraint that $\epsilon_p \leq \epsilon_i$. Since the main difference between the two schemes is the proofreading transition, we fix all other rates to be the same as in the ERPR, as given by (<ref>). As a result of the different modes of proofreading of both schemes, the proofreading parameter $\delta_p$ cannot be directly used in a similar fashion in both schemes, so we keep it as a free parameter that can be optimised in the Pareto algorithm. Conversely, since $\gamma$ and $\delta$ retain their physical interpretation of binding energy difference and initial kinetic binding barrier, respectively, they constitute the tuneable parameters that are common for both discriminatory schemes, and can be used for direct comparison. We again fix $\gamma=2$, $\epsilon=5$ and $\omega = 1$, such that $\delta$ is the only remaining control parameter. Additionally, we require that the value of the proofreading parameter is bounded by $\delta_p \leq \delta_{p,\rm max} = 5$, in order to maintain numerical accuracy and to avoid the minimal KPR error from becoming too small, since it can be seen from eq. (<ref>) that $\eta_{K}\downarrow 0$ if $\delta_p$ can be increased indefinitely.

By varying $\delta$, the entropy production rate for a fixed error rate $\eta$ can be tuned; increasing $\delta$ leads to decreasing $\Delta\sigma$ for both the KPR and ERPR. The rate at which this decrease happens, however, is different for both schemes. For low values of $\delta$, there exists a critical error rate $\eta_c$ above which the ERPR scheme produces a smaller amount of entropy than the KPR. This effectively makes the energy relay a more effective proofreading scheme when the error rate is in the range $\eta\in[\eta_c,\eta_{\rm eq}]$.

Comparison between the ERPR (red) and KPR (black) proofreading schemes, with $\gamma = \delta = 2$ and $\delta_p \in [0,5]$. Vertical lines correspond to the respective minimal error rates of both schemes. Inset: Critical error rate $\eta_c$ above which $\Delta\sigma_{\rm KPR} \geq \Delta\sigma_{\rm ERPR}$, as a function of $\delta$. The error $\eta_{\rm eq}$ is indicated by a dashed line.

In Fig. <ref>, the error-entropy production trade-offs for both proofreading schemes are shown together. While the minimal errors differ in over two order of magnitude, the ERPR outperforms the KPR in the low-dissipation regime. The inset shows the critical error rate $\eta_c$ where KPR becomes energetically favourable to ERPR for a given value of $\delta$. When $\delta$ is zero, $\eta_c$ lies very close to $\eta_{\rm eq}$, and therefore KPR essentially always outperforms ERPR. However when $\delta$ increases towards $\delta = \gamma$ the error range wherein the ERPR is the preferable proofreading mechanism increases. This effect quickly vanishes when the system is not in the full ERPR regime $(\delta\leq\gamma)$ anymore; when $\delta \gtrsim \gamma$, the critical error $\eta_c$ sharply increases to $\eta_{\rm eq}$, such that the KPR scheme is the most effective for all error rates. This behaviour is robust against changing the range in which $\delta_p$ is allowed to vary. No noticeable changes to the inset of Fig. <ref> were observed when changing the maximum allowed value of $\delta_p$ in the range $\delta_{p,\rm max} \in [3,7]$.

§ CONCLUSIONS

We have done an extensive thermodynamic analysis of Hopfield's energy relay proofreading scheme. This analysis reveals several crucial new insights that might have profound biological implications. Firstly we found that the energy-relay scheme consists of three distinct operational regimes: i) an energy relay regime, wherein discrimination occurs solely on the basis of the energy-relay mechanism, ii) a mixed relay-MM regime, where the discrimination can be performed by means of MM kinetics, until the minimal error is reached, after which the relay is activated and iii) a Michaelis-Menten regime, where the relay is not used and the mechanism reduces to known MM kinetics. Remarkably, each of these regimes has the same logarithmic divergence in the entropy production when the error rate approaches its minimal value.

Surprisingly, we also found that the mixed regime features a phase transition, where the optimal kinetic rates change drastically. It would therefore be interesting to study the biological and evolutionary consequences of this type of phase-transitions in the Pareto front. Furthermore, it would be interesting to see whether other biological systems have similar types of phase-transitions.

Finally, we addressed the question of whether ERPR can thermodynamically outperform KPR in any regime. The answer to this turns out to be `yes'. Although it is generally possible to reach lower error rates with KPR in the high-dissipation limit, ERPR reaches lower error-rates when the amount of dissipation is limited. It would be interesting to see whether, e.g., the discrimination mechanism found for the CCA-adding enzyme shows this type of behaviour.

We thank S. Mondal and S. Pigolotti for their detailed comments on the use of the optimisation algorithm.

J.B. is funded by the European Union’s Horizon Europe framework under the Marie Skłodowska-Curie grant agreement No. 101104602 `STBR'. K.P. is funded by the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No. 101064626 `TSBC’, and from the Novo Nordisk Foundation (grant No. NNF18SA0035142 and NNF21OC0071284).

§ COMPARISON OF THE MINIMAL ERROR RATES

§.§ Energy relay – Michaelis-Menten

To see that the ERPR scheme leads to a lower error than the MM scheme, we need to prove that $\eta_{E}\leq\eta_{M}$ for both the energetic and kinetic discrimination regimes. Let us start with the energetic regime, i.e., $\delta\leq\gamma$, where the MM error rate is equal to $\eta_{M} = 1/(1+\me^{\gamma})$. We need to prove that the following inequality holds:

\begin{equation}
\frac{1}{1+\me^\gamma} \geq \frac{\me^{\gamma+\delta_p} + 2\me^{\gamma + \frac{\delta+\delta_p}{2}}-1-\me^\gamma - \me^\delta}{(1+\me^\gamma) (1+\me^\delta)(\me^{\gamma+\delta_p}-1)} = \eta_{E}\,.
\end{equation}

Since the denominator on the right-hand side of the inequality is strictly positive, we can cancel some terms, and rearrange the remaining ones as follows

\begin{equation}
\me^{\gamma+\delta+\delta_p}\geq 2\me^{\gamma+\frac{\delta+\delta_p}{2}}-\me^\gamma\,.
\end{equation}

After rearranging the terms on one side and completing the square, the inequality reduces to

\begin{equation}
\me^\gamma \left(1-\me^{\frac{\delta+\delta_p}{2}}\right)^2\geq0\,,
\end{equation}

which is true for all values of $\gamma,\,\delta,\,\delta_p$. In the kinetic discrimination regime where $\delta\geq\gamma$, the MM error rate is $\eta_{M} = 1/(1+\me^{\delta})$ and the inequality between the error rates becomes

\begin{equation}
\eta_{M} = \frac{1}{1+\me^\delta} \geq \frac{\me^{\gamma+\delta_p} + 2\me^{\gamma + \frac{\delta+\delta_p}{2}}-1-\me^\gamma - \me^\delta}{(1+\me^\gamma) (1+\me^\delta)(\me^{\gamma+\delta_p}-1)} = \eta_{E}\,.
\end{equation}

Following the same procedure of rearranging the terms and completing the square, the inequality can be written as follows:

\begin{equation}
\left(\me^\frac{\delta}{2}-\me^{\gamma+\frac{\delta_p}{2}}\right)^2\geq0\,,
\end{equation}

which is once again always true, proving our claim.

§.§ Energy relay – Kinetic proofreading

Showing that $\eta_{K} \leq \eta_{E}$ is slightly trickier than the previous comparison. We again proceed with showing the inequality first in the energetic regime. Here, we need to show that the following holds:

\begin{equation}
\frac{1}{1+\me^{2\gamma+\delta_p}} \leq \frac{\me^{\gamma+\delta_p} + 2\me^{\gamma + \frac{\delta+\delta_p}{2}}-1-\me^\gamma - \me^\delta}{(1+\me^\gamma) (1+\me^\delta)(\me^{\gamma+\delta_p}-1)}\,.
\end{equation}

Collecting and factoring both expressions to the l.h.s. of the equation, we simplify to

\begin{equation}
\me^\frac{\delta}{2} +2 \me^\frac{\delta_p}{2} - \me^{\frac{\delta}{2}+\delta_p} - 2\me^{\gamma+\delta_p} \left(\me^\frac{\delta}{2}+\sinh{\left(\frac{\delta_p}{2}\right)}\right) \leq 0\,,
\end{equation}

which can be rewritten in the following compact form:

\begin{equation}
\me^\gamma \geq \frac{2 \me^\frac{\delta_p}{2}+\me^\frac{\delta}{2}-\me^{\frac{\delta}{2}+\delta_p}}{2 \me^{\delta_p} \left(\me^\frac{\delta}{2}+\sinh{\left(\frac{\delta_p}{2}\right)}\right)}\,.
\end{equation}

It can now be seen that the l.h.s. is only a function of $\gamma$, which is bounded from below by unity. The r.h.s., however, depends on both $\delta$ and $\delta_p$. It can be checked that the r.h.s. exhibits a boundary global maximum at $\delta = \delta_p = 0$, which is equal to unity. Hence, since the l.h.s. is bounded from below by unity and the r.h.s. from above, $\eta_K \leq \eta_E$ is proven.

For the kinetic regime, we follow the same procedure. Starting from

\begin{equation}
\frac{1}{1+\me^{\gamma+\delta+\delta_p}} \leq \frac{\me^{\gamma+\delta_p} + 2\me^{\gamma + \frac{\delta+\delta_p}{2}}-1-\me^\gamma - \me^\delta}{(1+\me^\gamma) (1+\me^\delta)(\me^{\gamma+\delta_p}-1)}\,,
\end{equation}

we simplify to the following compact form

\begin{equation}
\me^\gamma \geq \frac{\me^\delta + \me^\frac{\delta+\delta_p}{2}(2+\me^\delta)}{1+2 \me^\delta +\me^\frac{\delta+\delta_p}{2}}\me^{-\delta_p}\,,
\end{equation}

where, once again, the l.h.s. only contains $\gamma$. The r.h.s., however, is now increasing as a function of $\delta$ and decreasing as a function of $\delta_p$. Since at $\delta = 2\gamma + \delta_p$, $\eta_E = \eta_M$, the relevant global boundary maximum of the r.h.s. is located at $(\delta,\delta_p) = (2\gamma,0)$, such that the condition on $\gamma$ reduces to

\begin{equation}
\me^\gamma \geq \frac{2+\me^\gamma + \me^{2\gamma}}{1+\me^\gamma + 2\me^{2\gamma}}\me^\gamma\,,
\end{equation}

which simply yields the trivial condition $\me^{2 \gamma} \geq 1$, proving our claim.

§ COST-ERROR TRADE-OFF

The Pareto optimal proofreading cost $C$ as a function of the error rate $\eta$ is given by solving for $x$ in equation (<ref>) and subsequently plugging the result into equation (<ref>). This then becomes the following:

\begin{equation}
\label{eq:cost_error_tradeoff}
\begin{split}
C(\eta) &= \frac{4 \me^{\gamma+\delta_p} f^{-2}(\gamma)\left(1-\eta f^{-1}(\delta)\right)^2}{\left(z+f^{-1}(\delta) -2f^{-1}(2\gamma+\delta_p)-\sqrt{(\eta-\eta_+)(\eta-\eta_-)}\right)\left(z-f^{-1}(\delta)+\sqrt{(\eta-\eta_+)(\eta-\eta_-)}\right)}\times\\
&\left(1-\frac{f(\delta) f(\gamma)}{2 f(\delta-\gamma-\delta_p) (1-\eta f^{-1}(\delta))}\left(z+f^{-1}(\delta)+2(f^{-1}(\gamma+\delta_p)-1)\right)\right)\,,
\end{split}
\end{equation}

\begin{equation}
\label{eq:error_roots}
\eta_\pm = \frac{f^{-1}(\gamma+\delta_p)-f^{-1}(\delta)-f^{-1}(\gamma)\pm 2\me^{\gamma + \frac{\delta+\delta_p}{2}}}{\me^{\gamma+\delta_p}-1} f(\gamma) f(\delta)\,,
\end{equation}

\begin{equation}
\label{eq:z}
z(\eta) = \left(1-\me^{\gamma+\delta_p}\right) + f^{-1} \left(1-\eta f^{-1}(\delta) \left(1-\me^{\gamma+\delta_p}\right)\right)\,.
\end{equation}

§ SCALING OF THE ENTROPY PRODUCTION-ERROR TRADE-OFF

For a simple MM scheme with only one intermediate bound state, as in Fig. <ref>(a), the trade-off between the error and entropy production rate can be found analytically in closed form. The transition matrix ${\bf \Gamma}$ is given by

\begin{equation}
\label{eq:matrix_MM}
{\bf \Gamma} = \begin{pmatrix}
-(k_R^- + F) & k_R^+ & 0 \\
k_R^- + F& -(k_R^+ + k_W^+) & k_W^- + F \\
0 & k_W^+ & -(k_W^- + F)\,,
\end{pmatrix}
\end{equation}

with kinetic rates given by equation (<ref>). The error rate and entropy production rate per product are given by

\begin{equation}
\label{eq:MM_error_rate_full}
\eta = \frac{(k_R^- + F) k_W^+}{(k_R^- + F) k_W^+ + (k_W^- + F) k_R^+}\,.
\end{equation}

Solving for $F$ and inserting in the expression for the entropy production per product, given by equation (<ref>), the relation between $\eta$ and $\Delta\sigma$ is given by

\begin{equation}
\label{eq:MM_entropy_full}
\begin{split}
\Delta\sigma &= \eta \ln{\left(\frac{k_W^+}{k_W^-}\frac{(k_R^- - k_W^-)  (1-\eta)}{\eta (k_R^+ + k_W^+) -k_W^+}\right)} \\
&+ (1-\eta) \ln{\left(\frac{k_R^+}{k_R^-}\frac{(k_R^- - k_W^-)  \eta}{\eta (k_R^+ + k_W^+) -k_W^+}\right)}\,.
\end{split}
\end{equation}

Inserting the expression for the kinetic rates based on the free energy landscape and rewriting results in the following

\begin{equation}
\Delta\sigma = \eta \ln{\left(\frac{1-\eta}{1-\eta_{\rm eq}}\frac{\eta_{\rm eq}}{\eta}\right)} + \ln{\left(\frac{\eta_{\rm eq}-\eta_M}{\eta-\eta_M}\frac{\eta}{\eta_{\rm eq}}\right)}\,,
\end{equation}

such that for $\eta \downarrow \eta_M$, the entropy production rate scales logarithmically as

\begin{equation}
\Delta\sigma\sim \ln{\left(\frac{1}{\eta-\eta_M}\right)}\,.
\end{equation}

As a result, when the amplitude of the scaling equals unity, the discriminatory scheme functions as a MM discriminatory network. Deviations in the amplitude signify non-MM behaviour.

§ SPEED-ERROR TRADE-OFF

Fig. <ref> shows the speed-error trade-off for $\delta = 2$. It can be seen that the speed completely decouples from the error, for all values of $\eta$, and steeply drops to zero at $\eta = \eta_E$.

Speed-error trade-off for $\delta = 2$ and $\delta_p = 0$ (pink), $\delta_p = 1$ (purple). The black lines show the marginalised trade-off, indicating that the speed decouples from the error. Dashed vertical lines indicate the minimal error $\eta_E$.