The covering cover pebbling number for some acyclic graphs

Lourdusamy, A.; Mathivanan, T.

doi:10.61091/um122-03

Abstract

1. Introduction
2. The covering cover pebbling number for an m-ary tree
3. The covering cover pebbling number for a caterpillar

References

Utilitas Mathematica

Volume 122
Pages: 41-52

Research article

The covering cover pebbling number for some acyclic graphs

^¹, ^²

¹Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai – 627 002, Tamilnadu, India

²Department of Mathematics, Athoor Cooperative Arts and Science College, Seeval Saragu, Dindigul – 624 303, Tamilnadu, India

Received: 25/08/2025
Accepted: 25/02/2025
Published Online: 22/03/2025

Copyright Link
License

Abstract

The covering cover pebbling number, $σ (G)$ , of a graph $G$ , is the smallest number such that some distribution $D \in K$ is reachable from every distribution starting with $σ (G)$ (or more) pebbles on $G$ , where $K$ is a set of covering distributions. In this paper, we determine the covering cover pebbling number for two families of graphs those do not contain any cycles.

Keywords: pebbling number, covering set, acyclic graph

1. Introduction

Pebbling, one of the latest evolutions in graph theory proposed by Lakarias and Saks, has been the topic of vast investigation with significant observations. Having Chung [2] as the forerunner to familiarize pebbling into writings, many other authors too have developed this topic. Given a connected graph $G$ , distribute certain number of pebbles on its vertices in some configuration. Precisely, a configuration on a graph $G$ , is a function from $V (G)$ to $N \cup {0}$ representing a placement of pebbles on $G$ . The size of the configuration is the total number of pebbles placed on the vertices. A pebbling move is the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. In (regular) pebbling, the target is selected and the aim is to move a pebble to the target vertex. The minimum number of pebbles, such that regardless of their initial placement and regardless of the target vertex, we can pebble that target vertex is called the pebbling number of $G$ , denoted by $f (G)$ . In cover pebbling, the aim is to cover all the vertices with at least one pebble, when the pebbling process ends. The minimum number of pebbles required such that regardless of their initial placement on $G$ , there is a sequence of pebbling moves, at the end of which, every vertex has at least one pebble on it, is called the cover pebbling number of $G$ . The following definitions are stated from [3]:

Definition 1.1. A distribution or configuration $D$ is a function $D : V (G) ⟶ N$ where $D (v)$ represents the number of pebbles on the vertex $v$ . Also, for every distribution $D$ and every positive integer, we define $t D$ as the distribution given by $(t D) (v) = t D (v)$ for every vertex $v$ in $G$ .

Definition 1.2. Given two distributions $D^{'}$ and $D^{″}$ on a graph $G$ , we say that $D^{″}$ contains $D^{'}$ if $D^{'} (v) \leq D^{″} (v)$ for every vertex $v \in V (G)$ .

Definition 1.3. Given two distributions $D$ and $D^{'}$ on a graph $G$ , we say that $D^{'}$ is reachable from $D$ if it is possible to use a sequence of pebbling moves to go from $D$ to a distribution $D^{″}$ that contains $D$ .

Definition 1.4. Let $S$ be a set of distributions on a graph $G$ . The pebbling number of $S$ in $G$ , denoted $π (G, S)$ , is the smallest number such that every distribution $D \in S$ is reachable from every distribution that starts with $π (G, S)$ (or more) pebbles on $G$ .

We find similar definitions for the following concepts in [3]:

(i) pebbling number of a distribution D, i.e., $π (G, D)$ ,

(ii) t-pebbling number of a vertex in G, i.e., $π_{t} (G, v)$ ,

(iii) t-pebbling number of a graph G, i.e., $π_{t} (G)$ .

Definition 1.5. .In a distribution on a graph $G$ , a vertex with $D (v) \geq 1$ pebbles is called an occupied vertex.

Now we are going to define covering cover pebbling number of a graph $G$ , using Definition 1.2 and Definition 1.3. A set $K \subseteq V (G)$ is a covering [1], if every edge of $G$ has at least one end in $K$ . The concept of covering cover pebbling number was first introduced by Lourdusamy et al. [11], and they determined the covering cover pebbling number for complete graphs, paths, wheel graphs, complete r-partite graphs and binary trees in [11]. For more results on covering cover pebbling number, please refer to [7,8,9,11,10,4,5,6]. Let us now define some specific distribution and set of distributions that would be helpful in formulating Definition 1.8.

Definition 1.6. For a set $K \subseteq V (G)$ and a vertex $x \in V (G)$ , we define the distribution $χ_{K}$ on $G$ as the function:

$χ_{K} (x) = {\begin{cases} 1 if x \in K, \\ 0 otherwise, \end{cases}$

where the set $K$ forms a covering for $G$ .

Definition 1.7. We also let $K = {χ_{K} : K \subseteq V (G) is a covering set}$ . That is, $K$ is the set of covering distributions.

Definition 1.8. The covering cover pebbling number, $σ (G)$ , of a graph $G$ , is the smallest number such that some distribution $D \in K$ is reachable from every distribution starting with $σ (G)$ (or more) pebbles on $G$ .

Theorem 1.9. [11] For a Star graph $K_{m, 1}$ $(m \geq 2)$ , $σ (K_{m, 1}) = m$ .

Theorem 1.10.[11] $σ (B_{0}) = 1$ , $σ (B_{1}) = 2$ , $σ (B_{2}) = 12$ , $σ (B_{3}) = 86$ , $σ (B_{4}) = 634$ and for $n \geq 2$ , $σ (B_{n}) = 2^{n - 1} + \sum_{i = 0}^{⌊ \frac{n - 3}{2} ⌋} (2^{2 i + 1} + \sum_{j = 1}^{n - 2 i - 2} 2^{j - 1} 2^{2 i + 2 j + 1}) + \sum_{k = 1}^{⌊ \frac{n}{2} ⌋} 2^{n - 2 k} 2^{2 n - 2 k + 2} + 2^{2 ⌊ \frac{n - 1}{2} ⌋ + 1} .$

2. The covering cover pebbling number for an $m$ -ary tree

In this section, we are going to determine the covering cover pebbling number of an $m$ -ary tree ( $m \geq 2$ ), using Definition 1.8.

Definition 2.1. A complete $m$ -ary tree, denoted by $M_{n}$ , is a tree of height $n$ with $m^{i}$ vertices at distances $i$ from the root. Each vertex of $M_{n}$ has $m$ children except for the set of $m^{n}$ vertices that are at distance $n$ away from the root, none of which have children. The root is denoted by $R_{n}$ .

Obviously, $σ (M_{0}) = 1$ , and $σ (M_{1}) = m$ [11], since $M_{0} ≅ K_{1}$ , the complete graph on one vertex, and $M_{1} ≅ K_{1, m}$ , the star graph on $m + 1$ vertices.

Remark 2.2. Note that $M_{2}$ has $m - M_{1}$ ’s as subtrees on it. We label them, as $M_{11}$ , $M_{12}$ , $\dots$ , $M_{1 m}$ and their corresponding roots are $R_{11}$ , $R_{12}$ , $\dots$ , $R_{1 m}$ . So, in general, the complete $m$ -ary tree $M_{n}$ has $m - M_{n - 1}$ ’s as subtrees on it and hence we label them as $M_{(n - 1) 1}$ , $M_{(n - 1) 2}$ , $\dots$ , $M_{(n - 1) m}$ and we denote their corresponding roots by $R_{(n - 1) 1}$ , $R_{(n - 1) 2}$ , $\dots$ , $R_{(n - 1) m}$ . Let $v$ be the rightmost bottom vertex of $M_{n}$ .

Lemma 2.3. We can send a pebble to $R_{n}$ , the root of $M_{n}$ , at a cost of at most $2^{n}$ pebbles,

1) when $n = 2$ and there exists a $M_{1 i}$ ( $1 \leq i \leq m$ ), a subtree of $M_{2}$ , such that $p (M_{1 i}) \geq m + 3$ ,

2) when $n = 3$ and there exists a $M_{2 i}$ ( $1 \leq i \leq m$ ), a subtree of $M_{3}$ , such that $p (M_{2 i}) \geq m^{2} + 7 m$ ,

3) when $n = 4$ and there exists a $M_{3 i}$ ( $1 \leq i \leq m$ ), a subtree of $M_{4}$ , such that $p (M_{3 i}) \geq m^{3} + 31 m^{2} - 24 m + 14$ .

Proof. 1). Let $n = 2$ and $p (M_{1 i}) \geq m + 3$ for a subtree $M_{1 i}$ of $M_{2}$ . If $p (R_{1 i}) \geq 2$ or a vertex of $M_{1 i} - R_{1 i}$ has more than three pebbles or two verices of $M_{1 i} - R_{1 i}$ contain at least two pebbles each on them, then we can send one pebble to the root $R_{2}$ of $M_{2}$ easily at a cost of at most $4$ pebbles. If not, then $p (M_{1 i}) \leq 3 + (m - 1) = m + 2$ – a contradiction to our assumption.

2). Let $n = 3$ and $p (M_{2 i}) \geq m^{2} + 7 m$ for a subtree $M_{2 i}$ of $M_{3}$ . If $p (R_{2 i}) \geq 2$ then clearly we can move a pebble to $R_{3}$ . So assume that $p (R_{2 i}) \leq 1$ . Assume $p (R_{2 i}) = 0$ (otherwise, $⌈ \frac{m^{2} + 7 m - 1}{m} ⌉ \geq m + 3$ and hence we can move one more pebble to $p (R_{2 i})$ by (1)). Let $p (R_{2 i}) = 0$ . Clearly any one of the subtree of $M_{2 i}$ must contain at least $⌈ \frac{m^{2} + 7 m}{m} ⌉ \geq m + 7$ . By (1), we can move a pebble to $R_{2 i}$ and then the remaining number of pebbles on the subtree of $M_{2 i}$ is at least $m + 3$ . Again by (1), we can move another one pebble to $R_{2 i}$ and hence we move a pebble to $R_{3}$ using at most eight pebbles.

3). Let $n = 4$ and $p (M_{3 i}) \geq m^{3} + 31 m^{2} - 24 m + 14$ for a subtree $M_{3 i}$ of $M_{4}$ . If $p (R_{3 i}) \geq 2$ then we can move a pebble to $R_{4}$ . Assume $p (R_{3 i}) = 0$ (otherwise we are done). Then any one of the subtree of $M_{3 i}$ must contain at least $⌈ \frac{m^{3} + 31 m^{2} - 24 m + 14}{m} ⌉ \geq m^{2} + 31 m - 24$ . By (2), we can move a pebble (at a cost of at most 16 pebbles) to $R_{4}$ through $R_{3 i}$ , since the subtree of $M_{3 i}$ contains at least $m^{2} + 7 m + 8$ pebbles.

Theorem 2.4. For the m-ary tree $M_{2}$ , $σ (M_{2}) = m^{2} + 7 m - 6$ .

Proof. First, we place $m^{2} - m$ pebbles on the bottom vertices such that no $m$ pebbles of which share a parent and we did not put any pebbles on the vertex $v$ . And then we place $8 m - 7$ pebbles on the vertex $v$ , then no distribution of $K$ is reachable. Thus $σ (M_{2}) \geq m^{2} + 7 m - 6$ .

Now, consider the distribution of $m^{2} + 7 m - 6$ pebbles on the vertices of $M_{2}$ . According to the distributions of $p (M_{2})$ pebbles, we can partite them into three cases.

Case 1. Let $p (M_{1 i}) \geq m$ for all $1 \leq i \leq m$ .

If $p (R_{2}) \geq 1$ then there exists a distribution of $K$ which is reachable by our assumption and $σ (M_{1}) = m$ . Let $p (R_{2}) = 0$ . Any one of the subtree, say $M_{11}$ , must contain at least $⌈ \frac{m^{2} + 7 m - 6}{m} ⌉ \geq m + 4$ pebbles and hence we can move a pebble to $R_{2}$ by Lemma 2.3 (1). The remaining number of pebbles on $M_{11}$ is at least $m$ and thus there exists a distribution of $K$ which is reachable by our assumption and $σ (M_{1}) = m$ .

Case 2. Let $p (M_{1 i}) \leq m - 1$ for all $1 \leq i \leq m$ .

Clearly $p (R_{2}) \geq p (M_{2}) - m (m - 1) = 8 m - 7 \geq 2 m$ and hence we put one pebble each on the vertices $R_{11}$ , $R_{12}$ , $\dots$ , $R_{1 m}$ from the pebbles at $R_{2}$ . Thus, the distribution $χ_{{R_{11}, R_{12}, \dots, R_{1 m}}}$ of $K$ is reachable.

Case 3. Let $p (M_{1 i}) \leq m - 1$ for some $i$ .

Let $h$ subtrees contain at most $m - 1$ pebbles each on them, where $1 \leq h \leq m - 1$ . We prove this case by induction on $h \geq 1$ . Let $h = 1$ , that is, only one subtree, say $M_{1 m}$ , has at most $m - 1$ pebbles on it. So, our aim is to provide two pebbles to the root $R_{2}$ from the subtrees those have totally at least $m^{2} + 6 m - 5$ pebbles, so that we can move one pebble to $R_{1 m}$ . Clearly, any one of the subtree, say $M_{11}$ , must contain at least $⌈ \frac{m^{2} + 6 m - 5}{m - 1} ⌉ \geq m + 8$ and hence we can move two pebbles to $R_{2}$ while retaining $m$ pebbles, by Lemma 2.3 (1). Thus, the distribution $χ_{{K}} \cup χ_{{R_{1 m}}} = χ_{{K \cup R_{1 m}}}$ of $K$ is reachable, where $χ_{{K}}$ is a distribution of $K$ which is reachable from those subtrees having at least $m$ pebbles each on them and $χ_{{R_{1 m}}}$ is a reachable distribution of $K$ for $V (M_{1 m}) \cup R_{2}$ . So assume the result is true for $h \leq m - 2$ . Let $h = m - 1$ . WLOG, let $M_{11}$ be the subtree that contains at least $m$ pebbles. Clearly, $p (M_{11}) \geq p (M_{2}) - (m - 1) (m - 1) \geq 9 m - 7$ . We have to retain $m + 1$ pebbles on $M_{11}$ and thus $M_{11}$ has $8 m - 8$ extra pebbles on it. Now, we need at most eight pebbles from $M_{11}$ to put one pebble on a root vertex, say $R_{12}$ of the subtree $M_{12}$ , by induction and by Lemma 2.3 (1). After using eight pebbles (at most) from $M_{11}$ , the remaining number of pebbles is at least $(m + 1) + 8 (m - 2)$ and therefore we can move one pebble to every root vertex $R_{1 j}$ ( $j \neq 1$ , $2$ ) of $M_{1 j}$ by induction and by Lemma 2.3 (1). Thus, $M_{11}$ has at least $m + 1$ pebbles on it and hence we can move one pebble to $R_{11}$ easily. So the distribution $χ_{{R_{11}, R_{12}, \dots, R_{1 m}}}$ of $K$ is reachable.

Thus $σ (M_{2}) \leq m^{2} + 7 m - 6$ .

Theorem 2.5. For the m-ary tree $M_{3}$ , $σ (M_{3}) = m^{3} + 31 m^{2} - 24 m + 2$ .

Proof. First, we place $m^{3} - m^{2}$ pebbles on the bottom vertices such that no $m$ pebbles of which share a parent and we did not put any pebbles on the vertex $v$ . This leaves the rightmost bottom vertex $v$ unpebbled; and then we place $32 m^{2} - 24 m + 1$ pebbles on the vertex $v$ . Then no distribution of $K$ is reachable. Thus $σ (M_{3}) \geq m^{3} + 31 m^{2} - 24 m + 2$ .

Now, consider the distribution of $m^{3} + 31 m^{2} - 24 m + 2$ pebbles on the vertices of $M_{3}$ . According to the distributions of $p (M_{3})$ pebbles, we can partite them into three cases.

Case 1. Let $p (M_{2 i}) \geq m^{2} + 7 m - 6$ for all $1 \leq i \leq m$ .

If $p (R_{3}) \geq 1$ then there exists a distribution $χ_{{K \cup R_{3}}}$ of $K$ which is reachable by our assumption and $σ (M_{2}) = m^{2} + 7 m - 7$ , where $K \subseteq ⋃_{i = 1}^{m} V (M_{2 i})$ . Let $p (R_{3}) = 0$ . Any one of the subtree, say $M_{21}$ , must contain at least $⌈ \frac{m^{3} + 31 m^{2} - 24 m + 2}{m} ⌉ \geq m^{2} + 7 m + 2$ pebbles and hence we can move a pebble to $R_{3}$ by Lemma 2.3 (2). The remaining number of pebbles on $M_{21}$ is at least $m^{2} + 7 m - 6$ and thus there exists a distribution $χ_{{K \cup R_{3}}}$ of $K$ which is reachable by our assumption and $σ (M_{2}) = m^{2} + 7 m - 6$ , where $K \subseteq ⋃_{i = 1}^{m} V (M_{2 i})$ .

Case 2. Let $p (M_{2 i}) \leq m^{2} + 7 m - 7$ for all $1 \leq i \leq m$ .

Clearly $p (R_{3}) \geq p (M_{3}) - m (m^{2} + 7 m - 7) = 24 m^{2} - 17 m + 2 \geq 4 m^{2} + 1$ and hence we can put $2 m$ pebbles each on the vertices $R_{21}$ , $R_{22}$ , $\dots$ , $R_{2 m}$ from the pebbles at $R_{3}$ . Thus, the distribution $χ_{{R_{3} \cup K}}$ of $K$ is reachable, where $K = {v : d (v, R_{3}) = 2} \subseteq ⋃_{i = 1}^{m} V (M_{2 i})$ .

Case 3. Let $p (M_{2 i}) \leq m^{2} + 7 m - 7$ for some $i$ .

Let $h$ subtrees contain at most $m^{2} + 7 m - 7$ pebbles each on them, where $1 \leq h \leq m - 1$ . We prove this case by induction on $h \geq 1$ . Let $h = 1$ , that is, only one subtree, say $M_{2 m}$ , has at most $m^{2} + 7 m - 7$ pebbles on it. So, our aim is to provide $4 m + 1$ pebbles to the root $R_{3}$ from the subtrees $M_{2 i}$ ( $i \neq m$ ), those have totally at least $m^{3} + 30 m^{2} - 31 m - 5$ pebbles, so that we can move $2 m$ pebbles to $R_{2 m}$ from $R_{3}$ . Also, note that, any preexisting pebbles on $R_{3}$ or any pebbles on $M_{2 m}$ other than the $m (m - 1)$ pebbles on the bottom vertices of $M_{2 m}$ , $m - 1$ pebbles each with a different parent, only make our strategy easier to implement, so assume that $p (M_{2 m}) \leq m (m - 1)$ . Clearly, any one of the subtree, say $M_{21}$ , must contain at least $⌈ \frac{m^{3} + 30 m^{2} - 23 m + 2}{m - 1} ⌉ \geq m^{2} + 30 m - 23$ . Let $x \geq 0$ pebble(s) is/are sent by the other subtrees $M_{2 j}$ $j \neq 1, m$ to the root $R_{3}$ at a cost of at most $8 x$ pebbles by Lemma 2.3 (2). So, the remaining number of pebbles on $M_{21}$ is at least $m^{3} + 30 m^{2} - 23 m + 2 - (m - 2) (m^{2} + 7 m + 1) - 8 x \geq 25 m^{2} - 10 m + 4 - 8 x$ , and hence we can move $4 m - x + 1$ pebbles to the root $R_{3}$ from the subtree $M_{21}$ , by Lemma 2.3 (1) & (2). Assume the result is true for $h \leq m - 2$ . Let $h = m - 1$ . WLOG, let $M_{21}$ be the subtree that has at least $m^{2} + 7 m - 6$ pebbles. As we said earlier in this case, we also assume that the other subtrees only contain at most $m (m - 1)$ pebbles each on them. So, the subtree $M_{21}$ contains at least $p (M_{3}) - (m - 1) m (m - 1) \geq 33 m^{2} - 25 m + 2$ pebbles and hence we can move $4 m^{2} - 4 m + 1$ pebbles to the root $R_{3}$ from the subtree $M_{21}$ , by applying induction and by Lemma 2.3 (1) & (2). Thus, the distribution $χ_{{R_{3} \cup K \cup L}}$ of $K$ is reachable, where $K = {v : d (v, R_{3}) = 2} \subseteq ⋃_{i = 2}^{m} V (M_{2 i})$ and $L \subseteq V (M_{21})$ .

Thus $σ (M_{3}) \leq m^{3} + 31 m^{2} - 24 m + 2$ .

Theorem 2.6. For the m-ary tree $M_{4}$ , $σ (M_{4}) = m^{4} + 127 m^{3} - 96 m^{2} + 8 m - 30$ .

Proof. First, we place $m^{4} - m^{3}$ pebbles on the bottom vertices such that no $m$ pebbles of which share a parent. This should leave the rightmost bottom vertex unpebbled; and then we place $128 m^{3} - 96 m^{2} + 8 m - 31$ pebbles on the vertex $v$ . Then no distribution of $K$ is reachable. Thus $σ (M_{4}) \geq m^{4} + 127 m^{3} - 96 m^{2} + 8 m - 30$ .

Now, consider the distribution of $m^{4} + 127 m^{3} - 96 m^{2} + 8 m - 30$ pebbles on the vertices of $M_{4}$ . According to the distributions of $p (M_{4})$ pebbles, we can partite them into three cases.

Case 1. Let $p (M_{3 i}) \geq m^{3} + 31 m^{2} - 24 m + 2$ for all $1 \leq i \leq m$ .

If $p (R_{4}) \geq 1$ then there exists a distribution $χ_{{K \cup R_{4}}}$ of $K$ which is reachable by our assumption and $σ (M_{3}) = m^{3} + 31 m^{2} - 24 m + 2$ , where $K \subseteq ⋃_{i = 1}^{m} V (M_{3 i})$ . Let $p (R_{4}) = 0$ . Any one of the subtree, say $M_{31}$ , must contain at least $⌈ \frac{m^{4} + 127 m^{3} - 96 m^{2} + 8 m - 30}{m} ⌉ \geq m^{3} + 31 m^{2} - 24 m + 18,$ pebbles and hence we can move a pebble to $R_{4}$ by Lemma 2.3 (3). The remaining number of pebbles on $M_{31}$ is at least $m^{3} + 31 m^{2} - 24 m + 2$ and thus there exists a distribution $χ_{{K \cup R_{4}}}$ of $K$ which is reachable by our assumption and $σ (M_{3}) = m^{3} + 31 m^{2} - 24 m + 2$ , where $K \subseteq ⋃_{i = 1}^{m} V (M_{3 i})$ .

Case 2. Let $p (M_{3 i}) \leq m^{3} + 31 m^{2} - 24 m + 1$ for all $1 \leq i \leq m$ .

Clearly $p (R_{4}) \geq p (M_{4}) - m (m^{3} + 31 m^{2} - 24 m + 1) \geq 8 m^{3} + 2 m$ and hence we put $4 m^{2} + 1$ pebbles each on the vertices $R_{31}$ , $R_{32}$ , $\dots$ , $R_{3 m}$ from the pebbles at $R_{4}$ . Thus, the distribution $χ_{{R_{31}, R_{32}, \dots, R_{3 m} \cup K}}$ of $K$ is reachable, where $K = {v : d (v, R_{4}) = 3} \subseteq ⋃_{i = 1}^{m} V (M_{3 i})$ .

Case 3. Let $p (M_{3 i}) \leq m^{3} + 31 m^{2} - 24 m + 1$ for some $i$ .

Let $h$ subtrees contain at most $m^{3} + 31 m^{2} - 24 m + 1$ pebbles each on them, where $1 \leq h \leq m - 1$ . We prove this case by induction on $h \geq 1$ . Let $h = 1$ , that is, only one subtree, say $M_{3 m}$ , has at most $m^{3} + 31 m^{2} - 24 m + 1$ pebbles on it. We have to send $8 m^{2} + 1$ pebbles to the root $R_{4}$ from the subtrees those have totally at least $m^{4} + 126 m^{3} - 127 m^{2} + 32 m - 31$ pebbles, so that we can move $4 m^{2}$ pebbles to $R_{3 m}$ from $R_{4}$ . Also, note that, any preexixting pebbles on $R_{4}$ or any pebbles on $M_{3 m}$ other than the $m^{2} (m - 1)$ pebbles on the bottom vertices of $M_{3 m}$ , $m (m - 1)$ pebbles each with a different parent, only make our strategy easier to implement, so assume that $p (M_{3 m}) \leq m^{2} (m - 1)$ . Clearly, any one of the subtree, say $M_{31}$ , must contain at least $⌈ \frac{m^{4} + 126 m^{3} - 95 m^{2} + 8 m - 30}{m - 1} ⌉ \geq m^{3} + 126 m^{2} - 95 m - 14$ . Let $x \geq 0$ pebble(s) is/are sent by the other subtrees $M_{3 j}$ $j \neq 1, m$ , to the root $R_{4}$ at a cost of at most $16 x$ pebbles by Lemma 2.3 (3). So, the remaining number of pebbles on $M_{31}$ is at least $m^{4} + 126 m^{3} - 95 m^{2} + 8 m - 30 - (m - 2) (m^{3} + 31 m^{2} - 24 m + 13) - 16 x \geq 98 m^{3} - 10 m^{2} - 53 m - 4 - 16 x$ , and hence we can move $8 m^{2} + 1 - x$ pebbles to the root $R_{4}$ from the subtree $M_{31}$ , by Lemma 2.3 (3). Assume the result is true for $h = l \leq m - 2$ . Let $h = m - 1$ . WLOG, let $M_{31}$ be the subtree that has at least $m^{3} + 31 m^{2} - 24 m + 2$ pebbles. As we said earlier in this case, we also assume that the other subtrees only contain at most $m^{2} (m - 1)$ pebbles each on them. So, the subtree $M_{31}$ contains at least $p (M_{4}) - (m - 1) m^{2} (m - 1) \geq 129 m^{3} - 97 m^{2} + 8 m - 30$ pebbles and hence we can move $8 m^{3} - 8 m^{2}$ pebbles to the root $R_{4}$ and one pebble to $R_{31}$ from the subtree $M_{31}$ , by applying induction and by Lemma 2.3 (3). Thus, the distribution $χ_{K \cup L \cup M}$ of $K$ is reachable, where $K = {v : d (v, R_{4}) = 3} \subseteq ⋃_{i = 2}^{m} V (M_{3 i})$ , $L = {v : d (v, R_{4}) = 1}$ and $M \subseteq V (M_{31}) - {R_{31}}$ .

Thus $σ (M_{4}) \leq m^{4} + 127 m^{3} - 96 m^{2} + 8 m - 30$ .

Theorem 2.7. For $n \geq 2$ , $\begin{aligned} σ (M_{n}) = & m^{n - 1} (m - 1) + (m - 1) \sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{2 n - 2 k + 1} + 2^{2 ⌊ \frac{n - 1}{2} ⌋ + 1} \\ + \sum_{i = 0}^{⌊ \frac{n - 3}{2} ⌋} (2^{2 i + 1} + (m - 1) \sum_{j = 1}^{n - 2 i - 2} m^{j - 1} 2^{2 i + 2 j + 1}) . \end{aligned}$

Before proving the above theorem, we state a theorem below to prove Theorem 2.7, which is a generalization of the Lemma 2.3.

Theorem 2.8. We can send a pebble to $R_{n}$ , the root of $M_{n}$ , at a cost of at most $2^{n}$ pebbles, when $n = k$ $(k \geq 2)$ and there exists a $M_{(n - 1) i}$ ( $1 \leq i \leq m$ ), a subtree of $M_{n}$ , such that $p (M_{(n - 1) i}) \geq σ (M_{n - 1}) + 3 (2^{n - 2})$ .

Proof. It can be easily proved by induction on $k$ and using the Lemma 2.3.

Now, we are going to prove Theorem 2.7.

Proof of Theorem 2.7. Let $\begin{aligned} T (M_{n}) = & m^{n - 1} (m - 1) + (m - 1) \sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{2 n - 2 k + 1} + 2^{2 ⌊ \frac{n - 1}{2} ⌋ + 1} \\ + \sum_{i = 0}^{⌊ \frac{n - 3}{2} ⌋} (2^{2 i + 1} + (m - 1) \sum_{j = 1}^{n - 2 i - 2} m^{j - 1} 2^{2 i + 2 j + 1}) . \end{aligned}$

We place $m^{n - 1} (m - 1)$ pebbles on the bottom verices such that no $m$ pebbles of which share a parent. This should leave the rightmost bottom vertex unpebbled; and then we place $T (M_{n}) - m^{n - 1} (m - 1) - 1$ pebbles on the vertex $v$ . Then no distribution of $K$ is reachable. Thus $σ (M_{n}) \geq T (M_{n})$ .
We now proceed to prove the upper bound by induction. Clearly, the result is true for $n = 2, 3, 4$ by Thorem 2.4, 2.5 and 2.6. Consider the distribution of $T (M_{n})$ pebbles on the vertices of $M_{n}$ ( $n \geq 5$ ). According to the distributions of $T (M_{n})$ pebbles, we can partite them into three cases.

Case 1. Let $p (M_{(n - 1) i}) \geq T (M_{n - 1})$ for all $1 \leq i \leq m$ .

If $p (R_{n}) \geq 1$ then there exists a distribution of $K$ which is reachable by our assumption and $σ (M_{n - 1}) = T (M_{n - 1})$ . Let $p (R_{n}) = 0$ . Any one of the subtree, say $M_{(n - 1) 1}$ , must contain at least $⌈ \frac{T (M_{n})}{m} ⌉ \geq T (M_{n - 1}) + 2^{n}$ pebbles and hence we can move a pebble to $R_{n}$ by the Theorem 2.8. The remaining number of pebbles on $M_{(n - 1) 1}$ is at least $T (M_{n - 1})$ and thus there exists a distribution of $K$ which is reachable by our assumption and $σ (M_{n - 1}) = T (M_{n - 1})$ .

Case 2. Let $p (M_{(n - 1) i}) \leq T (M_{n - 1}) - 1$ for all $1 \leq i \leq m$ .

Clearly $p (R_{n}) \geq T (M_{n}) - m (T (M_{n - 1}) - 1) \geq m (\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1}) + 1$ and hence we put $\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k}$ pebbles each on the vertices $R_{(n - 1) 1}$ , $R_{(n - 1) 2}$ , $\dots$ , $R_{(n - 1) m}$ from the pebbles at $R_{n}$ . From the pebbles on $R_{(n - 1) i}$ , we move a pebble to every vertex in every second row, starting, in the subtree $M_{(n - 1) i}$ , with the row that is next to the bottom row. Thus, the distribution $χ_{{K \cup R_{n}}}$ of $K$ is reachable, where $K \subseteq ⋃_{i = 1}^{m} V (M_{(n - 1) i})$ .

Case 3. Let $p (M_{(n - 1) i}) \leq T (M_{n - 1}) - 1$ for some $i$ .

Let $h$ subtrees contain at most $T (M_{n - 1}) - 1$ pebbles each on them, where $1 \leq h \leq m - 1$ . We prove this case by induction on $h \geq 1$ . Let $h = 1$ , that is, only one subtree, say $M_{(n - 1) m}$ , has at most $T (M_{n - 1}) - 1$ pebbles on it. So, our aim is to provide $(\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1})$ pebbles to the root $R_{n}$ from the subtrees those have totally at least $T (M_{n}) - m^{n - 2} (m - 1)$ pebbles, so that we can move $(\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k})$ pebbles to $R_{(n - 1) m}$ . Clearly, any one of the subtree, say $M_{(n - 1) 1}$ , must contain at least $⌈ \frac{T (M_{n}) - m^{n - 2} (m - 1)}{m - 1} ⌉ \geq T (M_{n - 1}) + 2^{n} (\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1} + 1)$ and hence we can move $(\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1}) + 1$ pebbles to $R_{n}$ while retaining $T (M_{n - 1})$ pebbles, by the Theorem 2.8. Thus, the distribution $χ_{{K \cup L \cup R_{n}}}$ of $K$ is reachable, where $χ_{{K}}$ is a distribution of $K$ which is reachable from those subtrees having at least $T (M_{n - 1})$ pebbles each on them, $χ_{{L}}$ is a reachable distribution of $K$ in $M_{(n - 1) m}$ and $χ_{{R_{n}}}$ is a reachable distribution of $K$ for the incident edges of $R_{n}$ . So assume the result is true for $h = l \leq m - 2$ . Let $h = m - 1$ . WLOG, let $M_{(n - 1) 1}$ be the subtree that contains at least $T (M_{n - 1})$ pebbles. Clearly, $p (M_{(n - 1) 1}) \geq T (M_{n}) - (m - 1) m^{n - 2} (m - 1) \geq T (M_{n - 1}) + 2^{n} (m - 1) (\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1}) + (m - 1) m^{n - 2}$ . We have to retain $T (M_{n - 1})$ pebbles on $M_{(n - 1) 1}$ and thus $M_{(n - 1) 1}$ has $2^{n} (m - 1) (\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1})$ extra pebbles on it. Now, we need at most $2^{n + 1}$ pebbles from $M_{(n - 1) 1}$ to put one pebble on a root vertex, say $R_{(n - 1) 2}$ of the subtree $M_{(n - 1) 2}$ , by induction and by the Theorem 2.8. After using at most $2^{n} (\sum_{k = 1}^{⌊ \frac{n}{3} ⌋} m^{n - 2 k} 2^{n - 2 k + 1})$ pebbles from $M_{(n - 1) 1}$ , the remaining number of pebbles is at least $T (M_{n - 1}) + 2^{n} (m - 2) (\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k + 1}) + (m - 1) m^{n - 2}$ and therefore we can move $(\sum_{k = 1}^{⌊ \frac{n}{2} ⌋} m^{n - 2 k} 2^{n - 2 k})$ pebbles to every root vertex $R_{(n - 1) j}$ ( $j \neq 1$ , $2$ ) of $M_{(n - 1) j}$ by induction and by the Theorem 2.8. In this process, for even values of $n$ , as we place one pebble each on the root vertex $R_{(n - 1) j}$ (for all $j \neq 1$ ), the edges between $R_{n}$ and $R_{(n - 1) j}$ is also covered. The edge between $R_{n}$ and $R_{(n - 1) 1}$ can also be covered as the root vertex $R_{(n - 1) 1}$ can be pebbled with at least $T (M_{n - 1}) = σ (M_{n - 1})$ on the vertices of $M_{(n - 1) 1}$ . For the case when $n$ is odd, as there are $2^{n}$ extra pebbles (after covering all the edges of $M_{(n - 1) 1}$ ), we can pebble the root vertex $R_{n}$ of $M_{n}$ and thus the edge $R_{n} R_{(n - 1) 1}$ is also covered. So there exists a distribution of $K$ is reachable.

Thus, $σ (M_{n}) \leq T (M_{n})$ .

Corollary 2.9. [11] $σ (B_{0}) = 1$ , $σ (B_{1}) = 2$ , $σ (B_{2}) = 12$ , $σ (B_{3}) = 86$ , $σ (B_{4}) = 634$ and for $n \geq 2$ , $σ (M_{n}) = 2^{n - 1} + \sum_{k = 1}^{⌊ \frac{n}{2} ⌋} 2^{n - 2 k} 2^{2 n - 2 k + 1} + 2^{2 ⌊ \frac{n - 1}{2} ⌋ + 1} + \sum_{i = 0}^{⌊ \frac{n - 3}{2} ⌋} (2^{2 i + 1} + \sum_{j = 1}^{n - 2 i - 2} 2^{j - 1} 2^{2 i + 2 j + 1}) .$

Proof.Let $m = 2$ in Theorem 2.7.

3. The covering cover pebbling number for a caterpillar

In this section, we are going to determine the covering cover pebbling number of a caterpiller, using Definition 1.8.

Definition 3.1. A tree $T$ is called a caterpillar if the deletion of all pendent vertices of the tree results in a path $P^{^{'}}$ , the spine of the caterpillar $T$ . For convenience, we shall call a path $P$ with maximum length which contains $P^{^{'}}$ a body of the caterpillar, and all the edges which are incident to pendent vertices are the legs of the caterpillar $T$ . Furthermore, the vertex $v \in V (P)$ is a joint of $T$ provided that $d e g_{T} (v) \geq 3$ or $v$ is adjacent to the end vertices.

In otherwords, a tree is said to be caterpillar iff all nodes of degree three or more are surrounded by at most two nodes of degree two or greater.

Let $C (n, s_{1}, s_{2}, s_{3}, \dots, s_{n})$ be the caterpillar tree T such that the spine $P^{^{'}} : v_{1} v_{2} v_{3} \dots v_{n}$ has $n$ vertices and let the vertex $v_{i} \in V (P^{^{'}})$ has $s_{i} \geq 0$ pendant vertices where $1 \leq i \leq n$ . Clearly $s_{1} \geq 1$ and $s_{n} \geq 1$ , and hence we label a vertex as $v_{0}$ which is adjacent to $v_{1}$ and label another vertex as $v_{n + 1}$ which is adjacent to $v_{n}$ . Let $I = {v_{i} : s_{i} \geq 2}$ where $1 \leq i \leq n$ and let $J = {v_{j} : s_{j} = 1}$ where $1 \leq j \leq n$ . Let $I \cup J = {v_{1}, v_{k}, v_{l}, \dots, v_{m}, v_{n} : 1 < k < l < \dots < m < n}$ .

Theorem 3.2. [11] For the path $P_{n}$ $(n \geq 2)$ , $σ (P_{n}) = ⌈ \frac{2^{n} - 1}{3} ⌉$ .

Theorem 3.3. For a caterpillar $C (n, s_{1}, s_{2}, \dots, s_{n})$ , the covering cover pebbling number is equal to, $\sum_{v_{a} \in I \cup J} 2^{a} - {\begin{cases} 1 & if v_{2} \in I \cup J or | P_{A}^{1 k} | = 0 (mod 2) \\ 0 & otherwise \end{cases} + \sum_{v_{a} \in I \cup J} (s_{a} - 1) + \sum_{v_{b}, v_{c} \in I \cup J} 2^{b + 1} T (P_{A}^{b c}),$ where $v_{b}$ and $v_{c}$ $(b < c)$ are a pair of consecutive vertices in $I \cup J$ , and $P_{A}^{b c} : v_{b + 1} v_{b + 2} \dots v_{c - 2} v_{c - 1}$ with $T (P_{A}^{b c}) = σ (P_{d}) if | P_{A}^{b c} | = d \geq 2$ and $0$ otherwise.

Proof. Let $p (C) = \sum_{v_{a} \in I \cup J} 2^{a} - {\begin{cases} 1 & if v_{2} \in I \cup J or | P_{A}^{1 k} | = 0 (mod 2) \\ 0 & otherwise \end{cases} + \sum_{v_{a} \in I \cup J} (s_{a} - 1) + \sum_{v_{b}, v_{c} \in I \cup J} 2^{b + 1} T (P_{A}^{b c}) .$ First we place one pebble each on the $s_{i} - 1$ pendant vertices of $v_{i} \in I$ for all $i$ , and place zero pebbles on the pendant vertex of $v_{j} \in J$ for all $j$ such that we do not place pebbles on $v_{0}$ . After that we place $p (C) - \sum_{v_{a} \in I \cup J} (s_{a} - 1)$ pebbles on the vertex $v_{0}$ and zero pebbles on the other vertices of $C (n, s_{1}, s_{2}, \dots, s_{n})$ . Thus no distribution of $K$ is reachable and so $σ (C (n, s_{1}, s_{2}, \dots, s_{n})) \geq p (C)$ .

Now consider the distribution of $p (C)$ pebbles on the vertices of $C (n, s_{1}, s_{2}, \dots, s_{n})$ . Here our strategy is to move one pebble each to the vertices belong to $I \cup J$ and we have to cover the edges of in between vertices, for example $v_{k}$ and $v_{l}$ , of $I \cup J$ using the path $P_{A}^{k l}$ , if needed. Note that if we have one pebble each at the $s_{i} - 1$ pendant vertices of $v_{i} \in I$ does not decrease the number of pebbles needed for $v_{i}$ from the other vertex. If we add one more pebble to a pendant vertex of $v_{i}$ , clearly all edges except $v_{i - 1} v_{i}$ and $v_{i} v_{i + 1}$ incident with the vertex $v_{i}$ is covered. We now prove that a worst case scenario is indeed the one in which all the $p (C) - \sum_{v_{a} \in I \cup J} (s_{a} - 1)$ pebbles are in either $v_{0}$ or $v_{n + 1}$ , first we let $v_{0}$ be the vertex: Let $C$ be a worst case configuration that contains pebbles on $P^{^{'}} \cup {v_{n + 1}} \cup {unpebbled pendant vertices}$ other than those on the above mentioned pendant vertices. Then moving all of these to the vertex $v_{0}$ would require us to use more pebbles to cover the edges of $C (n, s_{1}, s_{2}, \dots, s_{n})$ , a contradiction to the fact that $C$ is a worst case configuration. Also, as noted before, removing single pebble from the pebbled pendant vertices does not lessen the covering cover pebbling number starting at $v_{0}$ .

Now, we put one pebble each to the vertices of $I \cup J$ from $v_{0}$ to cover the incident edge of the unpebbled pendant vertices which are adjacent to some vertices of $I \cup J$ . Clearly, to achieve that we need $\sum_{v_{a} \in I \cup J} 2^{a}$ pebbles from $v_{0}$ . Let $v_{k}$ be the next vertex in $I \cup J$ after the vertex $v_{1}$ . We have to cover the edges between the vertices $v_{1}$ and $v_{k}$ in $C (n, s_{1}, s_{2}, \dots, s_{n})$ . Clearly, we have covered the incident edges of $v_{1}$ and $v_{k}$ . Consider the path $P_{A}^{1 k} : v_{2} v_{4} \dots v_{k - 2} v_{k - 1}$ . To cover the edges of this $P_{A}^{1 k}$ path from the vertex $v_{0}$ , we need $2^{3} σ (P_{d})$ pebbles if $| P_{A}^{1 k} | = d \geq 2$ and we don’t need any pebbles if $| P_{A}^{1 k} | \leq 1$ . We do the same procedure for other pairs of consecutive verices $(v_{k}, v_{l})$ , $\dots$ , $(v_{m}, v_{n})$ of $I \cup J$ . So, to cover the edges between the vertices of the pair of vertices of $I \cup J$ , we need $\sum_{v_{b}, v_{c} \in I \cup J} 2^{b + 1} T (P_{A}^{b c})$ pebbles from $v_{0}$ . Clearly, we are done using $p (C)$ pebbles if $v_{2} \notin I \cup J$ and $| P_{A}^{1 k} | \neq 0 (mod 2)$ . Suppose $v_{2} \in I \cup J or | P_{A}^{1 k} | = 0 (mod 2)$ , then we remove the single pebble at $v_{1}$ and put one pebble at $v_{0}$ . So we subtract one pebble for the case $v_{2} \in I \cup J or | P_{A}^{1 k} | = 0 (mod 2)$ . Thus we have covered all the edges of $C (n, s_{1}, s_{2}, \dots, s_{n})$ using $p (C)$ pebbles.

We relabel the vertices $v_{n + 1}, v_{n}, \dots, v_{1}, v_{0}$ by $v_{0}, v_{1}, \dots, v_{n}, v_{n + 1}$ respectively and then we do the same thing as we did above. Finally choose the one (before relabeling or after relabeling) having maximum amount of pebbles with it will be the covering cover pebbling number for $C (n, s_{1}, s_{2}, \dots, s_{n})$ .

For our convenience, we take $p (C) = T_{11} + T_{12} + T_{13}$ , where $\begin{aligned} T_{11} = & \sum_{v_{a} \in I \cup J} 2^{a} - {\begin{cases} 1 & if v_{2} \in I \cup J or | P_{A}^{1 k} | = 0 (mod 2), \\ 0 & otherwise, \end{cases} \\ T_{12} = & \sum_{v_{b}, v_{c} \in I \cup J} 2^{b + 1} T (P_{A}^{b c}), \end{aligned}$ and $T_{13} = \sum_{v_{a} \in I \cup J} (s_{a} - 1) .$

Theorem 3.4. For the path $P_{n}$ ( $n \geq 4$ ), $σ (P_{n}) = 2^{n - 2} + 4 σ (P_{n - 4}) + 2 - {\begin{cases} 1 & if | P_{A}^{1 (n - 2)} | = 0 (mod 2), \\ 0 & otherwise. \end{cases}$

Proof. Let $P_{n} : v_{0} v_{1} \dots v_{n - 1}$ . Clearly, $I = \emptyset$ and $J = {v_{1}, v_{n - 2}}$ , so $s_{1} = 1$ , $s_{n - 2} = 1$ and $I \cup J = {v_{1}, v_{n - 2}}$ . Then $P_{A}^{1 (n - 2)} : v_{2} \dots v_{n - 3}$ . Now we are going to apply Thorem 3.3.

Case 1. $| P_{A}^{1 (n - 2)} | = 0 (mod 2)$ .

$\begin{aligned} T_{11} = & (2 + 2^{n - 2}) - 1 = 2 + 2^{n - 2} - 1, \\ T_{12} = & 2^{2} T (P_{A}^{1 (n - 2)}) = 4 σ (P_{n - 4}), \end{aligned}$ and $T_{13} = (s_{1} - 1) + (s_{n - 2} - 1) = 0.$ Thus $σ (P_{n}) = 2^{n - 2} + 4 σ (P_{n - 4}) + 1$ .

Case 2. $| P_{A}^{1 (n - 2)} | \neq 0 (mod 2)$ .

$T_{11} = 2 + 2^{n - 2}$ , $T_{12} = 4 σ (P_{n - 4})$ and $T_{13} = 0.$ Thus $σ (P_{n}) = 2^{n - 2} + 4 σ (P_{n - 4}) + 2$ .

Definition 3.5. A graph is called Double Star-Path(DSP) if the end vertices of a path $P : v_{1} v_{2} \dots v_{n}$ on $n$ vertices adjoint to the center vertices of the star graphs $K_{1, l}$ $(l \geq 2)$ and $K_{1, m}$ $(m \geq 2)$ respectively. We denote it by $P_{n} (l, m)$ .

Corollary 3.6. For the graph Double Star-Path $P_{n} (l, m)$ , $σ (P_{n} (l, m)) = 2^{n} + 4 σ (P_{n - 2}) + l + m - {\begin{cases} 1 & if | P_{A}^{1 n} | = 0 (mod 2), \\ 0 & otherwise, \end{cases}$ where $P_{A}^{1 n} : v_{2} v_{3} \dots v_{n - 1}$ ( $n \geq 4$ ). Note that, we let $σ (P_{n - 2}) = 0$ if $n \leq 3$ .

Proof. Let $P_{n + 2} : v_{0} v_{1} \dots v_{n + 1}$ . Clearly, $I = {v_{1}, v_{n}}$ and $J = \emptyset$ , so $s_{1} = l$ , $s_{n} = m$ and $I \cup J = {v_{1}, v_{n}}$ . Then $P_{A}^{1 n} : v_{2} \dots v_{n - 1}$ . Now we are going to apply Thorem 3.3.

Case 1. $| P_{A}^{1 n} | = 0 (mod 2)$ .

$\begin{aligned} T_{11} = & 2 + 2^{n} - 1, \\ T_{12} = & 2^{2} T (P_{A}^{1 n}) = 4 σ (P_{n - 2}), \end{aligned}$ and $T_{13} = (s_{1} - 1) + (s_{n} - 1) = l + m - 2.$

Thus $σ (P_{n} (l, m)) = 2^{n} + 4 σ (P_{n - 2}) + l + m - 1$ .

Case 2. $| P_{A}^{1 (n - 2)} | \neq 0 (mod 2)$ .

$T_{11} = 2 + 2^{n}, T_{12} = 4 σ (P_{n - 2}) and T_{13} = l + m - 2.$

Thus $σ (P_{n} (l, m)) = 2^{n} + 4 σ (P_{n - 2}) + l + m$ .

Definition 3.7. The class of fuses is defined as follows: the vertices of a Fuse $F_{l} (k)$ ( $l \geq 1$ and $k \geq 2$ )are $v_{0} v_{1}, v_{2}, \dots, v_{n - 1}$ with $n = l + k + 1$ , so that the first $l + 1$ vertices form a path from $v_{0} v_{1}, v_{2}, \dots, v_{l}$ , and the remaining vertices $v_{l + 1}, v_{l + 2}, \dots, v_{n - 1}$ are independent and adjacent only to $v_{l}$ . The path sometimes called the wick, while the remaining vertices are sometimes called the sparks. For example, $F_{1} (k)$ is the star $K_{1, k + 1}$ on $k + 2$ vertices.

Corollary 3.8. For the Fuse graph $F_{l} (k)$ ( $l \geq 2$ ), the covering cover pebbling number is equal to $2^{l} + 4 σ (P_{l - 2}) + k + 1 - {\begin{cases} 1 & if | P_{A}^{1 l} | = 0 (mod 2), \\ 0 & otherwise. \end{cases}$

Proof. Let $P_{l + 2} : v_{0} v_{1} \dots v_{l} v_{l + 1}$ . Clearly, $I = {v_{l}}$ and $J = {v_{1}}$ , so $s_{1} = 1$ , $s_{l} = k$ and $I \cup J = {v_{1}, v_{l}}$ . Then $P_{A}^{1 l} : v_{2} \dots v_{l - 1}$ . Now we are going to apply Theorem 3.3.

Case 1. $| P_{A}^{1 l} | = 0 (mod 2)$ .

$\begin{aligned} T_{11} = & 2 + 2^{l} - 1, \\ T_{12} = & 4 σ (P_{l - 2}), \end{aligned}$ and $T_{13} = k - 1.$

Thus $σ (F_{l} (k)) = 2^{l} + 4 σ (P_{l - 2}) + k$ .

Case 2. $| P_{A}^{1 l} | \neq 0 (mod 2)$ . $T_{11} = 2 + 2^{l}, T_{12} = 4 σ (P_{l - 2}) and T_{13} = k - 1.$ Thus $σ (F_{l} (k)) = 2^{l} + 4 σ (P_{l - 2}) + k + 1$ .

References:

S. Arumugam and S. Ramachandran. Covering set in graphs. In Invitation to Graph Theory. Scitech publications (India) pvt. ltd., 2008.
F. R. K. Chung. Pebbling in hypercubes. SIAM Journal on Discrete Mathematics, 2:467–472, 1989. https://doi.org/10.1137/0402041.
D. Herscovici, B. Hester, and G. Hurlbert. Generalizations of graham’s pebbling conjecture. Discrete Mathematics, 312:2286–2293, 2012. https://doi.org/10.1016/j.disc.2012.03.032.
A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for even cyclic lollipop. General Mathematics Notes, 5(2):24–41, 2011.
A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for odd cyclic lollipop. International Journal of Pure and Applied Sciences and Technology, 5(2):1–40, 2011.
A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for sun. International Journal of Pure and Applied Sciences and Technology, 5(2):109–118, 2011.
A. Lourdusamy and T. Mathivanan. Covering cover pebbling number for the square of a cycle. Journal of Prime Research in Mathematics, 8:102–105, 2012.
A. Lourdusamy and T. Mathivanan. Covering cover pebbling number for the square of a path. Gulf Journal of Mathematics, 2(2):83–87, 2014. http://dx.doi.org/10.56947/gjom.v2i2.199.
A. Lourdusamy and T. Mathivanan. The domination cover pebbling number for some cyclic graphs and path graphs. Ars Combinatoria, 138:51–61, 2018.
A. Lourdusamy and A. P. Tharani. Covering cover pebbling number of hypercube and diameter d graphs. Journal of the Korea society of Mathematical Education Series B, 15(2):121–134, 2008.
A. Lourdusamy and A. P. Tharani. Covering cover pebbling number. Utilitas Mathematica, 78:41–54, 2009.

[1] S. Arumugam and S. Ramachandran. Covering set in graphs. In Invitation to Graph Theory. Scitech publications (India) pvt. ltd., 2008.

[2] F. R. K. Chung. Pebbling in hypercubes. SIAM Journal on Discrete Mathematics, 2:467–472, 1989. https://doi.org/10.1137/0402041.

[3] D. Herscovici, B. Hester, and G. Hurlbert. Generalizations of graham’s pebbling conjecture. Discrete Mathematics, 312:2286–2293, 2012. https://doi.org/10.1016/j.disc.2012.03.032.

[4] A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for even cyclic lollipop. General Mathematics Notes, 5(2):24–41, 2011.

[5] A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for odd cyclic lollipop. International Journal of Pure and Applied Sciences and Technology, 5(2):1–40, 2011.

[6] A. Lourdusamy, S. S. Jayaseelan, and T. Mathivanan. Covering cover pebbling number for sun. International Journal of Pure and Applied Sciences and Technology, 5(2):109–118, 2011.

[7] A. Lourdusamy and T. Mathivanan. Covering cover pebbling number for the square of a cycle. Journal of Prime Research in Mathematics, 8:102–105, 2012.

[8] A. Lourdusamy and T. Mathivanan. Covering cover pebbling number for the square of a path. Gulf Journal of Mathematics, 2(2):83–87, 2014. http://dx.doi.org/10.56947/gjom.v2i2.199.

[9] A. Lourdusamy and T. Mathivanan. The domination cover pebbling number for some cyclic graphs and path graphs. Ars Combinatoria, 138:51–61, 2018.

[10] A. Lourdusamy and A. P. Tharani. Covering cover pebbling number of hypercube and diameter d graphs. Journal of the Korea society of Mathematical Education Series B, 15(2):121–134, 2008.

[11] A. Lourdusamy and A. P. Tharani. Covering cover pebbling number. Utilitas Mathematica, 78:41–54, 2009.

Contents

Utilitas Mathematica

The covering cover pebbling number for some acyclic graphs

Abstract

1. Introduction

2. The covering cover pebbling number for an $m$ -ary tree

3. The covering cover pebbling number for a caterpillar

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Utilitas Mathematica

The covering cover pebbling number for some acyclic graphs

Abstract

1. Introduction

2. The covering cover pebbling number for an m-ary tree

3. The covering cover pebbling number for a caterpillar

References:

Information

Guidelines

CP Initiatives

Follow CP

2. The covering cover pebbling number for an $m$ -ary tree