• GRAHAM’S PEBBLING CONJECTURE ON PRODUCT OF THORN GRAPHS OF PATHS

Abstract

Given a distribution of pebbles on the vertices of a connected graph G, the pebbling number of a graph G, is the least number f(G) such that no matter how these f(G) pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p_1, p_2,…,p_n be positive integers and G be such a graph, V(G) = n. The thorn graph of the graph G, with parameters p_1, p_2,…,p_nis obtained by attaching p_i new vertices of degree 1 to the vertex v_i of the graph G, where i = 1, 2,…, n. In this paper we discuss about the pebbling number of the thorn graph of path of length n also called as thorn path and we show that Graham’s conjecture holds for thorn path and it satisfies the two pebbling property. As a corollary, Graham’s conjecture holds when G and H are thorn paths with every p_i≥ 2, i = 1, 2,…, n.