Graph pebbling is a network optimization method modeling the movement of resources in transit. A pebbling move on a connected graph \(G\) removes two pebbles from a vertex, places one on an adjacent vertex, and discards the other, with the loss analogous to packet loss in communication networks. The generalized version, \(t\)-pebbling, defines the \(t\)-pebbling number \(f_t(G)\) as the smallest integer such that, from any distribution of \(f_t(G)\) pebbles, \(t\) pebbles can be moved to any vertex \(v\) via a pebbling sequence. A graph satisfies the \(2t\)-pebbling property if \(2t\) pebbles can be transferred to \(v\) when \(2f_t(G)-q+1\) pebbles are distributed, where \(q\) is the number of occupied vertices. This paper establishes a lower bound for the rooted product of two graphs \(G\) and \(H\), sharp when one factor is a path, complete graph, or star. Further results on pebbling in triangle-free graphs are also obtained, including verification of the \(2t\)-pebbling property for rooted products involving such graphs.
Graph pebbling is a combinatorial game played on graphs and it was first introduced by Chung in 1989 [2]. Pebbling on graphs plays a very important role in number theory and game theory problems [9]. The blend of Graph Theory, Number Theory and Optimization was well exhibited in [8] by Hurlbert. All graphs considered are connected. Place a distribution of pebbles on the vertices of the graph \(G\). A pebbling move involves removing two pebbles from a vertex and placing one on a neighboring vertex. The pebbling number of a vertex \(v\) in a graph \(G\) is the smallest number \(f(G,v)\), with the condition that for every placement of \(f(G,v)\) pebbles on \(G\), a pebble may be moved to \(v\) using a sequence of pebbling moves. For a graph \(G\), the pebbling number \(f(G)\) is the maximum of \(f(G,v)\) across all of its vertices. A graph \(G\) satisfies \(2\)-pebbling property if two pebbles may be moved to any arbitrary vertex with a total beginning number of pebbles of \(2f(G)-q+1\), where \(q\) is the number of vertices with at least one pebble.
If \(t\) pebbles may be placed on vertex \(r\) after a certain sequence of pebbling moves, then the distribution \(P\) is \(t\)-fold \(r\)-solvable; otherwise, it is \(t\)-fold \(r\)-unsolvable. This pertains to a distribution \(P\) of pebbles on the vertices of \(G\). Additionally, if \(P\) is \(t\)-fold \(r\)-solvable for each \(r \in V(G)\), then it is \(t\)-fold solvable. The lowest integer \(f_t(G,r)\) such that for every distribution of \(f_t(G,r)\) pebbles on \(G\) is \(t\)-fold \(r\)-solvable is the \(t\)-pebbling number of a vertex \(r \in V(G)\). The maximum of \(f_t(G,r)\) across all the vertices of \(G\) is the \(t\)-pebbling number \(f_t(G)\). Lourdusamy extended the definition of \(2\)-pebbling property to \(2t\)-pebbling property [12]. Let \(p\) represent the number of pebbles on \(G\) and \(q\) represent the number of vertices with at least one pebble. The \(2t\)-pebbling property of a graph \(G\) is satisfied if and only if \(2t\) pebbles may be moved from the distribution of \(p \geq 2f_t(G) – q + 1\) or \(p+q > 2f_t(G)\) to any given target vertex. He also proposed the \(t\)-pebbling conjecture \(f_t(G \times H) \leq f(G) f_t(H)\) for any two connected graphs \(G\) and \(H\). The literature has ample number of research articles verifying the \(t\)-pebbling conjecture on Cartesian product of two graphs. To explore more on pebbling and its variations one can refer [1, 5, 7, 10, 11, 13, 14, 15, 16].
Modern technology is focusing on the development and innovation of adhoc networks, including Unmanned Aerial Vehicles (UAVs), Vehicular Adhoc Networks (VANETs), and Mobile Adhoc Networks (MANETs). Adhoc network plays a vital role in many fields like networking of electronic devices, maritime communications, military troops wireless networking, interconnection of rescue teams etc. In an adhoc network, the information is communicated from one node to another node through a routing algorithm. There are some challenges in the routing protocol such as breakage of routers due to heavy traffic flow or congestion. Hence, there is a demand in designing an efficient adhoc network which can overcome these challenges. This can effectively be done by reducing the packet loss in a network. A unit of data is referred as a packet. Whenever the node sends or receives messages it actually uses some energy which is referred as packet loss. The packet loss can either be time loss, fuel loss or information loss. To ensure good communication in adhoc networks, it’s crucial to limit packet loss. The concept of pebbling has its applications in the reduction of memory traffic in computers, register allocation problem and transmission of information from one directory to the other. The pebbling steps determine the cost of pebble loss and have been the focus of substantial research in the context of proving lower bounds for computation on graphs. The generalization of packet loss in this process is defined as \(t\)-pebbling. This paper aims to correlate the results of \(t\)-pebbling with the general packet loss. In section 3, we propose a result on \(t\)-pebbling number of triangle-free graphs where we can locate many graphs and networks under this large class. In section 4, we have proposed an algorithm for obtaining the lower bound on \(t\)-pebbling number of rooted product of two graphs \(G\) and \(H\) and derive computational outcomes for different types of graphs like a path, a complete graph and a star.
The study of some special classes of graphs is an interesting field of study as it paves way for advanced research of more complicated problems. Triangle-free graphs are one such class of graphs which has widely been studied in the literature as it is a natural generalization of bipartite graphs. Triangle-free graphs have no adjacent vertices that share a common vertex. Most triangle-free graphs are bipartite, and those that are not are quasi-bipartite [3], see Figure 1 and 2.
Theorem 3.1. [4] The pebbling number of a complete bipartite graph is \(f(K_{r,s}) = r+s\).
Notation 3.2. Let \(G\) be a connected graph with diameter \(d\) and \(\kappa(G)\) denote the connectivity of \(G\). For all \(d\), there is a \(\kappa(d)\) such that every graph with diameter \(d\) and connectivity at least \(\kappa(d)\) is Class 0. A graph is classified as Class 0, if \(2^d \leq n(G)\), where \(n(G)\) is the number of vertices in \(G\).
Theorem 3.3. For a triangle-free graph \(G\) of order \(n\) with connectivity \(\kappa\) and diameter \(d\), \[f_t(G) \geq \begin{cases} nt & \text{if } \kappa \geq d, \\ t2^d & \text{if } \kappa < d. \end{cases}\]
Proof. Partition the vertex set of \(G\) into two sets \(X\) and \(Y\), in which, \(x_1, x_2, \dots, x_r\) be the vertices of \(X\) and \(y_1, y_2, \dots, y_s\) be the vertices of \(Y\), either \(r = s\) or \(r \neq s\). Without loss of generality, fix \(X\) as the independent set. Let \(N_Y(x_i)\) denote the neighbors of \(x_i\) in \(Y\). For \(x_1x_2 \in E(G)\), \(x_1 \stackrel{w}{\rightarrow} x_2\) refers to taking at least \(2w\) pebbles from \(x_1\) and placing at least \(w\) pebbles on \(x_2\). Let \(p(x_1)\) represent the number of pebbles placed on the vertex \(x_1\). Refer to the source vertex as the vertex that starts the pebbling motion and the target vertex as the vertex to which \(t\) pebbles are eventually transferred after a series of pebbling moves. Suppose that \(G = C_n\), where \(n\) is even and \(\kappa \leq d\). Let the vertices of \(C_n\) be \(x_1, x_2, \dots, x_n\). Set the target vertex to \(x_1\). Distribute \((n-1)t\) pebbles over vertices of \(C_n\) such that there are zero pebbles on the target and at least \(t\) pebbles on the remaining vertices of \(C_n\). For the above distribution, there is no vertex to initiate the pebbling move and hence in the context of our proof \(f_t(G) \geq nt\), where \(n=r+s\). Now assume a distribution of \(nt\) pebbles over the vertices of \(G\).
Case 1. When \(\kappa \geq d\).
Choose some vertex say \(x_1 \in X\) as the target vertex. Let \(p_1\) and \(p_2\) denote the number of pebbles in the set \(X\) and \(Y\) respectively such that \(p_1 + p_2 \geq nt\). The various configurations of pebbles are categorized into the following cases.
Case 1.1. Let \(p(N_Y(x_1)) \geq 2t\).
If \(p(N_Y(x_1)) \geq 2t\), then \(t\) pebbles can be easily moved to \(x_1\) for any \(N_Y(x_1)\).
Case 1.2. Let \(0 < p(N_Y(x_1)) < 2t\).
Let \(a_1, a_2, \dots,\ a_d\) where \(a_d = x_1\), be the diametric path from any vertex \(a_1\) to the target vertex \(a_d = x_1\). If \(G\) is bipartite then \(a_1, a_3, a_5, \dots,\ a_d \in X\) and \(a_2, a_4, a_6 \dots,\ a_{d-1} \in Y\) or \(a_1, a_3, a_5, \dots,\ a_{d-1} \in Y\) and \(a_2, a_4, a_6 \dots,\ a_{d} \in X\). Excluding the pebbles considered on \(N_Y(x_1)\) there will be \(p_1 + p_2 \geq nt – t\) remaining pebbles on \(G\). Therefore, there exist at least one vertex say \(a_1\) with a minimum of \(2t\) pebbles to initiate the pebbling move. Further, excluding the pebbles considered on \(a_1\) there will be \(p_1 + p_2 \geq (n-1)t-2t = (n-3)t\) remaining pebbles on \(G\). Distribute this \((n-3)t\) remaining pebbles such that each vertex should have at least \(t\) pebbles. With \(p(a_1) = 2t\), there exists a sequence a pebbling move along the path \(a_1 \stackrel{t}{\rightarrow} a_2 \stackrel{t}{\rightarrow} a_3 \stackrel{t}{\rightarrow} \dots \stackrel{t}{\rightarrow} a_d\). The discussion is similar if \(a_1\) is a vertex in \(Y\). This method allows \(t\) pebbles to be moved to the desired vertex. The theorem’s proof proceeds similarly when \(G\) is a quasi-bipartite graph, with the small exception that the diametric path will include a vertex \(a_i\) either in \(X\) or \(Y\).
Case 1.3. Let \(p(N_Y(x_1)) = 0\).
Excluding the possibilities discussed in Case 1.1 and 1.2, now assume that there are zero pebbles on all the vertices except the source vertex. Let \(a_1\) be the source vertex. Place \(nt\) pebbles on \(a_1\). For the above possibility, it is possible to move \(t\) pebbles to the target considering the sequence of pebbling move along the diametric path \(a_1 \stackrel{\frac{nt}{2}}{\rightarrow} a_2 \stackrel{\frac{nt}{4}}{\rightarrow} a_3 \stackrel{\frac{nt}{8}}{\rightarrow} \dots \stackrel{t}{\rightarrow} a_d =x_1\).
Case 2. When \(\kappa < d\).
In this case, the diameter \(d\) of a triangle-free graph is larger than the connectivity \(\kappa\) of \(G\). The target \(x_1\) cannot be pebbled with the available \(nt\) pebbles because only \(t\) pebbles can be transmitted to \(N_Y(x_1)\). In order to overcome this inadequacy of pebbles, consider a pebbling move along the diametric path \(a_1 \stackrel{t2^{d-1}}{\rightarrow} a_2 \stackrel{t2^{d-2}}{\rightarrow} a_3 \stackrel{t2^{d-3}}{\rightarrow} \dots \stackrel{t}{\rightarrow} a_d =x_1\) which requires \(t2^d\) pebbles on the vertex \(a_1\) to reach the target \(x_1\) with \(t\) pebbles.
The proof is hypothetical for the target vertex chosen as some vertex \(y_i \in Y\). ◻
Theorem 3.4. Every triangle-free graph \(G\) satisfies \(2t\)-pebbling property.
Proof. Let \(p\) be the number of pebbles on a triangle-free graph \(G\), \(q\) be the number of vertices with at least one pebble. Let \(\left|V(G)\right| = n\). Consider a distribution \(p = 2f_t(G) – q + 1\) of pebbles on \(G\). Without loss of generality, assume the target vertex either in the set \(X\) or \(Y\). Let \(x_1 \in X\) be chosen as the target vertex.
Case 1. If \(p(x_1) = 0\) then \(q \leq n-1\). The count of pebbles that remain on the vertices of \(G\) after eliminating the pebbles that are on \(x_1\) will be \(p \geq 2f_t(G) – q + 1 \geq 2f_t(G) +1 -(n-1) \geq 2f_t(G) -n +2\). To pebble the target, take into consideration the placement of pebbles on the diametric path \(a_1, a_2, \dots,\ a_d\). With \(2f_t(G) -n +2\) pebbles, each vertex \(a_i\) will have at least \(2t\) pebbles. Thus, after a sequence of pebbling move, at least \(4t\) pebbles can be moved to \(N_Y(x_1)\) and as a consequence \(2t\) pebbles can be moved to \(x_1\).
Case 2. If \(p(x_1) = l, 1 \leq l \leq 2t – 1\) then \(q \leq n\). In this case, the number of pebbles remaining on the vertices of \(G\) will be \(p \geq 2f_t(G) – n + 1 – l\). As in Case 1, after the pebbling move along the diametric path there exists at least \(4t – 2l\) pebbles on \(N_Y(x_1)\). Hence, \(2t – l\) pebbles are moved to \(x_1\) such that after a pebbling move \(p(x_1) = 2t\). Thus, every triangle-free graph satisfies \(2t\)-pebbling property. ◻
Let \(G\) be a graph of order \(n\) with \(V(G) = \{u_1,u_2, \dots, u_n\}\) and let \(H\) be a graph of order \(m\) with \(V(H) = \{v_1,v_2, \dots, v_m\}\). Fix any vertex \(v_i, 1 \leq i \leq m\) of the graph \(H\) as the root vertex \(v\). The rooted product of two graphs \(G\) and \(H\) denoted by \(G \circ_v H\) is a graph that is obtained by identifying the root vertex \(v\) of \(H\) with every \(i^{th}\) vertex of \(G\) for \(i = 1,2, \dots, n\). The vertex set of \(G \circ_v H\) is \(V(G) \times V(H)\) [6].
Notation 4.1. In \(G \circ_{v} H\) the vertices of \(G\) are labeled as \((u_i,v)\) for \(1 \leq i \leq n\) and the vertices of \(H\) are labeled as \((u_i,v_1), (u_i,v_2), \dots, (u_i,v_{m-1})\) sequentially for every \(i^{th}\) copy of \(G\). The schematic representation of the rooted product of graphs and its labeling scheme are represented in Figure 3. Let \(d_G(u_i,u_j)\) denote the length of the shortest path between the vertices \(u_i\) and \(u_j\) for \(u_i,u_j \in G\). The distance between two vertices \((u_i,v_l), (u_j,v_k) \in V(G \circ_{v} H)\) is denoted by \(D\) where \(D = d_H(v_l,v) + d_G(u_i,u_j) + d_H(v,v_k)\), where \(v\) is the root vertex of \(H\). Let \(p(u_i,v_j)\) denote the number of pebbles initially placed on the vertex \((u_i, v_j)\). For \(\left\{(u_i,v_j) (u_l,v_k)\right\} \in E(G \circ_{v} H)\}\), \((u_i,v_j) \stackrel{t}{\rightarrow} (u_l,v_k)\) refers to taking off at least \(2t\) pebbles from \((u_i,v_j)\) and placing at least \(t\) pebbles on \((u_l,v_k)\). Let \(P_G\) denote the number of pebbles distributed over the vertices of \(G\) and \(P_{H_i}, 1 \leq i \leq n\) denote the number of pebbles distributed on \(i^{th}\) copy of \(H\) in \(G \circ_{v} H\).
Algorithm 4.1. The \(t\)– pebbling number of rooted product of two graphs \(G\) and \(H\) can be obtained by the following algorithm.
Input: Graph \(G\)
of order \(n \geq 2\) and Graph \(H\) of order \(m
\geq 2\).
Step 1. Select any vertex \(v\) of \(H\) as the root vertex.
Step 2. Identify whether \(H\) is a vertex transitive graph or not.
Based on this condition the solution will be found considering \(d(v)\), the degree of the root vertex \(v\).
Step 3. Find the rooted product of the two graphs \(G\) and \(H\) and label the vertices as in Notation
4.1.
Step 4. Select the target vertex as \((u_n,v)\) and the source vertex as \((u_i,v)\), for \(1 \leq i \leq n-1\).
Step 5.
target is pebbled the target is pebbled with \(nf_t(H) – P_G\) pebbles on the vertices of \(H_i\), \(1 \leq i \leq n-1\).
Step 6. Select the target vertex as \((u_n,v)\) and the source vertex as \((u_i,v_j)\), for \(1 \leq i,j \leq n-1\).
target is pebbled with at least \(nf_t(H) – P_{H_i} – P_{H_n}\) pebbles on the vertices \((u_i,v)\) \(1 \leq i \leq n-1\). target is pebbled with \(nf_t(H)- P_{H_i} – P_{H_n}\) and \(P_{H_l} \geq f_t(H)\) or \(P_{H_k} \geq f_t(H)\) pebbles.
Step 7. Select the target vertex as some \((u_i,v_j)\) and source vertex as \((u_k,v), 1 \leq k \leq n\).
Repeat the Step 5.
Step 8. Select the target vertex as some \((u_i,v_j)\) and source vertex as \((u_l,v_k)\), \(1
\leq k \leq n\).
target is pebbled target is pebbled
Theorem 4.2. Let \(G\) and \(H\) be two connected graphs with orders \(n \geq 2\) and \(m \geq 2\) respectively. Then \(f_t(G \circ_{v} H) \geq\) max \(\left\{nf_t(H), t2^D\right\}\).
Proof. Let \(G\) be a connected graph on \(n\) vertices. Consider \(v\) to be the root vertex of \(H\). In \(G \circ_{v} H\), let \(H_1, H_2, \dots, H_n\) denote the \(n\) copies of \(H\). Consider the distribution of \(nf_t(H)\) pebbles on the vertices of \(G \circ_{v} H\).
Case 1. Initially choose the target vertex as \((u_n,v)\) and the source vertex as any \((u_i,v), 1 \leq i \leq n-1\). The theorem’s proof corresponds for any vertex \((u_l,v)\) selected as the target vertex. Throughout this case assume \(P_{H_n} = 0\). If so, the solution is trivial.
Case 1.1. Let \(nf_t(H)\) be \(P_G\). Transferring \(t\) pebbles to the target vertex is feasible by using \(f_t(G)\) pebbles on the vertices of \(G\). It then turns out that since \(f_t(G) < nf_t(H)\), the target \((u_n,v)\) is pebbled.
Case 1.2. If \(P_G < nf_t(H)\) then there may arise a situation of insufficiency of pebbles in sequencing the pebbling move along the path \((u_i,v) \rightarrow (u_{i+1},v) \rightarrow (u_{i+2},v) \rightarrow \dots \rightarrow (u_n,v)\). In this case, we extract pebbles from each copy of \(H\). Excluding the pebbles considered on \((u_i,v)\) for all \(i\), there will be \(nf_t(H) – P_G\) remaining pebbles on \(G \circ_v H\). Consider the distribution of \(nf_t(H) – P_G\) pebbles on the vertices of \(H\). Now, each copy of \(H\) contributes \(t\) pebbles to \((u_i,v), 1 \leq i \leq n-1\) and as a consequence \((n-1)t\) pebbles are transmitted to the vertices \((u_i,v)\). Assuming \(P_G\) pebbles on \((u_i,v)\), \(t\) pebbles can be moved to the target vertex.
Case 2. Suppose \((u_n,v)\) is fixed as the target vertex and source vertex as any vertex \((u_i,v_j) \in H_i\). Assume \(P_{H_n} < f_t(H)\). Otherwise, the solution is trivial.
Case 2.1. If \(P_{H_i} = f_t(H), i \neq n\) then \(t\) pebbles can be moved to \((u_i,v)\). Now there will be at least \(nf_t(H) – P_{H_i} – P_{H_n}\) remaining pebbles on \((u_i,v)\). Further, \(t\) pebbles can be moved to \((u_n,v)\) through the path \((u_i,v_j) \rightarrow (u_i,v_{j-1}) \rightarrow (u_i,v_{j-2}) \rightarrow (u_i,v) \rightarrow (u_{i+1},v) \rightarrow (u_{i+2},v) \rightarrow \dots \rightarrow (u_n,v)\).
Case 2.2. If \(P_{H_i} < f_t(H)\), then there is an insufficiency in the number of pebbles to place \(t\) pebbles on the vertex \((u_i,v)\). In such a case, with the remaining distribution of \(nf_t(H) – P_{H_i} – P_{H_n}\) pebbles there exist a copy of \(H\) say \(H_k\) with \(P_{H_k} \geq f_t(H)\) or there exist at least two copies of \(H\) say \(H_l\) and \(H_k\) with \(P_{H_l} \geq f_t(H)\) and \(P_{H_k} \geq f_t(H)\). Hence, the target is pebbled as in Case 2.1.
Case 3. Let us choose the target vertex as some \((u_i,v_j)\) and source vertex as \((u_k,v), 1 \leq k \leq n\). The desired pebbling distribution and the discussion is similar to that of Case 1.2.
Case 4. Let us choose the target vertex as \((u_i,v_j)\) and source vertex as \((u_l,v_k)\).
Case 4.1. If \(P_{H_l} \geq f_t(H)\) then at least \(t\) pebbles can be moved to \((u_l,v)\) through a sequence of pebbling move. Now excluding the pebbles considered on \(H_l\) there are \(nf_t(H) – P_{H_l}\) pebbles on the vertices of \(G\). In this case, with \(nf_t(H) – P_{H_l}\) pebbles it is possible to place at least \(2t\) pebbles on \((u_i,v)\). Furthermore, with \(f_t(H)\) pebbles on \(H_i\), \(t\) pebbles can be moved to the target \((u_i,v_j)\).
Case 4.2. Suppose there are zero pebbles on all the vertices of \(G \circ_v H\). In this case, reaching the target vertex becomes impossible with \(nf_t(H)\) pebbles. In order to pebble the target we need to move \(t\) pebbles from \((u_l,v_k)\) to \((u_l,v)\) and thereafter from \((u_l,v)\) to \((u_i,v)\) \(t\) pebbles are moved through a sequence of pebbling move. Finally, from the vertex \((u_i,v)\) it is possible to transmit \(t\) pebbles to \((u_i,v_j)\) through a sequence of pebbling move. Hence, with \(t2^D\) pebbles the target receives \(t\) pebbles where \(D = d_{G \circ_{v} H}\left\{(u_l,v_k), (u_i,v_j)\right\} = d_H(v_k,v) + d_G(u_l,u_i)+d_H(v,v_j)\). ◻
Theorem 4.3. For \(n,m \geq 2\), \[f_t(G \circ_v P_m) = \begin{cases} (t2^{m-1})^{2} f_t(G) & \text{if } d(v) = 1 ,\\ t2^D & \text{if } d(v) = 2 .\end{cases}\]
Proof. Consider a path on \(m\) vertices \(v_1, v_2, \dots, v_m\). Let \(G\) be a connected graph on \(n\) vertices \(u_1, u_2, \dots, u_n\). Choose any vertex \(v\) of \(P_m\) as the root vertex. We get two different graphs depending on \(d(v)\), the degree of the root vertex \(v\). See Figure 4 and Figure 5 for two possible cases of root vertex \(v\).
Case 1. When \(d(v) = 1\).
The proof of this case is same for either \(v = v_m\) or \(v_1\). Choose the target vertex as \((u_n,v_{m-1})\) and source vertex as \((u_1,v_{m-1})\) which are at maximum distance. With \(t2^{m-1}\) pebbles on \(H_1\) which is a path on \(m\) vertices it is possible to move \(t\) pebbles to \((u_1,v)\) after the pebbling move in \(H_1\). With \(f_t(G)\) pebbles distributed on the vertices of \((u_i,v), 1 \leq i \leq n\), at least \(t\) pebbles can be transferred to \((u_n,v)\) using a pebbling move sequence. In order to pebble the target vertex \((u_n,v_{m-1})\), at least \(t2^{m-1}\) pebbles are required on the \(n^{th}\) copy of \(H\). In this way with \((t2^{m-1})^{2} f_t(G)\) of pebbles, it is possible to move \(t\) pebbles to the target.
Case 2. When \(d(v)=2\).
If \(d(v)=2\), then the \(i^{th}\) copy of \(H\) for all \(i \in \left\{1, 2, \dots, n\right\}\) will have two distinct paths namely \(P_{A_i}\) and \(P_{B_i}\). Let us denote the paths as \(P_{A_i}=\left\{(u_i,v_1), (u_i,v_2), \dots, (u_i,v_k)\right\}\) and \(P_{B_i} = \left\{(u_i,w_1),(u_i,w_2), \dots, (u_i,w_l)\right\}\) such that \(l+k+1=m\).
Choose the target vertex as either \((u_n,v_{k})\) or \((u_n,w_{l})\) and the source vertex as either \((u_1,v_{k})\) or \((u_1,w_{l})\) which are at maximum distance. In order to pebble the target vertex \((u_n,v_{k})\), place \(t2^D\) pebbles on \((u_1,v_{k})\) where \(D = d_H(v_k,v)+d_G(u_1,u_n)+d_H(v,v_k)\). The target is pebbled through the pebbling sequence path \((u_1,v_k) \rightarrow (u_1,v_{k-1}) \rightarrow (u_1,v_1) \rightarrow (u_1,v) \rightarrow (u_2,v) \rightarrow (u_3,v) \rightarrow \dots \rightarrow (u_n,v) \rightarrow (u_n,v_1) \rightarrow (u_n,v_2) \rightarrow \dots \rightarrow (u_n,v_k)\). Similarly, to pebble the target vertex \((u_n,w_l)\) we require \(t2^D\) pebbles on \((u_1,w_l)\) where \(D = d_H(w_l,v)+d_G(u_1,u_n)+d_H(v,w_l)\). The corresponding pebbling sequence path is \((u_1,w_l) \rightarrow (u_1,w_{l-1}) \rightarrow (u_1,w_1) \rightarrow (u_1,v) \rightarrow (u_2,v) \rightarrow \dots \rightarrow (u_n,v) \rightarrow (u_n,w_1) \rightarrow \dots \rightarrow (u_n,w_l)\). ◻
Theorem 4.4. For \(n,m \geq 2\), \(f_t(K_n \circ_v H) = nf_t(H)\).
Proof. Consider a graph \(H\) of order \(m\) with root vertex \(v\). Let the \(t\)-pebbling number of the graph \(H\) be \(f_t(H)\). Assume the source vertex as some vertex \((u_i,v_k)\) and target vertex as some \((u_j,v_l)\) which are at maximum distance. Without loss of generality, assume that there are zero pebbles on the vertices of \(H_j\) otherwise the discussion is trivial. With \(f_t(H)\) pebbles on the vertices of \(H_i\), it is possible to move \(t\) pebbles to \((u_i,v)\). Similarly, it is evident that for each copy of \(H\) with a distribution of \(f_t(H)\) pebbles it is possible to move \(t\) pebbles to the vertices \((u_r,v)\), \(r \in \{1,2, \dots,j-1,j+1, \dots, n \}\).
Now consider the pebbles that were excluded from the \(j^{th}\) copy of \(H\). Place at least \((n-1)t\) pebbles on the vertices of \((u_r,v)\). It is to note that, there exists some vertex with at least \(2t\) pebbles which will trigger the pebbling move. Since \(G\) is a complete graph it is possible to place \(t\) pebbles on \((u_j,v)\). Further, with the remaining \(f_t(H)-(n-1)t\) pebbles on \(H_j\) it is possible to pebble the target vertex.
Suppose there are zero pebbles on the vertices of \(K_n \circ_v H\), then with \(nf_t(H)\) pebbles placed on \((u_i,v_k)\) it is possible to move \(t\) pebbles to the target \((u_j,v_l)\). Hence, \(f_t(K_n \circ_v H) = nf_t(H)\). ◻
Theorem 4.5. For \(n,m \geq 2\), \[f_t(G \circ_v K_{1,m}) = \begin{cases} 16tf_t(G) & \text{if } d(v) = 1 ,\\ n(1+m)t & \text{if } d(v) = m .\end{cases}\]
Proof. Let \(G\) be a connected graph on \(n\) vertices \(u_1, u_2, \dots, u_n\). The star graph \(K_{1,m}\) has a center vertex \(v_0\) with degree \(m\). In other words, the center vertex \(v_0\) has \(m\) adjacent vertices of degree 1 which are labeled as \(v_1, v_2, \dots, v_m\). These vertices are referred as leaf vertices. Depending on the root vertex we get two different graphs for \(G \circ_v K_{1, m}\). Let the source vertex be some vertex \((u_1,v_j)\) and target vertex \((u_{n-1},v_j)\), \(1 \leq j \leq m-1\).
Case 1. When \(d(v) = 1\).
In this case, let any vertex \(v_k\), \(k \in \left\{1, 2, \dots, m\right\}\) of \(K_{1, m}\) be the root vertex in \(G \circ_v K_{1, m}\). Let \((u_i,v_0)\) be a vertex in the \(i^{th}\) copy of \(K_{1,m}\) such that \(d(u_i,v_0)=m\) and \((u_i,v_0)\) is adjacent to \(m-1\) leaf vertices excluding the root vertex \(v\). At least \(4t\) pebbles are needed to pebble the target from any leaf vertex so that \(t\) pebbles can be placed on \((u_i,v)\). Further, using \(f_t(G)\) pebbles it is possible to move \(t\) pebbles to any vertex say \((u_{n-1},v)\) through a sequence of pebbling move. In order to pebble the target vertex, additional \(4t\) pebbles are required to be placed on the copy of \(H_n\). Thus, with \(4t\) pebbles one can move \(t\) pebbles to any leaf vertex \((u_{n-1},v_j)\), \(1 \leq j \leq m-1\). Hence, it is sufficient to have \(16tf_t(G)\) pebbles to pebble the target.
Case 2. When \(d(v) = m\).
In this case, the vertex \(v_0 \in K_{1, m}\) becomes the root vertex in \(G \circ_v K_{1,m}\). In every \(i^{th}\) copy of \(H\) there are \(m\) pendant vertices. With \(nmt\) pebbles on each copy of \(H\) it is possible to place at least \(t\) pebbles on each vertex \((u_i,v)\). By placing the remaining \(t\) pebbles on each \((u_i,v)\) it possible to move \(t\) pebbles to the target vertex through a sequence of pebbling move from \((u_i,v)\) to \((u_1,v)\). ◻
Theorem 4.6. Let \(G\) be a connected graph of order \(n\) and \(H\) a triangle-free graph. Then \(f_t(G \circ_v H) \leq n f_t(H)\).
Proof. Consider a distribution of \(nf_t(H)\) pebbles over the vertices of \(G \circ_v H\). Let the target vertex be \((u_1,v)\). Now consider \(f_t(H)\) pebbles on each copy of \(H\) in \(G \circ_v H\). By Theorem 3.3 the graph \(H_i\) satisfies \(2t\)-pebbling property which results in \(p(u_i,v) = 2t, 2 \leq i \leq n\). Thus, with \(2t\) pebbles on \((u_i,v), 2 \leq i \leq n\) it is possible to move \(t\) pebbles to the target vertex through a sequence a pebbling move along the path \((u_i,v) \rightarrow (u_{i+1},v) \rightarrow (u_{i+2},v) \rightarrow \dots \rightarrow (u_1,v)\) .
Next, choose the target vertex as \((u_i,v_j), 1 \leq i,j \leq n\). Assume that there are no pebbles on the vertices of \(H_i\), otherwise the solution is trivial. By Theorem 3.3, with \(f_t(H)\) pebbles on every copy of \(H\) it is possible to move \(2t\) pebbles to every root vertex of \(H\). Due to this condition, it is observed that \(t\) pebbles can be moved to \((u_i,v)\) through a sequence of pebbling moves. But still there are \(f_t(H)\) pebbles remaining on the vertices of \(G \circ_v H\) which was initially excluded. Now, using these additional pebbles it is possible to transmit \(t\) pebbles to the target vertex. ◻
Theorem 4.7.For any two connected graphs \(G\) and \(H\), \(G \circ _v H\) satisfies \(2t\)-pebbling property whenever \(H\) satisfies \(2t\)-pebbling property.
Proof. Let \(\left|V(G)\right| = n\). Now consider a distribution of \(p\geq 2(f_t(G \circ_v H)) -q +1\) pebbles, where \(q\) represents the number of occupied vertices. Without loss of generality choose any vertex of \(G \circ _v H\) as the target vertex. Fix \(r = (u_n,v)\) as the target vertex. We break down the possible configuration of pebbles by extracting only \(2f_t(H)-q+1\) pebbles to be distributed over the vertices of \(H\) and the remaining pebbles over the vertices of \((u_k,v),1 \leq k \leq n-1\). Assume that \(p(u_n,v_j) < f_t(H), 1 \leq j \leq n-1\), otherwise the solution is trivial. Since, \(H\) satisfies \(2t\)-pebbling property, \(p(u_k,v) = 2t,1 \leq k \leq n-1\). But this will allow only \(t\) pebbles to be placed on the target \(r\). To overcome the insufficiency of pebbles use the remaining \(2(f_t(G \circ _v H) – f_t(H))\) pebbles over the vertices of \((u_k,v), 1 \leq k \leq n-1\). It is evident to see that at least \(t\) pebbles can be placed on the target \(r\). Hence, \(p(r)=2t\). This proves that \(G \circ_v H\) satisfies \(2t\)-pebbling property whenever \(H\) satisfies \(2t\)-pebbling property. ◻
Single hop message transmission with considerable packet loss is studied with graph pebbling technique. One unit of packet loss is generalized using \(t\)-pebbling and \(2t\)-pebbling approach. In this paper, we have determined a lower bound for the \(t\)-pebbling number of triangle-free graphs and verified that all triangle-free graphs satisfy \(2t\)-pebbling property. We have also proposed a lower bound for \(t\)-pebbling number of rooted product of two graphs and the results have been derived for certain graphs like paths, complete graphs and star graphs. This paper introduces many generalized results which could be anticipated for further extensions of research findings. Our computational results on rooted product inspires some theoretical questions. Is the rooted product of any graph \(G\) and \(H\) satisfies the \(2t\)-pebbling property? Further, it will also be interesting to find any counter example which is not satisfying the bounds of rooted product.
The authors declare no conflict of interest.