Distance 2-restricted optimal pebbling in cycles

1.   Introduction

Let $G$ be a graph. A distribution $\delta$ of $G$ is a mapping from $V(G)$ to the set of nonnegative integers. For each vertex $v\in V(G)$, $\delta(v)$ denotes the number of pebbles distributed to $v$. A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. Let $\delta$ be a distribution of $G$, and let $H$ be an induced subgraph of $G$. For convenience, we use $|\delta(H)|$ to denote the number of pebbles distributed onto the vertices of $H$. For each vertex $v\in V(H)$, we use $m(\delta, H, v)$ to denote the maximum number of pebbles that can be moved to $v$ from the vertices of $H$ by using pebbling moves.

Given a positive integer $d$ and a distribution $\delta$ of $G$, if we can move pebbles to any target vertex $v$ in $G$ only from the vertices in the set $N_d[v] = \{u\in V(G):d(u, v)\le d\}$ by pebbling moves, where $d(u, v)$ is the distance between $u$ and $v$, then such a graph pebbling is said to be distance $d$-restricted. We use $m(\delta, d, v)$ to denote the maximum number of pebbles that can be moved to $v$ only from the vertices in the set $N_d[v]$. That is, $m(\delta, d, v) = m(\delta, H, v)$, where $H$ is a subgraph of $G$ induced by $N_d[v]$. A distribution $\delta$ of a graph $G$ is $(d, t)$-solvable if $m(\delta, d, v)\geq t$ for each vertex $v$ of $G$. The optimal $(d, t)$-pebbling number of $G$, $\pi^*_{(d, t)}(G)$, is the minimum number of pebbles needed so that there is a $(d, t)$-solvable distribution of $G$. A distribution $\delta$ of $G$ is said to be optimal $(d, t)$-solvable if it is $(d, t)$-solvable and $|\delta(G)| = \pi^*_{(d, t)}(G)$. When $d$ is not less than the diameter of $G$, the subgraph induced by $N_d[v]$ is $G$ itself. In this situation, $\pi^*_{(d, 1)}(G) = \pi^*(G)$, which is known as the optimal pebbling number of $G$, see ^{[2,5,7,8,9,11]} for references. Moreover, $\pi^*_{(d, t)}(G) = \pi^*_t(G)$, which is the optimal $t$-pebbling number, see ^[12,14] for references.

2.   Preliminaries

In 2018, the distance-restricted graph pebbling was first proposed by Chen and Shiue ^[4], and they showed that $\pi^*_{(2, 2)}(C_3) = 4$ and $\pi^*_{(2, 2)}(C_n) = n$ for all $n\ge 4$. In 2020, Shiue ^[13] studied distance 1-restricted pebbling in cycles and obtained the following result.

Theorem 2.1. ^[13] Let $C_n$ be an $n$-cycle, $n\ge 3$. Then

In ^[13], Shiue also showed that if $G$ is an $r$-regular graph of order $n$ with girth at least 5 and $t$ is a multiple of $r^2+r+4$, then $\pi^*_{(2, t)}(G) = \frac{4nt}{r^2+r+4}$. Since an $n$-cycle is $2$-regular, we have the following.

Corollary 2.1. ^[13] Let $C_n$ be an $n$-cycle. If $n\ge 5$, then $\pi^*_{(2, 10k)}(C_n) = 4nk$ for each positive integer $k$.

The conclusion of Corollary 2.1 gives the recurrence relation $\pi^*_{(2, 10k)}(C_n) = \pi^*_{(2, 10k-10)}(C_n)+4n = \pi^*_{(2, 10k-10)}(C_n)+\pi^*_{(2, 10)}(C_n)$ for $k\ge 2$. Hence, we are interested in the following problem.

Problem 1. For $n\ge 5$ and $t\ge 11$, determine the values of $t$ that satisfy the recurrence relation

It is easy to see that for any graph $G$ and any two positive integers $t_1$ and $t_2$, $\pi^*_{(2, t_1+t_2)}(G)\leq \pi^*_{(2, t_1)}(G)+\pi^*_{(2, t_2)}(G)$.

Usually, the equality does not hold. For example, $\pi^*_{(2, 2)}(C_6) = 6 < 8 = \pi^*_{(2, 1)}(C_6)+\pi^*_{(2, 1)}(C_6)$.

In this article, we mainly study the distance $2$-restricted pebbling in cycles. Note that the diameter of $C_3$ is equal to one. This implies that $\pi^*_{(2, t)}(C_3) = \pi^*_ t(C_3) = \pi^*_{(1, t)}(C_3)$, see Theorem 2.1. As $C_3 = K_3$, an alternative result about $\pi^*_ t(C_3)$ can be seen in ^[12]. Regarding the research on $\pi^*_ t(C_n)$, readers can refer to ^[14]. Note that the authors in ^[14] have only given an upper and a lower bound for $\pi^*_t(C_n)$ when $n\ge 4$ and $t\ge 3$. In this article, we show that for $t\ge 13$ and $n\ge 6$, $\pi_{(2, t)}^*(C_n) = \pi_{(2, t-10)}^*(C_n)+4n$ in Section 2 and completely determine the exact value of $\pi^*_t(C_n)$ for $n = 4, 5$, and $t\ge 1$ in Sections 4 and 5, respectively.

3.   Main results

Throughout the rest of this article, let $C_n = v_0, v_1, \cdots, v_{n-1}, v_0$ be an $n$-cycle, $n\ge 3$, and all subscripts referring to the vertices of the cycle $C_n$ will be interpreted modulo $n$. We write "$a$ mod $b$" to denote the remainder when $a$ is divided by $b$. For convenience, we use "$[\ell_1, \ell_2]$" to denote the set of all integers between $\ell_1$ and $\ell_2$ and, if $\delta$ is a distribution of pebbles on $C_n$, we use $\langle x_0, x_1, \cdots, x_{n-1} \rangle$ to denote $\delta$, where $x_i = \delta(v_i)$. Thus, $|\delta(C_n)| = \sum_{i = 0}^{n-1}x_i$. Note that the diameter of $C_n$ is not more than two for $3\le n\le 5$. It follows that $\pi^*_{(2, t)}(C_n) = \pi^*_ t(C_n)$ for $3\le n\le 5$. So we only consider the case when $n\ge 6$ in this section. For $n\ge 6$, and for $i\in [0, n-1]$,

The following proposition is an important key for solving Problem 1.

Proposition 3.1. For $t\ge 11$ and $n\ge 6$, if there exists an optimal $(2, t)$-solvable distribution $\delta = \langle x_0, x_1, \cdots, x_{n-1} \rangle$ of $C_n$ such that $x_i\ge 4$ for $i\in [0, n-1]$, then $\pi_{(2, t)}^*(C_n) = \pi_{(2, t-10)}^*(C_n)+4n$.

Proof. Assume that $t\ge 11$ and $n\ge 6$. By Corollary 2.1, we have $\pi^*_{(2, 10)}(C_n) = 4n$. It follows that

Thus,

Assume that $\delta = \langle x_0, x_1, \cdots, x_{n-1} \rangle$ is an optimal $(2, t)$-solvable distribution of $C_n$ with $x_i\ge 4$ for all $i\in [0, n-1]$. Then let $\delta' = \langle y_0, y_1, \cdots, y_{n-1} \rangle$ be a distribution of $C_n$ such that $y_i = x_i-4$ for $i\in [0, n-1]$. Clearly,

To complete the proof, it is left to show that $\delta'$ is $(2, t-10)$-solvable. For $i\in [0, n-1]$, by $(3.1)$, we have

Thus, $\delta'$ is $(2, t-10)$-solvable, and we have the proof.

Proposition 3.1 gives a sufficient condition for satisfying the recurrence relation in Problem 1. Now, we will find the values of $t$ that satisfy the assumption of the statement in Proposition 3.1.

Let $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ be a $(2, t)$-solvable distribution of $C_n$ with $n\ge 6$. Consider any subpath

in $C_n$, for some $j\in [0, n-1]$. When $6\le n\le 10$, the subpath is the cycle $C_n$. We let $n = 10-k$, where $0\le k \le 4$. Then the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, k]$. For example, if $n = 8$, then $v_{j+5} = v_{j-3}$, $v_{j+4} = v_{j-4}$, and $v_{j+3} = v_{j-5}$. By $(3.1)$, we have

It follows that

Without loss of generality, we can assume that

where $r$ is a nonnegative integer. Then we have

It follows that

and

By (3.1)–(3.5), we have the following four facts:

Fact 1.

Fact 2.

Fact 3.

Fact 4.

Fact 5. If $x_{j-2}\ge 8$ and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+2$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8$, $y_{j-3} = x_{j-3}+4$, and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-3, j]$, then $|\delta'(C_n)| = |\delta(C_n)|$, $m(\delta', 2, v_{j-2})\ge m(\delta, 2, v_{j-2})-5$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-2\}$.

Proof. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. If $n\ge 11$, then the vertices

are all distinct. Otherwise, $6\le n \le 10$. Let $n = 10-k$, where $0 \le k \le 4$. Then, the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, 4]$. By (3.1), it is easy to see that $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-2, j-1\}$. So, we only need to check $m(\delta', 2, v_{j-2})$ and $m(\delta', 2, v_{j-1})$. Since $n\ge 6$, $v_i\notin \{v_{j-3}, v_{j-2}, v_{j-1}, v_j\}$ for $i\in \{j-4, j+1\}$. By (3.1), we have

and

Fact 6. If $x_{j-2}\ge 4$ and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+1$, $y_{j-1} = x_{j-1}+1$, $y_{j-2} = x_{j-2}-4$, $y_{j-3} = x_{j-3}+2$ and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-3, j]$, then $|\delta'(C_n)| = |\delta(C_n)|$, $m(\delta', 2, v_{j-2})\ge m(\delta, 2, v_{j-2})-3$, $m(\delta', 2, v_{j-1})\ge m(\delta, 2, v_{j-1})-1$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-1, j-2\}$.

Proof. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. If $n\ge 11$, then the vertices

are all distinct. Otherwise, $6\le n \le 10$. Let $n = 10-k$, where $0 \le k \le 4$. Then the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, 4]$. By (3.1), it is easy to see that $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-2, j-1\}$. Now, we only need to check $m(\delta', 2, v_{j-2})$ and $m(\delta', 2, v_{j-1})$. Since $n\ge 6$, $v_i\notin \{v_{j-3}, v_{j-2}, v_{j-1}, v_j\}$ for $i\in \{j-4, j+1\}$. By (3.1), we have

and

By using Eq (3.1) to check, we can obtain Facts 7 and 8.

Fact 7. If $x_{j-1}\ge 4$ and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+2$, $y_{j-1} = x_{j-1}-4$, $y_{j-2} = x_{j-2}+2$, and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-2, j]$, then $|\delta'(C_n)| = |\delta(C_n)|$, $m(\delta', 2, v_{j-1}) = m(\delta, 2, v_{j-1})-2$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-1\}$.

Fact 8. If $x_{j-1}\ge 2$ and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+1$, $y_{j-1} = x_{j-1}-2$, $y_{j-2} = x_{j-2}+1$, and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-2, j]$, then $|\delta'(C_n)| = |\delta(C_n)|$, $m(\delta', 2, v_{j-1})\ge m(\delta, 2, v_{j-1})-2$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-1\}$.

Fact 9. If $x_{j-1}$ and $x_{j+1}$ are both odd, and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+2$, $y_{j-1} = x_{j-1}-1$, $y_{j+1} = x_{j+1}-1$, and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-1, j, j+1]$, then $|\delta'(C_n)| = |\delta(C_n)|$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]$.

Proof. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. If $n\ge 11$, then the vertices

are all distinct. Otherwise, $6\le n \le 10$. Let $n = 10-k$, where $0 \le k \le 4$. Then, the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, 4]$. By (3.1), it is easy to see that $m(\delta', 2, v_i) = m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-3, j-2, j-1, j, j+1, j+2, j+3\}$. So, we only need to check $m(\delta', 2, v_i)$ for $i\in \{j-3, j-2, j-1, j, j+1, j+2, j+3\}$. Note that $x_{j-1}$ and $x_{j+1}$ are both odd. It follows that $\lfloor (x_{j-1}-1)/2\rfloor = \lfloor x_{j-1}/2\rfloor$ and $\lfloor (x_{j+1}-1)/2\rfloor = \lfloor x_{j+1}/2\rfloor$. Since $n\ge 6$, $v_i\notin \{v_{j-1}, v_j, v_{j+1}\}$ for $i\in \{j-4, j-3, j-2, j+2 \}$. By using (3.1) to check, we can verify that $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in \{j, j-1, j-2\}$. For the value of $m(\delta', 2, v_{j-3})$, if $n\ge 7$, then $v_i\notin \{v_{j-1}, v_j, v_{j+1}\}$ for $i\in \{j-5, j-4, j-3, j-2\}$, and

Otherwise, $n = 6$, and hence $v_{j-5} = v_{j+1}$; then we have

By a similar argument as above, we also have $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in \{j+1, j+2, j+3\}$.

Fact 10. If $x_{j-1}$ and $x_j$ are both odd, and $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ is a distribution of $C_n$ such that $y_j = x_j+1$, $y_{j-1} = x_{j-1}-1$, and $y_i = x_i$ for $i\in [0, n-1]\setminus [j-1, j]$, then $|\delta'(C_n)| = |\delta(C_n)|$, $m(\delta', 2, v_{j-1})\ge m(\delta, 2, v_{j-1})-1$ and $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-1\}$.

Proof. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. If $n\ge 11$, then, the vertices

are all distinct. Otherwise, $6\le n \le 10$. Let $n = 10-k$, where $0 \le k \le 4$. Then the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, 4]$. By (3.1), it is easy to see that $m(\delta', 2, v_i) = m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-3, j-2, j-1, j, j+1, j+2\}$. So, we only need to check $m(\delta', 2, v_i)$ for $i\in \{j-3, j-2, j-1, j, j+1, j+2\}$. Note that $x_{j-1}$ and $x_{j}$ are both odd. It follows that $\lfloor (x_{j-1}-1)/2\rfloor = \lfloor x_{j-1}/2\rfloor$ and $\lfloor (x_{j}+1)/2\rfloor = \lfloor x_{j}/2\rfloor+1$. Since $n\ge 6$, $v_i\notin \{v_{j-1}, v_j\}$ for $i\in \{j-4, j-3, j-2, j+1, j+2 \}$. By using (3.1) to check, we can verify that $m(\delta', 2, v_{j-1})\ge m(\delta, 2, v_{j-1})-1$ and $m(\delta', 2, v_j)\ge m(\delta, 2, v_j)$. For the value of $m(\delta', 2, v_{j-2})$, $v_i\notin \{v_{j-1}, v_j\}$ for $i\in \{j-4, j-3, j-2\}$, and

For the value of $m(\delta', 2, v_{j-3})$, $v_i\notin \{v_{j-1}, v_j\}$ for $i\in \{j-5, j-4, j-3, j-2\}$, and

By a similar argument as above, we also have $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in \{j+1, j+2\}$.

Lemma 3.1. For $t\ge 13$ and $n\ge 6$, there exists an optimal $(2, t)$-solvable distribution $\delta$ of $C_n$ such that $\delta(v)\ge 1$ for each vertex $v$ of $C_n$.

Proof. Let $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ be an optimal $(2, t)$-solvable distribution of $C_n$. Suppose that there exists a vertex $v_j$, $j\in [0, n-1]$, with $\delta(v_j) = x_j = 0$. It suffices to show that there exists a $(2, t)$-solvable distribution $\delta'$ of $C_n$ such that $\delta'(v_j)\ge 1$ and $\delta'(v_k)\ge 1$ or $\delta'(v_k)\ge x_k$ for $k\in [0, n-1]\backslash\{j\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$. By (3.1), we have

Without loss of generality, we can assume that $\lfloor x_{j-2}/2\rfloor+x_{j-1} = t-x_j+r$, where $r$ is a nonnegative integer. This implies that (3.2)–(3.5) are valid. Now, we will modify the distribution of pebbles on the vertices in $\{v_i|i\in [j-3, j+3]\}$ if necessary. Let $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ be a distribution of $C_n$ such that $y_i = x_i$ for $i\in [0, n-1]\setminus [j-3, j+3]$. For $i\in [j-3, j+3]$, $y_i$ will be defined according to the following cases. Initially, we let $y_i = x_i$ for $i\in [j-3, j+3]$.

By (3.4) and Fact 3, we have

and

Case 1. $r = 0$.

If $x_{j-1}\le 5$, then $x_{j-2}\ge 2(13+0-5) = 16$ and $m(\delta, 2, v_{j-2})\ge t+13+0-(2\cdot 5-\lfloor 5/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 2$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. By Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Similarly, if $x_{j+1}\le 5$, then, by $(3.5)$ and Fact 4, we have $x_{j+2}\ge 16$ and $m(\delta, 2, v_{j+2})\ge t+5$. Let $y_j = x_j+2 = 2$, $y_{j+1} = x_{j+1}+2$, $y_{j+2} = x_{j+2}-8\ge 8$, $y_{j+3} = x_{j+3}+4$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Now, we can assume that $x_{j-1}\ge 6$ and $x_{j+1}\ge 6$. Let $y_j = x_j+1 = 1$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we have

Case 2. $r = 1$.

If $x_{j-1}\le 6$, then $x_{j-2}\ge 2(13+1-6) = 16$ and $m(\delta, 2, v_{j-2}) \ge t+13+2-(2\cdot 6-\lfloor 6/2 \rfloor) = t+6$. Let $y_j = x_j+2 = 2$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 7$. If $x_{j+1}\ge 4$, then, by Fact 1, we have $m(\delta, 2, v_{j-1})\ge (t+r-x_j)+ \lfloor (x_j+\lfloor x_{j+1}/2\rfloor)/2\rfloor \ge t+2$. Let $y_j = x_j+2 = 2$, $y_{j-1} = x_{j-1}-4\ge 3$, and $y_{j-2} = x_{j-2}+2$. Then, by Fact 7, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. If $x_{j+1}\le 3$, then, by (3.5) and Fact 4, $x_{j+2}\ge 2(t-r-x_j-x_{j+1}) \ge 2(13-1-0-3) = 18$ and $m(\delta, 2, v_{j+2})\ge \lfloor x_{j+1}/2\rfloor+2(t-r-x_j-x_{j+1}) \ge \lfloor 3/2\rfloor+ t+13+2(-1-0-3) = t+6$. Let $y_j = x_j+2 = 2$, $y_{j+1} = x_{j+1}+2$, $y_{j+2} = x_{j+2}-8\ge 10$, and $y_{j+3} = x_{j+3}+4$. Then, by Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Case 3. $r\ge 2$.

If $x_{j-1}\le 8$, then $x_{j-2}\ge 2(13+2-8) = 14$ and $m(\delta, 2, v_{j-2})\ge t+13+4-(2\cdot 8-\lfloor 8/2\rfloor)+4 = t+5$. Let $y_j = x_j+2 = 2$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 9$. By Fact 1, $m(\delta, 2, v_{j-1})\ge t+r-x_j\ge t+2$. Let $y_j = x_j+2 = 2$, $y_{j-1} = x_{j-1}-4\ge 5$, $y_{j-2} = x_{j-2}+2$. Then, by Fact 7, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. □

Lemma 3.2. For $t\ge 13$ and $n\ge 6$, there exists an optimal $(2, t)$-solvable distribution $\delta$ of $C_n$ such that $\delta(v)\ge 2$ for each vertex $v$ of $C_n$.

Proof. By Lemma 3.1, we assume that $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ is an optimal $(2, t)$-solvable distribution of $C_n$ such that $\delta(v)\ge 1$ for each vertex $v$ of $C_n$. Suppose that $x_j = 1$ for some $j\in [0, n-1]$. Then, let $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ be defined as the description in Lemma 3.1. It suffices to show that $\delta'(v_j)\ge 2$ and $\delta'(v_k)\ge 2$ or $\delta'(v_k)\ge x_k$ for $k\in [0, n-1]\backslash\{j\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$.

By (3.4) and Fact 3, we have $x_{j-2}\ge 2(12+r-x_{j-1})$ and $m(\delta, 2, v_{j-2})\ge t+11+2r-(2x_{j-1}- \lfloor x_{j-1}/2 \rfloor)$.

Case 1. $r = 0$.

If $x_{j-1}\le 4$, then $x_{j-2} \ge 2(12+0-4) = 16$ and $m(\delta, 2, v_{j-2})\ge t+11+0-(2\cdot 4-\lfloor 4/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 3$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. By Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Similarly, if $x_{j+1}\le 4$, then $x_{j+2}\ge 16$ and $m(\delta, 2, v_{j+2})\ge t+5$. Let $y_j = x_j+2 = 3$, $y_{j+1} = x_{j+1}+2$, $y_{j+2} = x_{j+2}-8\ge 8$, $y_{j+3} = x_{j+3}+4$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Now, we assume that $x_{j-1}\ge 5$ and $x_{j+1}\ge 5$. Note that $x_j = 1$ is odd. If $x_{j-1}$ is odd, let $y_j = x_j+1 = 2$, and $y_{j-1} = x_{j-1}-1\ge 4$. By Fact 10, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Similarly, if $x_{j+1}$ is odd, let $y_j = x_j+1 = 2$, and $y_{j+1} = x_{j+1}-1\ge 4$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Now, we can assume that $x_{j-1}\ge 6$ and $x_{j+1}\ge 6$, and $x_{j-1}$ and $x_{j+1}$ are both even. For the case $x_{j-1}\ge 6$ and $x_{j+1}\ge 8$, let $y_j = x_j+1 = 2$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1$. Then, by Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. Also, by using (3.1) and (3.2), it is easy to check that $m(\delta', 2, v_{j-1})\ge t$.

Similarly, for the case $x_{j-1}\ge 8$ and $x_{j+1}\ge 6$, let $y_j = x_j+1 = 2$, $y_{j+1} = x_{j+1}-2\ge 4$, and $y_{j+2} = x_{j+2}+1$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

For the case $x_{j-1} = x_{j+1} = 6$, let $y_j = x_j+1 = 2$, $y_{j-1} = x_{j-1}-1 = 5$, $y_{j-2} = x_{j-2}-1\ge 2(t+r-x_j-x_{j-1})-1\ge 2(13+0-1-6)-1\ge 11$, and $y_{j-3} = x_{j-3}+1$. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. If $n\ge 11$, then the vertices

are all distinct. Otherwise, $6\le n \le 10$. Let $n = 10-k$, where $0 \le k \le 4$. Then the vertex $v_{j+5-i} = v_{j-5+k-i}$ for $i\in[0, 4]$. By (3.1), it is easy to see that $m(\delta', 2, v_i) = m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-5, j-4, j-3, j-2, j-1, j, j+1, j+2\}$. If $n\ge 9$, $v_i\notin \{v_{j-3}, v_{j-2}, v_{j-1}, v_j\}$ for $i\in \{j-7, j-6, j-5, j-4, j+1, j+2, j+3, j+4, j+5\}$. Note that when $n = 9$, $v_{j+5} = v_{j-4}$ and $v_{j+4} = v_{j-5}$, or when $n = 10$, $v_{j+5} = v_{j-5}$. So, for $n\ge 9$, it is easy to see that $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in \{j-5, j-4, j+1, j+2\}$. By (3.1)–(3.3), we also can verify that $m(\delta', 2, v_i)\ge t$ for $i\in \{j, j-1, j-2, j-3\}$. For the case that $6\le n \le 8$, without loss of generality, let $j = 0$. Then, by (3.1)–(3.3), it is easy to verify that $\delta'$ is $(2, t)$-solvable by checking $m(\delta', 2, v_i)$ for each $i\in [0, n-1]$.

Case 2. $r = 1$.

If $x_{j-1}\le 5$, then $x_{j-2}\ge 2(12+1-5) = 16$ and $m(\delta, 2, v_{j-2}) \ge t+11+2-(2\cdot 5- \lfloor 5/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 3$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. By Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. If $x_{j+1}\le 2$, then, by (3.5) and Fact 4, $x_{j+2}\ge 2(t-r-x_j-x_{j+1}) \ge 2(13-1-1-2) = 18$ and $m(\delta, 2, v_{j+2})\ge \lfloor x_{j+1}/2\rfloor +2(t-r-x_j-x_{j+1})\ge \lfloor 2/2 \rfloor+ t+13-2(1+1+2) = t+6$. Let $y_j = x_j+2 = 3$, $y_{j+1} = x_{j+1}+2$, $y_{j+2} = x_{j+2}-8\ge 10$, and $y_{j+3} = x_{j+3}+4$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Now, we can assume that $x_{j-1}\ge 6$ and $x_{j+1}\ge 3$. If $x_{j+1}\ge 4$, let $y_j = x_j+1 = 2$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify that $m(\delta', 2, v_{j-1})\ge t$. For the case $x_{j-1}\ge 6$ and $x_{j+1} = 3$, let $y_j = x_j+1 = 2$, $y_{j-1} = x_{j-1}-2\ge 4$, $y_{j-2} = x_{j-2}+1$, $y_{j+1} = x_{j+1}+1$, $y_{j+2} = x_{j+2}-2\ge 2(13-1-1-3)-2\ge 14$ and $y_{j+3} = x_{j+3}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$ and $m(\delta', 2, v_{j+2})$. By using (3.1), (3.2) and (3.5), we can verify that $m(\delta', 2, v_{j-1})\ge t$ and $m(\delta', 2, v_{j+2})\ge t+4$.

Case 3. $r\ge 2$.

If $x_{j-1}\le 6$, then $x_{j-2} \ge 2(12+2-6) = 16$ and $m(\delta, 2, v_{j-2})\ge t+11+4-(2\cdot 6-\lfloor 6/2 \rfloor) = t+6$. Let $y_j = x_j+2 = 3$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 7$. Let $y_j = x_j+1 = 2$, $y_{j-1} = x_{j-1}-2\ge 5$, and $y_{j-2} = x_{j-2}+1$. Then, by Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify that $m(\delta', 2, v_{j-1})\ge t$.

Lemma 3.3. For $t\ge 13$ and $n\ge 6$, there exists an optimal $(2, t)$-solvable distribution $\delta$ of $C_n$ such that $\delta(v)\ge 3$ for each vertex $v$ of $C_n$.

Proof. By Lemma 3.2, we assume that $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ is an optimal $(2, t)$-solvable distribution of $C_n$ such that $\delta(v)\ge 2$ for each vertex $v$ of $C_n$. Suppose that $x_j = 2$ for some $j\in [0, n-1]$. Then, let $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ be defined as the description in Lemma 3.1. It suffices to show that $\delta'(v_j)\ge 3$ and $\delta'(v_k)\ge 3$ or $\delta'(v_k)\ge x_k$ for $k\in [0, n-1]\backslash\{j\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$.

By (3.4) and Fact 3, we have $x_{j-2}\ge 2(11+r-x_{j-1})$ and $m(\delta, 2, v_{j-2}) \ge t+10+2r-(2x_{j-1}- \lfloor (x_{j-1}+1)/2 \rfloor)$.

Case 1. $r = 0$.

If $x_{j-1}\le 3$, then $x_{j-2}\ge 2(11+0-3) = 16$ and $m(\delta, 2, v_{j-2}) \ge t+10+0-(2\cdot 3-\lfloor (3+1)/2\rfloor) = t+6$. Let $y_j = x_j+2 = 4$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. Similarly, if $x_{j+1}\le 3$, then $x_{j+2}\ge 16$ and $m(\delta, 2, v_{j+2})\ge t+6$. Let $y_j = x_j+2 = 4$, $y_{j+1} = x_{j+1}+2$, $y_{j+2} = x_{j+2}-8\ge 8$, and $y_{j+3} = x_{j+3}+4$. By Fact 5, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Now, we can assume that $x_{j-1}\ge 4$ and $x_{j+1}\ge 4$. For the case $x_{j-1} = 4$ and $x_{j+1}\ge 4$, we have $x_{j-2}\ge 2(11+0-4) = 14$ and $m(\delta, 2, v_{j-2})\ge t+10+0-(2\cdot 4-\lfloor (4+1)/2\rfloor) = t+4$. Let $y_j = x_j+1 = 3$, $y_{j-1} = x_{j-1}+1$, $y_{j-2} = x_{j-2}-4\ge 10$, and $y_{j-3} = x_{j-3}+2$. Then, by Fact 6, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Similarly, for the case $x_{j-1}\ge 4$ and $x_{j+1} = 4$, let $y_j = x_j+1 = 3$, $y_{j+1} = x_{j+1}+1$, $y_{j+2} = x_{j+2}-4\ge 10$, and $y_{j+3} = x_{j+3}+2$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Now, we can assume that $x_{j-1}\ge 5$ and $x_{j+1}\ge 5$. For the case $x_{j-1} = x_{j+1} = 5$, let $y_j = x_j+2 = 4$, $y_{j-1} = x_{j-1}-1 = 4$, and $y_{j+1} = x_{j+1}-1 = 4$. Note that $x_{j-1}$ and $x_{j+1}$ are both odd. By Fact 9, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. For the case $x_{j-1}\ge 5$ and $x_{j+1}\ge 6$, let $y_j = x_j+1 = 3$, $y_{j-1} = x_{j-1}-2\ge 3$, and $y_{j-2} = x_{j-2}+1$. Then, by Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Similarly, for the case $x_{j-1}\ge 6$ and $x_{j+1}\ge 5$, let $y_j = x_j+1 = 3$, $y_{j+1} = x_{j+1}-2\ge 3$, and $y_{j+2} = x_{j+2}+1$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Case 2. $r = 1$.

If $x_{j-1}\le 4$, then $x_{j-2}\ge 2(11+1-4) = 16$ and $m(\delta, 2, v_{j-2}) \ge t+10+2-(2\cdot 4-\lfloor 4/2 \rfloor) = t+6$. Let $y_j = x_j+2 = 4$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 8$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 5$, let $y_j = x_j+1 = 3$, $y_{j-1} = x_{j-1}-2\ge 3$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Case 3. $r\ge 2$.

If $x_{j-1}\le 6$, then $x_{j-2} \ge 2(11+2-6) = 14$ and $m(\delta, 2, v_{j-2}) \ge t+10+4-(2\cdot 6-\lfloor 6/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 4$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 7$, let $y_j = x_j+1 = 3$, $y_{j-1} = x_{j-1}-2\ge 5$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t+1$. □

Lemma 3.4. For $t\ge 13$ and $n\ge 6$, there exists an optimal $(2, t)$-solvable distribution $\delta$ of $C_n$ such that $\delta(v)\ge 3$ for each vertex $v$ of $C_n$ and $x_k = 3$ implies $x_{k+1}\ge 4$ for any $k\in [0, n-1]$.

Proof. By Lemma 3.3, we assume that $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ is an optimal $(2, t)$-solvable distribution of $C_n$ such that $\delta(v)\ge 3$ for each vertex $v$ of $C_n$. Suppose that $x_{j-1} = 3$ and $x_j = 3$ or $x_{j} = 3$ and $x_{j+1} = 3$ for some $j\in [0, n-1]$. Then, let $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ be defined as the description in Lemma 3.1. For the case that $x_{j-1} = 3$ and $x_j = 3$, it suffices to show that $\delta'(v_k)\ge 4$ for $k = j$ or $j-1$ and $\delta'(v_i)\ge 4$ or $\delta'(v_i) = x_i$ for $i\in [0, n-1]\backslash\{k\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$. For the case that $x_{j} = 3$ and $x_{j+1} = 3$, it suffices to show that $\delta'(v_k)\ge 4$ for $k = j$ or $j+1$ and $\delta'(v_i)\ge 4$ or $\delta'(v_i) = x_i$ for $i\in [0, n-1]\backslash\{k\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$.

Case 1. $x_{j-1} = 3$ and $x_j = 3$.

By (3.4) and Fact 3, we have

and

Let $y_j = x_j+2 = 5$, $y_{j-1} = x_{j-1}+2 = 5$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4$. Then, by Fact 5, $\delta'$ is a desired distribution.

Case 2. $x_{j} = 3$ and $x_{j+1} = 3$.

If $r = 0$, then by (3.5) and Fact 4, we have $x_{j+2}\ge 14$ and $m(\delta, 2, v_{j+2})\ge t+5$. Let $y_j = x_j+2 = 5$, $y_{j+1} = x_{j+1}+2 = 5$, $y_{j+2} = x_{j+2}-8\ge 6$, and $y_{j+3} = x_{j+3}+4\ge 7$. Then, by Fact 5, $\delta'$ is a desired distribution. Otherwise, $r\ge 1$. Suppose that $r = 1$. Then, by (3.5) and Fact 4, we have $x_{j+2}\ge 12$ and $m(\delta, 2, v_{j+2})\ge t+3$. Let $y_{j+1} = x_{j+1}+2 = 5$, $y_{j+2} = x_{j+2}-4\ge 8$, and $y_{j+3} = x_{j+3}+2\ge 5$. Then, by Fact 7, $\delta'$ is a desired distribution. Suppose that $r\ge 2$ and $x_{j-1}\le 5$. Then, by (3.4) and Fact 3, we have $x_{j-2}\ge 14$ and $m(\delta, 2, v_{j-2})\ge t+5$. Let $y_j = x_j+2 = 5$, $y_{j-1} = x_{j-1}+2\ge 5$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4\ge 7$. Then, by Fact 5, $\delta'$ is a desired distribution. Suppose that $r\ge 2$ and $x_{j-1}\ge 6$. Then, by Fact 1, we have $m(\delta, 2, v_{j-1})\ge t+1$. If $x_{j-1}$ is odd, let $y_j = x_j+1 = 4$, $y_{j-1} = x_{j-1}-1\ge 5$. We only need to check $m(\delta', 2, v_{j-2})$ and $m(\delta', 2, v_{j-3})$. By using (3.1), it is easy to see that $m(\delta', 2, v_{j-2}) = m(\delta, 2, v_{j-2})$ and $m(\delta', 2, v_{j-3}) = m(\delta, 2, v_{j-3})$. Otherwise, $x_{j-1}$ is even, let $y_j = x_j+1 = 4$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1 \ge 4$. We only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we have

This completes the proof. □

We demonstrate the techniques of Lemmas 3.1–3.4 with the following example.

Let $\delta = \langle 4, 8, 12, 0, 3, 14\rangle$ be a distribution of $C_6$ such that $0 = x_j$. Note that $\delta$ is $(2, 13)$-solvable. By Eq (3.2), $r = 3$. Since $x_{j-1}\ge 9$, by Case 3 in Lemma 3.1, $\delta$ is modified to $\langle 4, 10, 8, 2, 3, 14 \rangle$ with $x_j = 2$. Note that at this stage, the new $\delta$ is still $(2, 13)$-solvable, $\delta(v)\ge 2$ for all $v\in V(C_6)$ and $r = 2$. Since $x_{j-1}\ge 7$, by Case 3 of Lemma 3.3, $\delta$ is modified to $\langle 4, 11, 6, 3, 3, 14 \rangle$. Note that at this stage the new $\delta$ is still $(2, 13)$-solvable, $\delta(v)\ge 3$ for all $v\in V(C_6)$, $x_j = x_{j+1} = 3$, and $r = 1$. By Case 2 of Lemma 3.4, $\delta$ is modified to $\langle 6, 11, 6, 3, 5, 10 \rangle$. Note that $x_{j+1}\ge 4$ and $\delta$ is still $(2, 13)$-solvable. Now, we are in a position to make a $(2, 13)$-solvable $\delta$ such that $\delta(v)\ge 4$ for each vertex $v$ of the cycle with the following proposition.

Proposition 3.2. If $t\ge 13$ and $n\ge 6$, then there exists an optimal $(2, t)$-solvable distribution $\delta$ of $C_n$ such that $\delta(v)\ge 4$ for each vertex $v$ of $C_n$.

Proof. By Lemma 3.4, we assume that $\delta = \langle x_0, x_1, \cdots, x_{n-1}\rangle$ is an optimal $(2, t)$-solvable distribution of $C_n$ such that $x_i\ge 3$ for all $i\in [0, n-1]$ and $x_k = 3$ implies $x_{k+1}\ge 4$ for any $k\in [0, n-1]$. Suppose that $x_j = 3$ for some $j\in [0, n-1]$. Then, let $\delta' = \langle y_0, y_1, \cdots, y_{n-1}\rangle$ be defined as the description in Lemma 3.1. It suffices to show that $\delta'(v_j)\ge 4$ and $\delta'(v_k)\ge 4$ or $\delta'(v_k) = x_k$ for $k\in [0, n-1]\backslash\{j\}$ and $|\delta'(C_n)|\leq|\delta(C_n)|$.

By (3.4) and Fact 3, we have $x_{j-2}\ge 2(10+r-x_{j-1})$ and $m(\delta, 2, v_{j-2})\ge t+9+2r-(2x_{j-1}- \lfloor (x_{j-1}+1)/2 \rfloor)$.

Case 1. $r = 0$.

If $4 \le x_{j-1}\le 6$ and $x_{j+1}\ge 4$, let $y_j = x_j+1 = 4$, $y_{j-2} = x_{j-2}-2\ge 2(t+r-x_j-x_{j-1})-2\ge 2(13+0-3-6)-2\ge 6$, and $y_{j-3} = x_{j-3}+1$. Clearly, $|\delta'(C_n)| = |\delta(C_n)|$. By (3.1), it is easy to see that $m(\delta', 2, v_i) = m(\delta, 2, v_i)$ for $i\in [0, n-1]\setminus \{j-5, j-4, j-3, j-2, j-1, j, j+1, j+2\}$. For $n\ge 9$, $v_i\notin \{v_{j-3}, v_{j-2}, v_j\}$ for $i\in \{j-7, j-6, j-5, j-4, j+1, j+2, j+3, j+4, j+5\}$. By (3.1), it is easy to check that $m(\delta', 2, v_i)\ge m(\delta, 2, v_i)$ for $i\in \{j-5, j-4, j-3, j, j+1, j+2\}$. Hence, we only need to check $m(\delta', 2, v_{j-1})$ and $m(\delta', 2, v_{j-2})$. Note that $x_{j-3}\ge 4$ or $x_{j-4}\ge 4$. It follows that $\lfloor x_{j-4}/2\rfloor+x_{j-3}\ge 5$. By (3.1)–(3.3), we have

and

For the case that $6\le n \le 8$, without loss of generality, let $j = 0$. Then by (3.1)–(3.3), it is easy to verify that $\delta'$ is $(2, t)$-solvable by checking $m(\delta', 2, v_i)$ for each $i\in [0, n-1]$.

Similarly, if $x_{j-1}\ge 4$ and $4\le x_{j+1}\le 6$, let $y_j = x_j+1 = 4$, $y_{j+2} = x_{j+2}-2\ge 6$, and $y_{j+3} = x_{j+3}+1$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Now, we can assume that $x_{j-1}\ge 7$ and $x_{j+1}\ge 7$. If $x_{j-1} = x_{j+1} = 7$, then $x_{j-1}$ and $x_{j+1}$ are both odd. Let $y_j = x_j+2 = 5$, $y_{j-1} = x_{j-1}-1 = 6$ and $y_{j+1} = x_{j+1}-1 = 6$. Then, by Fact 9, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

For the case $x_{j-1}\ge 7$ and $x_{j+1}\ge 8$, let $y_j = x_j+1 = 4$, $y_{j-1} = x_{j-1}-2\ge 5$, and $y_{j-2} = x_{j-2}+1$. Then, by Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Similarly, for the case $x_{j-1}\ge 8$ and $x_{j+1}\ge 7$, let $y_j = x_j+1 = 4$, $y_{j+1} = x_{j+1}-2\ge 5$, and $y_{j+2} = x_{j+2}+1$. Then, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable.

Case 2. $r = 1$.

If $x_{j-1} = 4$, then $x_{j-2}\ge 2(10 +1-4) = 14$ and $m(\delta, 2, v_{j-2})\ge t+9+2-(2\cdot 4-\lfloor 4/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 5$, $y_{j+1} = x_{j+1}+2$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4$. By Fact 5, $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 5$. If $x_{j-1} = 5$, then $x_{j}$ and $x_{j-1}$ are both odd. Let $y_j = x_j+1 = 4$ and $y_{j-1} = x_{j-1}-1 = 4$. By Fact 10, we only need to check $m(\delta', 2, v_{j-1})$. By (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Now, we can assume that $x_{j-1}\ge 6$. Let $y_j = x_j+1 = 4$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t$.

Case 3. $r\ge 2$.

If $x_{j-1}\le 5$, then $x_{j-2}\ge 2(10+2-5) = 14$ and $m(\delta, 2, v_{j-2})\ge t+9+4-(2\cdot 5-\lfloor 5/2 \rfloor) = t+5$. Let $y_j = x_j+2 = 5$, $y_{j-1} = x_{j-1}+2$, $y_{j-2} = x_{j-2}-8\ge 6$, and $y_{j-3} = x_{j-3}+4$. By Fact 5, we have $|\delta'(C_n)| = |\delta(C_n)|$ and $\delta'$ is $(2, t)$-solvable. Otherwise, $x_{j-1}\ge 6$. Let $y_j = x_j+1 = 4$, $y_{j-1} = x_{j-1}-2\ge 4$, and $y_{j-2} = x_{j-2}+1$. By Fact 8, we only need to check $m(\delta', 2, v_{j-1})$. By using (3.1) and (3.2), we can verify $m(\delta', 2, v_{j-1})\ge t+1$. □

As a demonstration of the techniques used in the proof of Proposition 3.2, we give one example for each of the three cases.

For $t = 13, n = 6$, we let $\delta = \langle x_{j-3}, x_{j-2}, x_{j-1}, x_j, x_{j+1}, x_{j+2}\rangle$.

If $\delta = \langle 4, 12, 4, 3, 4, 12\rangle$, then, $\delta$ is a $(2, 13)$-solvable distribution of $C_6$ with $x_j = 3$. By Eq (3.2), $r = 0$. Since $x_{j-1} = x_{j+1} = 4$, $\delta' = \langle 5, 10, 4, 4, 4, 12\rangle$.

If $\delta = \langle 6, 11, 6, 3, 5, 10\rangle$, then $\delta$ is $(2, 13)$-solvable and $r = 1$. Since $x_{j-1}\ge 6$, $\delta' = \langle 6, 12, 4, 4, 5, 10\rangle$. Note that this is a continuation of the example above Proposition 3.2.

If $\delta = \langle 4, 12, 6, 3, 4, 12\rangle$, then $\delta$ is $(2, 13)$-solvable and $r = 2$. Since $x_{j-1}\ge 6$, $\delta' = \langle 4, 13, 4, 4, 4, 12\rangle$.

Note that in all examples above $\delta'(v)\ge 4$ for each $v\in V(C_6)$ and $\delta'$ is still $(2, 13)$-solvable.

By combining Propositions 3.1 and 3.2, we have the following.

Theorem 3.1. For $t\ge 13$ and $n\ge 6$, $\pi_{(2, t)}^*(C_n) = \pi_{(2, t-10)}^*(C_n)+4n$.

By using Theorem 3.1 repeatedly (if necessary), we have the following.

Corollary 3.1. For $n\ge 6$, $\pi^*_{(2, 10k+r)}(C_n) = \pi^*_{(2, r)}(C_n)+4kn$, where $k\ge 1$ and $3\le r \le 12$.

4.   The optimal $(2, t)$-pebbling number of $C_4$

Let $\delta = \langle x_0, x_1, x_2, x_3 \rangle$ be a $(2, t)$-solvable distribution of $C_4$. Note that $v_{i-2} = v_{i+2}$ for all $i\in [0, 3]$. Hence, Eq (3.1) is not true for $C_4$; it must be modified into the following:

where $m_i = \left\lfloor (\lfloor y_{i-2}/2\rfloor+x_{i-1})/2\right\rfloor+x_i+\left \lfloor (x_{i+1}+\lfloor y_{i+2}/2\rfloor)/2\right \rfloor$.

This implies that if $x_{i+2}\le 1$, then

Otherwise,

It follows that $\frac{9}{4}(x_0+x_1+x_2+x_3)\ge4t$ or $x_0+x_1+x_2+x_3\ge\frac{16t}{9}$. This implies

It is not difficult to see $\langle 4k, 4k, 4k, 4k \rangle$ is an optimal $(2, 9k)$-solvable distribution of $C_4$ for $k\ge 1$. Thus, we have the following.

Proposition 4.1. For $k\ge 1$, $\pi^*_{(2, 9k)}(C_4) = 16k$.

Clearly, $\pi^*_{(2, 9k+r)}(C_4)\le \pi^*_{(2, 9k)}(C_4)+\pi^*_{(2, r)}(C_4)$ for $r\ge 1$. Also, by Proposition 4.1, for $k\ge 1$, we have

It is known that $\pi^*(C_4) = \lceil \frac{2\times 4}{3}\rceil = 3$, see ^[2]. So, we have the following.

Proposition 4.2. $\pi^*_{(2, 1)}(C_4) = 3$.

Proposition 4.3. If $t = 9k+1$ and $k\ge 1$, then $\pi^*_{(2, t)}(C_4) = \lceil 16t/9\rceil$.

Proof. For $k = 1$, by (4.2), we have $\pi^*_{(2, 10)}(C_4)\ge\lceil 160/9\rceil = 18$. By (4.1), it is easy to check that $\langle 4, 5, 4, 5 \rangle$ is a $(2, 10)$-solvable distribution of $C_4$. Hence, we have $\pi^*_{(2, 10)}(C_4) = 18$. For $k\ge 2$, by (4.2), we have $\pi^*_{(2, 9k+1)}(C_4)\ge\lceil 16(9k+1)/9\rceil$. Also, by (4.3), we have $\pi^*_{(2, 9k+1)}(C_4) = \pi^*_{(2, 9(k-1)+10)} (C_4)\le 16(k-1)+\pi^*_{(2, 10)} (C_4) = 16(k-1)+18 = \lceil 16(9k+1)/9\rceil$. This completes the proof. □

Proposition 4.4. For $r\in \{2, 3, 4, 6, 7, 8\}$, if $t = 9k+r$ and $k\ge 0$, then $\pi^*_{(2, t)}(C_4) = \lceil 16t/9\rceil$.

Proof. For $k\ge 0$ and $r\ge 0$, by (4.2), we have $\pi^*_{(2, 9k+r)}(C_4)\ge\lceil 16(9k+r)/9\rceil = 16k+\lceil \frac{16r}{9}\rceil$. Also, by (4.3), we have $\pi^*_{(2, 9k+r)}(C_4)\le 16k+\pi^*_{(2, r)} (C_4)$. So, it suffices to prove that $\pi^*_{(2, r)}(C_4)\le \lceil \frac{16r}{9}\rceil$ for $r\in \{2, 3, 4, 6, 7, 8\}$. We will prove it by constructing a $(2, r)$-solvable distribution with $\lceil \frac{16r}{9}\rceil$ pebbles for $r\in \{2, 3, 4, 6, 7, 8\}$. Let

It is easy to see $|\delta_r(C_5)| = \lceil \frac{16r}{9}\rceil$ and by using (4.1), it is not difficult to verify that $\delta_r$ is a $(2, r)$-solvable distribution of $C_4$ for each $r\in \{2, 3, 4, 6, 7, 8\}$. □

Proposition 4.5. If $t = 9k+5$ and $k\ge 0$, then $\pi^*_{(2, t)}(C_4) = \lceil 16t/9\rceil+1$.

Proof. For $k = 0$, by (4.1), it is easy to check that $\langle 4, 2, 2, 2 \rangle$ is a $(2, 5)$-solvable distribution of $C_4$. Hence, we have $\pi^*_{(2, 5)}(C_4)\le 10$. For $k\ge 1$, by $(**2)$, we have $\pi^*_{(2, 9k+5)}(C_4)\le 16k+\pi^*_{(2, 5)} (C_4)\le 16k+10$. Assume that $\delta = \langle x_0, x_1, x_2, x_3 \rangle$ is a $(2, 9k+5)$-solvable distribution of $C_4$ with $x_0+x_1+ x_2+x_3 = 16k+9$, where $k\ge 0$. Let $x_i = 4k+r_i$, $i = 0, 1, 2, 3$. Then, $r_0+r_1+r_2+r_3 = 9$. Without loss of generality, let $r_0 = \min \{r_i|i = 0, 1, 2, 3\}$. By (4.1), we have $x_0+(x_1+x_3)/2+x_2/4 = 9k+r_0+(r_1+r_3)/2+r_2/4\ge m(\delta, 2, v_0)\ge 9k+5$. This implies that $r_0+(r_1+r_3)/2+r_2/4\ge 5$, equivalently, $r_0+r_1+r_2+r_3\ge 10-r_0+r_2/2$. Thus, $9\ge 10-r_0+r_2/2$, and we have $r_0\ge 1 + r_2/2\ge 1 + r_0/2$. Hence, $r_0 \ge 2$. This implies that $\delta$ is one of the following distributions:

It is easy to check that $\delta$ is not $(2, 9k+5)$-solvable, which is a contradiction. Therefore, $\pi^*_{(2, 9k+5)}(C_4)\ge 16k+10 = \lceil 16(9k+5)/9\rceil +1$, and we have the proof. □

By Propositions 4.1–4.5, we conclude the following.

Theorem 4.1. Let $t$ be a positive integer. If $t = 1$ or $t\mod 9 = 5$, then $\pi_{(2, t)}^*(C_4) = \lceil 16t/9\rceil+1$. Otherwise, $\pi_{(2, t)}^*(C_4) = \lceil 16t/9\rceil$.

5.   The optimal $(2, t)$-pebbling number of $C_5$

Let $\delta = \langle x_0, x_1, x_2, x_3, x_4 \rangle$ be a $(2, t)$-solvable distribution of $C_5$. Then we have

for each $i\in [0, 4]$. This implies that $\frac{5}{2}(x_0+x_1+x_2+x_3+x_4)\ge 5t$. Thus,

Note that Eq (3.1) is not always true for $C_5$. For example, let $\delta = \langle 0, 1, 1, 2, 0 \rangle$. Then, we can move one pebble to $v_0$ by applying three pebbling moves. First, we can move one pebble to $v_2$ from $v_3$, and then move one pebble to $v_1$ from $v_2$. Finally, we can move one pebble to $v_0$ from $v_1$. But, when we use (3.1), we have $\left\lfloor \frac{1}{2}(\lfloor \frac{x_3}{2}\rfloor+ x_4)\right\rfloor+x_0+\left \lfloor \frac{1}{2}(x_1+\lfloor \frac{x_2}{2}\rfloor)\right \rfloor = 0$. So, Eq (3.1) should be modified into the following:

where

and

By Corollary 2.1, we have the following.

Proposition 5.1. $\pi_{(2, 10k)}^*(C_5) = 20k$ for $k\ge 1$.

By Proposition 5.1, we have the following.

Lemma 5.1. $\pi_{(2, 10k+r)}^*(C_5)\le 20k+\pi_{(2, r)}^*(C_5)$ for $k\ge 1$ and $r\ge 1$.

Now, we will give a lower bound for $\pi_{(2, t)}^*(C_5)$ when $t \mod 10 \neq 0$.

Lemma 5.2. $\pi_{(2, t)}^*(C_5)\ge 2t+1$ when $t \mod 10 \neq 0$.

Proof. Let $\delta = \langle x_0, x_1, x_2, x_3, x_4 \rangle$ be an optimal $(2, t)$-solvable distribution of $C_5$. By (5.2), we have $\pi_{(2, t)}^*(C_5)\ge 2t$. By (5.1), we can write $x_i+(x_{i+1}+x_{i-1})/2+(x_{i+2}+x_{i-2})/4 = t+s_i$, where $s_i$ is a nonnegative real number for each $i\in [0, 4]$. If $\pi_{(2, t)}^*(C_5) = 2t$, then $s_i = 0$ for all $i\in[0, 4]$, and this system of linear equations can be represented as a matrix.

After Gaussian elimination, we have

Thus, the system of equations has a unique solution $x_0 = x_1 = x_2 = x_3 = x_4 = \frac{2t}{5}$. If $t \mod 5 \neq 0$, then the solution is not integral, hence, there exists at least one $i\in [0, 4]$ such that $s_i > 0$. This implies $\pi_{(2, t)}^*(C_5)\ge 2t+1$ because $\pi_{(2, t)}^*(C_5)$ is an integer. If $t \mod 10 = 5$ and $\pi_{(2, t)}^*(C_5) = 2t$, let $t = 10k+5$, where $k$ is a nonnegative integer, then $\delta = \langle 4k+2, 4k+2, 4k+2, 4k+2, 4k+2 \rangle$. It is easy to check that $\delta$ is not $(2, t)$-solvable. It leads to a contradiction and hence $\pi_{(2, t)}^*(C_5)\ge 2t+1$. This completes the proof. □

It is known that $\pi^*(C_5) = \lceil \frac{2\times 5}{3}\rceil = 4$, see ^[2]. So, we have the following.

Proposition 5.2. $\pi_{(2, 1)}^*(C_5) = 4$.

In 2018, Chen and Shiue ^[4] showed that $\pi^*_{(2, 2)}(C_3) = 4$ and $\pi^*_{(2, 2)}(C_n) = n$ for $n\ge 4$. So, we have the following.

Proposition 5.3. $\pi_{(2, 2)}^*(C_5) = 5$.

Lemma 5.3. $\pi_{(2, r)}^*(C_5) = 2r+1$ for $r\in [2, 9] \cup \{11\}$.

Proof. By Proposition 5.3, it is true for $r = 2$. By Lemma 5.2, we have $\pi_{(2, r)}^*(C_5)\ge 2r+1$ for $r\in [3, 9] \cup \{11\}$. We will prove that the lower bound is also an upper bound by constructing a $(2, r)$-solvable distribution with $2r+1$ pebbles. Let

Clearly, $|\delta_r(C_5)| = 2r+1$. Then, by using (5.3), it is not difficult to verify that $\delta_r$ is a $(2, r)$-solvable distribution of $C_5$ for each $r\in [3, 9] \cup \{11\}$. □

Proposition 5.4. $\pi_{(2, 10k+r)}^*(C_5) = 20k+2r+1$ for $k\ge 0$ and $r\in [2, 9] \cup \{11\}$.

Proof. By Lemma 5.3, it is true for $k = 0$. By combining Proposition 5.1 and Lemma 5.3, we have $\pi_{(2, 10k+r)}^*(C_5)\le 20k+\pi_{(2, r)}^*(C_5) = 20k+2r+1$ for $k\ge 1$. By Lemma 5.2, we can see that the upper bound is also a lower bound, hence, we have the proof. □

By combining Propositions 5.1, 5.2, and 5.4, we have the main result of this section.

Theorem 5.1. Let $t$ be a positive integer. Then,

6.   Conclusions

In 2018, the distance-restricted pebbling was first proposed by Chen and Shiue ^[4], and they showed that $\pi^*_{(2, 2)}(C_3) = 4$ and $\pi^*_{(2, 2)}(C_n) = n$ for $n\ge 4$. In 2020, Shiue ^[13] studied distance 1-restricted pebbling in cycles, and he determined the exact value of $\pi^*_{(1, t)}(C_n)$ for all $t\ge 1$ and $n\ge 3$; see Theorem 2.1. For $t = 1$, $\pi^*_{(1, 1)}(C_n) = \pi^*(C_n) = \left\lceil \frac{2n}{3} \right\rceil$; see ^[2]. This implies that $\pi^*_{(d, 1)}(C_n) = \left\lceil \frac {2n}{3} \right\rceil$ for all $d\ge 1$. Thus, we have $\pi^*_{(2, 1)}(C_n) = \left\lceil \frac{2n}{3} \right\rceil$.

"$(d, t)$-pebbling" can be seen as a generalization of optimal pebbling. In addition to this, it is our belief that $(d, t)$-pebbling is more applicable than other versions of pebbling. For example, in a transportation and resource allocation system, the resource must be delivered to a target in a set amount of time, thus, in practicality, we need to restrict the distance to the target. Ideally, in such a resource allocation scheme, the storehouses for the resources should have a capacity restriction since the space for the storehouse is limited. Studies on capacity-restricted optimal pebbling can be found in ^[3,10]. We discussed the optimal capacity and distance-restricted $t$-fold pebbling, also known as the optimal $(c, d, t)$-pebbling number, in ^[15]. In some sense, $\pi^*_{(d, t)}(G)$ can also be viewed as a distance-based parameter, which is a topic that has been studied before, for example, in ^[1].

In this article, we give a further study into "$(d, t)$-pebbling". Our result makes progress towards understanding $(d, t)$-pebbling for cycles. Specifically, we study $(2, t)$-pebbling as a continuation from the study of $(1, t)$-pebbling done in ^[13]. We were able to show that the optimal $(2, t)$-pebbling number of cycles can be determined by considering only a finite number of cases, namely, $1\le t \le 12$. We were also able to completely determine the optimal $(2, t)$-pebbling number for $C_4$ and $C_5$. For cycles of length greater than 5, our result relies on repeated application of the tools developed in Facts 1–10. For cycles of length not greater than 5, the key to our results is obtained by modifying Eq (3.1). The process of obtaining a lower bound for $\pi^*_{(2, t)}(C_5)$ involves the solution of a system of linear equations whose matrix is positive semi-definite. For arbitrarily large distance $d$, the matrix can be very large. Thus, in order to obtain a lower bound for $\pi^*_{(d, t)}(C_n)$ when $d > 2$, one may consider the use of the conjugate gradient method; see ^[6].

Finally, we will give a summary of progress towards the determination of $\pi^*_{(2, t)}(C_n)$ for all $n\ge 3$ and $t\ge 1$. Corollary 3.1 implies that the problem of determining the exact value of $\pi^*_{(2, t)}(C_n)$ for $n\ge 6$ and $t\ge 1$ can be reduced to the problem of determining the exact value of $\pi^*_{(2, r)}(C_n)$ for $n\ge 6$ and $r\in[1, 12]$. By the discussion above, we know the exact value of $\pi^*_{(2, t)}(C_n)$ for $n\ge 3$ and $t = 1, 2$. Furthermore, note that the diameter of $C_3$ is equal to one. This implies that $\pi^*_{(2, t)}(C_3) = \pi^*_{(1, t)}(C_3)$ for $t\ge 1$, see Theorem 2.1. Theorems 4.1 and 5.1 give the exact value of $\pi^*_{(2, t)}(C_n)$ for $n = 4, 5$ and $t\ge 1$. So, to completely determine the exact value of $\pi^*_{(2, t)}(C_n)$ for $n\ge 3$ and $t\ge 1$, it is left to solve the following problem.

Problem 2. Determine the exact value of $\pi^*_{(2, t)}(C_n)$ for $n\ge 6$ and $3 \le t \le 12$.

Recently, we have shown that $\pi^*_{(2, 3)}(C_n) = \lceil \frac{4n}{3}\rceil$ for $n\ge 4$, see ^[15]. By combining Corollary 3.1, we have $\pi^*_{(2, 10k+3)}(C_n) = \lceil \frac{4n}{3}\rceil+4kn$ for $n\ge 6$ and $k\ge 0$. For example, by using the two facts that $\langle 4, 0, 0, 4, 0, 0\rangle$ is an optimal $(2, 3)$-solvable distribution of $C_6$ (see ^[15]) and that $\langle 4, 4, 4, 4, 4, 4\rangle$ is an optimal $(2, 10)$-solvable distribution of $C_6$ (see ^[13]), we can conclude that $\langle 8, 4, 4, 8, 4, 4\rangle$ is an optimal $(2, 13)$-solvable distribution of $C_6$.

Author contributions

Chin-Lin Shiue: Conceptualization, Supervision, Writing–original draft; Tzu-Hsien Kwong: Conceptualization, Validation, Writing–review and editing. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research was supported in part by the Ministry of Science and Technology of Taiwan under Grant MOST 111-2115-M-033-003.

Conflict of interest

The authors declare that there are no conflicts of interest in this paper.