Graham’s pebbling conjecture on products of many cycles |
| |
Authors: | David S. Herscovici |
| |
Affiliation: | Department of Computer Science/IDD, CL-AC1, Quinnipiac University, 275 Mount Carmel Avenue, Hamden, CT 06518, United States |
| |
Abstract: | A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define ft(G) as the smallest number such that whenever ft(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f1(G×H)≤f1(G)f1(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(Cpj×?×Cp2×Cp1×G)≤α(Cpj)?α(Cp2)α(Cp1)α(G) when none of the cycles is C5, and G satisfies one more criterion. We also apply this result with G=C5×C5 by showing that C5×C5 satisfies Chung’s two-pebbling property, and establishing bounds for ft(C5×C5). |
| |
Keywords: | Pebbling Graham&rsquo s conjecture Cartesian product Cycle |
本文献已被 ScienceDirect 等数据库收录! |
|