Given a connected graph \(G\) and a configuration \(D\) of pebbles on \(V(G)\), a pebble move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A monophonic path is a longest chordless path between two non-adjacent vertices \(u\) and \(v\). The line segment that connects two vertices on a curve is known as a chord. The monophonic distance between \(u\) and \(v\) is the number of vertices in the longest \(u\)–\(v\) monophonic path, denoted by \(d_{\mu}(u,v)\) in \(G\). The monophonic pebbling number (MPN) of \(G\) is the least number of pebbles needed to guarantee that, from any distribution of pebbles on a graph \(G\), one pebble can be moved to any specified vertex using monophonic paths through pebbling moves. The monophonic \(t\)-pebbling number (MtPN) of \(G\) is the least number of pebbles needed to guarantee that, from any distribution of pebbles, \(t\) pebbles can be moved to any specified vertex using monophonic paths. In this article, we determine the \(MPN\) and \(MtPN\) of Dutch windmill graphs, square of cycles, tadpole graphs, lollipop graphs, double star path graphs, and fuse graphs, and we also discuss their \(t\)-pebbling versions.
Pebbling, a recent development in graph theory introduced by Lagarias and Saks, has attracted considerable interest. Chung [2] was the first to introduce it into the literature, and many others have followed, including Hulbert, who published an overview of graph pebbling [3]. Graph pebbling is a concept that can be used to solve a variety of practical problems. “Graph pebbling” is a network optimization model used to move resources or materials that are absorbed during the journey. For example, when moving energy, heat, electricity, water, or information between locations, some loss may occur. Hence, the graph pebbling problem provides a way to measure the cost of pebble loss during conveyance. Because of its many applications, graph pebbling is currently one of the fastest-growing fields of research in graph theory.
Assume that \(G\) is a simple connected graph with vertex set \(V(G)\) and edge set \(E(G)\). Consider a connected graph with a fixed number of pebbles distributed on its vertices. Santhakumaran, A. P. et al. introduced the monophonic distance in graphs in [10]. Lourdusamy et al. introduced detour pebbling in [7]. By making use of these ideas, the monophonic pebbling number is defined. The monophonic distance between non-adjacent vertices \(u\) and \(v\) is the length of the longest chordless \(u\)–\(v\) monophonic path, denoted by \(d_{\mu}(u,v)\) in \(G\). For any two non-adjacent vertices \(u\) and \(v\) in a connected graph \(G\), a longest \(u\)–\(v\) path is a monophonic path if it contains no chords [10]. The monophonic pebbling number and monophonic \(t\)-pebbling number of several typical graphs are determined in this study.
This paper is organized as follows. In Section 2, we give some preliminaries that are needed for the subsequent sections. In Section 3, we determine the \(MPN\) of Dutch windmill graphs. In Section 4, we determine the \(MPN\) of the square of cycles, tadpole graphs, lollipop graphs, double star path graphs, and fuse graphs. In Section 5, we determine the \(MtPN\) of Dutch windmill graphs, square of cycles, tadpole graphs, lollipop graphs, double star path graphs, and fuse graphs.
Definition 2.1. [5] A chord in a path is an edge joining two non-adjacent vertices. A monophonic path between \(u\) and \(v\) is a \(u\)–\(v\) path without a chord between \(u\) and \(v\). The monophonic pebbling number of \(v\) in \(G\), denoted by \({\mu}(G,v)\), is the least positive integer such that we can move a pebble to \(v\) through a monophonic path by a sequence of pebbling moves for all distributions of \({\mu}(G,v)\). The monophonic pebbling number of \(G\) is \[{\mu}(G)=\max_{v\in V}{\mu}(G,v).\] Instead of moving one pebble to a target, if we move \(t\) pebbles, it is called the \(MtPN\) of \(G\) and is denoted by \({\mu}_t(G)\). Thus, the \(MtPN\) of \(G\) is \[{\mu}_t(G)=\max_{v\in V}{\mu}_t(G,v).\]
Note 2.2. A distribution \(f\) on a graph \(G\) is a function \[f:V(G)\longrightarrow \mathbb{N}\cup\{0\}.\] Suppose that \(m\) pebbles are distributed on the vertices of a connected graph \(G\). A pebbling move, or shift, consists of removing two pebbles from one vertex and then placing one pebble on an adjacent vertex.
Definition 2.3. [1] A graph \(D_n^m\), with \(m\geq 1\) and \(n\geq 3\), is known as a Dutch windmill graph. The graph \(D_n^m\) can be obtained by taking \(m\) copies of cycles \(C_n\) with one common vertex.
Definition 2.4. [12] The \((m,n)\) tadpole graph is the graph obtained by joining a cycle graph \(C_m\) to a path graph \(P_n\) with a bridge. It is denoted by \(T_{(m,n)}\).
Definition 2.5. [11] The \((m,n)\)-lollipop graph is the graph obtained by joining a complete graph \(K_m\) to a path graph \(P_n\) with a bridge. It is denoted by \(L(m,n)\).
Definition 2.6. [8] A graph is called a double star path if the end vertices of a path \(P_n\) are joined to the center vertices of the star graphs \(K_{1,l}\), where \(l\geq2\), and \(K_{1,m}\), where \(m\geq2\), respectively. We denote it by \(P_n(l,m)\).
Definition 2.7. [4] The class of fuses is defined as follows: the vertices of a fuse \(F_l(k)\), where \(l\geq1\) and \(k\geq2\), are \(v_0,v_1,v_2,\cdots,v_{n-1}\) with \(n=l+k+1\), such that the first \(l+1\) vertices form a path \(v_0,v_1,v_2,\cdots,v_l\), and the remaining vertices \(v_{l+1},v_{l+2},\cdots,v_{n-1}\) are independent and adjacent only to \(v_l\).
Definition 2.8. Let \(G\) be a connected graph. For \(u,v\in V(G)\), we denote by \(d_G(u,v)\) the distance between \(u\) and \(v\) in \(G\). The \(p^{th}\) power of \(G\), denoted by \(G^p\), is the graph obtained from \(G\) by adding an edge \(uv\) to \(G\) whenever \(2\leq d_G(u,v)\leq p\). That is, \[E(G^p)=\{uv:1\leq d_G(u,v)\leq p\}.\] In particular, the square of a path is denoted by \(P_n^2\), and the square of a cycle is denoted by \(C_n^2\).
Note 2.9. [9] The notation \(D_n^m\), with \(m\geq1\) and \(n\geq3\), denotes a Dutch windmill graph and is taken from [1]. The notation \(L(m,n)\) denotes a lollipop graph and is taken from [11]. The notation \(T_{m,n}\) denotes the \((m,n)\) tadpole graph and is taken from [12]. The notation \(P_n(l,m)\) denotes a double star path graph and is taken from [8]. The notation \(F_l(k)\), where \(l\geq1\) and \(k\geq2\), denotes the class of fuses and is taken from [4].
Result 2.10. Let \(G\) be a connected graph. The monophonic distance between \(u\) and \(v\) is \(0\) if and only if \(u=v\), and it is \(1\) when \(uv\) is an edge of \(G\).
Theorem 2.11. [5] For the path graph of order \(n\), the monophonic pebbling number is \(2^{n-1}\).
Theorem 2.12. [6] For the cycle graph \(C_n\), the monophonic pebbling number is \(2^{n-2}+1\).
Theorem 2.13. [6] For the complete graph \(K_n\), the monophonic pebbling number is \(n\).
Notation 2.14. Throughout this article, we use the following notation:
\(M_i\) denotes a monophonic path, and \(M_i^\sim\) contains the vertices that are not on \(M_i\).
We use \(MPN\) for the monophonic pebbling number and \(MtPN\) for the monophonic \(t\)-pebbling number.
\(d_\mu\) denotes the monophonic distance.
\(v_k \xleftarrow{t}\) means retaining \(t\) pebbles on \(v_k\), and \(v_k \xrightarrow{t}\) means transferring \(t\) pebbles to \(N(v_k)\).
\(N(v_0)\) denotes the neighborhood of \(v_0\).
Pebble transformation means removing two pebbles from a vertex and placing one pebble on an adjacent vertex.
In this section, we determine the monophonic pebbling number of Dutch windmill graphs.
Theorem 3.1. For the Dutch windmill graph \(D_3^1\), the monophonic pebbling number is \(3\).
Proof. Let \[V(D_3^1)=\{v_0,\ v_1^1,\ v_2^1\}.\] The graph \(D_3^1\cong K_3\), and by Theorem 2.13, the result follows. ◻
Theorem 3.2. For the Dutch windmill graph \(D_n^1\), the monophonic pebbling number is \[2^{n-2}+1,\qquad n\geq3.\]
Proof. Let \[V(D_n^1)=\{v_0,\ v_1^1,\ v_2^1,\ v_3^1,\cdots,v_{n-1}^1\}.\] The graph \(D_n^1\cong C_n\), and by Theorem 2.12, the result follows. ◻
Theorem 3.3. For the Dutch windmill graph \(D_4^2\), the monophonic pebbling number is \(16\).
Proof. Let \[V(D_4^2)=\{v_0,\ v_1^1,\ v_2^1,\ v_3^1,\ v_1^2,\ v_2^2,\ v_3^2\}\] and \[E(D_4^2)=\{v_0v_k^j,\ v_s^jv_{s+1}^j\},\] where \(s,j=1,2\) and \(k=1,3\). The distance \(d_\mu(v_2^1,v)\leq4\), where \(v\in V(D_4^2)\). By placing \(15\) pebbles on \(v_2^2\), we cannot reach \(v_2^1\). Hence, \[{\mu}(D_4^2)\geq16.\] Now we prove that \({\mu}(D_4^2)\leq16\).
Case 1. Let the target be \(v_2^2\).
Consider \[M_1:\ v_1^2,\ v_1^1,\ v_0,\ v_3^2,\ v_2^2.\] Note that \(d_{\mu}(M_1)\) is \(4\). By Theorem 2.11, using at most \(16\) pebbles, we can pebble \(v_2^2\). Suppose \(p(V(M_1))\leq16\). If \(p(v_1^2)\geq2\) or \(p(v_3^1)\geq2\), then we can bring \(\left\lfloor\frac{p(v_1^2)}{2}\right\rfloor\) pebbles to \(v_2^2\) or \(\left\lfloor\frac{p(v_3^1)}{2}\right\rfloor\) pebbles to \(v_0\), which is sufficient to pebble \(v_2^2\). If \(p(v_0)\geq4\), then we can pebble \(v_2^2\). If \(p(v_1^2)=1\) or \(p(v_3^2)=1\) and \(p(v_0)\geq2\), then we can pebble \(v_2^2\). If \(p(v_0)\leq4\) and \(p(v_1^2)=p(v_3^2)=0\), then at most \(16\) pebbles will be distributed on \(v_1^1,\ v_2^1,\ v_3^1\). Now \(d_\mu(v_0,v)\leq2\), where \(v\in\{v_1^1,\ v_2^1,\ v_3^1\}\), from which we can pebble \(v_2^2\). Therefore, in every possible configuration, we can bring at least \(4\) pebbles to \(v_0\), and \(v_2^2\) is pebbled. By symmetry, the same argument applies to \(v_2^1\).
Case 2. Let the target be \(v_0\).
There are \(4\) vertices adjacent to \(v_0\) and \(2\) vertices at monophonic distance \(2\). Thus, \(d_\mu(v_0,v)\leq2\) where \(v\in V(D_4^2)-\{v_0\}\). Hence, if there are \(4\) pebbles on the vertices at distance \(2\) or \(2\) pebbles on the adjacent vertices, we can pebble \(v_0\). Otherwise, if \(N(v_0)\) has one pebble and an adjacent vertex of \(N(v_0)\) that is at monophonic distance \(2\) has at least \(2\) pebbles, then we can pebble \(v_0\). Thus, in this case, using at most \(7\) pebbles, we can pebble \(v_0\).
Case 3. Let the target be \(N(v_0)\).
Fix the target as \(v_3^1\). The monophonic distance satisfies \(d_\mu(v_3^1,v)\leq3\), where \(v\in V(D_4^2)-\{v_3^1\}\). There is one vertex at monophonic distance \(3\), three vertices at monophonic distance \(2\), and two vertices adjacent to \(v_3^1\). If \(v_2^2\) has at least \(8\) pebbles, or any vertex at distance \(2\) receives at least \(4\) pebbles, or any adjacent vertex receives at least \(2\) pebbles, then we can pebble \(v_3^1\). Thus, in this case, using at most \(10\) pebbles, we can pebble \(v_3^1\). In the same way, we can prove the result for \(v_1^1,\ v_1^2,\) and \(v_3^2\). ◻
Theorem 3.4. For \(D_n^m\), \[{\mu}(D_n^m)=2^{2n-4}+(m-2)(2^{n-2}-1)+m,\] where \(m\geq2\) and \(n\geq5\).
Proof. Let \[V(D_n^m)=\{v_0,\ v_i^j: i=1,2,\cdots,n-1,\ j=1,2,\cdots,m\}\] and \[E(D_n^m)=\{v_0v_m^j,\ v_0v_1^j,\ v_k^jv_{k+1}^j: k=1,2,\cdots,n-2,\ j=1,2,\cdots,m\}.\] There are many monophonic paths with the same length. Without loss of generality, consider \[M_1:\ v_{n-2}^1,\ v_{n-3}^1,\cdots,\ v_1^1,\ v_0,\ v_1^2,\ v_2^2,\ v_3^2,\cdots,\ v_{n-3}^2,\ v_{n-2}^2,\] whose length is \(2n-4\). Suppose we have \[2^{2n-4}-1+(m-2)(2^{n-2}-1)+m\] pebbles. By placing \(2^{n-2}-1\) pebbles on each \(v_2^l\), where \(l=3,4,\cdots,m\), one pebble on each \(v_1^j\), where \(j=1,2,\cdots,m\), and \(2^{2n-4}-1\) pebbles on \(v_{n-2}^1\), we cannot pebble the vertex \(v_{n-2}^2\). Therefore, \[{\mu}(D_n^m)\geq2^{2n-4}+(m-2)(2^{n-2}-1)+m.\] Now let us prove the sufficient part.
Case 1. Let the target be \(v_2^1\).
Without loss of generality, take \[M_2:\ v_2^2,\ v_3^2,\cdots,\ v_{n-1}^2,\ v_0,\ v_{n-1}^1,\ v_{n-2}^1,\cdots,\ v_3^1,\ v_2^1\] with length \(2n-4\). The vertex set consisting of vertices that are not on the monophonic path \(M_2\) is \(V(D_n^m)-V(M_2)\) and is denoted by \(M_2^{\sim}\). By Theorem 2.11, using \(2^{2n-4}\) pebbles, we can pebble \(v_2^1\). Suppose \(p(V(M_2))<2^{2n-4}\). If \(v_1^1\) has at least \(2\) pebbles, then we can bring \(\left\lfloor\frac{p(v_1^1)}{2}\right\rfloor\) pebbles to \(v_0\), with which we can pebble \(v_2^1\). Now consider the pebbling moves \[\sum\limits_{r=2,3,\cdots,m} v_1^r \xrightarrow{u_r} v_0, \tag{1}\] and \[\sum\limits_{z=2,3,\cdots,m} v_2^z \longrightarrow v_3^z \longrightarrow \cdots \longrightarrow v_{n-1}^z \xrightarrow{y_z} v_0. \tag{2}\] If \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+p(v_0)\geq2^{n-2},\] then we are done. Suppose \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+p(v_0)<2^{n-2}.\] Then the remaining pebbles will be on \[V(M_2)-\{v_{n-1}^1,\ v_{n-2}^1,\cdots,\ v_3^1\},\] and so we can reach \(v_2^1\). By using the same argument, we can prove the result for \(v_2^j\) and \(v_{n-2}^j\), where \(j=1,2,\cdots,m\).
Case 2. Let the target be \(N(v_0)\).
Fix the target as \(v_1^1\). Without loss of generality, consider \[M_3:\ v_{n-2}^2,\ v_{n-3}^2,\cdots,\ v_2^2,\ v_1^2,\ v_0,\ v_1^1,\] whose length is \(n-1\). By Theorem 2.11, if \(p(V(M_3))\geq2^{n-1}\), then we can pebble \(v_1^1\). If \(p(v_0)\geq2\) or \(p(v_2^1)\geq2\), then we can pebble \(v_1^1\). Otherwise, consider \[M_4:\ v_{n-1}^1,\ v_{n-2}^1,\cdots,\ v_2^1,\ v_1^1,\] which has monophonic length \(n-2\). By Theorem 2.11, if \(p(V(M_4))\geq2^{n-2}\), then we can pebble \(v_1^1\). Suppose \[p(V(M_3))<2^{n-1},\quad p(V(M_4))<2^{n-2},\quad p(v_0)<2,\quad p(v_2^1)<2.\] Consider \[\sum\limits_{r=2,3,\cdots,m} v_1^r \xrightarrow{u_r} v_0, \tag{3}\] and \[\sum\limits_{z=2,3,\cdots,m} v_2^z \longrightarrow v_3^z \longrightarrow \cdots \longrightarrow v_{n-1}^z \xrightarrow{y_z} v_0. \tag{4}\] If \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+p(v_0)\geq2,\] then we can pebble \(v_1^1\). Suppose \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+p(v_0)<2\] and \(p(V(M_4))<2^{n-2}\). This contradicts the total number of pebbles in the initial configuration. By the same argument, we can prove the result for \(v_1^j\) and \(v_{n-1}^j\), where \(j=1,2,\cdots,m\).
Case 3. Let the target be \(v_l^j\), where \(3\leq l\leq n-3\) and \(j=1,2,\cdots,m\).
Fix \(j=1\). The distance satisfies \[d_\mu(v_l^1,v)\leq n+l-2\] or \[d_\mu(v_l^1,v)\leq2n-(l+2),\] where \(v\in V(D_n^m)-\{v_l^j\}\). If \(\lfloor n/2\rfloor\geq l\), then the monophonic path \(M_5\) is \[M_5=\{v_l^1,\ v_{l+1}^1,\cdots,\ v_{n-2}^1,\ v_{n-1}^1,\ v_0,\ v_1^2,\cdots,\ v_{n-2}^2\}\] with length \(2n-(l+2)\). If \(\lfloor n/2\rfloor<l\), then the monophonic path \(M_6\) is \[M_6=\{v_l^1,\ v_{l-1}^1,\cdots,\ v_2^1,\ v_1^1,\ v_0,\ v_1^2,\cdots,\ v_{n-2}^2\}\] with length \(n+l-2\). Without loss of generality, consider \(M_5\). Suppose \(p(V(M_5))\geq2^{2n-(l+2)}\). Then, by Theorem 2.11, we can pebble \(v_l^j\). Also, if \(p(v_{l+1}^1)\geq2\) or \(p(v_{l-1}^1)\geq2\), then we can reach \(v_l^j\). Suppose \(p(V(M_5))<2^{2n-(l+2)}\), \(p(v_{l-1}^1)<2\), and \(p(v_{l+1}^1)\leq1\). Then \[\sum\limits_{r=2,3,\cdots,m} v_1^r \xrightarrow{u_r} v_0, \tag{5}\] \[\sum\limits_{z=2,3,\cdots,m} v_2^z \longrightarrow v_3^z \longrightarrow \cdots \longrightarrow v_{n-1}^z \xrightarrow{y_z} v_0, \tag{6}\] and \[v_{l-2}^z \longrightarrow v_{l-3}^z \longrightarrow \cdots \longrightarrow v_1^z \xrightarrow{x} v_0. \tag{7}\] If \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+x+p(v_0)\geq2^{n-l},\] then we can pebble \(v_l^j\). Suppose \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+x+p(v_0)<2^{n-1}.\] Then \[\sum\limits_{r=2,3,\cdots,m}u_r+\sum\limits_{z=2,3,\cdots,m}y_z+x+p(v_0) +p(v_{n-1}^1)+p(v_{n-2}^1)+\cdots+p(v_{l+1}^1)\geq2^{n-1},\] and so we can pebble \(v_l^j\). The same method applies when \(\lfloor n/2\rfloor<l\).
Case 4. Let the target be \(v_0\).
Note that \(v_0\) is a cut vertex. Let \(M_j\) be a monophonic path with length \(n-2\). That is, \(M_j\) is either \[v_2^j,\ v_3^j,\cdots,\ v_{n-1}^j,\ v_0\] or \[v_{n-2}^j,\ v_{n-3}^j,\cdots,\ v_1^j,\ v_0,\] where \(j=1,2,\cdots,m\). By Theorem 2.11, if \(p(V(M_j))\geq2^{n-2}\), then we can pebble \(v_0\). ◻
In this section, we determine the monophonic pebbling number \((MPN)\) of the square of a cycle, tadpole graph, lollipop graph, double star path graph, and fuse graph.
Theorem 4.1. The monophonic pebbling number of the square of a cycle \(C_n^2\) is \[\begin{cases} 2^{n-\left(\frac{n}{3}+2\right)}+2, & \text{if } n\equiv0\pmod{3},\\[4pt] 2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+\left\lceil\frac{n}{3}\right\rceil, & \text{if } n\equiv1\pmod{3},\\[4pt] 2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3, & \text{if } n\equiv2\pmod{3}. \end{cases}\]
Proof. Let \[V(C_n^2)=\{v_1,\ v_2,\dots,\ v_n\}\] and \[E(C_n^2)=\{v_iv_{i+1},\ v_jv_{j+2},\ v_1v_n,\ v_1v_{n-1},\ v_2v_n\},\] where \(i=1,2,\dots,n-1\) and \(j=1,2,\dots,n-2\).
Case 1. \(n\equiv0\pmod{3}\).
Consider \[M_1:\ v_{n-2},\ v_{n-4},\ v_{n-5},\ v_{n-7},\cdots,\ v_5,\ v_4,\ v_2,\ v_1.\] The vertices not on \(M_1\) are \[v_n,\ v_{n-1},\ v_{n-3},\ v_{n-6},\cdots,\ v_6,\ v_3.\] The length of \(M_1\) is \(n-\left(\frac{n}{3}+2\right)\), and \(\frac{n}{3}+1\) vertices are not on \(M_1\). Let \[p(V(C_n^2))=2^{n-\left(\frac{n}{3}+2\right)}+1.\] By placing \(2^{n-\left(\frac{n}{3}+2\right)}-1\) pebbles on \(v_{n-2}\) and one pebble each on \(v_n\) and \(v_{n-1}\), we cannot pebble \(v_1\). Hence, \[\mu(C_n^2)\geq2^{n-\left(\frac{n}{3}+2\right)}+2.\] Now we prove that \[\mu(C_n^2)\leq2^{n-\left(\frac{n}{3}+2\right)}+2.\] Consider any distribution of \(2^{n-\left(\frac{n}{3}+2\right)}+2\) pebbles on \(V(C_n^2)\). Without loss of generality, fix \(v_1\) as the target vertex. Now \(d_\mu(v_1,v)\leq n-\left(\frac{n}{3}+2\right)\), where \(v\in V(C_n^2)\). Consider \[M_2:\ v_1,\ v_3,\ v_4,\ v_6,\cdots,\ v_{n-6},\ v_{n-5},\ v_{n-3},\ v_{n-2}.\] The vertices not on \(M_2\) are \[\{v_2,\ v_5,\ v_8,\cdots,\ v_{n-7},\ v_{n-4},\ v_{n-1},\ v_n\},\] and this set is denoted by \(M_2^\sim\). The set \(M_2^\sim\) has \(\frac{n}{3}+1\) vertices. If \(p(V(M_2))\geq2^{n-\left(\frac{n}{3}+2\right)}\), then by Theorem 2.11, we can pebble \(v_1\). Otherwise, if \(p(v_n)\geq2\), \(p(v_{n-1})\geq2\), \(p(v_2)\geq2\), or \(p(v_3)\geq2\), then we can pebble \(v_1\). Suppose \(p(V(M_2))<2^{n-\left(\frac{n}{3}+2\right)}\) and \(p(v_n)<2\), \(p(v_{n-1})<2\), \(p(v_2)<2\), and \(p(v_3)<2\). Then the remaining pebbles will be on \(V(M_2^\sim)\). Now we bring the pebbles to \(V(M_2)\), and so we can pebble \(v_1\).
Case 2. \(n\equiv1\pmod{3}\).
Consider \[M_3:\ v_1,\ v_2,\ v_4,\ v_5,\cdots,\ v_{n-6},\ v_{n-5},\ v_{n-3},\ v_{n-2}.\] The vertices not on \(M_3\) are \[v_n,\ v_{n-1},\ v_{n-4},\cdots,\ v_9,\ v_6,\ v_3,\] and they form \(M_3^\sim\). The length of \(M_3\) is \(n-\left(\left\lfloor\frac{n}{3}\right\rfloor+1\right)\), and \(\left\lceil\frac{n}{3}\right\rceil\) vertices are in \(M_3^\sim\). Let \[p(V(C_n^2))=2^{n-\left(\frac{n}{3}+2\right)}-1+\left\lceil\frac{n}{3}\right\rceil.\] By placing \(2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}-1\) pebbles on \(v_1\) and one pebble each on the \(\left\lceil\frac{n}{3}\right\rceil\) vertices on \(M_3^\sim\), we cannot pebble \(v_{n-2}\). Hence, \[\mu(C_n^2)\geq2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+\left\lceil\frac{n}{3}\right\rceil.\] Now we prove the reverse inequality. Consider any distribution of \[2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+\left\lceil\frac{n}{3}\right\rceil\] pebbles on \(V(C_n^2)\). Without loss of generality, fix \(v_{n-2}\) as the target. We have \[d_\mu(v_{n-2},v)\leq n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right),\] where \(v\in V(C_n^2)\). Consider \(M_3\). If \[p(V(M_3))\geq2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)},\] then by Theorem 2.11, we can pebble \(v_{n-2}\). Otherwise, if \(p(v_n)\geq2\), \(p(v_{n-1})\geq2\), \(p(v_{n-3})\geq2\), or \(p(v_{n-4})\geq2\), then we can pebble \(v_{n-2}\). Suppose \[p(V(M_3))<2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}\] and \(p(v_n)<2\), \(p(v_{n-1})<2\), \(p(v_{n-3})<2\), and \(p(v_{n-4})<2\). Then the remaining pebbles will be on \(V(M_3^\sim)\). Now we bring the pebbles to \(V(M_3)\), and so we pebble \(v_{n-2}\).
Case 3. \(n\equiv2\pmod{3}\).
Consider \[M_4:\ v_{n-2},\ v_{n-4},\ v_{n-6},\ v_{n-7},\cdots,\ v_5,\ v_4,\ v_2,\ v_1.\] The vertices not on \(M_4\) are \[v_n,\ v_{n-1},\ v_{n-3},\ v_{n-5},\ v_{n-8},\cdots,\ v_6,\ v_3,\] and they form \(M_4^\sim\). The length of \(M_4\) is \[n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right),\] and \(\left\lceil\frac{n}{3}\right\rceil\) vertices are on \(M_4^\sim\). Let \[p(V(C_n^2))=2^{n-\left(\frac{n}{3}+2\right)}+2.\] By placing \(2^{n-\left(\frac{n}{3}+2\right)}-1\) pebbles on \(v_{n-2}\) and one pebble each on \(v_{n-1},v_n,v_{n-3}\), we cannot pebble \(v_1\) using a monophonic path. Thus, \[\mu(C_n^2)\geq2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3.\] Now we prove the reverse inequality. Consider any distribution of \[2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3\] pebbles on \(V(C_n^2)\). Without loss of generality, let \(v_1\) be the target vertex. Then \[d_\mu(v_1,v)\leq n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right),\] where \(v\in V(C_n^2)\). Consider \(M_4\). If \[p(V(M_4))\geq2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)},\] then by Theorem 2.11, we can pebble \(v_1\). Otherwise, if \(p(v_n)\geq2\), \(p(v_{n-1})\geq2\), \(p(v_2)\geq2\), or \(p(v_3)\geq2\), then we can pebble \(v_1\). Suppose \[p(V(M_4))<2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}\] and \(p(v_n)<2\), \(p(v_{n-1})<2\), \(p(v_2)<2\), and \(p(v_3)<2\). Then the remaining pebbles will be on \(V(M_4^\sim)\). Now we bring the pebbles to \(V(M_4)\), and so we pebble \(v_1\). ◻
Theorem 4.2. The monophonic pebbling number of the lollipop graph is \[2^{n+1}+m-2.\]
Proof. Let \[V(L(m,n))=\{v_1,\ v_2,\cdots,\ v_m,\ u_1,\ u_2,\cdots,\ u_n\},\] where the \(m\) vertices form a complete graph and the \(n\) vertices form a path. Consider a bridge between \(u_1\) and \(v_1\) based on the definition. Let \[p(V(L(m,n)))=2^{n+1}+m-3.\] Consider \[M_1:\ u_n,\ u_{n-1},\cdots,\ u_1,\ v_1,\ v_2.\] If we place one pebble each on \(v_3,v_4,\cdots,v_m\) and \(2^{n+1}-1\) pebbles on \(u_n\), then we cannot place a pebble on \(v_2\). Thus, \[{\mu}(L(m,n))\geq2^{n+1}+m-2.\] Now we prove that \[{\mu}(L(m,n))\leq2^{n+1}+m-2.\]
Case 1. Let the target vertex be \(v_m\).
Consider \[M_2:\ v_m,\ v_1,\ u_1,\ u_2,\cdots,\ u_n,\] a monophonic path of length \(n+1\). The vertex set consisting of vertices that are not on \(M_2\) is \[\{v_2,\ v_3,\cdots,\ v_{m-1}\}\] and is denoted by \(M_2^\sim\). By Theorem 2.11, if \(p(V(M_2))\geq2^{n+1}\), then we can pebble \(v_m\). Suppose \(p(V(M_2))<2^{n+1}\). Then the remaining pebbles will be distributed in \(V(M_2^\sim)\). That is, \[p(V(L(m,n)))-p(V(M_2))=2^{n+1}+m-2-p(V(M_2))>m-1.\] Since \(M_2^\sim\) has \(m-2\) vertices, by the Pigeonhole principle, there will be vertices with more than one pebble. Now we bring the pebbles to \(v_1\). Since \(p(V(M_2))=2^{n+1}\), we can pebble \(v_m\). By symmetry, we can prove the result for \(u_n\), and by using the same argument, we can prove the result for \(v_{m-1},v_{m-2},\cdots,v_2\).
Case 2. Let the target vertex be \(v_1\).
Consider \[M_3:\ v_1,\ u_1,\ u_2,\cdots,\ u_n\] with length \(n\). Now either \(p(V(M_3))\geq2^n\) or \(p(v_j)\geq2\), where \(j=2,3,\cdots,m\). Hence, by Theorem 2.11, we can pebble \(v_1\).
Case 3. Let the target vertex be \(u_l\), where \(l=1,2,3,\cdots,n-1\).
There exist two monophonic paths: \[M_4:\ u_l,\ u_{l-1},\cdots,\ u_1,\ v_1,\ v_2\] of length \(l+1\), and \[M_5:\ u_l,\ u_{l+1},\cdots,\ u_n\] of length \(n-l\). Then either \(p(V(M_4))\geq2^{l+1}\) or \(p(V(M_5))\geq2^{n-l}\). Hence, by Theorem 2.11, we can pebble \(u_l\). ◻
Theorem 4.3. The monophonic pebbling number of the tadpole graph is \[2^{m+n-2}+1.\]
Proof. By the definition of the tadpole graph, consider a bridge between \(u_1\) and \(v_1\). 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_nv_1,\ v_kv_{k+1},\ v_mv_1\},\] where \(i=1,2,\cdots,n-1\) and \(k=1,2,\cdots,m-1\). Let \[p(V(T_{m,n}))=2^{m+n-2}.\] Consider \[M_1:\ u_n,\ u_{n-1},\cdots,\ u_1,\ v_1,\ v_2,\cdots,\ v_{m-1}\] of length \(m+n-2\). If we place one pebble on \(v_m\) and \(2^{m+n-2}-1\) pebbles on \(u_1\), then we cannot place a pebble on \(v_{m-1}\) using a monophonic path. Thus, \[{\mu}(T_{m,n})\geq2^{m+n-2}+1.\]
Now let us prove the sufficient condition.
Case 1. Let the target vertex be \(u_n\).
Consider \[M_2:\ u_n,\ u_{n-1},\cdots,\ u_1,\ v_1,\ v_m,\cdots,\ v_3\] of length \(m+n-2\). By Theorem 2.11, if \(p(V(M_2))\geq2^{m+n-2}\), then we can pebble \(u_n\). Suppose \(p(V(M_2))<2^{m+n-2}\). Then \(2^{m+n-2}+1-p(V(M_2))\) pebbles will be on \(v_2\), and we bring pebbles to \(v_1\). Now \[p(V(M_2))+\left\lfloor\frac{p(v_m)}{2}\right\rfloor\geq2^{m+n-2},\] and we can pebble \(u_n\). By symmetry, the same argument proves the result for \(v_3\) and \(v_{m-1}\).
Case 2. Let the target vertex be \(v_j\), where \(j=3,4,\cdots,m-2\).
If \(\left\lceil\frac{m}{2}\right\rceil+1\leq j\), then there is a monophonic path \[M_3:\ u_1,\ u_2,\cdots,\ u_n,\ v_1,\ v_2,\cdots,\ v_j\] of length \(n+j-1\). If \(\left\lceil\frac{m}{2}\right\rceil+1>j\), then there is a monophonic path \[M_4:\ u_1,\ u_2,\cdots,\ u_n,\ v_1,\ v_m,\ v_{m-1},\cdots,\ v_j\] of length \(m+n-j+1\). By Theorem 2.11, if \(p(V(M_3))\geq2^{n+j-1}\), then we can pebble \(v_j\). Otherwise, if \(p(V(M_4))\geq2^{m+n-j+1}\), then we can pebble \(v_j\).
Case 3. Let the target vertex be \(u_l\), where \(l=1,2,3,\cdots,n-1\).
Consider the monophonic paths \[M_5:\ u_l,\ u_{l+1},\cdots,\ u_n\] of length \(n-l\), and \[M_6:\ u_l,\ u_{l-1},\ u_{l-2},\cdots,\ u_1,\ v_1,\ v_2,\cdots,\ v_{m-1}\] of length \(m+l-2\). By Theorem 2.11, if \(p(V(M_5))\geq2^{n-l}\), then we can pebble \(u_l\). Otherwise, if \(p(V(M_6))\geq2^{m+l-2}\), then we can pebble \(u_l\). ◻
Theorem 4.4. The monophonic pebbling number of the double star path graph is \[2^{n+3}+l+m-2.\]
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\). Consider \[M_1:\ x_1,\ x_0,\ v_1,\ v_2,\cdots,\ v_n,\ y_0,\ y_1.\] Suppose \[p(V(P_n(l,m)))=2^{n+3}+l+m-3.\] By placing one pebble each on \(x_2,x_3,\cdots,x_l\), one pebble each on \(y_2,y_3,\cdots,y_m\), and \(2^{n+3}-1\) pebbles on \(x_1\), we cannot pebble \(y_1\) using a monophonic path. Thus, \[{\mu}(P_n(l,m))\geq2^{n+3}+l+m-2.\] To prove the sufficient condition, consider a distribution of \[2^{n+3}+l+m-2\] pebbles on \(V(P_n(l,m))\).
Case 1. Let the target vertex be \(x_1\).
Consider \[M_2:\ y_1,\ y_0,\ v_n,\ v_{n-1},\cdots,\ v_1,\ x_0,\ x_1\] of length \(n+3\). If \(p(V(M_2))\geq2^{n+3}\), then by Theorem 2.11, we can pebble \(x_1\). Suppose \(p(V(M_2))<2^{n+3}\). Then \[p(V(P_n(l,m)))-p(V(M_2))\] pebbles will be distributed on the remaining pendant vertices of the graph. We bring the pebbles to \(V(M_2)\) to reach \(x_1\). In the same way, we can prove the result for \(x_2,x_3,\cdots,x_l,y_1,\\y_2,\cdots,y_m\).
Case 2. Let the target vertex be \(y_0\).
Consider \[M_3:\ y_0,\ v_n,\ v_{n-1},\cdots,\ v_1,\ x_0,\ x_1\] of length \(n+2\). If \(p(V(M_3))\geq2^{n+2}\), then by Theorem 2.11, we can pebble \(y_0\). Suppose \(p(V(M_3))<2^{n+2}\). Then \[p(V(P_n(l,m)))-p(V(M_3))\] pebbles will be distributed on the remaining pendant vertices of the graph. Thus, by using pebbling moves, we can transfer pebbles from the pendant vertices to \(V(M_3)\), which is sufficient to reach \(y_0\). By the same argument, we can prove the result for the vertex \(x_0\).
Case 3. Let the target vertex be \(v_k\).
There exist two monophonic paths: \[M_4:\ v_k,\ v_{k+1},\cdots,\ v_n,\ y_0,\ y_1\] of length \(n-k+2\), and \[M_5:\ v_k,\ v_{k-1},\cdots,\ v_1,\ x_0,\ x_1\] of length \(k+1\). By Theorem 2.11, if \(p(V(M_4))\geq2^{n-k+2}\) or \(p(V(M_5))\geq2^{k+1}\), then we can pebble \(v_k\).
Hence, \[{\mu}(P_n(l,m))\leq2^{n+3}+l+m-2.\] ◻
Theorem 4.5. The monophonic pebbling number of the class of fuses is \[2^{l+1}+k-1.\]
Proof. Let \[V(F_l(k))=\{v_1,\ v_2,\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\). Suppose \[p(V(F_l(k)))=2^{l+1}+k-2.\] By placing \(k-1\) pebbles on \(v_{l+2},v_{l+3},\cdots,v_{n-1}\) and \(2^{l+1}-1\) pebbles on \(v_{l+1}\), we cannot pebble \(v_0\) using a monophonic path. Thus, \[{\mu}(F_l(k))\geq2^{l+1}+k-1.\]
Now let us prove the sufficient condition.
Case 1. Let the target vertex be \(v_0\).
Consider \[M_1:\ v_0,\ v_1,\cdots,\ v_l,\ v_{l+1}\] of length \(l+1\). By Theorem 2.11, if \(p(V(M_1))\geq2^{l+1}\), then we can pebble \(v_0\). Suppose \(p(V(M_1))<2^{l+1}\). Then \[2^{l+1}+k-1-p(V(M_1))\] pebbles will be on the vertices that are adjacent to \(v_l\) and are not on \(M_1\). Now we can bring the pebbles to \(v_l\) to reach \(v_0\). By symmetry, we prove the result for \(v_{l+1},v_{l+2},\cdots,v_{n-1}\).
Case 2. Let the target vertex be \(v_a\), where \(a=1,2,\cdots,l\).
Then the monophonic path \[M_2:\ v_a,\ v_{a+1},\cdots,\ v_l,\ v_j,\] where \(j=l+1,l+2,\cdots,n-1\), has length \(l+1-a\), and the monophonic path \[M_3:\ v_a,\ v_{a-1},\cdots,\ v_0\] has length \(a\). By Theorem 2.11, if \(p(V(M_2))\geq2^{l+1-a}\), then we can pebble \(v_a\), and if \(p(V(M_3))\geq2^{a}\), then we can pebble \(v_a\).
Thus, \[{\mu}(F_l(k))=2^{l+1}+k-1.\] ◻
In this section, we determine the \(MtPN\) of Dutch windmill graphs, square of cycles, tadpole graphs, lollipop graphs, double star path graphs, and fuse graphs.
Theorem 5.1. The monophonic \(t\)-pebbling number of \(D_n^m\) is \[t2^{2n-4}+(m-2)(2^{n-2}-1)+m,\] where \(m\geq2\) and \(n\geq5\).
Proof.By placing \(2^{n-2}\) pebbles on \(v_2^l\), where \(l=3,4,\cdots,m\), one pebble each on \(v_1^j\), where \(j=1,2,\cdots,m\), and \(t2^{2n-4}-1\) pebbles on \(v_{n-2}^1\), we cannot place \(t\) pebbles on \(v_{n-2}^2\). Therefore, \[{\mu}_t(D_n^m)\geq t2^{2n-4}+(m-2)(2^{n-2}-1)+m.\]
Now let us prove the sufficient part. If \(t=1\), then the result follows from Theorem 3.4. Assume that the result is true for \(2\leq t\leq t-1\). Let us fix any vertex \(u\) as the target.
Clearly, the graph \(D_n^m\) has at least \[2^{2n-3}+(m-2)(2^{n-2}-1)+m\] pebbles. Also, \(d_\mu(u,v)\leq2n-4\), where \(v\in V(D_n^m)\). We can move a pebble to \(u\) at a cost of at most \(2^{2n-4}\) pebbles. Hence, the number of pebbles remaining on \(V(D_n^m)-\{u\}\) is at least \[\begin{aligned} {\mu}_t(D_n^m)-2^{2n-4} &=t2^{2n-4}+(m-2)(2^{n-2}-1)+m-2^{2n-4} \\ &=(t-1)2^{2n-4}+(m-2)(2^{n-2}-1)+m\\ &={\mu}_{t-1}(D_n^m). \end{aligned}\] By induction on \(t\), we can shift \(t-1\) additional pebbles to \(u\). Suppose \(p(u)=x\), where \(1\leq x\leq t-1\). Thus, the number of pebbles distributed on \(V(D_n^m)-\{u\}\) is \[\begin{aligned} {\mu}_t(D_n^m)-p(u) &=t2^{2n-4}+(m-2)(2^{n-2}-1)+m-x\\ &\geq (t-x)2^{2n-4}+(m-2)(2^{n-2}-1)+m\\ &={\mu}_{t-x}(D_n^m). \end{aligned}\] Then we can move \(t-x\) additional pebbles to \(u\). Thus, \[{\mu}_t(D_n^m)\leq t2^{2n-4}+(m-2)(2^{n-2}-1)+m.\] Hence, the proof is complete. ◻
Theorem 5.2. The \(MtPN\) of \(C_n^2\) is \[\begin{cases} t2^{n-\left(\frac{n}{3}+2\right)}+2, & \text{if } n\equiv0\pmod{3},\\[4pt] t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+\left\lceil\frac{n}{3}\right\rceil, & \text{if } n\equiv1\pmod{3},\\[4pt] t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3, & \text{if } n\equiv2\pmod{3}. \end{cases}\]
Proof. To prove this theorem, we consider the following three cases.
Case 1. \(n\equiv0\pmod{3}\).
Let \[p(V(C_n^2))=t2^{n-\left(\frac{n}{3}+2\right)}+1.\] By placing \(t2^{n-\left(\frac{n}{3}+2\right)}-1\) pebbles on \(v_{n-2}\) and one pebble each on \(v_n\) and \(v_{n-1}\), we cannot place \(t\) pebbles on \(v_1\). Hence, \[\mu_t(C_n^2)\geq t2^{n-\left(\frac{n}{3}+2\right)}+2.\]
Now we prove the sufficient condition. Consider any distribution of \[t2^{n-\left(\frac{n}{3}+2\right)}+2\] pebbles on the vertices of \(C_n^2\). If \(t=1\), then the result follows from Theorem 4.1. Assume that the result is true for \(2\leq t\leq t-1\). Let us fix any vertex \(v\) as the target.
We notice that the graph has at least \[2^{n-\left(\frac{n}{3}+1\right)}+2\] pebbles. The monophonic distance from \(v\) to any vertex in the graph is at most \[n-\left(\frac{n}{3}+2\right).\] Hence, using at most \(2^{n-\left(\frac{n}{3}+2\right)}\) pebbles, we can place one pebble on the target. Now \[\begin{aligned} \mu_t(C_n^2)-2^{n-\left(\frac{n}{3}+2\right)} &=t2^{n-\left(\frac{n}{3}+2\right)}+2-2^{n-\left(\frac{n}{3}+2\right)} \\ &=(t-1)2^{n-\left(\frac{n}{3}+2\right)}+2\\ &=\mu_{t-1}(C_n^2). \end{aligned}\] Thus, by induction, we can move \(t-1\) additional pebbles to \(v\). Suppose we have \(y\) pebbles on \(v\), where \(y<t\). Then the total number of pebbles on \(V(C_n^2)-\{v\}\) is \[\begin{aligned} \mu_t(C_n^2)-p(v) &=t2^{n-\left(\frac{n}{3}+2\right)}+2-y\\ &\geq (t-y)2^{n-\left(\frac{n}{3}+2\right)}+2\\ &=\mu_{t-y}(C_n^2). \end{aligned}\] Thus, we can move \(t-y\) pebbles to \(v\). Therefore, \[\mu_t(C_n^2)\leq t2^{n-\left(\frac{n}{3}+2\right)}+2,\] and the case is proved.
Case 2. \(n\equiv1\pmod{3}\).
Consider the monophonic path \[M_3:\ v_1,\ v_2,\ v_4,\ v_5,\cdots,\ v_{n-6},\ v_{n-5},\ v_{n-3},\ v_{n-2}.\] The vertices that are not on \(M_3\) are \[v_n,\ v_{n-1},\ v_{n-4},\cdots,\ v_9,\ v_6,\ v_3,\] and these elements form the set \(M_3^\sim\). Let \[p(V(C_n^2))=t2^{n-\left(\frac{n}{3}+2\right)}-1+\left\lceil\frac{n}{3}\right\rceil.\] By placing \(t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}-1\) pebbles on \(v_1\) and one pebble each on the \(\left\lceil\frac{n}{3}\right\rceil\) vertices on \(M_3^\sim\), we cannot place \(t\) pebbles on \(v_{n-2}\). Hence, \[\mu_t(C_n^2)\geq t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+\left\lceil\frac{n}{3}\right\rceil.\]
Now we prove the sufficient condition. Consider any distribution of \[t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil\] pebbles on the vertices of \(C_n^2\). If \(t=1\), then the result follows from Case 2 of Theorem 4.1. Assume that the result is true for \(2\leq t\leq t-1\). Let us fix any vertex \(u\) as the target.
Clearly, the graph has at least \[2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+1\right)} +\left\lceil\frac{n}{3}\right\rceil\] pebbles. Note that \[d_\mu(u,v)\leq n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right),\] where \(v\in V(C_n^2)\), and we can move a pebble to \(u\) at a cost of \[2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}\] pebbles. Hence, the number of pebbles remaining on \(V(C_n^2)-\{u\}\) is at least \[\begin{aligned} {\mu}_t(C_n^2)-2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} & =t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil -2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} \\ &=(t-1)2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil\\ &={\mu}_{t-1}(C_n^2). \end{aligned}\] Thus, by induction, we can move \(t-1\) additional pebbles to \(u\). Suppose \(p(u)=x\), where \(1\leq x\leq t-1\). Then the total number of pebbles distributed on \(V(C_n^2)-\{u\}\) is \[\begin{aligned} {\mu}_t(C_n^2)-p(u) &=t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil-x \\&\geq (t-x)2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil \\&={\mu}_{t-x}(C_n^2). \end{aligned}\] Since \(1\leq x\leq t-1\), we can move \(t-x\) additional pebbles to \(u\). Thus, \[{\mu}_t(C_n^2)\leq t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)} +\left\lceil\frac{n}{3}\right\rceil.\]
Case 3. \(n\equiv2\pmod{3}\).
Let \[p(V(C_n^2))=t2^{n-\left(\frac{n}{3}+2\right)}+2.\] By placing \(t2^{n-\left(\frac{n}{3}+2\right)}-1\) pebbles on \(v_{n-2}\) and one pebble each on \(v_{n-1},v_n,v_{n-3}\), we cannot place \(t\) pebbles on the vertex \(v_1\) using a monophonic path. Thus, \[\mu_t(C_n^2)\geq t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3.\] Now we prove the sufficient condition. Consider any distribution of \[t2^{n-\left(\left\lfloor\frac{n}{3}\right\rfloor+2\right)}+3\] pebbles on \(V(C_n^2)\). If \(t=1\), then the result follows from Theorem 4.1. The rest of the proof is similar to that of Case 1. ◻
Theorem 5.3. The monophonic \(t\)-pebbling number of the lollipop graph is \[t2^{n+1}+m-2.\]
Proof. Suppose \[p(V(L(m,n)))=t2^{n+1}+m-3.\] By placing \(t2^{n+1}-1\) pebbles on \(u_n\) and one pebble each on \(v_2,v_3,\cdots,v_{m-1}\), we cannot place \(t\) pebbles on \(v_m\) using a monophonic path. Thus, \[{\mu}_t(L(m,n))\geq t2^{n+1}+m-2.\] Now let us prove the sufficient condition. If \(t=1\), then the result follows from Theorem 4.2. Assume that the result is true for \(2\leq t\leq t-1\). Let \(u\) be the target.
Case 1. Suppose \(p(u)=0\).
Clearly, the graph \(L(m,n)\) has at least \(2^{n+2}+m-3\) pebbles. Note that \[d_\mu(u,v)\leq n+1,\] where \(v\in V(L(m,n))\), and we can move a pebble to \(u\) at a cost of \(2^{n+1}\) pebbles. Hence, the number of pebbles remaining on \(V(L(m,n))\) other than \(u\) is at least \[{\mu}_t(L(m,n))-2^{n+1} =t2^{n+1}+m-2-2^{n+1} =(t-1)2^{n+1}+m-2 ={\mu}_{t-1}(L(m,n)).\] Thus, by induction, we can move \(t-1\) additional pebbles to \(u\).
Case 2. Suppose \(p(u)=y\), where \(1\leq y\leq t-1\).
Thus, the total number of pebbles distributed on \(V(L(m,n))-\{u\}\) is \[\begin{aligned} {\mu}_t(L(m,n))-p(u) &=t2^{n+1}+m-2-y \\&\geq (t-y)t2^{n+1}+m-2 \\&={\mu}_{t-y}(L(m,n)). \end{aligned}\] Since \(1\leq y\leq t-1\), we can move \(t-y\) additional pebbles to \(u\). Hence, the result follows. ◻
Theorem 5.4. The monophonic \(t\)-pebbling number of the tadpole graph is \[t2^{m+n-2}+1.\]
Proof. Let \[p(V(T_{m,n}))=t2^{m+n-2}.\] By placing \(t2^{n+m-2}-1\) pebbles on \(u_n\) and one pebble on \(v_m\), we cannot place \(t\) pebbles on \(v_{m-1}\) using a monophonic path. Thus, \[{\mu}_t(T_{m,n})\geq t2^{n+m-2}+1.\]
Now let us prove the sufficient condition. If \(t=1\), then the result follows from Theorem 4.3. Assume that the result is true for \(2\leq t\leq t-1\). Let \(u\) be the target.
Clearly, the graph \(T_{m,n}\) has at least \(2^{n+m-1}+1\) pebbles. Also, \[d_\mu(u,v)\leq n+m-2,\] where \(v\in V(T_{m,n})\), and we can move one pebble to any target vertex at a cost of \(2^{n+m-2}\) pebbles. Hence, the number of pebbles remaining on \(V(T_{m,n})-\{u\}\) is at least \[\begin{aligned} {\mu}_t(T_{m,n})-2^{n+m-2} &=t2^{n+m-2}+1-2^{n+m-1} \\&=(t-1)2^{n+m-1}+1 \\&={\mu}_{t-1}(T_{m,n}). \end{aligned}\] Thus, by induction, we can move \(t-1\) additional pebbles to \(u\). Suppose \(p(u)=x\), where \(1\leq x\leq t-1\). Thus, the total number of pebbles distributed on the vertices of the graph is \[\begin{aligned} {\mu}_t(T_{m,n})-p(u) &=t2^{n+m-2}+1-x \\&\geq (t-x)t2^{n+m-2}+1 \\&={\mu}_{t-x}(T_{m,n}). \end{aligned}\] Since \(1\leq x\leq t-1\), we can move \(t-x\) additional pebbles to \(u\). Thus, \[{\mu}_t(T_{m,n})\leq t2^{n+m-1}.\] Hence, the proof is complete. ◻
Theorem 5.5. The monophonic \(t\)-pebbling number of the double star path graph is \[t2^{n+3}+l+m-2.\]
Proof. Let \[p(V(P_n(l,m)))=t2^{n+3}+l+m-3.\] By placing one pebble each on \[x_2,x_3,\cdots,x_l,\ y_2,y_3,\cdots,y_m\] and \(t2^{n+3}-1\) pebbles on \(x_1\), we cannot place \(t\) pebbles on \(y_1\) using a monophonic path. Thus, \[{\mu}_t(P_n(l,m))\geq t2^{n+3}+l+m-2.\]
To prove the sufficient condition, consider a distribution of \[t2^{n+3}+l+m-2\] pebbles on \(V(P_n(l,m))\). If \(t=1\), then the result follows from Theorem 4.4. Assume that the result is true for \(2\leq t\leq t-1\). Let \(u\) be the target.
We notice that the graph has at least \[2^{n+4}+l+m-2\] pebbles. Clearly, \[d_\mu(u,v)\leq n+3,\] where \(v\in V(P_n(l,m))\). Hence, using at most \(2^{n+3}\) pebbles, we can place one pebble on \(u\). Now \[\begin{aligned} \mu_t(P_n(l,m))-2^{n+3} &=t2^{n+3}+l+m-2-2^{n+3} \\ &=(t-1)2^{n+3}+l+m-2\\ &=\mu_{t-1}(P_n(l,m)). \end{aligned}\] Thus, by induction, we can move \(t-1\) additional pebbles to \(u\). Suppose we have \(y\) pebbles on \(u\), where \(y<t\). Then the total number of pebbles on the remaining vertices of the graph is \[\begin{aligned} \mu_t(P_n(l,m))-p(u) &=t2^{n+3}+l+m-2-y \\ &\geq (t-y)2^{n+3}+l+m-2\\ &=\mu_{t-y}(P_n(l,m)). \end{aligned}\] Thus, we can move \(t-y\) pebbles to \(u\). Therefore, \[\mu_t(P_n(l,m))\leq t2^{n+3}+l+m-2.\] ◻
Theorem 5.6. The monophonic \(t\)-pebbling number of the class of fuse graphs is \[t2^{l+1}+k-1.\]
Proof. Let \[p(V(F_l(k)))=t2^{l+1}+k-2.\] By placing one pebble on each vertex \[v_{l+2},v_{l+3},\cdots,v_{n-1}\] and \(t2^{l+1}-1\) pebbles on \(v_{l+1}\), we cannot place \(t\) pebbles on the vertex \(v_0\) using a monophonic path. Thus, \[\mu_t(F_l(k))\geq t2^{l+1}+k-1.\] Now let us prove the sufficient condition. If \(t=1\), then the result follows from Theorem 4.5. Assume that the result is true for \(2\leq t\leq t-1\). Let us fix any vertex \(u\) as the target.
Case 1. Suppose \(p(u)=0\).
Clearly, the graph \(F_l(k)\) has at least \[2^{l+2}+k-1\] pebbles. The distance satisfies \[d_\mu(u,v)\leq l+1,\] where \(v\in V(F_l(k))\), and we can move one pebble to any target vertex at a cost of \(2^{l+1}\) pebbles. Hence, the number of pebbles remaining on the vertices of the graph \(F_l(k)\) other than the vertex \(u\) is at least \[\begin{aligned} \mu_t(F_l(k))-2^{l+1} &=t2^{l+1}+k-1-2^{l+1}\\ &=(t-1)2^{l+1}+k-1\\ &=\mu_{t-1}(F_l(k)). \end{aligned}\] Thus, by induction, we can move \(t-1\) additional pebbles to \(u\).
Case 2. Suppose \(p(u)=y\), where \(1\leq y\leq t-1\).
Thus, the total number of pebbles on the vertices of the graph is \[\begin{aligned} \mu_t(F_l(k))-p(u) &=t2^{l+1}+k-1-y \\ &\geq (t-y)2^{l+1}+k-1\\ &=\mu_{t-y}(F_l(k)). \end{aligned}\] Since \(1\leq y\leq t-1\), we can move \(t-y\) additional pebbles to \(u\). Thus, \[\mu_t(F_l(k))\leq t2^{l+1}+k-1.\] ◻
In this article, we computed the \(MPN\) and \(MtPN\) of several cycle and path graphs. This approach has been developed based on the limitations of the methodology used in the literature. The concept of the monophonic pebbling number helps in minimizing or optimizing the flow of information through a network. Our future scope will be to develop an algorithm that can be implemented on a computer.