Given a connected graph \(G\) and a configuration \(D\) of pebbles on the vertices of \(G\), a pebbling transformation involves removing two pebbles from one vertex and placing one pebble on its adjacent vertex. A monophonic path is defined as a chordless path between two non-adjacent vertices \(u\) and \(v\). The monophonic cover pebbling number, \(\gamma_{\mu}(G)\), is the minimum number of pebbles required to ensure that, after a series of pebbling transformations using monophonic paths, all vertices of \(G\) are covered with at least one pebble each. In this paper, we determine the monophonic cover pebbling number (\(MCPN\)) for the gear graph, sunflower planar graph, sun graph, closed sun graph, tadpole graph, lollipop graph, double star-path graph, and a class of fuses.
A pebbling move is defined as the removal of two pebbles from one vertex, followed by the placement of one pebble on an adjacent vertex, while the other pebble is eliminated. The pebbling number of a vertex \(v\) in a graph \(G\) is the smallest positive integer \(f(G, v)\) such that, for every distribution of \(f(G, v)\) pebbles on the vertices of \(G\), one pebble can be moved to \(v\) through a sequence of pebbling moves. The pebbling number \(f(G)\) is the maximum of \(f(G, v)\) over all vertices of \(G\). For more information on graph pebbling, interested readers can refer to [5].
The pebbling problem focuses on ensuring that one pebble can reach any specified target vertex. This problem can be interpreted as the transmission of information from one specific location to a target location. However, a natural question arises: how can information reach all locations of a graph simultaneously within a reasonable time? In pebbling terminology, this requires placing one pebble on all the vertices of the graph \(G\) simultaneously. For example, in an Adhoc Network, if there is congestion in the network, the information must reach neighboring locations immediately. This question is addressed by a variation of pebbling, called the cover pebbling number.
The cover pebbling number of a graph \(\gamma(G)\) is the minimum number of pebbles required such that, for any configuration of \(\gamma(G)\) pebbles on the vertices of \(G\), each vertex will have at least one pebble after a series of pebbling moves. At the end of this process, no vertex is left uncovered. Crull et al. [3] introduced the concept of cover pebbling, determining the cover pebbling number for complete graphs, paths, and trees. In [6], Hulbert and Munyan determined the cover pebbling number of the \(d\)-cube. Later, in 2010, Subido and Aniversario [10] expanded upon the work of Crull et al. by determining the cover pebbling number of graphs via a key vertex. Furthermore, Vuong and Wyckoff [11] introduced the stacking conjecture, where all pebbles for cover pebbling are placed on a single vertex. For any connected graph \(G\), by the stacking theorem, \(\gamma(G) = \sum\limits_{u \in V(G)} 2^{\text{dist}(u, v)}\). Any vertex \(v\) satisfying this equation is a key vertex of the graph. Selecting a suitable key vertex is particularly challenging for random graphs, graphs with a large number of vertices, and graphs with varying diameters. Specifically, the intuition of obtaining the cover pebbling number of graphs by distributing pebbles over the vertices of \(G\) is equivalent to finding the cover pebbling number by stacking all the pebbles at a suitable key vertex.
Santhakumaran et al. [9] introduced the concept of monophonic distance in graphs. The monophonic distance between \(u\) and \(v\), denoted as \(d_m(u, v)\), is the length of the longest \(u\)–\(v\) monophonic path in \(G\). For any two vertices \(u\) and \(v\) in a connected graph \(G\), a \(u\)–\(v\) path is a monophonic path if it contains no chords [9]. (A chord is a line segment connecting two points on a curve.) Lourdusamy et al. [7] defined the monophonic pebbling number using monophonic paths. The monophonic pebbling number, \(\mu(G)\), of a connected graph \(G\), is the smallest positive integer \(n\) such that any distribution of \(n\) pebbles on \(G\) allows one pebble to be moved to any specified vertex using monophonic paths via a sequence of pebbling moves.
Building on these definitions, we introduce the concept of a monophonic cover pebbling number. The monophonic cover pebbling number, \(\gamma_{\mu}(G)\), is the minimum number of pebbles required to cover all the vertices of \(G\) with at least one pebble on each vertex after a series of pebbling transformations using monophonic paths. While the pebbling number of a graph is determined using the shortest distance in a graph \(G\), the monophonic pebbling number is determined using monophonic distance. These two concepts play a crucial role in applications such as the supply of goods and transportation problems. When geodesic paths are unavailable, monophonic paths can serve as alternatives. The choice of paths directly impacts the cost of goods. Similarly, these concepts are applicable in network information transmission from one node to another. The monophonic cover pebbling number ensures the equitable distribution of goods across all customers using monophonic paths. For basic terminologies in graph theory, readers can refer to [1] and [2].
In this paper, we determine the monophonic cover pebbling number for various graphs, including the gear graph, sunflower planar graph, sun graph, closed sun graph, tadpole graph, lollipop graph, double star-path graph, and a class of fuses.
The notation \(G_n\) stands for the gear graph, which is taken from [4]. The notation \(Sf_n\) stands for the sunflower planar graph, also taken from [4]. The notation \(S_u\) stands for the sun graph, and \(\overline{S_u}\) stands for the closed sun graph, both referenced in [4]. The notation \(T_{m,n}\) stands for the \((m,n)\) tadpole graph, which is taken from [12].
Theorem 1.2. [8] For the path \(P_n\), \(\gamma_{\mu}(P_n)\) is \(2^{n} – 1\).
[10] Let \(v \in V(G)\). Then \(v\) is called a key or source vertex if \(\text{dist}(v)\) is maximum.
Throughout this article, we denote:
\(\beta\) as the source vertex.
\(M_i\) as the monophonic path, and \(M_i^\sim\) contains the vertices that are not on \(M_i\).
\(MCPN\) as the monophonic cover pebbling number.
\(d_m\) as the monophonic distance.
\(N(v_0)\) as the neighborhood of \(v_0\).
For the gear graph \(G_n\), \(\gamma_{\mu}(G_n)\) is \(2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^{n} + 9\).
Proof. Let \(V(G_n) = \{u_0, u_1, u_2, \cdots, u_n, v_1, v_2, \cdots, v_n\}\) and \(E(G_n) = \{u_iv_{i}, v_ju_{j+1}, v_{n}u_1, u_0u_i\}\), where \(1 \leq i \leq n\) and \(1 \leq j \leq n-1\). Without loss of generality, let \(n\) be odd. Let \(p(v_1) = 2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^n + 8\). To cover the vertices \[v_2, u_3, v_3, \cdots, u_{\lceil \frac {n}{2} \rceil}, v_{\lceil \frac {n}{2} \rceil}, v_{{\lceil \frac {n}{2} \rceil}+1}, u_{{\lceil \frac {n}{2} \rceil}+2}, \cdots, v_n,\] it will cost \(2(2^{n+1} + 2^{n+2} + \cdots + 2^{2(n-1)})\) pebbles; to cover \(u_{{\lceil \frac {n}{2} \rceil}+1}\) it will cost \(2^n\) pebbles; to cover \(N(v_1)\) it will cost \(4\) pebbles; to cover \(u_0\) it will cost \(4\) pebbles, and there is no pebble left to cover \(v_1\). Thus, \[\gamma_{\mu}(G_n) \geq 2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^{n} + 9.\]
Now we prove \(\gamma_{\mu}(G_n) \leq 2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^{n} + 9\).
Case 1: Let \(\beta = v_1\).
From Table 1, to cover the vertices \(v_2, u_3, v_3, \cdots, u_{\lceil \frac {n}{2} \rceil}, v_{\lceil \frac {n}{2} \rceil}, v_{{\lceil \frac {n}{2} \rceil}+1}, u_{{\lceil \frac {n}{2} \rceil}+2}, \cdots, v_n\), we require \(2(2^{n+1} + 2^{n+2} + \cdots + 2^{2(n-1)})\) pebbles; to cover \(u_{{\lceil \frac {n}{2} \rceil}+1}\) we require \(2^n\) pebbles; to cover \(N(v_1)\) we need \(4\) pebbles; to cover \(u_0\) we need \(4\) pebbles, and to cover \(v_1\) we need \(1\) pebble. Thus, in this case, we use \[\gamma_{\mu}(G_n) = 2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^{n} + 9\] pebbles.
| \(u_1\) | \(v_1\) | \(u_2\) | \(v_2\) | \(u_3\) | \(v_3\) | \(\cdots\) | \(u_\lceil \frac{n}{2} \rceil\) | \(v_\lceil \frac{n}{2} \rceil\) | \(u_\lceil \frac{n}{2} \rceil + 1\) | \(v_\lceil \frac{n}{2} \rceil + 1\) | \(\cdots\) | \(u_n\) | \(v_n\) | \(u_0\) | |
| \(v_1\) | \(1\) | \(0\) | \(1\) | \(2n-2\) | \(2n-3\) | \(2n-4\) | \(\cdots\) | \(n+2\) | \(n+1\) | \(n\) | \(n+1\) | \(\cdots\) | \(2n-3\) | \(2n-2\) | \(2\) |
| \(u_1\) | \(0\) | \(1\) | \(2n-2\) | \(2n-3\) | \(2n-4\) | \(2n-5\) | \(\cdots\) | \(n+1\) | \(n\) | \(n+1\) | \(n+2\) | \(\cdots\) | \(2n-2\) | \(1\) | \(1\) |
| \(u_0\) | \(1\) | \(2\) | \(1\) | \(2\) | \(1\) | \(2\) | \(\cdots\) | \(1\) | \(2\) | \(1\) | \(2\) | \(\cdots\) | \(1\) | \(2\) | \(0\) |
Case 2: Let \(\beta = u_1\).
From Table 1, to cover the vertices \(v_2, u_3, v_3, \cdots, u_{\lceil \frac{n}{2} \rceil}, v_{\lceil \frac{n}{2} \rceil}, u_{{\lceil \frac{n}{2} \rceil}+1}, u_{{\lceil \frac{n}{2} \rceil}+2}, \cdots, v_n\), we need \(2(2^{n+1} + 2^{n+2} + \cdots + 2^{2(n-1)})\) pebbles; to cover \(v_{\lceil \frac{n}{2} \rceil}\) we require \(2^n\) pebbles; to cover \(N(v_1)\) we need \(6\) pebbles; to cover \(u_1\) we need \(1\) pebble. Thus, in this case, we use \[\gamma_{\mu}(G_n) = 2\left(\sum\limits_{k = n + 1}^{2(n-1)} 2^k\right) + 2^{n} + 7\] pebbles.
Case 3: Let \(\beta = u_0\).
From Table 1, to cover the vertices \(u_1, u_2, \cdots, u_n\), we need \(2n\) pebbles; to cover \(v_1, v_2, \cdots, v_n\), we need \(4n\) pebbles; to cover \(u_0\), we need \(1\) pebble. Thus, here we use \[\gamma_{\mu}(G_n) = 6n + 1\] pebbles. ◻
The \(MCPN\) of the sunflower planar graph \(Sf_n\) is: \[\gamma_{\mu}(Sf_n) = \begin{cases} 4\left(\sum\limits_{i = \frac{n}{2} + 2}^{n-1} 2^i \right) + 3(2^{\frac{n}{2} + 1}) + 2^{n+1} + 9, & \text{if } n \text{ is even},\\ 4\left(\sum\limits_{i = \lceil \frac{n}{2} \rceil + 1}^{n-1} 2^i \right) + 2^{\lceil \frac{n}{2} \rceil} + 2^{n+1} + 9, & \text{if } n \text{ is odd}. \end{cases}\]
Proof. Let \(V(Sf_n) = \{u_0, u_1, \cdots, u_n, v_1, v_2, \cdots, v_n \}\) and \[E(Sf_n) = \{u_0u_i, u_ju_{j+1}, u_1u_n, u_iv_i, u_{j+1}v_j, u_1v_n\},\] where \(i = 1, 2, \cdots, n\) and \(j = 1, 2, \cdots, n-1\). The center vertex \(u_0\) has degree \(n\), vertices \(u_1, u_2, \cdots, u_n\) have degree 5, and vertices \(v_1, v_2, \cdots, v_n\) have degree 2.
Case 1: When \(n\) is even.
| \(u_1\) | \(v_1\) | \(u_2\) | \(v_2\) | \(u_3\) | \(v_3\) | \(\cdots\) | \(u_\frac{n}{2}\) | \(v_\frac{n}{2}\) | \(u_\frac{n}{2} + 1\) | \(v_\frac{n}{2} + 1\) | \(u_\frac{n}{2} + 2\) | \(\cdots\) | \(v_n-1\) | \(u_n\) | \(v_n\) | \(u_0\) | |
| \(v_1\) | \(1\) | \(0\) | \(1\) | \(n\) | \(n-1\) | \(n-1\) | \(\cdots\) | \(\frac{n}{2} + 2\) | \(\frac{n}{2} + 2\) | \(\frac{n}{2} + 1\) | \(\frac{n}{2} + 1\) | \(\frac{n}{2} + 1\) | \(\cdots\) | \(n-1\) | \(n-1\) | \(n\) | \(2\) |
| \(u_1\) | \(0\) | \(1\) | \(1\) | \(n-1\) | \(n-2\) | \(n-2\) | \(\cdots\) | \(\frac{n}{2} + 1\) | \(\frac{n}{2} + 1\) | \(\frac{n}{2}\) | \(\frac{n}{2} + 1\) | \(\frac{n}{2} + 1\) | \(\cdots\) | \(n-1\) | \(1\) | \(1\) | \(1\) |
| \(u_0\) | \(1\) | \(2\) | \(1\) | \(2\) | \(1\) | \(2\) | \(\cdots\) | \(1\) | \(2\) | \(1\) | \(2\) | \(1\) | \(\cdots\) | \(2\) | \(1\) | \(2\) | \(0\) |
Subcase 1.1: \(\beta = u_1\).
From Table 2, to cover \(v_2, v_{n-1}\) it will cost \(2(2^{n-1})\) pebbles; to cover \[u_3, v_3, \cdots, u_{\frac{n}{2}}, v_{\frac{n}{2}}, v_{\frac{n}{2} + 1}, u_{\frac{n}{2}+2}, \cdots, v_{n-2}, u_{n-1},\] it will cost \(4\left(\sum\limits_{j = \frac{n}{2} + 1}^{n-2} 2^j \right)\) pebbles; to cover \(u_{\frac{n}{2}+1}\) it will cost \(2^{\frac{n}{2}}\) pebbles; to cover \(N(u_1)\) it will cost \(10\) pebbles; to cover \(u_1\) it will cost \(1\) pebble. Thus, in this case to cover all the vertices we used \[4\left(\sum\limits_{j = \frac{n}{2} + 1}^{n-2} 2^j \right) + 2^{n} + 2^{\frac{n}{2}} + 11.\]
Subcase 1.2: \(\beta = v_1\).
From Table 2, to cover \(v_2\) and \(v_n\) it requires \(2^{n+1}\) pebbles; to cover \[u_3, v_3, \cdots, u_{\frac{n}{2}}, v_{\frac{n}{2}}, v_{\frac{n}{2} + 2}, u_{\frac{n}{2} + 3}, \cdots, v_{n-1}, u_n,\] it requires \(4\left(\sum\limits_{i = \frac{n}{2} + 2}^{n-1} 2^i \right)\) pebbles; to cover \(u_{\frac{n}{2} + 1}, v_{\frac{n}{2} + 1}, u_{\frac{n}{2} + 2}\), it requires \(3(2^{\frac{n}{2} + 1})\) pebbles; to cover \(u_1\) and \(u_2\), it requires \(4\) pebbles; to cover \(u_0\), it requires \(4\) pebbles; to cover \(v_1\), it requires \(1\) pebble. Thus, in this case we used \[4\left(\sum\limits_{i = \frac{n}{2} + 2}^{n-1} 2^i \right) + 3(2^{\frac{n}{2} + 1}) + 2^{n+1} + 9.\]
Subcase 1.3: \(\beta = u_0\).
From Table 2, to cover \(N(u_0)\) it will cost \(2n\) pebbles; to cover \(v_1, v_2, \cdots, v_n\) it will cost \(4n\) pebbles; to cover \(u_0\) it will cost \(1\) pebble. Thus, in this case we used \[6n + 1.\]
Case 2: When \(n\) is odd.
| \(u_1\) | \(v_1\) | \(u_2\) | \(v_2\) | \(u_3\) | \(v_3\) | \(\cdots\) | \(u_\lceil \frac{n}{2} \rceil\) | \(v_\lceil \frac{n}{2} \rceil\) | \(u_\lceil \frac{n}{2} \rceil+1\) | \(\cdots\) | \(v_n-1\) | \(u_n\) | \(v_n\) | \(u_0\) | |
| \(v_1\) | \(1\) | \(0\) | \(1\) | \(n\) | \(n-1\) | \(n-1\) | \(\cdots\) | \(\lceil \frac{n}{2} \rceil\) | \(\lceil \frac{n}{2} \rceil\) | \(\lceil \frac{n}{2} \rceil\) | \(\cdots\) | \(n-1\) | \(n-1\) | \(n\) | \(1\) |
| \(u_1\) | \(0\) | \(1\) | \(1\) | \(n-1\) | \(n-2\) | \(n-2\) | \(\cdots\) | \(\lceil \frac{n}{2} \rceil\) | \(\lceil \frac{n}{2} \rceil\) | \(\lceil \frac{n}{2} \rceil+1\) | \(\cdots\) | \(n-1\) | \(1\) | \(1\) | \(1\) |
| \(u_0\) | \(1\) | \(2\) | \(1\) | \(2\) | \(1\) | \(2\) | \(\cdots\) | \(1\) | \(2\) | \(1\) | \(\cdots\) | \(2\) | \(1\) | \(2\) | \(0\) |
Subcase 2.1: \(\beta = u_1\).
From Table 3, to cover \(v_2,\ v_{n-1}\) it will cost \(2^{n}\) pebbles; to cover \[u_3,\ v_3,\ \cdots,\ v_{\lceil \frac{n}{2} \rceil-1},\ v_{\lceil \frac{n}{2} \rceil+1},\ \cdots,\ v_{n-2},\ u_{n-1}\] it will cost \[4 \bigg(\sum\limits_{j = \lceil \frac{n}{2} \rceil + 1}^{n-2} 2^j \bigg)\] pebbles; to cover \[u_{\lceil \frac{n}{2} \rceil},\ v_{\lceil \frac{n}{2} \rceil},\ u_{\lceil \frac{n}{2} \rceil +1}\] it will cost \(3(2^{\lceil \frac{n}{2} \rceil})\) pebbles; to cover \(N(u_1)\) it will cost \(10\) pebbles; to cover \(u_1\) it will cost \(1\) pebble. Thus, in this case we used \[4 \bigg(\sum\limits_{j = \lceil \frac{n}{2} \rceil + 1}^{n-2} 2^j \bigg) + 3(2^{\lceil \frac{n}{2} \rceil}) + 2^{n} + 11\] pebbles.
Subcase 2.2: Let \(\beta = v_1\).
From Table 3, to cover \(v_2,\ v_n\) it will cost \(2^{n+1}\) pebbles; to cover \[u_3,\ v_3,\ \cdots,\ u_{\lceil \frac{n}{2} \rceil},\ v_{\lceil \frac{n}{2} \rceil},\ v_{\lceil \frac{n}{2}+1},\ u_{\lceil \frac{n}{2} \rceil +2},\ \cdots,\ v_{n-1},\ u_n\] it will cost \[4 \bigg(\sum\limits_{i = \lceil \frac{n}{2} \rceil + 1}^{n-1} 2^i \bigg)\] pebbles; to cover \(u_{\frac{n}{2} +1}\) it will cost \(2^{\lceil \frac{n}{2} \rceil}\) pebbles; to cover \(u_1,\ u_2\) it will cost \(4\) pebbles; to cover \(u_0\) it will cost \(4\) pebbles; to cover \(v_1\) it will cost \(1\) pebble. Thus, in this case we used \[4 \bigg(\sum\limits_{i = \lceil \frac{n}{2} \rceil + 1}^{n-1} 2^i \bigg) + 2^{\lceil \frac{n}{2} \rceil} + 2^{n+1} + 9\] pebbles.
Subcase 2.3: Let \(\beta = u_0\).
From Table 3, to cover \(N(u_0)\) it will cost \(2n\) pebbles; to cover \(v_1,\ v_2,\ \cdots,\ v_n\) it will cost \(4n\) pebbles; to cover \(u_0\) it will cost \(1\) pebble. Thus, in this case we used \[6n + 1\] pebbles. ◻
For the Sun graph \(S_u\), \(\gamma_{\mu}(S_u) = 12u – 11.\)
Proof. Let \(V(S_u) = \{y_1, y_2, \ldots, y_u, x_1, x_2, \ldots, x_u\}\) and \(E(S_u) = \{y_iy_{i+1}, y_1y_u, y_ix_i, x_iy_{i+1}, y_ux_u, x_uy_1, y_iv_j\}\) where \(1 \leq i, j \leq u-1\) and \(i \neq j\). The degree of \(x_i\) is \(u+1\) and \(y_i\) is \(2\). Let \(p(x_1) = 5u – 12.\) To cover the vertices \(x_2, x_3, \ldots, x_u\), we require \(2^3(u-1)\) pebbles; to cover \(y_3, y_4, \ldots, y_u\), we require \(2^2(u-2)\) pebbles; to cover \(y_1, y_2\), we require \(4\) pebbles. Now there is no pebble to cover \(x_1\). Hence, \(\gamma_{\mu}(S_u) \geq 12u – 11.\)
Now we show \(\gamma_{\mu}(S_u) \leq 12u – 11.\)
| \(y_1\) | \(x_1\) | \(y_2\) | \(x_2\) | \(y_3\) | \(x_3\) | \(\cdots\) | \(y_u-1\) | \(x_u-1\) | \(y_u\) | \(x_u\) | |
| \(y_1\) | \(0\) | \(1\) | \(1\) | \(2\) | \(1\) | \(2\) | \(\cdots\) | \(1\) | \(2\) | \(1\) | \(1\) |
| \(x_1\) | \(1\) | \(0\) | \(1\) | \(3\) | \(2\) | \(3\) | \(\cdots\) | \(2\) | \(3\) | \(2\) | \(3\) |
Case 1: Let \(\beta = x_k\) where \(1 \leq k \leq u\).
Fix \(k = 1\). From Table 4, to cover the vertices \(x_2, x_3, \ldots, x_u\), which are at the monophonic distance \(3\), we require \(2^3(u-1)\) pebbles; to cover \(y_3, y_4, \ldots, y_u\), which are at the monophonic distance \(2\), we require \(2^2(u-2)\) pebbles; to cover \(N(x_1)\), we require \(4\) pebbles; and to cover \(x_1\), we require \(1\) pebble. Thus, in this case, we used \(12u – 11\) pebbles.
Case 2: Let \(\beta = y_k\) where \(1 \leq k \leq u\).
Fix \(k = 1\). From Table 4, to cover the vertices \(x_2, x_3, \ldots, x_{u-1}\), which are at the monophonic distance \(2\), we require \(2^2(u-2)\) pebbles; to cover \(y_2, y_3, \ldots, y_u, x_1, x_u\), which are adjacent to \(y_1\), we require \(2(u+1)\) pebbles; to cover \(y_1\), we require \(1\) pebble. Thus, in this case, we used \[4u – 4 + 2u + 2 + 1 = 6u – 1 \text{ pebbles.}\] ◻
For \(\overline{S_u}\), \(\gamma_{\mu}(\overline{S_u})\) is \[\gamma_{\mu}(\overline{S_u}) = \begin{cases} 2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 3, & \text{if } u \text{ is even,}\\ 2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 3, & \text{if } u \text{ is odd.} \end{cases}\]
Proof. Let \(V(\overline{S_u}) = \{y_1, \ldots, y_u, x_1, x_2, \ldots, x_u \}\) and \(E(\overline{S_u}) = \left\{y_iy_{i+1}, y_1y_u, x_ix_{i+1}, x_1x_u, y_ix_i, x_iy_{i+1},\right.\\\left. y_ux_u, x_uy_1, y_iy_j\right\}\), where \(1 \leq i, j \leq u-1\) and \(i \neq j\). The degree of \(y_i\) is \(u+1\), and the degree of \(x_i\) is \(4\).
Case 1: When \(u\) is even.
Let \(p(y_1) = 2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 2\). To cover the vertices \(x_1, y_2, y_3, \ldots, y_u, x_u\), it requires \(2u + 2\) pebbles; to cover the vertices \(x_2, x_3, \ldots, x_{u-1}\), it requires \(2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right)\) pebbles, and there is no pebble left to cover \(y_1\). Thus, \[\gamma_{\mu}(\overline{S_u}) \geq 2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 2.\]
Now we show \(\gamma_{\mu}(\overline{S_u}) \leq 2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 2\).
| \(y_1\) | \(x_1\) | \(y_2\) | \(x_2\) | \(y_3\) | \(x_3\) | \(\cdots\) | \(x_\frac{u}{2}\) | \(y_\frac{u}{2} + 1\) | \(x_\frac{u}{2} + 1\) | \(y_\frac{u}{2} + 2\) | \(x_\frac{u}{2} + 2\) | \(\cdots\) | \(y_u-2\) | \(x_u-2\) | \(y_u-1\) | \(x_u-1\) | \(y_u\) | \(x_u\) | |
| \(x_1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(2\) | \(u-1\) | \(\cdots\) | \(\frac{u}{2} + 2\) | \(2\) | \(\frac{u}{2} + 1\) | \(2\) | \(\frac{u}{2} + 2\) | \(\cdots\) | \(2\) | \(u-2\) | \(2\) | \(u-1\) | \(2\) | \(1\) |
| \(y_1\) | \(0\) | \(1\) | \(1\) | \(u-1\) | \(1\) | \(u-2\) | \(\cdots\) | \(\frac{u}{2} + 1\) | \(1\) | \(\frac{u}{2} + 1\) | \(1\) | \(\frac{u}{2} + 2\) | \(\cdots\) | \(1\) | \(u-2\) | \(1\) | \(u-1\) | \(1\) | \(1\) |
Subcase 1.1: Let \(\beta = y_1\).
From Table 5, to cover \(N(y_1)\), it costs \(2u+2\) pebbles; to cover \(x_2, x_3, \ldots, x_{u-1}\), which are at monophonic distances \(u-1, u-2, \ldots, \frac{u}{2} + 1\), it costs \(2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right)\) pebbles; to cover \(y_1\), it costs \(1\) pebble. Thus, in this subcase, we used \(2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 2\) pebbles.
Subcase 1.2: Let \(\beta = x_1\).
From Table 5, to cover \(N(x_1)\), it costs \(8\) pebbles; to cover \(y_3, y_4, \ldots, y_u\), it costs \(4u – 8\) pebbles; to cover \(x_3, x_4, \ldots, x_{u-1}\), which are at monophonic distances \(u-1, u-2, \ldots, \frac{u}{2} + 2\), it costs \(2\left(\sum\limits_{k = \frac{u}{2} + 2}^{u-1} 2^k \right) + 2^{\frac{u}{2} + 1}\) pebbles; to cover \(x_1\), it costs \(1\) pebble. Thus, in this subcase, we used \[2\left(\sum\limits_{k = \frac{u}{2} + 2}^{u-1} 2^k \right) + 2^{\frac{u}{2} + 1} + 4u + 1 < 2\left(\sum\limits_{k = \frac{u}{2} + 1}^{u-1} 2^k \right) + 2u + 2.\]
Case 2: When \(u\) is odd.
Let \[p(y_1) = 2 \left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 2.\] To cover the vertices \(x_1, y_2, y_3, \ldots, y_u, x_u\), it requires \(2u + 2\) pebbles; to cover the vertices \(x_2, x_3, \ldots, x_{u-1}\), it requires \[2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil}\] pebbles, and there is no pebble to cover \(y_1\). Thus, \[\gamma_{\mu}(\overline{S_u}) \geq 2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 2.\]
Now we prove \[\gamma_{\mu}(\overline{S_u}) \leq 2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 2.\]
| \(y_1\) | \(x_1\) | \(y_2\) | \(x_2\) | \(y_3\) | \(x_3\) | \(\cdots\) | \(x_\lceil \frac{u}{2} \rceil\) | \(y_\lceil \frac{u}{2} \rceil+1\) | \(x_\lceil \frac{u}{2} \rceil+1\) | \(y_\lceil \frac{u}{2} \rceil + 2\) | \(x_\lceil \frac{u}{2} \rceil+2\) | \(\cdots\) | \(y_u-2\) | \(x_u-2\) | \(y_u-1\) | \(x_u-1\) | \(y_u\) | \(x_u\) | |
| \(x_1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(2\) | \(u-1\) | \(\cdots\) | \(\lceil \frac{u}{2} \rceil+1\) | \(2\) | \(\lceil \frac{u}{2} \rceil +1\) | \(2\) | \(\lceil \frac{u}{2} \rceil + 2\) | \(\cdots\) | \(2\) | \(u-2\) | \(2\) | \(u-1\) | \(2\) | \(1\) |
| \(y_1\) | \(0\) | \(1\) | \(1\) | \(u-1\) | \(1\) | \(u-2\) | \(\cdots\) | \(\lceil \frac{u}{2} \rceil\) | \(1\) | \(\lceil \frac{u}{2} \rceil+1\) | \(1\) | \(\lceil \frac{u}{2} \rceil+2\) | \(\cdots\) | \(1\) | \(u-2\) | \(1\) | \(u-1\) | \(1\) | \(1\) |
Subcase 2.1: Let \(\beta = y_1\).
From Table 6, to cover \(N(y_1)\), it will cost \(2u+2\) pebbles; to cover \(x_2, x_3, \ldots, x_{u-1}\), which are at the monophonic distances \(u-1, u-2, \ldots, \lceil \frac{u}{2} \rceil + 1\), it will cost \[2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil}\] pebbles; to cover \(y_1\), it will cost \(1\) pebble. Thus, in this case, we used \[2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 2\] pebbles.
Subcase 2.2: Let \(\beta = x_1\).
From Table 6, to cover \(N(x_1)\), it will cost \(8\) pebbles; to cover \(y_3, y_4, \ldots, y_u\), it will cost \(4u – 8\) pebbles; to cover \(x_3, x_4, \ldots, x_{u-1}\), which are at the monophonic distances \(u-1, u-2, \ldots, \lceil \frac{u}{2} \rceil + 2\), it will cost \[2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right)\] pebbles; to cover \(x_1\), it will cost \(1\) pebble. Thus, in this case, we used \[2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 4u + 1 < 2\left(\sum\limits_{k = \lceil \frac{u}{2} \rceil + 1}^{u-1} 2^k \right) + 2^{\lceil \frac{u}{2} \rceil} + 2u + 2\] pebbles. ◻
For \(T_{m,n},\) \[\gamma_{\mu}(T_{m,n}) = \begin{cases} 2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right) + 2^{\frac{m}{2} + n } + 3(2^{n+1}) – 1, & \text{if } m \text{ is even}, \\ 2 \left(\sum\limits_{k = \lceil \frac{m}{2} \rceil + n}^{m+n-2} 2^k \right) + 3(2^{n+1}) – 1, & \text{if } m \text{ is odd}. \end{cases}\]
Proof. Let \(V(T_{m,n}) = \{v_1,\ v_2,\ \cdots,\ v_m,\ u_1,\ u_2, \cdots,\ u_n \}\) and \[E(T_{m,n}) = \{ u_iu_{i+1}, u_1v_1, v_kv_{k+1}, v_mv_1\}\] where \(i = 1, 2, \cdots, n-1\) and \(k = 1, 2, \cdots, m-1\). Consider a bridge between \(u_1\) and \(v_1\).
Case 1: When \(m\) is even.
Let \[p(u_n) = 2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right) + 2^{\frac{m}{2} + n } + 3(2^{n+1}) – 2.\] To cover the vertices \(v_2, v_1, u_1, u_2, \cdots, u_n\) we need \(2^{n+2}-1\) pebbles; to cover \(v_m\) we need \(2^{n+1}\) pebbles; to cover \(v_2, v_3, \cdots, v_{\frac{m}{2}}, v_{\frac{m}{2}+2}, \cdots, v_{m-1}\) we need \[2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right)\] pebbles; to cover \(v_{\frac{m}{2}+1}\) we need \(2^{\frac{m}{2} + n}\) pebbles but we have \(2^{\frac{m}{2} + n}-1\) pebbles. Thus, there must be a vertex without cover. Hence, \[\gamma_{\mu}(T_{m,n}) \geq 2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right) + 2^{\frac{m}{2} + n } + 3(2^{n+1}) – 1.\] Now we prove \[\gamma_{\mu}(T_{m,n}) \leq 2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right) + 2^{\frac{m}{2} + n } + 3(2^{n+1}) – 1.\]
Subcase 1.1: Let \(\beta = u_n\).
To cover the vertices \(v_2, v_1, u_1, u_2, \cdots, u_n\), it will cost \(2^{n+2}-1\) pebbles; to cover \(v_m\) it will cost \(2^{n+1}\) pebbles; to cover \(v_2, v_3, \cdots, v_{\frac{m}{2}}, v_{\frac{m}{2}+2}, \cdots, v_{m-1}\) it will cost \[2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right)\] pebbles; to cover \(v_{\frac{m}{2}+1}\) we need \(2^{\frac{m}{2} + n}\) pebbles. Thus, we used \[2\left(\sum\limits_{k = \frac{m}{2} + n + 1}^{m+n-2} 2^k \right) + 3(2^{n+1}) + 2^{\frac{m}{2} + n} – 1\] pebbles.
Subcase 1.2: Let \(\beta = v_1\).
To cover the vertices \(v_1, u_1, u_2, \cdots, u_n\), it will cost \(2^{n+1}-1\) pebbles; to cover the vertices \(v_2, v_m\) it will cost \(4\) pebbles; to cover the vertices \(v_2, v_3, \cdots, v_{\frac{m}{2}}, v_{\frac{m}{2}+2}, \cdots, v_{m-1}\) it will cost \[2\left(\sum\limits_{i = \frac{m}{2} + 1}^{m-2} 2^i \right)\] pebbles; to cover \(v_{\frac{m}{2}+1}\) it will cost \(2^{\frac{m}{2}}\) pebbles. Thus, we used \[2\left(\sum\limits_{i = \frac{m}{2} + 1}^{m-2} 2^i \right) + 2^{\frac{m}{2}} + 2^{n+1} + 3\] pebbles.
Case 2: When \(m\) is odd.
Let \[p(u_n) = 2 \left(\sum\limits_{k = \lceil \frac{m}{2} \rceil + n}^{m+n-2} 2^k \right) + 3(2^{n+1}) – 2.\] To cover the vertices \(v_2, v_1, u_1, u_2, \cdots, u_n\), we need \(2^{n+2}-1\) pebbles; to cover \(v_m\), we need \(2^{n+1}\) pebbles; to cover \(v_2, v_3, \cdots, v_{m-1}\), we need \[2 \left(\sum\limits_{k = \lceil \frac{m}{2} \rceil + n}^{m+n-2} 2^k \right).\] Thus, in this case: \[\gamma_{\mu}(T_{m,n}) \geq 2 \left(\sum\limits_{k = \lceil \frac{m}{2} \rceil + n}^{m+n-2} 2^k \right) + 3(2^{n+1}) – 1.\] The equality holds when \(\beta = u_n\) or \(v_1\). ◻
For \(L(m,n), \gamma_{\mu}(L(m,n)) = 2^{n+1} – 1 + (m-1)2^{n+1}.\)
Proof. Let \(V(L(m,n)) = \{v_1, v_2, \cdots, v_m, u_1, u_2, \cdots, u_n \}\) where \(m\) vertices form a complete graph and \(n\) vertices form a path of order \(n\). Without loss of generality, consider a bridge between \(u_1\) and \(v_1\). Let \[p(u_n) = 2^{n+1} – 2 + (m-1)2^{n+1}.\] To cover the vertices \(v_2, v_3, \cdots, v_m\), it will cost \((m-1)2^{n+1}\) pebbles; to cover the vertices \(u_{n-1}, u_{n-2}, \cdots, u_1, v_1\), it will cost \(2^{n+1} – 2\) pebbles, and there is no pebble left to cover \(u_n\). Thus, \[\gamma_{\mu}(L(m,n)) \geq 2^{n+1} – 1 + (m-1)2^{n+1}.\]
Now we prove \[\gamma_{\mu}(L(m,n)) \leq 2^{n+1} – 1 + (m-1)2^{n+1}.\]
Case 1: Let \(\beta = u_n\).
Let the monophonic path \(M_1 : u_n, u_{n-1}, \cdots, u_1, v_1\) of length \(n\). By Theorem 1.2, to cover \(p(V(M_1))\), we require \(2^{n+1} – 1\) pebbles; to cover the vertices \(v_2, v_3, \cdots, v_m\), which are at a monophonic distance of \(n+1\), we need \((m-1)2^{n+1}\) pebbles. Thus, to cover all the vertices, it will cost \[\gamma_{\mu}(L(m,n)) = 2^{n+1} – 1 + (m-1)2^{n+1}\] pebbles.
Case 2: Let \(\beta = v_2\).
Consider the monophonic path \(M_2 : v_2, v_1, u_1, u_2, \cdots, u_n\) of length \(n+1\). By Theorem 1.2, to cover \(p(V(M_2))\), we require \(2^{n+2} – 1\) pebbles; to cover the vertices \(v_3, v_4, \cdots, v_m\), which are adjacent to \(v_2\), it will cost \(2(m-2)\) pebbles. Thus, to cover all the vertices from \(v_2\), it will cost \[2^{n+2} – 1 + 2(m-2)\] pebbles. By symmetry, the same can be proven for the vertices \(v_3, v_4, \cdots, v_m\).
We observe that if the source vertices are \(u_{n-1}, u_{n-2}, \cdots, u_1, v_1\), then the monophonic cover pebbling number of these vertices will lie between Case 1 and Case 2. ◻
For the double star-path graph \(P_n(l,m)\), \(\gamma_{\mu}(P_n(l,m)) = 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1), \text{ where } l \geq m.\)
Proof. Let \(V(P_n(l,m)) = \{x_0, x_1, \cdots, x_l, y_0, y_1, \cdots, y_m, v_1, v_2, \cdots, v_n \}\) and \[E(P_n(l,m)) = \{x_0x_i, x_0v_1, v_sv_{s+1}, v_ny_0, y_0y_j \},\] where \(i = 1, 2, \cdots, l\), \(s = 1, 2, \cdots, n-1\), and \(j = 1, 2, \cdots, m\). Let \[p(y_1) = 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1) – 1.\] To cover the vertices \(y_1, y_0, v_1, v_2, \cdots, v_n, x_0, x_1\), it will cost \(2^{n+2}-1\) pebbles; to cover \(x_2, x_3, \cdots, x_l\), it will cost \((l-1)2^{n+1}\) pebbles; to cover \(y_2, y_3, \cdots, y_m\), it will cost \(4(m-1)\) pebbles, but we have \(4(m-1)-1\) pebbles. Thus, there will be a vertex without cover. Hence, \[\gamma_{\mu}(P_n(l,m)) \geq 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1), \text{ where } l \geq m.\]
Now we prove \[\gamma_{\mu}(P_n(l,m)) \leq 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1), \text{ where } l \geq m.\]
Case 1: Let \(\beta = y_1\).
Let us consider the monophonic path \(M_1 : y_1, y_0, v_1, v_2, \cdots, v_n, x_0, x_1\) of length \(n+1\). By Theorem 1.2, to cover \(p(V(M_1))\), we require \(2^{n+2} – 1\) pebbles; to cover \(x_2, x_3, \cdots, x_l\), we require \((l-1)2^{n+1}\) pebbles; to cover \(y_2, y_3, \cdots, y_m\), which are at monophonic distance \(2\), we need \((m-1)4\) pebbles. Thus, in this case, we used \[2^{n+2} – 1 + (l-1)2^{n+1} + (m-1)4 = 2^{n+2} + (l-1)2^{n+1} + 4m – 5\] pebbles. By symmetry, the same can be proven for the vertices \(y_2, y_3, \cdots, y_m\).
Case 2: Let \(\beta = x_1\).
Let us consider the monophonic path \(M_2 : x_1, x_0, v_n, v_{n-1}, \cdots, v_1, y_0, y_1\) of length \(n+1\). By Theorem 1.2, to cover \(p(V(M_2))\), we require \(2^{n+2} – 1\) pebbles; to cover \(y_2, y_3, \cdots, y_m\), we require \((m-1)2^{n+1}\) pebbles; to cover \(x_2, x_3, \cdots, x_l\), which are at monophonic distance \(2\), we need \((l-1)4\) pebbles. Thus, in this case, we used \[2^{n+2} – 1 + (m-1)2^{n+1} + (l-1)4 < 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1)\] pebbles. Since \(l \geq m\).
Case 3: Let \(\beta = v_s\), where \(1 \leq s \leq n\).
There exist two monophonic paths. Let \(M_3 : v_k, v_{k+1}, \cdots, v_n, y_0, y_1\) of length \(n – k + 2\) and \(M_4 : v_k, v_{k-1}, \cdots, v_1, x_0, x_1\) of length \(k + 1\). By Theorem 1.2, to cover \(p(V(M_3))\), we need \(2^{n-k+3}-1\) pebbles, and to cover \(p(V(M_4))\), we need \(2^{k+2}-1\) pebbles. Now to cover \(y_2, y_3, \cdots, y_m\), we need \((m-1)2^{n-k+2}\) pebbles; to cover \(x_2, x_3, \cdots, x_l\), we need \((l-1)2^{k+1}\) pebbles. Thus, to cover all the vertices, we require \[2^{k+2} – 1 + 2^{n-k+3} – 1 + (m-1)2^{n-k+2} + (l-1)2^{k+1} < 2^{n+2} + 2^{n+1}(l-1) + 2^2(m-1)\] pebbles. Similarly, we can prove for \(x_0\) and \(y_0\). ◻
For the class of fuses \(F_l(k)\), \(\gamma_{\mu}(F_l(k)) = 2^{l+2} – 1 + (k-1)2^{l+1}.\)
Proof. Let \(V(F_l(k)) = \{ v_0, v_1, \cdots, v_l, v_{l+1}, \cdots, v_{n-1} \}\) and \[E(F_l(k)) = \{v_iv_{i+1}, v_lv_s \},\] where \(i = 0, 1, \cdots, l-1\), \(s = l+1, l+2, \cdots, n-1\), and \(n = l + k + 1\). Consider the monophonic path \(M_1 : v_0, v_1, v_2, \cdots, v_l, v_{l+1}\) of length \(l+1\). Let \[p(v_0) = 2^{l+2} – 2 + (k-1)2^{l+1}.\] To cover the vertices \(v_{l+2}, v_{l+3}, \cdots, v_{n-1}\), we require \((k-1)2^{l+1}\) pebbles. By Theorem 1.2, to cover the vertices of \(M_1\), we require \(2^{l+2} – 1\) pebbles, but we have only \(2^{l+2} – 2\) pebbles. Thus, there will be a vertex without cover. Hence, \[\gamma_{\mu}(F_l(k)) \geq 2^{l+2} – 1 + (k-1)2^{l+1}.\]
Now we prove \[\gamma_{\mu}(F_l(k)) \leq 2^{l+2} – 1 + (k-1)2^{l+1}.\]
Case 1: Let \(\beta = v_0\).
Consider the path \(M_1\). By Theorem 1.2, to cover \(p(V(M_1))\), we require \(2^{l+2} – 1\) pebbles. To cover the \(k\) vertices \(v_{l+2}, v_{l+3}, \cdots, v_{n-1}\), which are at the monophonic distance \(l+1\), we require \((k-1)2^{l+1}\) pebbles. Thus, with a configuration of \(2^{l+2} – 1 + (k-1)2^{l+1}\) pebbles, we can cover all the vertices. Similarly, we can prove for the vertices \(v_{l+1}, v_{l+2}, \cdots, v_{n-1}\).
Case 2: Let \(\beta = v_j\), where \(j = 1, 2, \cdots, l\).
There exist two different monophonic paths: \[M_2 : v_j, v_{j+1}, \cdots, v_l, v_{l+1},\] of length \(l-j+1\) and \[M_3 : v_j, v_{j-1}, \cdots, v_0,\] of length \(j\). By Theorem 1.2, to cover \(V(M_2)\), we require \(2^{l-j+2}-1\) pebbles; to cover \(V(M_3)\), we require \(2^{j+1}-2\) pebbles; and to cover the vertices \(v_{l+2}, v_{l+3}, \cdots, v_{n-1}\), we require \((k-1)2^{l-j+1}\) pebbles. Thus, to cover all the vertices, we require \[2^{l-j+2} – 1 + 2^{j+1} – 2 + (k-1)2^{l-j+1} = 3(2^{l-j+1}) + (k-1)2^{l-j+1} < 2^{l+2} – 1 + (k-1)2^{l+1}.\] ◻
1970-2025 CP (Manitoba, Canada) unless otherwise stated.