# Restricted optimal pebbling is NP-hard

László F. Papp Department of Computer Science and Information Theory, Budapest
University of Technology and Economics, Hungary<EMAIL_ADDRESS>
###### Abstract

Consider a distribution of pebbles on a graph. A pebbling move removes two
pebbles from a vertex and place one at an adjacent vertex. A vertex is
reachable under a pebble distribution if it has a pebble after the application
of a sequence of pebbling moves. A pebble distribution is solvable if each
vertex is reachable under it. The size of a pebble distribution is the total
number of pebbles. The optimal pebbling number $\pi^{*}(G)$ is the size of the
smallest solvable distribution. A $t$-restricted pebble distribution places at
most $t$ pebbles at each vertex. The $t$-restricted optimal pebbling number
$\pi_{t}^{*}(G)$ is the size of the smallest solvable $t$-restricted pebble
distribution. We show that deciding whether $\pi^{*}_{2}(G)\leq k$ is NP-
complete. We prove that $\pi_{t}^{*}(G)=\pi^{*}(G)$ if
$\delta(G)\geq\frac{2|V(G)|}{3}-1$ and we show infinitely many graphs which
satisfies $\delta(H)\approx\frac{1}{2}|V(H)|$ but
$\pi_{t}^{*}(H)\neq\pi^{*}(H)$, where $\delta$ denotes the minimum degree.

##  1 Introduction

Graph pebbling is a game on graphs initiated by a method of Saks and Lagarias
to answer a number-theoretic question of Erdős and Lemke, which was
successfully carried out by Chung in 1989[4]. Each graph in this paper is
simple. We denote the vertex set and the edge set of graph $G$ by $V(G)$ and
$E(G)$, respectively. A _pebble distribution_ $D$ on graph $G$ is a function
mapping the vertex set to non-negative integers. We can imagine that each
vertex $v$ has $D(v)$ pebbles. A _pebbling move_ removes two pebbles from a
vertex $v$ (having at least two pebbles) and places one on an adjacent vertex
$u$. We denote this move by $(v\rightarrow u)$.

If $\sigma$ is a sequence of pebbling moves, then let $D\sigma$ be the
distribution which we obtain after the application of $\sigma$ to distribtuion
$D$. A sequence of pebbling moves is _executable_ under $D$ if for any $\tau$
prefix of $\sigma$ $D\tau$ is a pebble distribution. In other words, $\sigma$
never removes two pebbles from a vertex which does not have at least two
pebbles. A vertex $v$ is _$k$ -reachable_ under a distribution $D$ if there is
an executable sequence of pebbling moves $\sigma$ such that $D\sigma(v)\geq
k$. When $k=1$ we write reachable instead of $1$-reachable. We say that a
distribution $D$ is _solvable_ if each vertex of the graph is reachable under
$D$.

Let $|D|$ denotes the total number of pebbles placed on the graph by $D$, so
$|D|=\sum_{v\in V(G)}D(v)$. We call this quantity as the _size of_ $D$. A
pebble distribution $D$ on a graph $G$ is called _optimal_ if it is solvable
and its size is the smallest possible. This size is called the _optimal
pebbling number_ and denoted by $\pi^{*}(G)$.

The optimal pebbling number of several graph families are known. For example
exact values were given for paths and cycles [6] [13], ladders [1],
caterpillars [7], $m$-ary trees [8] and some staircase graphs[9]. The values
for graphs with diameter smaller than four are also characterized by some
easily checkable domination conditions [12]. However, determining the optimal
pebbling number for a given graph is NP-hard [10].

In [2], Chelalli et al. introduced a new version of pebbling. In this setting,
a pebble distribution is _$t$ -restricted_ if no vertex has more than $t$
pebbles. The _$t$ -restricted_ optimal pebbling number, denoted by
$\pi^{*}_{t}$, is the size of the solvable $t$-restricted distribution
containing the least number of pebbles. It is easy to see that
$\pi_{2}^{*}(G)\geq\pi_{t}^{*}(G)\geq\pi_{t+1}^{*}(G)\geq\pi^{*}(G)$.

A set $S$ is a dominating set of graph $G$ if $S\subseteq V(G)$ and each
vertex of $G$ is contained in $S$ or adjacent to an element of $S$. The
domination number $\gamma(G)$ of graph $G$ is the size of the smallest
domination set of $G$. A function $f:V(G)\rightarrow\\{0,1,2\\}$ is called as
a Roman domination function if each $v\in V(G)$ for which $f(v)=0$ there is a
vertex $u$ which is adjacent to $v$ and $f(u)=2$. The weight of a Roman
domination function is $\sum_{v\in V(G)}f(v)$. The Roman domination number
$\gamma_{R}(G)$ is the minimum weight of a Roman domination function.

Chelalli et al. proved several bounds on these domination parameters by using
the $2$-restricted optimal pebbling number. They showed that
$\pi_{2}^{*}(G)\leq\gamma_{R}(G)$ [2]. These domination parameters are well
studied and they are in the limelight. Computing the Roman domination number
is a hard task. More specifically, the decision version of the Roman
domination number is NP-complete [5]

Recently Shiue _et al._ in [3] defined a new version of pebbling called
$(d,t)$-pebbling. In this new model a pebble distribution $D$ is called
$(d,t)$-solvable if each vertex $v$ can have $t$ pebbles after a sequence of
pebbling moves which only remove pebbles from vertices whose distance from $v$
is at most $d$. The optimal $(d,t)$-pebbling number $\pi^{*}_{(d,t)}(G)$ of
$G$ is the minimum size of a $(d,t)$-solvable distribution of $G$. Shiue
showed that $\gamma_{R}(G)=\pi^{*}_{(1,1)}(G)$ [14], so the Roman domination
number is a special case of this generalised pebbling parameter. In a
$(1,1)$-solvable distribution no vertex has more than $2$ pebbles, because $2$
pebbles at a vertex are enough to reach the adjacent vertices and we cannot
move a pebble further in this setting. So to sum up,
$\pi^{*}(G)\leq\pi^{*}_{2}(G)\leq\pi^{*}_{(1,1)}=\gamma_{R}(G)$.

Therefore the $t$-restricted optimal pebbling number is trapped between two
graph parameters whose calculation is an NP-hard task. Somebody may ask that
what is the computational complexity of the $2$-restricted optimal pebbling
number?

In Section 2 we show that deciding whether the $t$-restricted optimal pebbling
number is at most $k$ is NP-complete for any $t\geq 2$. Note that the $t=1$
case is trivial because $\pi^{*}_{1}(G)=|V(G)|$ for all graphs. We prove that
$\pi^{*}(G)=\pi^{*}\left(G\cdot K_{m}\right)=\pi^{*}_{t}\left(G\cdot
K_{m}\right)$ where $\cdot$ denotes the lexicographic graph product. We use
this result to give a reduction from optimal pebbling to $t$-restricted
optimal pebbling.

The authors of [2] asked the following interesting question: What graphs have
the same $2$-restricted optimal pebbling number and optimal pebbling number?
We can also ask what kind of properties implies the equality of these two
parameters. In Section 3 we investigate the role of the minimum degree in this
question and show some partial results.

We prove that that if $\delta(G)\geq\frac{2|V(G)|}{3}-1$, where $\delta(G)$
denotes the minimum degree of $G$, then $\pi_{2}^{*}(G)=\pi^{*}(G)$. For any
$n$ which satifies $n\equiv 1\mod 4$ and $n\geq 9$ we present an $n$-vertex
graph $H$ such that $\delta(H)=\frac{|V(H)|-3}{2}$ but
$\pi_{2}^{*}(H)\neq\pi^{*}(H)$.

##  2 Complexity of the t-restricted optimal pebbling number

###### Lemma 2.1

Let $G$ be a connected graph whose order is at least $2$. $G$ has an optimal
distribution $D$ such that for every vertex $v$ which is not 2-reachable under
$D$ we have that $D(v)=0$.

Proof: If a vertex is not 2-reachable but it has some pebbles, then it
contains exactly one pebble. Let $D$ be an optimal distribution on graph $G$
and let $S(D)$ be the set of vertices which are not 2-reachable under $D$ but
each of them has a pebble.

Consider a vertex $v\in S(D)$. Since the graph is connected it has a neighbor
$u$. This vertex can receive a pebble without the usage of the pebble placed
at $v$. If we remove the pebble placed at $v$ and place it at $u$, then under
the obtained distribution $u$ is 2-reachable so $v$ is reachable. The
relocated pebble could not be moved under $D$ so if a vertex was $k$-reachable
under $D$, then it is also $k$-reachable under the obtained distribution
$D^{\prime}$. Therefore $D^{\prime}$ is optimal and $S(D^{\prime})\subseteq
S(D)$. Since $v$ is not in $S(D^{\prime})$ we have that
$|S(D^{\prime})|<|S(D)|$. If we repeat this procedure, then we end up with a
distribution $D^{*}$ such that $S(D^{*})=\emptyset$. $\Box$

$G\cdot H$ denotes the lexicographic product of graphs $G$ and $H$, which is
well known. It is defined as follows: $V(G\cdot H)=V(G)\times V(H)$ and
$(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent iff either
$\\{g_{1},g_{2}\\}\in E(G)$ or $g_{1}=g_{2}$ and $\\{h_{1},h_{2}\\}\in E(H)$.

To prove our first theorem we are going to use the technique called
collapsing. It is invented in [1] and it is used in several pebbling papers.

Let $G$ and $H$ be simple graphs. Graph $H$ is called as a _quotient of_ $G$
if there is a surjective mapping $\phi:V(G)\rightarrow V(H)$ such that
$\\{h_{1},h_{2}\\}\in E(H)$ if and only if $h_{1}=\phi(g_{1})$ and
$h_{2}=\phi(g_{2})$ for some $\\{g_{1},g_{2}\\}\in E(G)$. We say that $\phi$
collapses $G$ to $H$ and if $D$ is a pebble distribution on $G$, then the
_collapsed distribution_ $\phi(D)$ on $H$ is defined by $\phi(D)(h)=\sum_{g\in
V(G)|\phi(g)=h}D(g)$.

######  Lemma 2.2 (Collapsing [1])

If $H$ is a quotient of $G$ then $\pi^{*}(G)\geq\pi^{*}(H)$.

It is known that the optimal pebbling number of any connected $n$-vertex graph
is at most $\left\lceil\frac{2n}{3}\right\rceil$ [1]. Interestingly, the same
upper bound holds for the $2$-restricted optimal pebbling number [15]. Now we
are well prepared to state and prove our first theorem.

###### Theorem 2.3

If $G$ is a connected n-vertex graph,
$m\geq\left\lceil\frac{n}{3}\right\rceil$ and $t\geq 2$ then:

$\pi^{*}(G)=\pi^{*}\left(G\cdot K_{m}\right)=\pi^{*}_{t}\left(G\cdot
K_{m}\right).$

Proof: Let $D$ be an optimal pebble distribution of $G$ which satisfies that
if a vertex has one pebble then it is 2-reachable under $D$. Lemma 2.1
guarantees that such a pebble distribution exists.

Since $|D|\leq\left\lceil\frac{2n}{3}\right\rceil$ and
$m\geq\left\lceil\frac{n}{3}\right\rceil$ we have that $|D|\leq 2m$. $D(g)=2m$
implies that all pebbles are placed at $g$. Assume that this is not the case,
so for each $g$ $D(g)<2m$.

Denote the vertices of $K_{m}$ with $(0,1,2,\ldots,m-1)$. Let $Q$ be the
following pebble distribution on $G\cdot K_{m}$:

$Q\left((g,i)\right)=\begin{cases}1&\text{if}\ i=0\ \text{and}\ D(g)\ \text{is
odd}\\\ 2&\text{if}\ 1\leq i\leq\frac{D(g)}{2}\\\
0&\text{otherwise.}\end{cases}$

For each $g$ we have that $\sum_{l=0}^{m-1}Q((g,l))=D(g)$. Therefore
$|D|=|Q|$. Now we show that $Q$ is a solvable distribution on $G\cdot K_{m}$.
To do this we show that any vertex $(g^{*},j)$ is reachable under $Q$.

If $D(g^{*})\geq 2$, then $Q((g^{*},1))=2$, therefore $(g^{*},j)$ is reachable
under $Q$.

When $D(g^{*})=1$ we can use that $g^{*}$ is 2-reachable under $D$. Therefore
in the $D(g^{*})\leq 1$ case there is an executable sequence of pebbling moves
$\sigma$ whose last move places a pebble at $g^{*}$. We can assume, that
$\sigma$ does not contain unnecessary steps, therefore it does not remove a
pebble from $g^{*}$ and it moves exactly one pebble to $g^{*}$.

We construct $\tau$ which is an executable sequence of pebbling moves on the
graph $G\cdot K_{m}$ and its last move places a pebble at $(g^{*},j)$. The
lengths of $\sigma$ and $\tau$ will be the same. If $g^{\prime}\neq g^{*}$,
$\sigma_{i}=(g\rightarrow g^{\prime})$ and this pebbling move appears exactly
$k$ times among the first $i$ elements of $\sigma$, then let

$\tau_{i}=\begin{cases}((g,k)\rightarrow(g^{\prime},0))\ \text{if}\
k\leq\frac{D(g)}{2}\\\ ((g,0)\rightarrow(g^{\prime},0))\
\text{otherwise.}\end{cases}$

Finally, if the last step of $\sigma$ is $\sigma_{i}=(g\rightarrow g^{*})$,
then let

$\tau_{i}=\begin{cases}((g,k)\rightarrow(g^{*},j))\ \text{if}\
k\leq\frac{D(g)}{2}\\\ ((g,0)\rightarrow(g^{*},j))\
\text{otherwise.}\end{cases}$

$\tau$ mimics $\sigma$ in the following way: It gathers the pebbles which are
received by $g$ at $(g,0)$. If a $(g\rightarrow g^{\prime})$ move is applied
by $\sigma$ then $\tau$ initially removes pebbles from vertices $(g,k)$,
$k\geq 1$ where the pebbles of $g$ were distributed. After all these pebbles
have been used $\tau$ uses the pebbles gathered to $(g,0)$.

For any $l$ it is easy to see that
$D\sigma_{1}\sigma_{2}\ldots\sigma_{l}(g)=\sum_{i=0}^{m-1}Q\tau_{1}\tau_{2}\ldots\tau_{l}((g,i))$.
These guarantee that $\tau$ never wants to remove pebbles from a vertex which
does not have at least two pebbles, thus it is executable.

If $|D|=D(g)=2m$, then let $Q^{\prime}$ be the distribution on $G\cdot K_{m}$
which places $2$ pebbles at each of $(g,i)$ and does not place any pebble at
the rest of the vertices. It is easy to prove, by the same reasoning which we
have used in the previous case, that $Q^{\prime}$ is a solvable $2$-restricted
distribution of $G\cdot K_{m}$ and $|Q^{\prime}|=|D|$.

So in both cases we have shown a solvable $2$-restricted distribution on
$G\cdot K_{m}$ and the size of these distributions is $|D|$. Therefore
$\pi^{*}(G)\geq\pi_{2}^{*}(G\cdot K_{m})$. We know that $\pi_{2}^{*}(G\cdot
K_{m})\geq\pi^{*}_{t}(G\cdot K_{m})\geq\pi^{*}(G\cdot K_{m})$. $G$ is a
quotient of $G\cdot K_{m}$ because $\phi((g,i))=g$ is a proper surjective
function. Therefore Lemma 2.2 gives that $\pi^{*}\left(G\cdot
K_{m}\right)\geq\pi^{*}(G)$.

Putting everything together we get that $\pi^{*}(G)\geq\pi_{2}^{*}(G\cdot
K_{m})\geq\pi^{*}_{t}(G\cdot K_{m})\geq\pi^{*}(G\cdot K_{m})\geq\pi^{*}(G)$.
Since the leftmost and rightmost quantities are the same, all the quantities
are equal. $\Box$

We consider the following two decision problems:

OPN: Given $G$, $k$: Is $\pi^{*}(G)\leq k$?

ROPN: Given $G$, $t\geq 2$, $k$: Is $\pi^{*}_{t}(G)\leq k$?

Milans and Clark proved that OPN is NP-complete [10]. Using our previous
theorem we are going to show that ROPN is NP-hard. We do not give a precise
proof that ROPN is in NP, since it is exactly the same as the proof that OPN
is in NP. In the next paragraph we give the sketch of the proof. If the reader
is interested in the details, then they can be found in [10].

The witness for $\pi^{*}(G)\leq k$ is the following: A solvable $2$-restricted
pebble distribution $D$ of size $k$ and for each vertex $v$ a compact
transcript of an executable sequence of pebbling moves $\sigma_{v}$, which
satisfy $D\sigma_{v}(v)\geq 1$. This transcription does not contain the order
of the pebbling moves, it just contains the total number of each possible
moves. From this transcription it is possible to decide in polynomial time
whether a compatible executable sequence of pebbling moves exists or not.

###### Lemma 2.4

OPN$\prec$ROPN.

Proof: Let $f$ be the function which maps $G$ to $G\cdot K_{|V(G)|}$. If $G$
is the input of OPN then let the corresponding input of ROPN be $f(G)$. $f$
can be calculated in polinomial time. By Lemma 2.3 $\pi^{*}(G)\leq k$ iff
$\pi^{*}_{t}(f(G))\leq k$. $\Box$

OPN is NP-complete and ROPN is in NP, therefore Lemma 2.4 implies our main
complexity result:

###### Theorem 2.5

ROPN is NP-complete.

##  3 Large minimum degree enforces ${\pi^{*}}(G)=\pi_{t}^{*}(G)$

The authors of [2] asked for a characterization of graphs whose optimal
pebbling number and $2$-restricted optimal pebbling number are the same. We
think that such a characterization is elaborate. Note that there are many
graphs which have this property. For example paths, cycles and complete
graphs.

Lemma 2.3 gives infinitely many examples. The graphs $G\cdot K_{k}$ belongs to
the investigated family when $k\geq\left\lceil\frac{|V(G)|}{3}\right\rceil$.
The number of vertices in $G\cdot K_{k}$ is $|V(G)|\cdot k$ and the minimum
degree $\delta$ is at least $2k-1$. Therefore the ratio of the minimum degree
and the number of vertices of $G\cdot K_{k}$ is at least $\frac{2}{|V(G)|}$.

Somebody may ask, that does high minimum degree guarantees that
$\pi^{*}_{2}=\pi^{*}$? The answer is yes. We need a short lemma to prove this.

###### Lemma 3.1

Let $G$ be a graph. If $D$ is a pebble distribution on $G$ such that $D(v)=3$
for a particular vertex $v$ and $D(u)\leq 1$ for any other vertex $u$, then
$D$ is not optimal.

Proof:

To reach a vertex the third pebble of $v$ is not needed. Any nonempty sequence
of pebbling moves, which can be applied to $D$, removes two pebbles from $v$
in the first step. Then at each step only one vertex has more than one pebble
and every other vertex has at most as many pebbles as initially. When the
third pebble of $v$ is used each vertex has at most as many pebbles as it has
under $D$. Therefore the subsequence whose first move removes the third pebble
of $v$ and contains all the later moves is executable under $D$ and reaches
the same vertex as the original sequence of pebbling moves. But it removes
only two pebbles from $v$, so one useless pebble remains there. $\Box$

This lemma immediately gives us a new class of graphs where equality holds
between the two investigated parameters.

###### Corollary 3.2

If $\pi^{*}(G)\leq 3$, then $\pi_{2}^{*}(G)=\pi^{*}(G)$.

$w$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Figure 1: The graph $H_{4}$.

###### Claim 3.3

Let $G$ be a graph of order $n$. If $\delta(G)\geq\frac{2}{3}n-1$ then
$\pi_{2}^{*}(G)=\pi^{*}(G)$.

In the proof we are going to use the well known fact that the optimal pebbling
number of a diameter two graph is at most $4$[12]. The neighborhood of a
vertex $u$ is the set of vertices which are adjacent to $u$. We denote this
set by $N(u)$.

Proof: We show that $D$ has an optimal distribution which is $2$-restricted.
The diameter of $G$ is at most two, because if two vertices are not adjacent,
then they share a common neighbor. If $D$ is an optimal distribution and
$|D|\leq 3$, then according to Lemma 3.1 $D$ is 2-restricted.

If $\pi^{*}(G)=4$, then we choose two non-adjacent vertices $u$ and $v$ and
place two pebbles at each of them. The vertices of $N(u)\cap N(v)$ are
$2$-reachable. Therefore each vertex which is adjacent to
$\\{u,v\\}\cup\left(N(u)\cap N(v)\right)$ is reachable. The size of this set
is at least $\frac{1}{3}n+2$. Therefore any vertex in $G$ is either in this
set or adjacent to it. So the constructed distribution is optimal and it is
$2$-restricted. $\Box$

Now we present infinitely many graphs whose optimal pebbling number and
$2$-restricted optimal pebbling number are different but their minimum degree
is large, where large means that it is almost half of the order.

The construction is the following: Consider two complete graphs of order $m$
where $m$ is even. Denote the vertices of the complete graphs by
$u_{1},u_{2},\ldots,u_{m}$ and $v_{1},v_{2},\ldots v_{m}$, respectively.
Remove the edges $\\{u_{i},u_{i+1}\\}$ and $\\{v_{i},v_{i+1}\\}$ for all $i$
which are odd. Note that we have removed a perfect matching. Add a vertex $w$
and add all the edges $\\{w,u_{i}\\}$ and $\\{w,v_{i}\\}$ where $i$ is odd.
Add the edges $\\{u_{i},v_{i}\\}$ for each even $i$. Denote this graph by
$H_{m}$. For an example see Figure 1. The minimum degree in this graph is
$m-1$ and the number of vertices is $2m+1$.

###### Claim 3.4

If $m\geq 4$, then $\pi_{2}^{*}(H_{m})=5$ but $\pi^{*}(H_{m})=4$.

Chelalli et al. have characterized the graphs whose 2-restricted optimal
pebbling number is at most 4. $\pi_{2}^{*}(G)\leq 4$ iff $G$ has vertices $u$
and $v$ such that $u\cup v\cup N(v)$ is a dominating set of $G$ [2]. Besides
this can be used to prove $\pi^{*}_{2}(H_{m})>5$, there are a lot of cases. To
shorten the proof, we are going to use a different lemma and the weight
argument, which was developed by Moews [11].

The _weight function_ of a pebble distribution $D$, which is defined on the
vertex set of $G$, is $W_{D}(u)=\sum_{v\in V(G)}D(v)2^{-d(u,v)}$. If the
distribution is clear from the context then we simply write $W(u)$. The weight
argument claims that if $W_{D}(u)<1$, then $u$ is not reachable under $D$.

###### Lemma 3.5

If $\pi^{*}_{2}(G)\leq 4$ and $G$ is connected, then $G$ has two vertices $x$
and $y$ such that the distribution

$D(v)=\begin{cases}2&\text{if }v\in\\{x,y\\}\\\ 0&\text{otherwise}\end{cases}$

is solvable.

Proof: Since $\pi^{*}_{2}(G)\leq 4$, $G$ has a solvable pebble distribution
$D^{\prime}$ whose size is 4 and it places its pebbles at more than one
vertex. If $D^{\prime}$ put pebbles at exactly two vertices, then $D^{\prime}$
places $2$ pebbles at each of the two vertices, because of the restriction,
and we are done.

If $D^{\prime}$ places pebbles at three vertices $u,v,w$ then we can assume
that $D^{\prime}(u)=2$ and $D(v)=D(w)=1$. By Lemma 2.1 we can assume that
$u,v$ and $w$ are $2$-reachable vertices. No other vertex is $2$-reachable
under $D^{\prime}$. Since $D^{\prime}$ is solvable, any other vertex of $G$
need to be adjacent to at least one of $u,v$ and $w$. The pebbles of $u$ are
needed in any pebbling sequence and $v$ and $w$ can receive a pebble, so one
of $u,v,w$ is adjacent to the other two. If $v,w\in N(u)$, then let

$D(x)=\begin{cases}2&\text{if }x\in\\{v,w\\}\\\
0&\text{otherwise.}\end{cases}$

In the other case we can assume WLOG that $v\in N\\{u,w\\}$ and let

$D(x)=\begin{cases}2&\text{if }x\in\\{u,w\\}\\\
0&\text{otherwise.}\end{cases}$

Since $u,v,w$ are $2$-reachable vertices under $D$ and every other vertex is
adjacent to one of them, $D$ is a solvable distribution.

If $4$ vertices have pebbles under $D^{\prime}$, then each of them has exactly
one pebble and no pebbling move is allowed, so $|V(G)|=4$. Consider a longest
path in $G$ and put $2$ pebbles at each of its end vertices. This is a
solvable distribution. Either the other two vertices are contained in a path
and they can receive a pebble from a neighbor or the path consists $3$
vertices and the fourth vertex is adjacent to the middle vertex which is
$2$-reachable. $\Box$

We have all the tools to prove Claim 3.4. In the proof we use the vertex
lables $u_{i},v_{i}$ and $w$ in the exact same way as we defined $H_{m}$.

Proof of Claim 3.4:

Let $D^{*}$ be the following pebble distribution:

$D^{*}(x)=\begin{cases}2&\text{if }x\in\\{v_{1},u_{1}\\}\\\ 1&\text{if }x=w\\\
0&\text{otherwise.}\end{cases}$

It is easy to see that any vertex except $u_{2}$ and $v_{2}$ can be reached by
a single pebbling move. The sequence $((u_{1}\rightarrow
u_{3}),(v_{1}\rightarrow w),(w\rightarrow u_{3}),(u_{3}\rightarrow u_{2}))$
put a pebble at $u_{2}$. Vertex $v_{2}$ can get a pebble in a similar manner,
so $D^{*}$ is solvable and $2$-restricted, thus $\pi_{2}^{*}(H_{m})\leq 5$.

Indirectly assume that $\pi^{*}_{2}(H_{m})\leq 4$. By Lemma 3.5 there are
vertices $x$ and $y$ in $H_{m}$ such that the distribution $D(x)=D(y)=2,\
D(z)=0$ if $z\notin\\{x,y\\}$ is solvable. We show by case by case analysis
that no such vertices do exist. Without loss of generality, assume that
$\sum_{i=1}^{m}D(u_{i})\leq\sum_{i=1}^{m}D(v_{i})$. Let $h,k,l,i$ be integers
between $1$ and $\left\lceil\frac{m}{2}\right\rceil$ and calculate the indices
of the vertices mod $m$.

Case 1. $D(w)=2$: If $D(v_{2k+1})=2$, then $W(u_{2k+2})=\frac{3}{4}$ so
$u_{2k+2}$ is not reachable. If $D(v_{2k})=2$, then $W(u_{2k+2})=1$. Assume
that there is a sequence of pebbling moves $\sigma$ which moves a pebble to
$u_{2k+2}$, so $D\sigma(u_{2k+2})=1$. Since a pebbling move cannot increase
$W(u_{2k+2})$ and it is already $1$, any move contained in $\sigma$ must not
decrease $W(u_{2k+2})$. The only pebbling moves which satisfy this condition
are $(v_{2k}\rightarrow u_{2k})$ and $(w\rightarrow u_{2j+1})$. But after the
application of these moves no more moves are available and $u_{2k+2}$ still
does not have a pebble, so no such $\sigma$ exists. Therefore $u_{2k+2}$ is
not reachable.

Case 2. $D(w)+\sum_{i=1}^{m}D(u_{i})=0$: If $D(v_{2k})=D(v_{2l})=2$ and $k\neq
l$, then $W(u_{2k-1})=\frac{3}{4}$, so it is not reachable. If
$D(v_{2k+1})=D(v_{2l+1})=2$ and $k\neq l$, then $W(u_{2k+2})=\frac{3}{4}$. If
$D(v_{2k+1})=D(v_{2l})=2$, then $W(u_{2l-1})=\frac{3}{4}$.

Case 3. $\sum_{i=1}^{m}D(u_{i})=2$: If $D(v_{2k+1})=D(u_{2l+1})=2$, then
$W(u_{2k+2})\leq\frac{3}{4}$.

If $D(v_{2k})=D(u_{2l})=2$, then $W(w)=1$. The only moves which do not
decrease $W(w)$ are $(v_{2k}\rightarrow v_{2h+1})$ and $(u_{2l}\rightarrow
u_{2i+1})$. But after the execution of these moves no pebbling move is
available and $w$ does not have a pebble so $w$ is not reachable in this case.

If $D(v_{2k+1})=D(u_{2l})=2$, then $W(u_{2l-1})=1$. The only move of the
pebbles of $v_{2k+1}$ which does not decrease $W(u_{2l-1})$ is
$(v_{2k+1}\rightarrow w)$. However $W(w)<2$, so the pebble which arrives at
$w$ cannot be moved further and the pebbles of $u_{2l}$ are not enough to
reach $u_{2l-1}$, so $u_{2l-1}$ is unreachable.

The subcase $D(u_{2k+1})=D(v_{2l})=2$ is equivalent to the previous subcase
due to symmetry.

We have find an unreachable vertex in each case, therefore no such $D$ exists.
This contradicts Lemma 3.5 and thus $\pi_{2}^{*}(H_{m})\geq 5$. $D^{*}$ is a
solvable $2$-restricted distribution and $|D^{*}|=5$, therefore
$\pi^{*}(H_{m})=5$.

Vertices $u_{i}$ and $v_{i}$ are neighbors of $w$ if $i$ is odd. When $i$ is
even, then $u_{i}$ has a neighbor $u_{j}$ where $j$ is odd. Therefore the
distance between any vertex and $w$ is at most $2$. Hence placing $4$ pebbles
at $w$ is a solvable distribution of size $4$. So $\pi^{*}(H_{m})\leq 4$.

Indirectly assume that $\pi^{*}(H_{m})<4$ and let $D^{\prime}$ be an optimal
distribution of $G$, thus $|D^{\prime}|\leq 3$. By lemma 3.1 $D^{\prime}$ does
not place $3$ pebbles at the same vertex, thus it is $2$-restricted solvable
distribution, which is a contradiction. $\Box$

$\delta(H_{m})=\frac{|V(H_{m})|-3}{2}$ and
$\pi_{2}^{*}(H_{m})\neq\pi^{*}(H_{m})$. This result and Claim 3.3 together
imply the existence of the following constant $c$: If $\delta(G)\geq c|V(G)|$,
then $\pi_{2}^{*}(G)=\pi^{*}(G)$, but for any $\epsilon>0$ there is a graph
$H$ such that $\delta(H)\geq(c-\epsilon)|V(G)|$ and
$\pi_{2}^{*}(H)\neq\pi^{*}(H)$. We have tried to determine this constant, but
up to this day we did not succeed. Our investigations lead us to state the
next conjecture.

Conjecture: If $\delta(G)\geq\frac{1}{2}|V(G)|$, then
$\pi_{2}^{*}(G)=\pi^{*}(G)$.

Note that those graphs whose minimum degree is at least half of their order
have diameter at most two. Corollary 3.2 implies that it is enough to show
that each of these graphs has a solvable $2$-restricted pebble distribution of
size $4$. We can use the results of [2] or Lemma 3.5 to reformulate the
previous conjecture as a dominating question.

Conjecture: If $\delta(G)\geq\frac{1}{2}|V(G)|$, then there are vertices $u$
and $v$ in $G$ such that $\\{u,v\\}\cup\left(N(u)\cap N(v)\right)$ is a
dominating set.

Open questions:

  1. 1.

Can $\pi_{2}^{*}(T)$ can be calculated in polynomial time if $T$ is a tree?

  2. 2.

Can $\pi^{*}(T)$ can be calculated in polynomial time if $T$ is a tree?

  3. 3.

What is the maximum $c$ such that $\delta(G)\geq c|V(G)|$ enforces
$\pi^{*}(G)=\pi_{2}^{*}(G)$?

## Acknowledgments

This research was supported by the Ministry of Innovation and Technology and
the National Research, Development and Innovation Office within the Artificial
Intelligence National Laboratory of Hungary.

## References

  * [1] D. Bunde, E. Chambers, D. Cranston, K. Milans, and D. West,  Pebbling and optimal pebbling in graphs  J. Graph Theory (2008) 57 no. 3 215–238.
  * [2] M. Chellali, T. W. Haynes, S. T. Hedetniemi, T. M. Lewis,  Restricted optimal pebbling and domination in graphs  Discrete Applied Math.  (2017) 221 46–53.
  * [3] C. Chen, C. Shiue,  An investigation of the game of defend the island  ICGA K.  40 (2018) 330–340.
  * [4] F. Chung,  Pebbling in hypercubes  SIAM J. Discrete Math.  (1989) 2 no. 4 467–472.
  * [5] E.J. Cockayne, P.M. Dreyer Sr., S.M. Hedetniemi, S.T. Hedetniemi,  Roman domination in graphs  Discrete Math. 278 (2004), 11–22.
  * [6] T. Friedman, C.Wyels,  Optimal pebbling of paths and cycles  arXiv:math/0506076 [math.CO]
  * [7] H. Fu, C. Shiue,  The optimal pebbling number of the caterpillar,  Taiwanese Journal of Mathematics (2009) 13 no. 2A 419–429.
  * [8] H. Fu, C. Shiue,  The optimal pebbling number of the complete m-ary tree,  Discrete Mathematics (2000) 222 no. 1–3 89–100.
  * [9] E. Győri, G. Y. Katona, L. F. Papp, C. Tompkins,  Optimal Pebbling Number of Staircase Graphs  Discrete Mathematics (2019) 342 , no. 7, 2148–2157.
  * [10] K. Milans, B. Clark,  The complexity of graph pebbling  SIAM J. Discrete Math.  (2006) 20 , no. 3, 769–798.
  * [11] D. Moews,  Pebbling graphs,  J. Combin. Theory (B) 55 (1992) 244–252.
  * [12] J. Muntz, S. Narayan, N. Streib, K. V. Ochten,  Optimal pebbling of graphs  Discrete Mathematics  (2007) 307 , 2315–2321.
  * [13] L. Pachter, H. Snevily, and B. Voxman,  On pebbling graphs  Congr. Numer. 107 (1995), 65–80.
  * [14] C. Shiue,  An investigation of the game of defend the island  Discrete Applied Math. 279 (2020), 125–133.
  * [15] C. Shiue,  Capacity restricted optimal pebbling in graphs  Discrete Applied Mathematics  260 (2019) 284–288.