Red-Blue Pebbling number of some graphs

C. Muthulakshmi@sasikala, A. Arul Steffi

Abstract: Red-Blue pebble game was introduced by Hong and Kung[1]. Given any DAG, G = (V,E) , a configuration C on G is a function C : V (G) → {R,B,O} where V (G) can be partitioned into V1(G), V2(G) and V3(G) in such a way that V1(G) comprises of just the vertices having red pebbles (R), V2(G) is just those have blue pebbles (B) , and V3(G) is the empty set that is vertices have no pebbles. Define the size |C| of a configuration C to be the total number of pebbles, that is |C| = v∈V(G)C(V ) . In this paper, we determine the min|C| pebbles used in the completion of Red-Blue pebble game for different Directed Acyclic graphs (DAG) such as r-pyramid, and complete r-partite graphs.