Graham's pebbling conjecture on Cartesian product of the middle graphs of even cycles

2017/04/29 by Xia, Zheng-Jiang, Pan, Yong-Liang, Xu, Jun-Ming +1
#05C50 #15A18 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.00191

Abstract

A pebbling move on a graph G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number of a graph G, denoted by f(G), is the least integer n such that, however n pebbles are located on the vertices of G, we can move one pebble to any vertex by a sequence of pebbling moves. Let M(G) be the middle graph of G. For any connected graphs G and H, Graham conjectured that f(G× H)≤ f(G)f(H). In this paper, we give the pebbling number of some graphs and prove that Graham's conjecture holds for the middle graphs of some even cycles.

Related

• Bounding the number of cycles in a graph in terms of its degree sequence
• A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung
• Three Graphs and the Erdős-Gyárfás Conjecture
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3
• Arithmetic Progressions of Cycle Lengths in Graphs