Monophonic cover pebbling number (MCPN) of network graphs

A. Lourdusamy1, S. Kither Iammal2, I. Dhivviyanandam3
1Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai-627002, Tamil Nadu, India
2Department of Mathematics, Jayaraj Annapackiam College for women (Autonomous), Periyakulam Tamilnadu, India
3Department of Mathematics, North Bengal st. Xavier’s college, Rajganj, west Bengal, India India

Abstract

Given a connected graph G and a configuration D of pebbles on the vertices of G, a pebbling transformation involves removing two pebbles from one vertex and placing one pebble on its adjacent vertex. A monophonic path is defined as a chordless path between two non-adjacent vertices u and v. The monophonic cover pebbling number, γμ(G), is the minimum number of pebbles required to ensure that, after a series of pebbling transformations using monophonic paths, all vertices of G are covered with at least one pebble each. In this paper, we determine the monophonic cover pebbling number (MCPN) for the gear graph, sunflower planar graph, sun graph, closed sun graph, tadpole graph, lollipop graph, double star-path graph, and a class of fuses.

Keywords: Gear graph, sun graph, Closed sun graph, Sunflower planer graph, Tadpole graph, Lollipop graph, Double star-path graph, Monophonic pebbling, Monophonic cover pebbling

1. Introduction

A pebbling move is defined as the removal of two pebbles from one vertex, followed by the placement of one pebble on an adjacent vertex, while the other pebble is eliminated. The pebbling number of a vertex v in a graph G is the smallest positive integer f(G,v) such that, for every distribution of f(G,v) pebbles on the vertices of G, one pebble can be moved to v through a sequence of pebbling moves. The pebbling number f(G) is the maximum of f(G,v) over all vertices of G. For more information on graph pebbling, interested readers can refer to [5].

The pebbling problem focuses on ensuring that one pebble can reach any specified target vertex. This problem can be interpreted as the transmission of information from one specific location to a target location. However, a natural question arises: how can information reach all locations of a graph simultaneously within a reasonable time? In pebbling terminology, this requires placing one pebble on all the vertices of the graph G simultaneously. For example, in an Adhoc Network, if there is congestion in the network, the information must reach neighboring locations immediately. This question is addressed by a variation of pebbling, called the cover pebbling number.

The cover pebbling number of a graph γ(G) is the minimum number of pebbles required such that, for any configuration of γ(G) pebbles on the vertices of G, each vertex will have at least one pebble after a series of pebbling moves. At the end of this process, no vertex is left uncovered. Crull et al. [3] introduced the concept of cover pebbling, determining the cover pebbling number for complete graphs, paths, and trees. In [6], Hulbert and Munyan determined the cover pebbling number of the d-cube. Later, in 2010, Subido and Aniversario [10] expanded upon the work of Crull et al. by determining the cover pebbling number of graphs via a key vertex. Furthermore, Vuong and Wyckoff [11] introduced the stacking conjecture, where all pebbles for cover pebbling are placed on a single vertex. For any connected graph G, by the stacking theorem, γ(G)=uV(G)2dist(u,v). Any vertex v satisfying this equation is a key vertex of the graph. Selecting a suitable key vertex is particularly challenging for random graphs, graphs with a large number of vertices, and graphs with varying diameters. Specifically, the intuition of obtaining the cover pebbling number of graphs by distributing pebbles over the vertices of G is equivalent to finding the cover pebbling number by stacking all the pebbles at a suitable key vertex.

Santhakumaran et al. [9] introduced the concept of monophonic distance in graphs. The monophonic distance between u and v, denoted as dm(u,v), is the length of the longest uv monophonic path in G. For any two vertices u and v in a connected graph G, a uv path is a monophonic path if it contains no chords [9]. (A chord is a line segment connecting two points on a curve.) Lourdusamy et al. [7] defined the monophonic pebbling number using monophonic paths. The monophonic pebbling number, μ(G), of a connected graph G, is the smallest positive integer n such that any distribution of n pebbles on G allows one pebble to be moved to any specified vertex using monophonic paths via a sequence of pebbling moves.

Building on these definitions, we introduce the concept of a monophonic cover pebbling number. The monophonic cover pebbling number, γμ(G), is the minimum number of pebbles required to cover all the vertices of G with at least one pebble on each vertex after a series of pebbling transformations using monophonic paths. While the pebbling number of a graph is determined using the shortest distance in a graph G, the monophonic pebbling number is determined using monophonic distance. These two concepts play a crucial role in applications such as the supply of goods and transportation problems. When geodesic paths are unavailable, monophonic paths can serve as alternatives. The choice of paths directly impacts the cost of goods. Similarly, these concepts are applicable in network information transmission from one node to another. The monophonic cover pebbling number ensures the equitable distribution of goods across all customers using monophonic paths. For basic terminologies in graph theory, readers can refer to [1] and [2].

In this paper, we determine the monophonic cover pebbling number for various graphs, including the gear graph, sunflower planar graph, sun graph, closed sun graph, tadpole graph, lollipop graph, double star-path graph, and a class of fuses.

Notation 1.1.

The notation Gn stands for the gear graph, which is taken from [4]. The notation Sfn stands for the sunflower planar graph, also taken from [4]. The notation Su stands for the sun graph, and Su¯ stands for the closed sun graph, both referenced in [4]. The notation Tm,n stands for the (m,n) tadpole graph, which is taken from [12].

Theorem 1.2. [8] For the path Pn, γμ(Pn) is 2n1.

Definition 1.3.

[10] Let vV(G). Then v is called a key or source vertex if dist(v) is maximum.

Notation 1.4.

Throughout this article, we denote:

  1. β as the source vertex.

  2. Mi as the monophonic path, and Mi contains the vertices that are not on Mi.

  3. MCPN as the monophonic cover pebbling number.

  4. dm as the monophonic distance.

  5. N(v0) as the neighborhood of v0.

2. MCPN of families of network graphs

Theorem 2.1.

For the gear graph Gn, γμ(Gn) is 2(k=n+12(n1)2k)+2n+9.

Proof. Let V(Gn)={u0,u1,u2,,un,v1,v2,,vn} and E(Gn)={uivi,vjuj+1,vnu1,u0ui}, where 1in and 1jn1. Without loss of generality, let n be odd. Let p(v1)=2(k=n+12(n1)2k)+2n+8. To cover the vertices v2,u3,v3,,un2,vn2,vn2+1,un2+2,,vn, it will cost 2(2n+1+2n+2++22(n1)) pebbles; to cover un2+1 it will cost 2n pebbles; to cover N(v1) it will cost 4 pebbles; to cover u0 it will cost 4 pebbles, and there is no pebble left to cover v1. Thus, γμ(Gn)2(k=n+12(n1)2k)+2n+9.

Now we prove γμ(Gn)2(k=n+12(n1)2k)+2n+9.

Case 1: Let β=v1.

From Table 1, to cover the vertices v2,u3,v3,,un2,vn2,vn2+1,un2+2,,vn, we require 2(2n+1+2n+2++22(n1)) pebbles; to cover un2+1 we require 2n pebbles; to cover N(v1) we need 4 pebbles; to cover u0 we need 4 pebbles, and to cover v1 we need 1 pebble. Thus, in this case, we use γμ(Gn)=2(k=n+12(n1)2k)+2n+9 pebbles.

Table 1 Monophonic distance from v1, u1, u0 to V(Gn)
u1 v1 u2 v2 u3 v3 un2 vn2 un2+1 vn2+1 un vn u0
v1 1 0 1 2n2 2n3 2n4 n+2 n+1 n n+1 2n3 2n2 2
u1 0 1 2n2 2n3 2n4 2n5 n+1 n n+1 n+2 2n2 1 1
u0 1 2 1 2 1 2 1 2 1 2 1 2 0

Case 2: Let β=u1.

From Table 1, to cover the vertices v2,u3,v3,,un2,vn2,un2+1,un2+2,,vn, we need 2(2n+1+2n+2++22(n1)) pebbles; to cover vn2 we require 2n pebbles; to cover N(v1) we need 6 pebbles; to cover u1 we need 1 pebble. Thus, in this case, we use γμ(Gn)=2(k=n+12(n1)2k)+2n+7 pebbles.

Case 3: Let β=u0.

From Table 1, to cover the vertices u1,u2,,un, we need 2n pebbles; to cover v1,v2,,vn, we need 4n pebbles; to cover u0, we need 1 pebble. Thus, here we use γμ(Gn)=6n+1 pebbles. ◻

Theorem 2.2.

The MCPN of the sunflower planar graph Sfn is: γμ(Sfn)={4(i=n2+2n12i)+3(2n2+1)+2n+1+9,if n iseven,4(i=n2+1n12i)+2n2+2n+1+9,if n is odd.

Proof. Let V(Sfn)={u0,u1,,un,v1,v2,,vn} and E(Sfn)={u0ui,ujuj+1,u1un,uivi,uj+1vj,u1vn}, where i=1,2,,n and j=1,2,,n1. The center vertex u0 has degree n, vertices u1,u2,,un have degree 5, and vertices v1,v2,,vn have degree 2.

Case 1: When n is even.

Table 2 Monophonic distance from v1, u1, u0 to V(Sfn) (even n)
u1 v1 u2 v2 u3 v3 un2 vn2 un2+1 vn2+1 un2+2 vn1 un vn u0
v1 1 0 1 n n1 n1 n2+2 n2+2 n2+1 n2+1 n2+1 n1 n1 n 2
u1 0 1 1 n1 n2 n2 n2+1 n2+1 n2 n2+1 n2+1 n1 1 1 1
u0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 0

Subcase 1.1: β=u1.

From Table 2, to cover v2,vn1 it will cost 2(2n1) pebbles; to cover u3,v3,,un2,vn2,vn2+1,un2+2,,vn2,un1, it will cost 4(j=n2+1n22j) pebbles; to cover un2+1 it will cost 2n2 pebbles; to cover N(u1) it will cost 10 pebbles; to cover u1 it will cost 1 pebble. Thus, in this case to cover all the vertices we used 4(j=n2+1n22j)+2n+2n2+11.

Subcase 1.2: β=v1.

From Table 2, to cover v2 and vn it requires 2n+1 pebbles; to cover u3,v3,,un2,vn2,vn2+2,un2+3,,vn1,un, it requires 4(i=n2+2n12i) pebbles; to cover un2+1,vn2+1,un2+2, it requires 3(2n2+1) pebbles; to cover u1 and u2, it requires 4 pebbles; to cover u0, it requires 4 pebbles; to cover v1, it requires 1 pebble. Thus, in this case we used 4(i=n2+2n12i)+3(2n2+1)+2n+1+9.

Subcase 1.3: β=u0.

From Table 2, to cover N(u0) it will cost 2n pebbles; to cover v1,v2,,vn it will cost 4n pebbles; to cover u0 it will cost 1 pebble. Thus, in this case we used 6n+1.

Case 2: When n is odd.

Table 3 Monophonic distance from v1,u1,u0 to V(Sfn) (odd n)
u1 v1 u2 v2 u3 v3 un2 vn2 un2+1 vn1 un vn u0
v1 1 0 1 n n1 n1 n2 n2 n2 n1 n1 n 1
u1 0 1 1 n1 n2 n2 n2 n2 n2+1 n1 1 1 1
u0 1 2 1 2 1 2 1 2 1 2 1 2 0

Subcase 2.1: β=u1.

From Table 3, to cover v2, vn1 it will cost 2n pebbles; to cover u3, v3, , vn21, vn2+1, , vn2, un1 it will cost 4(j=n2+1n22j) pebbles; to cover un2, vn2, un2+1 it will cost 3(2n2) pebbles; to cover N(u1) it will cost 10 pebbles; to cover u1 it will cost 1 pebble. Thus, in this case we used 4(j=n2+1n22j)+3(2n2)+2n+11 pebbles.

Subcase 2.2: Let β=v1.

From Table 3, to cover v2, vn it will cost 2n+1 pebbles; to cover u3, v3, , un2, vn2, vn2+1, un2+2, , vn1, un it will cost 4(i=n2+1n12i) pebbles; to cover un2+1 it will cost 2n2 pebbles; to cover u1, u2 it will cost 4 pebbles; to cover u0 it will cost 4 pebbles; to cover v1 it will cost 1 pebble. Thus, in this case we used 4(i=n2+1n12i)+2n2+2n+1+9 pebbles.

Subcase 2.3: Let β=u0.

From Table 3, to cover N(u0) it will cost 2n pebbles; to cover v1, v2, , vn it will cost 4n pebbles; to cover u0 it will cost 1 pebble. Thus, in this case we used 6n+1 pebbles. ◻

For the Sun graph Su, γμ(Su)=12u11.

Proof. Let V(Su)={y1,y2,,yu,x1,x2,,xu} and E(Su)={yiyi+1,y1yu,yixi,xiyi+1,yuxu,xuy1,yivj} where 1i,ju1 and ij. The degree of xi is u+1 and yi is 2. Let p(x1)=5u12. To cover the vertices x2,x3,,xu, we require 23(u1) pebbles; to cover y3,y4,,yu, we require 22(u2) pebbles; to cover y1,y2, we require 4 pebbles. Now there is no pebble to cover x1. Hence, γμ(Su)12u11.

Now we show γμ(Su)12u11.

Table 4 Monophonic distance from y1, x1 to V(Su)
y1 x1 y2 x2 y3 x3 yu1 xu1 yu xu
y1 0 1 1 2 1 2 1 2 1 1
x1 1 0 1 3 2 3 2 3 2 3

Case 1: Let β=xk where 1ku.

Fix k=1. From Table 4, to cover the vertices x2,x3,,xu, which are at the monophonic distance 3, we require 23(u1) pebbles; to cover y3,y4,,yu, which are at the monophonic distance 2, we require 22(u2) pebbles; to cover N(x1), we require 4 pebbles; and to cover x1, we require 1 pebble. Thus, in this case, we used 12u11 pebbles.

Case 2: Let β=yk where 1ku.

Fix k=1. From Table 4, to cover the vertices x2,x3,,xu1, which are at the monophonic distance 2, we require 22(u2) pebbles; to cover y2,y3,,yu,x1,xu, which are adjacent to y1, we require 2(u+1) pebbles; to cover y1, we require 1 pebble. Thus, in this case, we used 4u4+2u+2+1=6u1 pebbles. ◻

Theorem 2.4.

For Su¯, γμ(Su¯) is γμ(Su¯)={2(k=u2+1u12k)+2u+3,if u is even,2(k=u2+1u12k)+2u2+2u+3,if u is odd.

Proof. Let V(Su¯)={y1,,yu,x1,x2,,xu} and E(Su¯)={yiyi+1,y1yu,xixi+1,x1xu,yixi,xiyi+1,yuxu,xuy1,yiyj}, where 1i,ju1 and ij. The degree of yi is u+1, and the degree of xi is 4.

Case 1: When u is even.

Let p(y1)=2(k=u2+1u12k)+2u+2. To cover the vertices x1,y2,y3,,yu,xu, it requires 2u+2 pebbles; to cover the vertices x2,x3,,xu1, it requires 2(k=u2+1u12k) pebbles, and there is no pebble left to cover y1. Thus, γμ(Su¯)2(k=u2+1u12k)+2u+2.

Now we show γμ(Su¯)2(k=u2+1u12k)+2u+2.

Table 5 Monophonic distance from y1 and x1 to V(Su¯)
y1 x1 y2 x2 y3 x3 xu2 yu2+1 xu2+1 yu2+2 xu2+2 yu2 xu2 yu1 xu1 yu xu
x1 1 0 1 1 2 u1 u2+2 2 u2+1 2 u2+2 2 u2 2 u1 2 1
y1 0 1 1 u1 1 u2 u2+1 1 u2+1 1 u2+2 1 u2 1 u1 1 1

Subcase 1.1: Let β=y1.

From Table 5, to cover N(y1), it costs 2u+2 pebbles; to cover x2,x3,,xu1, which are at monophonic distances u1,u2,,u2+1, it costs 2(k=u2+1u12k) pebbles; to cover y1, it costs 1 pebble. Thus, in this subcase, we used 2(k=u2+1u12k)+2u+2 pebbles.

Subcase 1.2: Let β=x1.

From Table 5, to cover N(x1), it costs 8 pebbles; to cover y3,y4,,yu, it costs 4u8 pebbles; to cover x3,x4,,xu1, which are at monophonic distances u1,u2,,u2+2, it costs 2(k=u2+2u12k)+2u2+1 pebbles; to cover x1, it costs 1 pebble. Thus, in this subcase, we used 2(k=u2+2u12k)+2u2+1+4u+1<2(k=u2+1u12k)+2u+2.

Case 2: When u is odd.

Let p(y1)=2(k=u2+1u12k)+2u2+2u+2. To cover the vertices x1,y2,y3,,yu,xu, it requires 2u+2 pebbles; to cover the vertices x2,x3,,xu1, it requires 2(k=u2+1u12k)+2u2 pebbles, and there is no pebble to cover y1. Thus, γμ(Su¯)2(k=u2+1u12k)+2u2+2u+2.

Now we prove γμ(Su¯)2(k=u2+1u12k)+2u2+2u+2.

Table 6 Monophonic distance from y1 and x1 to V(Su¯)
y1 x1 y2 x2 y3 x3 xu2 yu2+1 xu2+1 yu2+2 xu2+2 yu2 xu2 yu1 xu1 yu xu
x1 1 0 1 1 2 u1 u2+1 2 u2+1 2 u2+2 2 u2 2 u1 2 1
y1 0 1 1 u1 1 u2 u2 1 u2+1 1 u2+2 1 u2 1 u1 1 1

Subcase 2.1: Let β=y1.

From Table 6, to cover N(y1), it will cost 2u+2 pebbles; to cover x2,x3,,xu1, which are at the monophonic distances u1,u2,,u2+1, it will cost 2(k=u2+1u12k)+2u2 pebbles; to cover y1, it will cost 1 pebble. Thus, in this case, we used 2(k=u2+1u12k)+2u2+2u+2 pebbles.

Subcase 2.2: Let β=x1.

From Table 6, to cover N(x1), it will cost 8 pebbles; to cover y3,y4,,yu, it will cost 4u8 pebbles; to cover x3,x4,,xu1, which are at the monophonic distances u1,u2,,u2+2, it will cost 2(k=u2+1u12k) pebbles; to cover x1, it will cost 1 pebble. Thus, in this case, we used 2(k=u2+1u12k)+4u+1<2(k=u2+1u12k)+2u2+2u+2 pebbles. ◻

Theorem 2.5.

For Tm,n, γμ(Tm,n)={2(k=m2+n+1m+n22k)+2m2+n+3(2n+1)1,if m iseven,2(k=m2+nm+n22k)+3(2n+1)1,if m is odd.

Proof. Let V(Tm,n)={v1, v2, , vm, u1, u2,, un} and E(Tm,n)={uiui+1,u1v1,vkvk+1,vmv1} where i=1,2,,n1 and k=1,2,,m1. Consider a bridge between u1 and v1.

Case 1: When m is even.

Let p(un)=2(k=m2+n+1m+n22k)+2m2+n+3(2n+1)2. To cover the vertices v2,v1,u1,u2,,un we need 2n+21 pebbles; to cover vm we need 2n+1 pebbles; to cover v2,v3,,vm2,vm2+2,,vm1 we need 2(k=m2+n+1m+n22k) pebbles; to cover vm2+1 we need 2m2+n pebbles but we have 2m2+n1 pebbles. Thus, there must be a vertex without cover. Hence, γμ(Tm,n)2(k=m2+n+1m+n22k)+2m2+n+3(2n+1)1. Now we prove γμ(Tm,n)2(k=m2+n+1m+n22k)+2m2+n+3(2n+1)1.

Subcase 1.1: Let β=un.

To cover the vertices v2,v1,u1,u2,,un, it will cost 2n+21 pebbles; to cover vm it will cost 2n+1 pebbles; to cover v2,v3,,vm2,vm2+2,,vm1 it will cost 2(k=m2+n+1m+n22k) pebbles; to cover vm2+1 we need 2m2+n pebbles. Thus, we used 2(k=m2+n+1m+n22k)+3(2n+1)+2m2+n1 pebbles.

Subcase 1.2: Let β=v1.

To cover the vertices v1,u1,u2,,un, it will cost 2n+11 pebbles; to cover the vertices v2,vm it will cost 4 pebbles; to cover the vertices v2,v3,,vm2,vm2+2,,vm1 it will cost 2(i=m2+1m22i) pebbles; to cover vm2+1 it will cost 2m2 pebbles. Thus, we used 2(i=m2+1m22i)+2m2+2n+1+3 pebbles.

Case 2: When m is odd.

Let p(un)=2(k=m2+nm+n22k)+3(2n+1)2. To cover the vertices v2,v1,u1,u2,,un, we need 2n+21 pebbles; to cover vm, we need 2n+1 pebbles; to cover v2,v3,,vm1, we need 2(k=m2+nm+n22k). Thus, in this case: γμ(Tm,n)2(k=m2+nm+n22k)+3(2n+1)1. The equality holds when β=un or v1◻

Theorem 2.6.

For L(m,n),γμ(L(m,n))=2n+11+(m1)2n+1.

Proof. Let V(L(m,n))={v1,v2,,vm,u1,u2,,un} where m vertices form a complete graph and n vertices form a path of order n. Without loss of generality, consider a bridge between u1 and v1. Let p(un)=2n+12+(m1)2n+1. To cover the vertices v2,v3,,vm, it will cost (m1)2n+1 pebbles; to cover the vertices un1,un2,,u1,v1, it will cost 2n+12 pebbles, and there is no pebble left to cover un. Thus, γμ(L(m,n))2n+11+(m1)2n+1.

Now we prove γμ(L(m,n))2n+11+(m1)2n+1.

Case 1: Let β=un.

Let the monophonic path M1:un,un1,,u1,v1 of length n. By Theorem 1.2, to cover p(V(M1)), we require 2n+11 pebbles; to cover the vertices v2,v3,,vm, which are at a monophonic distance of n+1, we need (m1)2n+1 pebbles. Thus, to cover all the vertices, it will cost γμ(L(m,n))=2n+11+(m1)2n+1 pebbles.

Case 2: Let β=v2.

Consider the monophonic path M2:v2,v1,u1,u2,,un of length n+1. By Theorem 1.2, to cover p(V(M2)), we require 2n+21 pebbles; to cover the vertices v3,v4,,vm, which are adjacent to v2, it will cost 2(m2) pebbles. Thus, to cover all the vertices from v2, it will cost 2n+21+2(m2) pebbles. By symmetry, the same can be proven for the vertices v3,v4,,vm.

We observe that if the source vertices are un1,un2,,u1,v1, then the monophonic cover pebbling number of these vertices will lie between Case 1 and Case 2. ◻

Theorem 2.7.

For the double star-path graph Pn(l,m), γμ(Pn(l,m))=2n+2+2n+1(l1)+22(m1), where lm.

Proof. Let V(Pn(l,m))={x0,x1,,xl,y0,y1,,ym,v1,v2,,vn} and E(Pn(l,m))={x0xi,x0v1,vsvs+1,vny0,y0yj}, where i=1,2,,l, s=1,2,,n1, and j=1,2,,m. Let p(y1)=2n+2+2n+1(l1)+22(m1)1. To cover the vertices y1,y0,v1,v2,,vn,x0,x1, it will cost 2n+21 pebbles; to cover x2,x3,,xl, it will cost (l1)2n+1 pebbles; to cover y2,y3,,ym, it will cost 4(m1) pebbles, but we have 4(m1)1 pebbles. Thus, there will be a vertex without cover. Hence, γμ(Pn(l,m))2n+2+2n+1(l1)+22(m1), where lm.

Now we prove γμ(Pn(l,m))2n+2+2n+1(l1)+22(m1), where lm.

Case 1: Let β=y1.

Let us consider the monophonic path M1:y1,y0,v1,v2,,vn,x0,x1 of length n+1. By Theorem 1.2, to cover p(V(M1)), we require 2n+21 pebbles; to cover x2,x3,,xl, we require (l1)2n+1 pebbles; to cover y2,y3,,ym, which are at monophonic distance 2, we need (m1)4 pebbles. Thus, in this case, we used 2n+21+(l1)2n+1+(m1)4=2n+2+(l1)2n+1+4m5 pebbles. By symmetry, the same can be proven for the vertices y2,y3,,ym.

Case 2: Let β=x1.

Let us consider the monophonic path M2:x1,x0,vn,vn1,,v1,y0,y1 of length n+1. By Theorem 1.2, to cover p(V(M2)), we require 2n+21 pebbles; to cover y2,y3,,ym, we require (m1)2n+1 pebbles; to cover x2,x3,,xl, which are at monophonic distance 2, we need (l1)4 pebbles. Thus, in this case, we used 2n+21+(m1)2n+1+(l1)4<2n+2+2n+1(l1)+22(m1) pebbles. Since lm.

Case 3: Let β=vs, where 1sn.

There exist two monophonic paths. Let M3:vk,vk+1,,vn,y0,y1 of length nk+2 and M4:vk,vk1,,v1,x0,x1 of length k+1. By Theorem 1.2, to cover p(V(M3)), we need 2nk+31 pebbles, and to cover p(V(M4)), we need 2k+21 pebbles. Now to cover y2,y3,,ym, we need (m1)2nk+2 pebbles; to cover x2,x3,,xl, we need (l1)2k+1 pebbles. Thus, to cover all the vertices, we require 2k+21+2nk+31+(m1)2nk+2+(l1)2k+1<2n+2+2n+1(l1)+22(m1) pebbles. Similarly, we can prove for x0 and y0◻

Theorem 2.8.

For the class of fuses Fl(k), γμ(Fl(k))=2l+21+(k1)2l+1.

Proof. Let V(Fl(k))={v0,v1,,vl,vl+1,,vn1} and E(Fl(k))={vivi+1,vlvs}, where i=0,1,,l1, s=l+1,l+2,,n1, and n=l+k+1. Consider the monophonic path M1:v0,v1,v2,,vl,vl+1 of length l+1. Let p(v0)=2l+22+(k1)2l+1. To cover the vertices vl+2,vl+3,,vn1, we require (k1)2l+1 pebbles. By Theorem 1.2, to cover the vertices of M1, we require 2l+21 pebbles, but we have only 2l+22 pebbles. Thus, there will be a vertex without cover. Hence, γμ(Fl(k))2l+21+(k1)2l+1.

Now we prove γμ(Fl(k))2l+21+(k1)2l+1.

Case 1: Let β=v0.

Consider the path M1. By Theorem 1.2, to cover p(V(M1)), we require 2l+21 pebbles. To cover the k vertices vl+2,vl+3,,vn1, which are at the monophonic distance l+1, we require (k1)2l+1 pebbles. Thus, with a configuration of 2l+21+(k1)2l+1 pebbles, we can cover all the vertices. Similarly, we can prove for the vertices vl+1,vl+2,,vn1.

Case 2: Let β=vj, where j=1,2,,l.

There exist two different monophonic paths: M2:vj,vj+1,,vl,vl+1, of length lj+1 and M3:vj,vj1,,v0, of length j. By Theorem 1.2, to cover V(M2), we require 2lj+21 pebbles; to cover V(M3), we require 2j+12 pebbles; and to cover the vertices vl+2,vl+3,,vn1, we require (k1)2lj+1 pebbles. Thus, to cover all the vertices, we require 2lj+21+2j+12+(k1)2lj+1=3(2lj+1)+(k1)2lj+1<2l+21+(k1)2l+1. ◻

References:

  1. J. Bondy and U. Murty. Graph theory with applications. Macmillan, 1977.
  2. G. Chartrand. Introductory Graph Theory. Dover Books on Mathematics. Dover Publications, 1985.
  3. B. Crull, T. Cundiff, P. Feltman, G. Hurlbert, L. Pudwell, Z. Szaniszlo, and Z. Tuza. The cover pebbling number of graphs. Discrete Mathematics, 296:15–23, 2005.
  4. S. N. Daoud and K. Mohamed. The complexity of some families of cycle-related graphs. Journal of Taibah University for Science, 11:205–228, 2017. https://doi.org/10.1016/j.jtusci.2016.04.002.
  5. G. Hurlbert. A survey of graph pebbling. Congressus Numerantium, 139:41–64, 1999.
  6. G. Hurlbert and B. Munyan. Cover pebbling hypercubes. Bulletin of the Institute of Combinatorics and its Applications, 47:71–76, 2006.
  7. A. Lourdusamy, I. Dhivviyanandam, and S. Kitheriammal. Monophonic pebbling number and t-pebbling number of some graphs. AKCE International Journal of Graphs and Combinatorics, 2022. https://doi.org/10.1080/09728600.2022.207278.
  8. A. Lourdusamy, S. Kitheriammal, and I. Dhivviyanandam. Monophonic cover pebbling number of some path related graphs. Industrial Engineering Journal, 52(4):167–170, Apr. 2023.
  9. A. Santhakumaran and P. Titus. Monophonic distance in graphs. Discrete Mathematics, Algorithms and Applications, 3(2):159–169, 2011. https://doi.org/10.1142/S1793830911001176.
  10. M. E. Subido and I. S. Aniversario. The cover pebbling number of the join of some graphs. Applied Mathematical Sciences, 2014. https://doi.org/10.12988/ams.2014.45377.
  11. A. Vuong and I. Wyckoff. Conditions for weighted cover pebbling of graphs. http://arxiv.org/abs/math/0410410, 2005. Manuscript.
  12. E. W. Weisstein. Tadpole graph. https://mathworld.wolfram.com/TadpoleGraph.html. Accessed: 2024-11-28.