- Graham's pebbling conjecture on product of thorn graphs of complete graphs
- 点击次数：
- 论文类型： 期刊论文
- 发表时间： 2009-05-28
- 发表刊物： DISCRETE MATHEMATICS
- 收录刊物： SCIE、EI
- 卷号： 309
- 期号： 10
- 页面范围： 3431-3435
- ISSN号： 0012-365X
- 关键字： Pebbling number; Graham's conjecture; Thorn graph; Complete graph; Cartesian product
- 摘要： 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.
