首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号