Menu
The hub cover pebbling number, \(h^{*}(G)\), of a graph $G$, is the least non-negative integer such that from all distributions of \(h^{*}(G)\) pebbles over the vertices of \(G\), it is possible to place at least one pebble each on every vertex of a set of vertices of a hub set for \(G\) using a sequence of pebbling move operations, each pebbling move operation removes two pebbles from a vertex and places one pebble on an adjacent vertex. Here we compute the hub cover pebbling number for wheel related graphs.
Pebbling was introduced in the field of graph theory by Chung [1]. Hulbert published details of graph pebbling in his survey paper [2]. At this stage there are many papers in this area contributed by many authors. Over the vertices of a graph \(G\) we distribute non negative number of pebbles. So a distribution of pebbles is a function from \(V (G)\) to \(N \cup \{0\}\). Here we consider simple connected graphs for our discussion. All basic concepts in graph are taken from the book entitled Graph Theory by Harary [3]. A pebbling move operation removes two pebbles from a vertex and the places one pebble on an adjacent vertex. For pebbling related concepts the readers can refer [1].
In cover pebbling it is require to put at least one pebble on every vertex of the vertex cover at the end of the pebbling move operation. The least number of pebbles having the property that from all distributions of \(\gamma(G)\) pebbles, it is possible to move a pebble to every vertex simultaneously using a sequence of pebbling moves is called the cover pebbling number. In [4] Crull et al., studied the cover pebbling number for complete graphs, paths and trees. Covering cover pebbling number [5] and domination cover pebbling number [6] are few other variations which come from the definition of cover pebbling. We introduce a new variation in the next section, named as ‘Hub cover pebbling number’, by combining the two concepts hub set and cover pebbling number, like they did in [5] and [6].
A hub set in a graph \(G\) is a set \(U\) of vertices in \(G\) such that any two vertices outside \(U\) are connected by a path whose internal vertices lie in \(U\). It was introduced by Walsh [7]. Adjacent vertices are joined by a path with no internal vertices, so the condition holds vacuously for them. The hub number of \(G\), denoted \(h(G)\), is the minimum size of a hub set in \(G\). Placing transmitters at the vertices of a hub set would facilitate communication among all vertices outside the set; Hence we seek a small hub set from which we introduce hub cover pebbling number (HCPN) of a graph \(G\).
Definition 1. The hub cover pebbling number, \(h^{*}(G)\), of a graph \(G\), is the least non-negative integer such that from all distributions of \(h^{*}(G)\) pebbles over the vertices of \(G\), it is possible to place at least one pebble each on every vertex of a set of vertices of a hub set for \(G\) using a sequence of pebbling move operations, each pebbling move operation removes two pebbles from a vertex and places one pebble on an adjacent vertex.
Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) and size \(m_{1}\) and \(m_{2}\) respectively. The Union of \(G_{1}\) and \(G_{2}\) is the graph denoted by \(G_{1} \cup G_{2}\) [3] having the vertex set \(V_{1}\cup V_{2}\) and the edge set \(E_{1} \cup E_{2}\). The join \(G_{1} + G_{2}\) of \(G_{1}\) and \(G_{2}\) is the graph obtained from \(G_{1} \cup G_{2}\) by joining each vertex of \(G_{1}\) with every vertex of \(G_{2}\) by an edge.
Definition 2. [8] The fan graph \(F_{n}\) for \(n \geq 4\) is defined as the join of \(K_{1}\) and \(P_{n-1}\), a path graph on \(n-1\) vertices.
Definition 3. [8] The wheel graph \(W_{n} = K_{1} + C_{n-1}\) is a graph where the vertex of degree \(n-1\) is called the central vertex and all other vertices on the cycle graph \(C_{n-1}\) are called rim vertices.
Definition 4. [8] The helm graph \(H_{n}\) is the graph obtained from a wheel \(W_{n}\) by attaching pendant edge to each rim vertex of the wheel graph.
Definition 5. [8] The flower \(Fl_{n}\) is the graph obtained from a helm \(H_{n}\) by joining each pendant vertex to the central vertex of the helm graph.
Definition 6. [8] The friendship graph \(FR_{n}\) is a collection of \(n\) triangles, all having a common vertex.
Remark 1. \(p(v)\) denotes the number of pebbles on the vertex \(v\) of \(G\) and \(p(G)\) denotes the total number of pebbles placed on the vertices of the graph \(G\). In a distribution of pebbles over the vertices of a graph \(G\), if \(p(v) \geq 1\) then the vertex \(v\) is called occupied vertex. Otherwise \(v\) is an unoccupied vertex.
Theorem 1. For a fan graph \(F_{n}\) \((n \geq 4)\), \(h^{*}(F_{n}) = n-3\).
Proof. Consider the following labeling for \(F_{n}\) (\(n \geq 4\)): label the vertices of \(P_{n-1}\) as \(a_{1},a_{2}, \dots, a_{n-1}\), and label the vertex of \(K_{1}\) as \(a_{n}\).
For \(F_{4}\), if we place one pebble on any vertex that would suffice to form a hub set and hence \(h^{*}(F_{4}) = 1\). Assume that \(n \geq 5\).
Consider the distribution: \(p(a_{i}) = 1\) for \(1 \leq i \leq n-4\) and \(p(a_{j}) = 0\) for all \(j \neq i\). Let \(S = \{a_{i} : 1 \leq i \leq n-4\}\). We can not find a path between the vertices \(a_{n-3}\) and \(a_{n-1}\) such that every internal vertex is a member of \(S\) and hence \(S\) is not a hub set for \(F_{n}\). Thus \(h^{*}(F_{n}) \geq n-3\).
Let \(p(F_{n}) = n-3\). If \(p(a_{n}) \geq 1\) then for any two unoccupied vertices \(a_{k}\) and \(a_{l}\), we can find the path \(a_{k}a_{n}a_{l}\). Thus \(\{a_{n}\}\) forms a hub set for \(F_{n}\). If \(p(a_{i}) \geq 2\) for some \(i\) where \(1 \leq i \leq n-1\) then we move a pebble to \(a_{n}\) and then for any two unoccupied vertices \(a_{k}\) and \(a_{l}\), we can find the path \(a_{k}a_{n}a_{l}\) as \(\{a_{n}\}\) forms a hub set for \(F_{n}\). So \(p(a_{n}) = 0\) and \(p(a_{i}) \leq 1\) for all \(1 \leq i \leq n-1\). Since \(p(F_{n}) = n-3\) and \(p(a_{n}) = 0\), we have two more unoccupied vertices \(a_{k}\) and \(a_{l}\) where \(k < l\). Let \(T = V(F_{n})-\{a_{k},a_{l},a_{n}\}\). As both \(a_{k}\) and \(a_{l}\) are adjacent to \(a_{n}\), it is enough to find a path between \(a_{k}\) and \(a_{l}\) such that every internal vertex is a member of \(T\). If \(a_{k}\) and \(a_{l}\) are adjacent then we are done. Otherwise, there exists a path \(a_{k}a_{k+1} \dots a_{l-1}a_{l}\) and hence \(T\) is a hub set of \(F_{n}\). Thus \(h^{*}(F_{n}) \leq n-3\). ◻
Theorem 2. For a wheel graph \(W_{n}\) \((n \geq 5)\), \(h^{*}(W_{n}) = n-4\).
Proof. For \(W_{5}\), if we place one pebble on any vertex that would suffice to form a hub set and hence \(h^{*}(W_{5}) = 1\). Assume that \(n \geq 6\).
Consider the distribution: \(p(a_{i}) = 1\) for \(1 \leq i \leq n-5\) and \(p(a_{j}) = 0\) for all \(j \neq i\). Let \(S = \{a_{i} : 1 \leq i \leq n-5\}\). We can not find a path between the vertices \(a_{n-3}\) and \(a_{n-1}\) such that every internal vertex is a member of \(S\) and hence \(S\) is not a hub set for \(W_{n}\). Thus \(h^{*}(W_{n}) \geq n-4\).
Let \(p(W_{n}) = n-4\). If \(p(a_{n}) \geq 1\) then for any two unoccupied vertices \(a_{k}\) and \(a_{l}\), we can find the path \(a_{k}a_{n}a_{l}\). Thus \(\{a_{n}\}\) forms a hub set for \(W_{n}\). If \(p(a_{i}) \geq 2\) for some \(i\) (\(1 \leq i \leq n-1\)) then we move one pebble to \(a_{n}\) and then for any two unoccupied vertices \(a_{k}\) and \(a_{l}\), we can find the path \(a_{k}a_{n}a_{l}\) so that \(\{a_{n}\}\) forms a hub set for \(W_{n}\). So \(p(a_{n}) = 0\) and \(p(a_{i}) \leq 1\) for \(1 \leq i \leq n-1\). Since \(p(W_{n}) = n-4\) and \(p(a_{n}) = 0\), we have three more unoccupied vertices \(a_{k}\), \(a_{l}\) and \(a_{m}\) where \(k < l < m\). Let \(T = V(W_{n})-\{a_{k},a_{l},a_{m},a_{n}\}\). As \(a_{k}\), \(a_{l}\) and \(a_{m}\) are adjacent to \(a_{n}\), it is enough to find a path between \(a_{k}\) & \(a_{l}\), \(a_{k}\) & \(a_{m}\) and \(a_{l}\) & \(a_{m}\) such that every internal vertex is a member of \(T\) for each path. If they are not adjacent to each other, then there exist following paths: the path \(a_{k}a_{k+1} \dots a_{l-1}a_{l}\) between the vertices \(a_{k}\) & \(a_{l}\), the path \(a_{l}a_{l+1} \dots a_{m-1}a_{m}\) between the vertices \(a_{l}\) & \(a_{m}\) and the path \(a_{m}a_{m+1} \dots a_{n-1}a_{1} \dots a_{k}\) between the vertices \(a_{m}\) & \(a_{k}\). Hence \(T\) forms a hub set for \(W_{n}\) and therefore \(h^{*}(W_{n}) \leq n-4\). ◻
Theorem 3. For a flower graph \(Fl_{n}\) \((n \geq 4)\), \(h^{*}(Fl_{n}) = 2n-4\).
Proof. Consider the following labeling for \(Fl_{n}\) (\(n \geq 4\)): label the vertices of the wheel graph as: \(a_{1},a_{2}, \dots, a_{n-1}, a_{n}\), where \(a_{n}\) is the center vertex and is of degree \(2(n-1)\) and label the vertex of degree two which is adjacent to \(a_{i}\) (\(1 \leq i \leq n-1\)) as \(x_{i}\).
For \(Fl_{n}\) (\(n \geq 4\)), let \(S = V(Fl_{n})-\{x_{n-1},a_{n},a_{n-1},a_{n-2}\}\). We place one pebble each on every vertex of \(S\). Then we can not find a path between the vertices \(x_{n-1}\) and \(a_{n-2}\) such that every internal vertex is a member of \(S\) and hence \(S\) is not a hub set for \(Fl_{n}\). Thus \(h^{*}(Fl_{n}) \geq 2n-4\).
Consider the distribution of \(2n-4\) pebbles on the vertices of \(Fl_{n}\). Clearly we are done if \(p(a_{n}) \geq 1\) or \(p(a_{i}) \geq 2\) or \(p(x_{i}) \geq 2\) for some \(i\), where \(1 \leq i \leq n-1\). So, we assume \(p(a_{n}) = 0\), \(p(a_{i}) \leq 1\) and \(p(x_{i}) \leq 1\) for all \(i\), where \(1 \leq i \leq n-1\). Since \(p(Fl_{n}) = 2n-4\), we get two more unoccupied vertices. Since \(a_{n}\) is adjacent to these unoccupied vertices, we look for adjacency between these two unoccupied vertices. If both of these unoccupied vertices are adjacent, then we are done. Otherwise, we consider the following cases:
Case 1. Let \(p(a_{k}) = 0\) and \(p(a_{l}) = 0\) for some \(k\) and \(l\) (\(1 \leq k < l \leq n-1\)).
Let \(T = V(Fl_{n}) – \{a_{k},a_{l},a_{n}\}\). We get the path \(a_{k}a_{k+1} \dots a_{l}\) such that every internal vertex is a member of \(T\).
Case 2. Let \(p(x_{k})=0\) and \(p(x_{l})=0\) for some \(k\) and \(l\) (\(1 \leq k < l \leq n-1\)).
Let \(T = V(Fl_{n}) – \{x_{k},x_{l},a_{n}\}\). We get the path \(x_{k}a_{k}a_{k+1} \dots a_{l}x_{l}\) such that every internal vertex is a member of \(T\).
Case 3. \(p(a_{k})=0\) and \(p(x_{l})=0\) for some \(k\) and \(l\), where \(1 \leq k \leq n-1\) and \(1 \leq l \leq n-1\).
Let \(T = V(Fl_{n}) – \{a_{k},x_{l},a_{n}\}\). We get the path \(a_{k}a_{k+1} \dots a_{l}x_{l}\) such that every internal vertex is a member of \(T\).
From the above cases, we can conclude that \(T\) is a hub set for \(Fl_{n}\) and hence \(h^{*}(Fl_{n}) \leq 2n-4\) ◻
Theorem 4. For a friendship graph \(FR_{n}\) \((n \geq 2)\), \(h^{*}FR_{n}) = 2n-1\).
Proof. The vertices of a graphs are \(a_{1},a_{2}, \dots, a_{2n-1},a_{2n}\) such that only \(a_{2i-1}\) and \(a_{2i}\) are adjacent (\(1 \leq i \leq n\)) and label the common vertex which is of degree \(2n\) as \(a_{2n+1}\).
Let \(S = V(FR_{n}) – \{a_{2n-2},a_{2n},a_{2n+1}\}\). Place one pebble each on the vertices of \(S\). Clearly, we can not find a path between the vertices \(a_{2n}\) and \(a_{2n-2}\) such that every internal vertex is a member of \(S\) and hence \(S\) is not a hub set for \(FR_{n}\). Thus \(h^{*}(FR_{n}) \geq 2n-1\).
Consider the distribution of \(2n-1\) pebbles on the vertices of \(FR_{n}\). Clearly we are done if \(p(a_{2n+1}) \geq 1\) or \(p(a_{i}) \geq 2\) for some \(i\), where \(1 \leq i \leq 2n\). So, we assume \(p(a_{2n+1}) = 0\), \(p(a_{i}) \leq 1\) for all \(i\), where \(1 \leq i \leq 2n\). Since \(p(FR_{n}) = 2n-1\), we get an additional unoccupied vertex, namely \(a_{k}\), for some \(k\) (\(1 \leq k \leq 2n\)). But \(a_{k}\) is adjacent to \(a_{2n+1}\). Thus, \(T = V(FR_{n}) – \{a_{k},a_{2n+1}\}\) forms a hub set for \(FR_{n}\) and hence \(h^{*}(FR_{n}) \leq 2n-1\). ◻
Theorem 5. For a helm graph \(H_{n}\) \((n \geq 4)\), \(h^{*}(H_{n}) = 8(n-3)+1\).
Proof. Label the vertices of the wheel graph as: \(a_{1},a_{2}, \dots, a_{n-1}, a_{n}\), where \(a_{n}\) is the centre vertex and is of degree \(n-1\) and label the vertex of degree one which is adjacent to \(a_{i}\) (\(1 \leq i \leq n-1\)) as \(x_{i}\).
Place \(8n-24\) pebbles on \(x_{1}\). We have to move one pebble each to every \(a_{i}\) so that we can form a path between any two \(x_{i}\)’s through \(a_{i}\)’s. While doing so, we burn all the pebbles from the vertex \(x_{1}\) and place one pebble each to every \(a_{i}\) except \(a_{1}\) and \(a_{n}\). Clearly, every path between \(x_{1}\) and \(a_{n}\) should go through \(a_{1}\) and there is no pebble on \(a_{1}\). Thus, \(h^{*}(H_{n}) \geq 8(n-3)+1\).
Let \(p(H_{n}) = 8n-23\). Let \(S = \{a_{i} : p(a_{i}) \geq 1 (i \neq n) \}\), \(T = \{a_{j}: p(a_{j}) = 0 (j \neq n)\}\) and assume \(|S| = x \geq 0\). If \(p(a_{n}) \geq 2(n-1-x)\) then clearly we are done by moving one pebble each to the set of vertices of \(T\). Let \(\sum_{i=1}^{n}p(a_{i}) \geq 4n-11\). Assume all the pebbles are placed on \(a_{i}\) \((i \neq n)\). From the vertex \(a_{i}\), there are \(n-3\) vertices that are at distance two and two vertices are at distance one. To put one pebble each on those vertices, we burn \(4(n-4)+2(2) = 4n-12\) pebbles from the vertex \(a_{i}\) and then we have at least one pebble on \(a_{i}\). Hence, the set \(\{a_{i}: i \neq n\}\) forms a hub set for \(H_{n}\). If \(|S| \geq 2\), then it is easy to move one pebble each to every vertex of \(T\). To complete this process, we consider the following cases:
Case 1. \(p(a_{k}) \geq 1\) is odd, where \(a_{k} \in S\).
Let \(p(a_{k}) \geq 3\). First, we retain one pebble on \(a_{k}\). If the adjacent vertices of \(a_{k}\) are in \(S\) then we move \(\frac{p(a_{k})-1}{2}\) pebbles to \(a_{n}\). If one of the adjacent vertices of \(a_{k}\) is in \(T\), then we move a pebble to that vertex and then \(\frac{p(a_{k})-3}{2}\) pebbles to \(a_{n}\). If all the adjacent vertices of \(a_{k}\) are in \(T\) and \(p(a_{k}) \geq 5\), then we move one pebble each to those vertices and then \(\frac{p(a_{k})-5}{2}\) pebbles to \(a_{n}\). If all the adjacent vertices of \(a_{k}\) are in \(T\) and \(p(a_{k}) = 3\), then we move one pebble to one of its adjacent vertex of \(a_{k}\) in \(T\). If \(p(a_{k}) = 1\) then we just retain that pebble on \(a_{k}\) itself.
Case 2. \(p(a_{l}) \geq 2\) is even, where \(a_{l} \in S\).
Let \(p(a_{l}) \geq 4\). First, we retain two pebbles on \(a_{l}\). If the adjacent vertices of \(a_{l}\) is in \(S\) then we move \(\frac{p(a_{l})-2}{2}\) pebbles to \(a_{n}\). If one of its adjacent vertex of \(a_{l}\) is in \(T\), then we move one pebble to that vertex and then \(\frac{p(a_{l})-4}{2}\) pebbles to \(a_{n}\). If all the adjacent vertices of \(a_{l}\) are in \(T\) and \(p(a_{l}) \geq 6\), then we move one pebble each to those adjacent vertices and then \(\frac{p(a_{l})-6}{2}\) pebbles to \(a_{n}\). If both the adjacent vertices of \(a_{l}\) are in \(T\) and \(p(a_{l}) = 4\), then we move a pebble to one of its adjacent vertices of \(a_{l}\) in \(T\). If \(p(a_{l}) = 2\) then we just retain that pebble on \(a_{l}\) itself.
From the above cases, we note that certain number of vertices from \(T\), (say \(y \geq 0\) vertices), are also pebbled using pebbling moves and also we could have moved some amount of pebbles to the vertex \(a_{n}\). Thus we can place one pebble each to the remaining unpebbled vertices of \(T\) using the pebbles from \(a_{n}\), since the vertex \(a_{n}\) contains at least \(2(n-1-(x+y))\) pebbles. Hence we have pebbled all the vertices of the set \(\{a_{i}: i \neq n\}\) and hence we are done.
Assume \(\sum_{i=1}^{n-1}p(x_{i}) \geq 4n-11\). Let \(S = \{a_{i} : p(a_{i}) \geq 1 (i \neq n) \}\), \(T = \{a_{j}: p(a_{j}) = 0 (j \neq n)\}\), \(U = \{x_{i} : p(x_{i}) \geq 1\}\), and \(V = \{x_{j}: p(x_{j}) = 0 \}\). Consider \(\sum p(a_{i}) + p(a_{n}) = p_{a}\) where \(a_{i} \in S\) and \(p_{a} \geq 0\). This implies that \(\sum p(x_{i}) \geq 8n-23 – p_{a}\) where \(x_{i} \in U\). If \(|S| \geq 1\), we do the same procedure as we discussed in the previous cases for the number of pebbles on \(a_{i}\). Suppose some of the vertices of \(T\), say \(z\) vertices, are not pebbled by these cases. To pebble those \(z\) vertices of \(T\), we use the pebbles on the vertices of \(U\).
Case 3. \(p(x_{m}) \geq 1\) is odd, where \(x_{m} \in U\).
We retain one pebble on \(x_{m}\) and then we move \(\frac{p(x_{m})-1}{2}\) pebbles to \(a_{m}\). Now, we undertake the operations as in Case \(1\) or Case \(2\) with the number of pebbles on the vertex \(a_{m}\) again, excluding the number of pebbles placed on the vertex \(a_{m}\).
Case 4. \(p(x_{m}) \geq 2\) is even, where \(x_{m} \in U\).
We do not retain any pebble on \(x_{m}\). We move \(\frac{p(x_{m})}{2}\) pebbles to \(a_{m}\). Now, we undertake the operations as in Case \(1\) or Case \(2\) with the number of pebbles on the vertex \(a_{m}\) again, excluding the number of pebbles placed on the vertex \(a_{m}\).
So, the vertex \(a_{n}\) receives some amount of pebbles from the vertex \(x_{m}\) through \(a_{m}\), that is, the vertex \(a_{n}\) receives at least \(2z\) pebbles which is enough to put one pebble each to the \(z\) unpebbled vertices of \(T\). Hence we have pebbled all the vertices of the set \(\{a_{i}: i \neq n\}\) and hence we are done.
Let \(|S| = 0\). This implies that \(\sum p(x_{i}) = 8n-23\) where \(x_{i} \in U\). Assume \(|U| \geq 3\). Now, we undertake the operations as in Case \(3\) and Case \(4\) with the number of pebbles on the vertex \(x_{i}\). We can easily placed one pebble each on every vertex \(a_{i}\), \(i \neq n\) which is adjacent to an unpebbled vertex \(x_{j}\) and hence we are done. Assume \(|U| = 1\) or \(2\). Now, we undertake the operations as in Case \(3\) and Case \(4\) with the number of pebbles on the vertex \(x_{i}\). We can easily placed one pebble each on every vertex \(a_{i}\), \(i \neq n\) which is adjacent to an unpebbled vertex \(x_{j}\) and hence we are done. There is an exception case where we cannot place a pebble on the vertex \(a_{k}\) of the set \(\{a_{i}\} (i \neq n)\). This case exists only when \(p(x_{k}) = 1\) and \(p(x_{l}) = 8n-24\) or \(p(x_{k}) = 8n-23\). But in this case also, we can find a path between any two unpebbled vertices of \(H_{n}\) in which all the internal vertices are members of \(S – \{a_{k}\} \cup \{x_{k}\}\) and hence we are done. Thus \(h^{*}(H_{n}) \leq 8n-23\). ◻
The authors declare no conflicts of interest to this work.