Graham’s pebbling conjecture on product of thorn graphs of complete graphs |
| |
Authors: | Zhiping Wang Zhongtuo Wang |
| |
Institution: | a Department of Mathematics, Dalian Maritime University, 116026, Dalian, PR China b College of Traffic and Logistics Engineering, 116026, Dalian, PR China c Department of Foundational Education, Yantai Nanshan University, 265713, Yantai, PR China d School of Management, Dalian University of Technology, 116024, Dalian, PR China |
| |
Abstract: | 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 p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every 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 . |
| |
Keywords: | Pebbling number Graham&rsquo s conjecture Thorn graph Complete graph Cartesian product |
本文献已被 ScienceDirect 等数据库收录! |
|