Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2009-05-28

Journal: DISCRETE MATHEMATICS

Included Journals: EI、SCIE

Volume: 309

Issue: 10

Page Number: 3431-3435

ISSN: 0012-365X

Key Words: Pebbling number; Graham's conjecture; Thorn graph; Complete graph; Cartesian product

Abstract: The pebbling number of a graph G, f(G), is the least n such that, no matter how n 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(n), is obtained by attaching p(i) new vertices of degree 1 to the vertex u(i) of the graph G, i = 1, 2,..., n. Graham conjectured that for any connected graphs G and H, f(G x H) <= f(G)f(H). We show that Graham's conjecture holds true for a thorn graph of the complete graph with every p(i) > 1 (i = 1, 2,..., n) by a graph with the two-pebbling property. As a corollary, Graham's conjecture holds when G and H are the thorn graphs of the complete graphs with every p(i) > 1 (i = 1, 2,..., n). (C) 2008 Elsevier B.V. All rights reserved.