Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (3): 35-44.

• Original Articles • Previous Articles     Next Articles

Pebbling numbers of middle graphs of cycles and Graham's conjecture

YE Yongsheng1,*, LIU Fang1, ZHAI Mingqing2   

  1. 1. School of Mathematical Sciences, Huaibei Normal University, Huaibei 235000, Anhui, China 2. Department of Mathematics, Chuzhou University, Chuzhou 239012, Anhui, China
  • Online:2013-09-15 Published:2013-09-15

Abstract:   A pebbling move on a graph G consists of taking two pebbles off one vertex and placing  one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f(G), is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. For any connected graphs G and H, Graham conjectured that  f(G\times H)\leq f(G)f(H). In this paper, we show  the pebbling numbers of  middle graphs of  cycles, and discuss that Graham^,s conjecture holds for  middle  graphs of some cycles.

Key words: Graham's conjecture, cycles, middle graphs, pebbling number

CLC Number: