• HERSCOVICI’s CONJECTURE ON THE PRODUCTS OF PATHS, COMPLETE GRAPHS

A. LOURDUSAMY, C. MUTHULAKSHMI, SASIKALA*

Abstract


Given a connected graph G, distribute k pebbles on its vertices in some configuration C. Specifically a configuration on a graph G is a function f from V(G) to NU{0} representing an assignment of  pebbles on G. We call the total number of pebbles, k, the size of the configuration. A pebbling move is defined as the removal of two pebbles from a vertex and addition of one of those pebbles on an adjacent vertex. The pebbling number of a connected graph G is the smallest number f(G) such that, however  f(G) pebbles are distributed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves. The t-pebbling number ft(G) of a simple connected graph G is the smallest positive integer such that for every distribution of ft(G) pebbles on the vertices of G, we can move t pebbles to any target vertex by a sequence of pebbling moves. Graham conjectured that For any connected graphs G and H, f(G×H) ≤ f(G) f(H). Herscovici further conjectured that fst(G×H) ≤ fs(G) ft(H) for any positive integers s and t. In this paper we show that Herscovici’s conjecture is true when G is a path, complete graph and H is a graph satisfying the 2t- pebbling property.


Keywords


Path, complete graph, t-pebbling number, Herscovici’s conjecture.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
© 2011-2019 Research Journal of Pure Algebra (RJPA)
Copyright Agreement & Authorship Responsibility
HTML Counter
Counter