Menu
Let \(G\) be a connected graph. A pebbling move is defined as taking two pebbles from one vertex and the placing one pebble to an adjacent vertex and throwing away the another pebble. A dominating set \(D\) of a graph \(G=(V,E)\) is a non-split dominating set if the induced graph \(\) is connected. The Non-split Domination Cover(NDC) pebbling number, \(\psi_{ns}(G)\), of a graph $G$ is the minimum of pebbles that must be placed on \(V(G)\) such that after a sequence of pebbling moves, the set of vertices with a pebble forms a non-split dominating set of \(G\), regardless of the initial configuration of pebbles. We discuss some basic results and determine \(\psi_{ns}\) for some families of standard graphs.
Lagarias and Saks were the first one to introduce the concept of pebbling and Chung [1] used the concept in pebbling to solve a number theoretic conjecture. Then many others followed suit including Glenn Hulbert who published a survey of pebbling variants [2]. The subject to graph pebbling has seen a massive growth after Hulbert’s survey. The past 30 years so many new variants in graph pebbling have been developed which can be applied to the filed of transportation, computer memory allocation, game theory and the installation of mobile towers.
Let us denote \(G'\)s vertex and edge sets as \(V (G)\) and \(E (G)\), respectively. Consider a graph with a fixed number of pebbles at each vertex. One pebble is thrown away and the other is placed on an adjacent vertex when two pebbles are removed from a vertex. This process is known as a pebble move. The pebbling number of a vertex \(v\) in a graph \(G\) is the smallest number \(\pi(G, v)\) that allows us to shift a pebble to \(v\) using a sequence of pebbling move, regardless of how these pebbles are located on G’s vertices. The pebbling number, \(\pi(G)\), of a graph \(G\) is the maximum of \(\pi(G, v)\) over all the vertices \(v\) of a graph. Considering the concept of cover pebbling [3] and non-split domination [4] we develop a new concept, called the non-split domination cover pebbling number of a graph, denoted by \(\psi_{ns}(G)\). In paper [3] “The cover pebbling number, \(\lambda(G)\), is defined as the minimum number of pebbles required such that given any initial configuration of at least \(\lambda(G)\) pebbles, it is possible to make a series of pebbling moves to place at least one pebble on every vertex of \(G\)” and in [4] The domination cover pebbling number, \(\gamma(G)\), is defined as “the minimum number of pebbles required so that any initial configuration of pebbles can be shifted by a sequence of pebbling moves so that the set of vertices that contain pebbles form a dominating set \(S\) of \(G\)“. Lourdusamy et al. [5] proposed the concept of covering cover pebbling number. The covering cover pebbling number of a graph of \(G\), \(\sigma(G)\), is the minimum number of pebbles required so that any initial configuration of pebbles can be transformed by a sequence of pebbling moves so that the set of vertices that contain pebbles form a covering set of \(G\). Kulli et al. introduced the non-split domination number in [4]. A dominating set \(D\) of a graph \(G=(V,E)\) is a non-split dominating set if the induced graph \(<V-D>\) is connected. The non-split domination number \(\gamma_{ns}(G)\) of \(G\) is the minimum cordinality of a non-split dominating set. We develop the concept of non-split domination cover pebbling deriving from concept of cover pebbling and non-split domination in graphs. Thus, we arrived the definition of the non-split domination cover(NDC) pebbling number, \(\psi_{ns}(G)\), of a graph \(G\) as the minimum of pebbles that must be placed on \(V(G)\) such that after a sequence of pebbling moves, the set of vertices with a pebble forms a non-split dominating set of \(G\), regardless of the initial configuration of pebbles. In this paper, we use the ’source vertex’ where all the pebbles are stocked or shared to move the pebbles to cover the non-split domination set. Source vertices can be one or more than one. From all the source vertices when we move the pebbles, we should cover all the vertices of non-split domination set. The notation \((x_{i}) \underrightarrow{t} (x_{l})\) refers taking off at least \(2t\) pebbles from \((x_{i})\) and placing at least \(t\) pebbles on \((x_{l})\) and the notation \((x_{i}) \underleftarrow{t} (x_{l})\) refers taking off at least \(2t\) pebbles from \((x_{l})\) and placing at least \(t\) pebbles on \((x_{i})\). We discuss the basic results and determine \(\psi_{ns}\) for complete graphs, path graphs, wheel graphs, cycle graphs, friendship graphs, comb graphs, banana tree and fire cracker tree.
For graph-theoretic terminologies, the reader can refer to [6, 7].
Theorem 1. [4]
The non-split domination number of a complete graph \(K_n\) is \(\gamma_{ns} (K_n)= 1\).
The non-split domination number of a Wheel graph is \(\gamma_{ns} (W_n)= 1\).
The non-split domination number of a path is \(\gamma_{ns} (P_n)= n-2\).
The non-split domination number of Cycle is \(\gamma_{ns}(C_n) = n-2\).
Theorem 2. [8] The domination cover pebbling number of the wheel graph is \(\psi(W_n)= n-2\).
Theorem 3. [3]The cover pebbling number of path \(P_n\) is \(\gamma(P_n)=2^{n}-1\).
Conjecture 1. For a simple connected graph \(G\), \(\psi(G) \leq \psi_{ns}(G) \le \sigma(G)\).
Theorem 4. The non-split domination cover pebbling number of a graph \(G\), \(\psi_{ns}(G)=1\) iff \(G\) is a complete graph.
Proof. The non-split domination number for a complete graph is 1 and hence by placing one pebble on any vertex, we are done. Conversely, if placing a pebble on any vertex produces a non-split domination cover solution, then it implies that the non-split domination number is 1 and hence the graph \(G\) is complete. ◻
Theorem 5. The non-split domination cover pebbling number of a wheel graph \(W_n\) is, \(\psi_{ns}(W_n)=n-2\)
Proof. Let \(V(W_n)=\{v_0,\ v_1,\ v_2, \ v_3,\cdots,\ v_{n-1}\}\) where \(v_0\) is called the hub of \(W_n\). Then \(E(W_n)=\{v_0v_i, v_jv_{j+1}, v_{n-1}v_1\}\) where \(1\leq i \leq n-1\) and \(1\leq \leq n-2\). Consider the nonsplit dominating set \(D= \{v_0\}\). Placing one pebble on each \(n-3\) consecutive outer vertices leaves a vertex of \(W_n\) undominated. If there are 2 pebbles on any vertex, shift it to the center. Thus, we cover \(D\). Similarly, if there is a pebble on \(v_0\), we can cover dominate \(D\). Thus, consider all distribution containing pebbled vertices that each contain a pebble. If there are \(n-2\) vertices having a pebble each, the 2 outer vertices of \(W_n\) are dominated since there are only 3 vertices in all \(W_n\) that do not have pebbles. Hence, \(\psi_{ns}(W_n)=n-2\). ◻
Theorem 6. The NDC pebbling number of path graphs is, \(\psi_{ns}(P_n)= 2^{n-1}+2^{n-3}-1\).
Proof. Let \(V(P_n)=\{v_1,\ v_2, \ v_3,\cdots,\ v_n\}\). Consider the non-split dominating set \(D= \{v_1,\ v_2,\ \cdots,\ v_{n-3},\ v_n\}\) or \(\{v_1,\ v_4,\ \cdots,\ v_n\}\). In both the non-split dominating set \(D\) there will be \((n-2)\) vertices. Then \(V(<V-D>)=\{v_{n-2},\ v_{n-1}\}\) or \(\{v_2,\ v_3\}\) and \(<V-D>\) is connected. Though we have many ways to construct the non-split dominating set, we consider these two because they require minimum number of pebbles to cover the non-split dominating sets.
Now we prove the necessary condition. We place all the pebbles either on \(v_1\) or \(v_n\). Without loss of generality, place \(2^{n-1}+2^{n-3}-2\) pebbles on \(v_1\). To cover \(v_n\) we need \(2^{n-1}\) pebbles. Then with the remaining \(2^{n-3}-2\) pebbles, it is not possible to cover \(v_1\). Hence, \(\psi_{ns}(P_n)\geq 2^{n-1}+2^{n-3}-1\).
Now we prove the sufficient condition. Consider a configuration \(C\) with \(2^{n-1}+2^{n-3}-1\) pebbles on the vertices of \(P_n\).
If we place all the pebbles on \(v_n\), to cover \(v_1\) we need \(2^{n-1}\) pebbles. The set \(\{v_2, \ v_3\}\) is connected but not a subset of \(D\). Next we need to place a pebble each on \(v_4,\ v_5,\ \cdots,\ v_n\). Now using the remaining \(2^{n-3}-1\) pebbles we cover the remaining vertices in the non-split dominating set \(D\). We can shift pebbles as follows: \(v_n\ \underrightarrow{2^{n-4}-1} \ \ v_{n-1}\ \underrightarrow{2^{n-)}-1} \ \cdots, \underrightarrow{3} \ v_{5}\ \underrightarrow{1}\ \ v_4\) using \(2^{n-)}+2^{n-)}+2^{n-6}+\cdots + 2^2+2^1+1=2^{n-3}-1\) pebbles. Hence with the configuration \(C\) we cover all the vertices in \(D\).
Let us place \(2^{n-1}+2^{n-3}-1\) pebbles on \(v_4\). By Theorem 3, we can cover a path of length \({n-3}\) from \(v_4\) to \(v_n\) using \(2^{n-3}-1\) pebbles. Hence, we are left with \(2^{n-1}\) pebbles. To cover \(v_1\) we require only 8 pebbles. Thus, with a Configuration of at most \(2^{(n-3)}+ 7\) pebbles we cover the vertices of \(D\). By symmetry, the proof follows for the source vertex \(v_{n-3}\).
Consider \(V(<V-D>) = \{v_2,\ v_3\}\). When \(n\) is even either \(v_{\lfloor\frac{n}{2}\rfloor}\) or \(v_{\lfloor\frac{n}{2}\rfloor+1}\) can be taken as a source vertex. If \(v_{\lfloor\frac{n}{2}\rfloor}\) is the source vertex, then to the right of \(v_{\lfloor\frac{n}{2}\rfloor}\) we have to cover the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor+1\) and to the left of \(v_{\lfloor\frac{n}{2}\rfloor}\) we have to cover the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor-3\) excluding the vertex \(v_1\) and the vertices in the graph \(<V-D>\). By Theorem 3 we require at most \(2^{\lfloor\frac{n}{2}\rfloor+1}-1+ 2^{\lfloor\frac{n}{2}\rfloor-3}-2\) pebbles to cover the vertices in the above path of length \(\lfloor\frac{n}{2}\rfloor+1\) and \(\lfloor\frac{n}{2}\rfloor-3\). Now to cover \(v_1\) we need \(2^{\lfloor\frac{n}{2}\rfloor-1}\) pebbles. The number of pebbles used in this process is \(2^{\lfloor\frac{n}{2}\rfloor+1}-1+ 2^{\lfloor\frac{n}{2}\rfloor-3}-2+ 2^{\lfloor\frac{n}{2}\rfloor-1} < 2^{n-1}+2^{n-3}-1\) pebbles.
If \(v_{\lfloor\frac{n}{2}\rfloor+1}\) is the source vertex, then to the right of \(v_{\lfloor\frac{n}{2}\rfloor+1}\) we have to cover the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor\) and to the left of \(v_{\lfloor\frac{n}{2}\rfloor}\) we have to cover the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor-2\) excluding the vertex \(v_1\) and the vertices in the graph \(<V-D>\). By Theorem 3 we require at most \(2^{\lfloor\frac{n}{2}\rfloor}-1+ 2^{\lfloor\frac{n}{2}\rfloor-2}-2\) pebbles to cover the vertices in the above path of length \(\lfloor\frac{n}{2}\rfloor\) and \(\lfloor\frac{n}{2}\rfloor-2\). Now to cover \(v_1\) we need \(2^{\lfloor\frac{n}{2}\rfloor}\) pebbles. The number of pebbles used in this process is \(2^{\lfloor\frac{n}{2}\rfloor}-1+ 2^{\lfloor\frac{n}{2}\rfloor-2}-2+ 2^{\lfloor\frac{n}{2}\rfloor} < 2^{n-1}+2^{(n-3)}-1\) pebbles.
If \(v_{k} \ (k<\lfloor\frac{n}{2}\rfloor\ or \ k>\lfloor\frac{n}{2}\rfloor+1)\) is the source vertex, then to the right of \(v_{k}\) we have to cover the the vertices in a path of length \(n-k\) and to the left of \(v_{k}\) we have to cover the vertices in a path of length \(k-3\) excluding the vertex \(v_1\) and the vertices in the graph \(<V-D>\). By Theorem 3 we require at most \(2^{n-k}-1+ 2^{k-3}-2\) pebbles to cover the vertices in the above path of length \(n-k\) and \(k-3\). Now to cover \(v_1\) we need \(2^{k}\) pebbles. The number of pebbles used in this process is \(2^{n-k}-1+ 2^{k-3}-2+ 2^{k} < 2^{n-1}+2^{n-3}-1\) pebbles.
When \(n\) is odd \(v_{\lfloor\frac{n}{2}\rfloor+1}\) can be taken as a source vertex. If \(v_{\lfloor\frac{n}{2}\rfloor+1}\) is the source vertex, then to the right of \(v_{\lfloor\frac{n}{2}\rfloor+1}\) we have to cover the the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor\) and to the left of \(v_{\lfloor\frac{n}{2}\rfloor+1}\) we have to cover the vertices in a path of length \(\lfloor\frac{n}{2}\rfloor-2\) excluding the vertex \(v_1\) and the vertices in the graph \(<V-D>\). By Theorem 3 we require at most \(2^{\lfloor\frac{n}{2}\rfloor}-1+ 2^{\lfloor\frac{n}{2}\rfloor-2}-2\) pebbles to cover the vertices in the above path of length \(\lfloor\frac{n}{2}\rfloor\) and \(\lfloor\frac{n}{2}\rfloor-2\). Now to cover \(v_1\) we need \(2^{\lfloor\frac{n}{2}\rfloor}\) pebbles. The number of pebbles used in this process is \(2^{\lfloor\frac{n}{2}\rfloor}-1+ 2^{\lfloor\frac{n}{2}\rfloor-2}-2+ 2^{\lfloor\frac{n}{2}\rfloor} < 2^{n-1}+2^{n-3}-1\) pebbles.
If \(v_{k} \ (k<\lfloor\frac{n}{2}\rfloor+1\ or \ k>\lfloor\frac{n}{2}\rfloor+1)\) is the source vertex, then to the right of \(v_{k}\) we have to cover the the vertices in a path of length \(n-k\) and to the left of \(v_{k}\) we have to cover the vertices in a path of length \(k-3\) excluding the vertex \(v_1\) and the vertices in the graph \(<V-D>\). By Theorem 3 we require at most \(2^{n-k}-1+ 2^{k-3}-2\) pebbles to cover the vertices in the above path of length \(n-k\) and \(k-3\). Now to cover \(v_1\) we need \(2^{k}\) pebbles. The number of pebbles used in this process is \(2^{n-k}-1+ 2^{k-3}-2+ 2^{k} < 2^{n-1}+2^{n-3}-1\). Hence, \(\psi_{ns}(P_n)= 2^{n-1}+2^{n-3}-1\).
◻
Theorem 7. The NDC pebbling number of cycle graphs is, \[\psi_{ns}(C_n)= \begin{cases} 2^{\left\lfloor \frac{n-1}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -2 & \ \ n \ {is\ even},\\ 2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-3 & \ \ n \ {is \ odd}. \end{cases}\]
Proof. Let \(V(C_n)= \{v_1,\ v_2,\ v_3, \ \cdots, \ v_n\}.\) When \(n\) is even, the non-split dominating set \(D_1=\{v_1, \ v_2,\ \cdots, \ v_{\left\lfloor \frac{n}{2}\right\rfloor-1}, \ v_{\left\lfloor \frac{n}{2}\right\rfloor+2}, \ v_{\left\lfloor \frac{n}{2}\right\rfloor+3},\ \cdots, \ v_{n-1}, \ v_n\}\). When \(n\) is odd, the non-split dominating set is \(D_2=\{v_1,\ v_2,\ \cdots, v_{\left\lfloor \frac{n}{2}\right\rfloor}, \ v_{\left\lfloor \frac{n}{2}\right\rfloor+3}, \ v_{\left\lfloor \frac{n}{2}\right\rfloor+4},\ \cdots,\ v_{n-1},\ v_n\}\).
We observe that \(V(<V-D_1>)=\{v_{\left\lfloor \frac{n}{2}\right\rfloor},\ v_{\left\lfloor \frac{n}{2}\right\rfloor+1}\}\) and \(V(<V-D_2>)=\{v_{\left\lfloor \frac{n}{2}\right\rfloor+1}, v_{\left\lfloor \frac{n}{2}\right\rfloor+2}\}\). Notice that there exist two paths from \(v_1\) to \(v_{\left\lfloor \frac{n}{2}\right\rfloor-1}\) and from \(v_1\) to \(v_{\left\lfloor \frac{n}{2}\right\rfloor+2}\). Let them be \(P_{\left\lfloor \frac{n-1}{2}\right\rfloor}\) and \(P_{\left\lfloor \frac{n}{2}\right\rfloor}\), when \(n\) is even. When \(n\) is odd, there exist two paths from \(v_1\) to \(v_{\left\lfloor \frac{n}{2}\right\rfloor}\) and from \(v_1\) to \(v_{\left\lfloor \frac{n}{2}\right\rfloor+3}\). Let them be \(P_{\left\lfloor \frac{n}{2}\right\rfloor}\) and \(P_{\left\lfloor \frac{n}{2}\right\rfloor}\) respectively.
Placing \(2^{\left\lfloor \frac{n-1}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -3\) pebbles on the source vertex \(v_1\) we cannot put one pebble each on all the vertices of \(D_1\). Hence, \(\psi_{ns}(C_n)\geq 2^{\left\lfloor \frac{n-1}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -2\).
Now we prove the sufficient condition. Consider a configuration of \(2^{\left\lfloor \frac{n-1}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -2\) pebbles. Let the source vertex be \(v_1\). Using Theorem 3, we can cover the non-split dominating set \(D_1\). Since \(D_1\) has two paths of length \((\left\lfloor \frac{n}{2}\right\rfloor-2)\) and \((\left\lfloor \frac{n}{2}\right\rfloor-1)\), using \(2^{\left\lfloor \frac{n}{2}\right\rfloor-1}-1\) pebbles we can cover all the vertices of the path of length \(\left\lfloor \frac{n}{2}\right\rfloor-2\) and using \(2^{\left\lfloor \frac{n}{2}\right\rfloor}-2\) pebbles we cover all the vertices of the path of length \(\left\lfloor \frac{n}{2}\right\rfloor-1\). The total number of pebbles used to cover the vertices of \(D_1\) is \(2^{\left\lfloor \frac{n}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -2\).
If we distribute all the pebbles on the vertices of \(<V-D_1>\), we need at least \(2^{\left\lfloor \frac{n}{2}\right\rfloor}-2\) pebbles whose pebbling process will result in another non-split dominating set \(D\). The new \(<V-D>\) is also connected. Similarly, we can prove the result for other source vertices. Hence, \(\psi_{ns}(C_n)= 2^{\left\lfloor \frac{n-1}{2}\right\rfloor}-1 +2^{\left\lfloor \frac{n}{2}\right\rfloor} -2\).
Placing \(2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-4\) pebbles on the source vertex \(v_1\) we cannot put one pebble each on all the vertices of \(D_2\). Hence, \(\psi_{ns}(C_n)\geq 2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-3\).
Now we prove the sufficient condition. Consider a configuration \(C\) with \(2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-3\) pebbles on the vertices of \(C_n\). Let the source vertex be \(v_1\). Using Theorem 3 of the cover pebbling number of path, we can cover the non-split dominating set \(D_2\). Note that \(D_2\) has two paths of equal length \((\left\lfloor \frac{n}{2}\right\rfloor-1)\). Using \(2^{\left\lfloor \frac{n}{2}\right\rfloor}-1\) pebbles we can cover all the vertices of the path of length \(\left\lfloor \frac{n}{2}\right\rfloor-1\) and \(2^{\left\lfloor \frac{n}{2}\right\rfloor}-2\) pebbles we cover all the vertices of path of length \(\left\lfloor \frac{n}{2}\right\rfloor-1\). The total number of pebbles used to cover the \(D_2\) is \(2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-3\).
If we distribute all the pebbles on the vertices of \(<V-D_2>\), we need at least \(2^{\left\lfloor \frac{n}{2}\right\rfloor-1}-1 + 2^{\left\lfloor \frac{n}{2}\right\rfloor}-1\) pebbles to form another non-split dominating set \(D\). The new \(<V-D>\) is also connected. Similarly, we can prove for the rest of the vertices assuming as source vertices. Hence, \(\psi_{ns}(C_n)= 2^{\left\lfloor \frac{n}{2}\right\rfloor+1}-3\).
◻
Theorem 8. The NDC pebbling number for a friendship graph \(Fr_n\) is given by, \(\psi_{ns}(Fr_n)=4(n-1)+1\).
Proof. Let the hub vertex be denoted by \(v_0\) and the vertices which are adjacent to \(v_0\) be denoted by \(v_1, v_2,…,v_{2n}\)(clockwise manner).
Consider the non-split dominating set \(D_1=\{v_1, \ v_3,\ \cdots, \ v_{2n-1}\}\) or \(D_2=\{v_2,\ v_4, \cdots, \ v_{2n}\}\). Clearly the induced sub-graph \(<V-D_1>\) and \(<V-D_2>\) are connected. Without loss of generality, let us consider the non-split dominating set \(D_1\). Consider the configuration of \(4(n-1)\) pebbles on the vertex of \(v_1\). Shifting \(2(n-1)\) pebbles to the hub vertex we could cover maximum \(n-1\) vertices of the non-split domination set. We are left with a vertex \(v_1\) without a cover. Hence, \(\psi_{ns}(Fr_n)\geq 4(n-1)+1\).
Now we prove the sufficient condition by distributing \(4(n-1)+1\) pebbles on the vertices of \(Fr_n\), that is, Hub vertex has minimum of \(2(n-1)+2\) pebbles on it.
Using \(2(n-1)\) pebbles we can cover dominate \(n-1\) vertices of the non-split dominating set \(D_1\). Further, using 2 pebbles we could cover the remaining vertex. Suppose, the hub vertex has less than \(2(n-1)+2\). Let it be \(p\) pebbles. Then using \(p\) pebbles we could cover \(\lfloor\frac{p}{2}\rfloor\) vertices. Assume that \(p^{'}\) is the number of vertices receiving pebbles in this way. Keep a maximum of two pebbles on each vertex and transfer the remaining to the hub vertex. Thus, Thus using at least \(2n\) pebbles we can cover dominate \(D_1\). Hence, \(\psi_{ns}(Fr_n)= 4(n-1)+1\). ◻
Theorem 9. The NDC pebbling number of a comb graph \(P_n\odot K_1\) is given by, \(\psi_{ns}(P_n\odot K_1)=\sum\limits_{i=0}^{n+1} 2^i-6\).
Proof. Let the vertices of the path \(P_n\odot K_1\) be denoted by \(v_1, v_2,…,v_n\) and the pendant vertices attached to each vertex \(v_i, 1\leq i \leq n\) on the path be \(u_i, 1\leq i \leq n\).
Consider the non-split dominating set \(D=\{u_1, u_2,\cdots, \ u_n\}\). Clearly, \(<V-D>\) is connected. Consider the configuration of \(\sum\limits_{i=0}^{n+1} 2^i-7\) pebbles placed on the vertex \(u_1\). Then, a minimum of \(1+2^3+2^4+\cdots+2^{n-1}+2^{n}+2^{n+1}\) pebbles are required in order to produce a non-split dominating set cover. But we lack one pebble to cover \(u_1\). Therefore, \(\psi_{ns}(P_n\odot K_1)\geq \sum\limits_{i=0}^{n+1} 2^i-6\).
Without loss of generality, let the source vertex be \(v_1\). To cover the vertex \(u_1\) we require 2 pebbles. Then, to cover the remaining vertices of \(\{D-{u_1}\}\) we need \(\sum\limits_{i=0}^{n} 2^i-3\) pebbles. Thus, the total number of pebbles used to cover the vertices of the non-split dominating set is \(\sum\limits_{i=0}^{n} 2^i-1\le \sum\limits_{i=0}^{n+1} 2^i-6\). By symmetry, we can prove when \(v_n\) is the source vertex.
Let \(v_k\) be the source vertex. To cover the adjacent vertex \(u_k\) we need 2 pebbles. Now to cover the remaining vertices \(u_{k-1}, u_{k-2},\cdots, u_2, u_1, u_{k+1},\cdots, u_{n-1},u_n\) of \(D\) we need \(\sum\limits_{i=1}^{k} 2^i + \sum\limits_{i=1}^{n-(k-1)} 2^i\) pebbles, which is less than the total number of available pebbles.
Let \(u_k\) be the source vertex. To cover the vertex \(u_k\) we need 1 pebble. Now to cover the remaining vertices \(u_{k-1}, u_{k-2},\cdots, u_2, u_1, u_{k+1},\cdots, u_{n-1},u_n\) of \(D\) we need \(\sum\limits_{i=1}^{k+1} 2^i + \sum\limits_{i=1}^{n-(k-2)} 2^i +1\le\sum\limits_{i=0}^{n+1} 2^i-6\) pebbles. Hence, \(\psi_{ns}(P_n\odot K_1)= \sum\limits_{i=0}^{n+1} 2^i-6.\)
◻
Theorem 10. The NDC pebbling number for Banana tree \(B_{n,k}\) is, \(\psi_{ns}(B_{n,k})=64(n-1)(k-2)+32(n-1)+4(k-2)+3\).
Proof. Let \(v_0\) be the vertex that joins all the \(k\)– star graphs. Let \(V(B_{n,k})=\{v_0,\ a_1^{j}, \ a_2^{j},\ \cdots,\ a_{k-1}^{j}, a_0^{j}\}\), where \(j=\{1,\ 2,\ 3,\ 4, \cdots, \ n\}\) and \(E(B_{n,k})=\{v_0a_{k-1}^{j}, a_0^{j}a_i^{j}\}\), where \(j=\{1,\ 2,\ 3,\ 4, \cdots, \ n\}\) and \(1=\{1,\ 2,\ 3,\ 4, \cdots, \ k-1\}\). Let the non-split dominating set \(D=\{v_0,\ a_1^{j}, \ a_2^{j},\ \cdots,\ a_{k-2}^{j}, a_0^{j}, a_{k-1}^1\}\), where \(j=\{1,\ 2,\ 3,\ 4, \cdots, \ n\}\). Clearly, the induced sub-graph \(<V-D>\) is connected.
Consider the distribution of \(64(n-1)(k-2)+32(n-1)+4(k-2)+2\) pebbles on any one of the pendant vertices. Let it be \(a_1^1\). Then we could cover all the vertices of the dominating set \(D\) except one vertex. Hence, \(\psi_{ns}(B_{n,k})\geq 64(n-1)(k-2)+32(n-1)+4(k-2)+3\).
Now consider distributing \(64(n-1)(k-2)+32(n-1)+4(k-2)+3\) pebbles on the vertices of \((B_{n,k})\).
There are \(n\) copies of \((k-2)\) star graph pendant vertices at a distance of 3 from \(v_0\) and \(n\) copies of the hub vertex of the \(k\)-star at a distance of 2. Thus, using \(8n(k-2)+4n\) pebbles, we could cover all the vertices of \(D\) except \(a_{k-1}^1\) which requires further 2 pebbles. Hence, using \(8n(k-2)+4n+2\) pebbles, we can dominate the set \(D\).
Without loss of generality, let \(a_0^1\) be the source vertex. To cover the dominating set of vertices that are adjacent to \(a_0^1\) we require \(2(k-1)\) pebbles. The rest of the vertices are at distances of 5 and 4. There are \((n-1)\) copies of \((k-2)\) star graph of pendant vertices is at a distance of 5 and \(n-1\) copies of the hub vertex of the star graph are at a distance of 4. Thus, using \(32(n-1)(k-2)+ 16(n-1)+2(k-1)\) pebbles, we can cover the non-split dominating set \(D\). Hence, \(\psi_{ns}(B_{n,k})= 64(n-1)(k-2)+32(n-1)+4(k-2)+3\).
◻
Theorem 11. The NDC pebbling number for \(F_{n,k}\)– fire cracker tree is, \(\psi_{ns}(F_{n,k})=4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\).
Proof. Let \(V(F_{n,k})=\{a_i, b_i, c_{ij} | i=1,2,\cdots,n,\ j=1,2,\cdots, k-2\} \ and \ E(F_{n,k})=\{a_ia_{i+1}|\ i=1,2,\cdots,n-1\}\cup \{a_ib_i,\ b_ic_{ij}\ | i=1,2,\cdots,n; \ j=1,2,\cdots, k-2\}\). Consider the non-split dominating set \(D=\{b_i, c_{ij}\ | i=1,2,\cdots,n; j=1,2,\cdots,\ k-2\}\). Clearly, \(<V-D>\) is connected.
Consider the distribution of placing \(4(k-3)+2+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles on a pendant vertex of the first \(k\) star graph of the \((F_{n,k})\). Then, we require a minimum of \(16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles to cover vertices of the non-split dominating set in \((n-1)\) k-star graphs. And the vertices in the first \((k-1)\) star graph are not covered. There are \(k-3\) vertices at a distance 2 and one vertex at a distance one in the first \(k-1\) star graph. Hence, we require further \(4(k-3)+3\) pebbles. But the number of pebbles remaining is \(4(k-3)+2\). Thus, \(\psi_{ns}(F_{n,k}\geq 4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\).
Now we prove the sufficient condition. Consider a configuration of \(4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles.
Without loss of generality, consider \(b_1\) be the source vertex. Let us place \(4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles on \(b_1\). Since there are \(k-2\) vertices of the non-split dominating set that are adjacent to \(b_1\), we need \(2(k-2)\) pebbles to cover them and one more pebble needed to cover \(b_1\). Now we are left with vertices in the \((n-1)\) parts of \((k-1)\) star graphs that are to be covered. To cover all those vertices we require \(8(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+4\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles. Thus, the total number of pebbles used to cover the vertices of the non-split dominating set is \(2(k-2)+1+8(k-2)+ \left(\sum\limits_{i=1}^{n-1}2^i\right)+4\left(\sum\limits_{i=1}^{n-1}2^i\right)\le 4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\). By symmetry, we can prove this for the source vertex \(b_n\).
Let us place \(4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles on \(b_s\). Since there are \(k-2\) vertices of the non-split dominating set that are adjacent to \(b_s\), we need \(2(k-2)\) pebbles to cover them and one more pebble to cover \(b_s\). Now we are left with the vertices that are not covered in the \(n-1\) parts of \((k-1)\) star graphs. To cover all those vertices we require \(8(k-2) \left(\sum\limits_{i=1}^{n-s}2^i\right)+4\left(\sum\limits_{i=1}^{n-s}2^i\right)+ 8(k-2) \left(\sum\limits_{i=1}^{s-1}2^i\right)+4\left(\sum\limits_{i=1}^{s-1}2^i\right)\) pebbles. Thus, the total number of pebbles used to cover the vertices of non-split dominating set is \(2(k-2)+1+8(k-2)+ 8(k-2) \left(\sum\limits_{i=1}^{n-s}2^i\right)+4\left(\sum\limits_{i=1}^{n-s}2^i\right)+ 8(k-2) \left(\sum\limits_{i=1}^{s-1}2^i\right)+4\left(\sum\limits_{i=1}^{s-1}2^i\right)\le 4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\).
Without loss of generality, consider \(a_1\) the source vertex. Let us place \(4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles on \(a_1\). Since there are \(k-2\) vertices of the non-split dominating set that are at distance 2 and one vertex that is adjacent to \(a_1\), we need \(4(k-2)+2\) pebbles to cover them. Now we are left with the vertices that are not covered in the \(n-1\) parts of \((k-1)\) star graphs. To cover all those vertices, we require \(4(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+2\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles. Thus, the total number of pebbles used to cover the vertices of the non-split dominating set is \(4(k-2)+2+4(k-2)+ \left(\sum\limits_{i=1}^{n-1}2^i\right)+2\left(\sum\limits_{i=1}^{n-1}2^i\right)\le 4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\). By symmetry, we can prove the result for the source vertex \(a_n\).
Let us place \(4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\) pebbles on \(a_s\). Since there are \(k-2\) vertices of the non-split dominating set that are at distance 2 and one vertex that is adjacent to \(a_s\), we need \(4(k-2)+2\) pebbles to cover them. Now we are left with vertices that are not covered in the \(n-1\) parts of the \((k-1)\) star graphs. To cover all those vertices, we require \(4(k-2) \left(\sum\limits_{i=1}^{n-s}2^i\right)+2\left(\sum\limits_{i=1}^{n-s}2^i\right)+ 4(k-2) \left(\sum\limits_{i=1}^{s-1}2^i\right)+2\left(\sum\limits_{i=1}^{s-1}2^i\right)\) pebbles. Thus, the total number of pebbles used to cover the vertices of non-split dominating set is \(4(k-2)+2+4(k-2)+ 8(k-2) \left(\sum\limits_{i=1}^{n-s}2^i\right)+2\left(\sum\limits_{i=1}^{n-s}2^i\right)+ 4(k-2) \left(\sum\limits_{i=1}^{s-1}2^i\right)+2\left(\sum\limits_{i=1}^{s-1}2^i\right)\le 4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\). Hence, \(\psi_{ns}(F_{n,k}=4(k-3)+3+16(k-2) \left(\sum\limits_{i=1}^{n-1}2^i\right)+8\left(\sum\limits_{i=1}^{n-1}2^i\right)\).
◻
In this paper, we introduced the graph invariant, namely, the ‘non-split domination cover pebbling number’. Some basic results are discussed. Also, the NDC pebbling numbers for certain families of graphs, such as the complete graph, wheel graph, path, cycle, friendship graph, comb graph, banana tree, and \((F_{n,k})\)– fire cracker tree, are determined. Finding the NDC pebbling numbers for other families of graphs is still open.
The authors thank the reviewers for the useful commends which enhanced the quality of the paper.