Let G be a simple connected graph with p vertices and q edges. An edge pebbling move on G is defined to be the removal of two pebbles from one edge and the addition of one pebble to an adjacent edge ^{1}. An edge pebbling number P_{E}(G) is defined to be the least number of pebbles such that any distribution of P_{E}(G) pebbles on the edges of G allows one pebble to be moved to any specified, but arbitrary edge ^{1}. The cover edge pebbling number CP_{E}(G) of a graph G is defined as, however the pebbles are initially placed the minimum number of pebbles required to place one pebble in all the edges through edge pebble move in all possible distribution ^{1}. The cover edge pebbling number for some standard graphs such as path, complete graph, friendship graph and star graphs are determined in ^{1}. The cover edge pebbling number for some families of graphs such as Helm graph, crown graph and pan graph are determined in ^{2}.

A graph G is said to be edge demonic if the edge pebbling number equals the number of edges. i.e., A graph G is said to be edge demonic if P_{E}(G) = q ^{3}.

In section 2 the edge pebbling number of friendship graph is determined by modifying the previously published result by including a new occurrence. The covering cover edge pebbling number of a graph G is defined and the same is computed for friendship graph F_{n}.

The possible minimum edge covering set of the graph is to be considered and the set with the minimum pebble requirement covering all vertices is selected. Then, by finding the key edges the covering cover edge pebbling number is computed.

_{n} is a simple graph with 2n + 1 vertices and 3n edges in which n copies of 3-cycles were joined in a common vertex.

Throughout this paper the edges of F_{n} are labelled as follows,

• The n edges not incident to the common vertex is labelled as e_{1}, e_{2}, …, e_{n} arbitrarily

• The two edges, adjacent to e_{i} are labelled as e_{i1} and e_{i2} in any arbitrary way, where i = 1,2, …, n.

_{c}P_{E}(G) is defined as the minimum number of pebbles required to cover the edges that forms a covering for G in all possible configurations of pebbles.

_{E}(F_{n}) = 3n +2, n>1.

The total number of edges in F_{n} is 3n. Distributing one pebble, on 3n – 1 edges each, leaving the target edge, edge pebble move is not possible. If one more pebble is placed on any of the 3n – 1 edge, the target edge will be reached. So altogether 3n pebbles are needed to reach any target edge.

We can conclude that in this case to reach any target edge, a maximum of 3n pebbles are needed.

The number of edges incident with the common vertex in F_{n} is 2n. Since all the edges are incident with the common vertex the distance between any of those edges is zero. Hence considering the worst case of distribution of pebbles. i.e., placing one pebble, on all the 2n-1 edges, edge pebble move is not possible. By adding one more pebble on any of the 2n-1 edges or on the target edge itself we are done. Hence if the target edge lies within those 2n edges, then it can be reached with 2n pebbles.

Number of edges not incident with the common vertex in F_{n} is n. To reach any of those n edges 2n+1 pebbles are needed by the same argument used in the previous subcase(i). Hence, in this case to reach any target edge in all possible distribution of pebbles a maximum of 2n+1 pebbles are needed.

Number of edges not incident with the common vertex in F_{n} is n. If we distribute one pebble each on those n edges then to reach any edge incident with the common vertex is not possible. If we distribute two pebbles each, on those n edges then any edge incident with the common vertex is possible to reach. In this case 2n pebbles are needed to reach the target edge.

The target edge can be any of the n edges from the n copies of 3-cycles. Suppose if the 3n pebbles found in

By the above three cases we can conclude that, P_{E}(F_{n}) = 3n+2. This completes the proof.

_{n} is not edge demonic.

The number of edges of a friendship graph is 3n. By the above theorem edge pebbling number of a friendship graph is 3n+2. Hence, by the definition of edge demonic graph

_{c}P_{E}(F_{2}) = 9.

_{2} are,

E_{1} = {e_{1}, e_{21}, e_{22}}

E_{2} = {e_{2}, e_{11,} e_{12}}

E_{3} = {e_{1}, e_{2}} ∪ {e_{i1} or e_{i2}}, i = 1,2

_{1}

Let us place 9 pebbles on e_{1}. After a number of edge pebble move from e_{1} we can place one pebble on each edge e_{21} and e_{22} by using 4+4 pebbles. The remaining one pebble will cover e_{1}. So, in this configuration of pebbles all the vertices of F_{2} will be incident to at least one edges of E_{1}.

Consider placing 8 pebbles on e_{1}. After a number of edge pebble move from e_{1} we can place one pebble on each edge e_{21} and e_{22} by using 4+4 pebbles or we can place one pebble on each edge e_{11}, e_{12} and e_{21} (or e_{22}) by using 2+2+4 pebbles or we can place one pebble on e_{2}. In either case we could not place a pebble on each edge of E_{1}.

Consider placing 8 pebbles on more than one edge, clearly all the edges in E_{1} can be pebbled.

Hence, placing all pebbles on e_{1} is the worst initial configuration.

_{2}

It can be dealt as in case 1 and placing all pebbles on e_{2} is the worst initial configuration.

_{3}

Let us place 9 pebbles on e_{1} (or e_{2}). After a number of edge pebble move from e_{1} (or e_{2}) we can place one pebble on e_{2} (or e_{1}) by using 2^{3} pebbles but to pebble e_{i1} or e_{i2} we need at least 2 more pebbles. In this case at least 11 pebbles are to be placed in e_{1} or e_{2}. Since the number of pebbles increase in this case than case(i), we can exclude this minimum edge covering.

Altogether, we can conclude that C_{c}P_{E}(F_{2}) = 9

_{3}, F_{4}, …, F_{n} remains the same as F_{2} in all the graphs the worst initial configuration is placing all the pebbles on their key edges. With this result we can prove the following theorem.

_{c}P_{E}(F_{n}) = 8n – 7, n > 1.

_{n} the key edges are those edges which are not incident with the common vertex. Choose such an edge say e_{1}.

Consider the 2n – 2 edges that are incident with the common vertex and not adjacent to the key edge e_{1}. The distance between any of the 2n – 2 edges and the key edge e_{1} is 2. Hence to pebble all those edges 2^{2}(2n – 2) = 8n – 8 pebbles are to be placed on e_{1}. Now to pebble e_{1} one more pebble is to be placed. Obviously, the pebbled edges will form an edge covering.

Hence altogether we can conclude that the covering cover edge pebbling number of a friendship graph F_{n} is 8n – 7, n > 1.

_{4} = 5.

Consider a path P_{4} = (v_{1},_{ }e_{1},_{ }v_{2}, e_{2}, v_{3}, e_{3}, v_{4}) with usual notations.

The minimum edge covering of P_{4} is,

E = {e_{1}, e_{3}}

Let us place 5 pebbles on e_{1} or e_{3}. To reach e_{3} from e_{1} four pebbles are to be placed on e_{1}(viceversa). So, in this configuration of pebbles all the vertices of P_{4} will be incident to at least one edges of E_{1}.

Consider placing 4 pebbles on e_{1} or e_{3}. After a number of edge pebble move from e_{1 }or e_{3} we can place one pebble only on the edge e_{3} or e_{1}. In either case we could not place a pebble on all edges of E.

Consider placing 4 pebbles on more than one edge, clearly all the edges in E can be pebbled.

Hence, placing all pebbles on e_{1} or e_{2} is the worst initial configuration.

Hence, we can conclude that C_{c}P_{E}(P_{4}) = 5.

_{6}, …, P_{2n} remains the same as P_{4}, in all the graphs the worst initial configuration is placing all the pebbles on their key edges. With this result we can prove the following theorem.

_{c}P_{E}(P_{2n}) =

_{2n} = (v_{1},_{ }e_{1},_{ }v_{2}, e_{2}, …, v_{2n-1}, e_{2n-1}, v_{2n}) with usual notations.

The minimum edge covering of P_{2n} is,

E = {e_{1}, e_{3}, e_{5}, …, e_{2n-1}}

The key edges for P_{2n} are e_{1} and e_{2n-1}. Let us place the pebbles on either of the key edges. Arbitrarily choose e_{1} as the edge to place pebbles.

Now,

d(e_{1}, e_{3}) = 1, d(e_{1}, e_{5}) = 3, d(e_{1}, e_{7}) = 5, …, d(e_{1}, e_{2n-1}) = 2n-3. So, the number of pebbles to be placed for the above considerations respectively is 2^{2}, 2^{4}, 2^{6}, …, 2^{2n-2}. One more pebble is to be placed on e_{1} to cover it.

Hence altogether the number of pebbles needed to cover the edges in E = 1 + 2^{2}+2^{4}+2^{6}+…+2^{2n-2} =

i.e., C_{c}P_{E}(P_{2n}) =

_{5} = 11.

Consider a path P_{5} = (v_{1},_{ }e_{1},_{ }v_{2}, e_{2}, v_{3}, e_{3}, v_{4}, e_{4}, v_{5}) with usual notations.

The minimum edge covering of P_{5} are,

E_{1} = {e_{1}, e_{2}, e_{4}}

E_{2} = {e_{1}, e_{3}, e_{4}}

Case(i) Consider E_{1}

Subcase(i)

Let us place 11 pebbles on e_{1}. To reach e_{2} from e_{1} two pebbles are to be placed on e_{1} and to reach e_{4} from e_{1} eight pebbles are to be placed on e_{1}. The remaining one pebble will cover e_{1}. So, in this configuration of pebbles all the vertices of P_{5} will be incident to at least one edges of E_{1}.

Consider placing 10 pebbles on e_{1}. After a number of edge pebble move from e_{1 }we could not place a pebble on all edges of E_{1}.

Consider placing 10 pebbles on more than one edge, clearly all the edges in E_{1} can be pebbled.

Subcase(ii)

Consider placing pebbles on e_{4}. To reach e_{2} from e_{4} four pebbles are to be placed on e_{4} and to reach e_{1} from e_{4} eight pebbles are to be placed on e_{4}. One more pebble is to be placed on e_{4} to cover it. Since the number of pebbles increase in this subcase than subcase(i), we can exclude this configuration of pebbles.

Case(ii) Consider E_{2}

Subcase(i)

Let us place 11 pebbles on e_{4}. To reach e_{3} from e_{4} two pebbles are to be placed on e_{4} and to reach e_{1} from e_{4} eight pebbles are to be placed on e_{4}. The remaining one pebble will cover e_{4}. So, in this configuration of pebbles all the vertices of P_{5} will be incident to at least one edges of E_{1}.

Consider placing 10 pebbles on e_{4}. After a number of edge pebble move from e_{4 }we could not place a pebble on all edges of E_{1}.

Consider placing 10 pebbles on more than one edge, clearly all the edges in E_{1} can be pebbled.

Subcase(ii)

Consider placing pebbles on e_{1}. To reach e_{3} from e_{1} four pebbles are to be placed on e_{1} and to reach e_{4} from e_{1} eight pebbles are to be placed on e_{1}. One more pebble is to be placed on e_{1} to cover it. Since the number of pebbles increase in this subcase(ii) than subcase(i), we can exclude this configuration of pebbles.

Hence, by case(i) placing all pebbles on e_{1} is the worst initial configuration and by case (ii) placing all pebbles on e_{4} is the worst initial configuration. And it is also clear that in both the cases the number of pebbles required is same ------ (*)

Hence, we can conclude that C_{c}P_{E}(P_{5}) = 11.

_{7}, …, P_{2n+1} remains the same as P_{5}, in all the graphs the worst initial configuration is placing all the pebbles on their key edges according to the minimum edge covering. With this result we can prove the following theorem.

i.e., C_{c}P_{E}(P_{2n+1}) =

_{2n+1} = (v_{1},_{ }e_{1},_{ }v_{2}, e_{2}, …, v_{2n-1}, e_{2n-1}, v_{2n}, e_{2n}, v_{2n+1}) with usual notations.

The minimum edge covering of P_{2n+1} are,

E_{1} = {e_{1}, e_{2}, e_{4}, e_{6}, …, e_{2n-2}, e_{2n}}

E_{2} = {e_{1}, e_{3}, e_{5}, e_{7}, …, e_{2n-1}, e_{2n}}

The key edges for P_{2n+1} are e_{1} and e_{2n}.

By previous theorem (*) , it is clear that we can consider either of the cases.

Let us consider E_{1}.

The key edges for P_{2n+1} are e_{1} and e_{2n}. Let us place the pebbles on either of the key edges. Arbitrarily choose e_{1} as the edge to place pebbles.

Now,

d(e_{1}, e_{2}) = 0, d(e_{1}, e_{4}) = 2, d(e_{1}, e_{6}) = 4, …, d(e_{1}, e_{2n}) = 2n – 2. So, the number of pebbles to be placed for the above considerations respectively is 2, 2^{3}, 2^{5}, 2^{7}, …, 2^{2n – }^{1}. One more pebble is to be placed on e_{1} to cover it.

Hence altogether the number of pebbles needed to cover the edges in E_{1} = 1 + 2^{3}+2^{5}+2^{7}+…+2^{2n – }^{1 } =

i.e., C_{c}P_{E}(P_{2n+1}) =

This paper shows that the covering cover edge pebbling number can be determined by finding the minimum edge covering number and key edges. In addition, it has many applications to optimization problems.