Pebbling and Graham's conjecture
type: Item
instance of: scholarly article
title: Pebbling and Graham's conjecture
zbMATH Open document ID: 0982.05100
DOI: 10.1016/S0012-365X(00)00177-1
author: Stephen S. Wang
published in: Discrete Mathematics
publication date: 2002-04-08T00:00:00Z
review text: Given an arrangement of pebbles on the vertices of a graph \(G\), a pebbling move is defined to consist of removing two pebbles from one vertex and placing one pebble on an adjacent vertex [see, i.e., \textit{F. R. K. Chung}, SIAM J. Discrete Math. 2, No. 4, 467-472 (1989; Zbl 0727.05043)]. Let \(f(G,v)\) be the minimum integer which guarantees that any starting pebble configuration allows reaching a configuration with at least one pebble on \(v\) through repeating pebbling moves. Let the pebbling number of \(G\) be the maximum of \(f(G,v)\) for all vertices \(v\). The author proves that the conjecture \(f(G\times H)\leq f(G)f(H)\) holds if \(H\) is a complete multipartite graph and \(G\) has Chung's 2-pebbling property. He also gives an infinite class of graphs which are not 2-pebbling.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 1565963
zbMATH Keywords: pebbling move
zbMATH Keywords: pebble configuration
zbMATH Keywords: pebbling number
Wikidata QID: Q123010052
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00177-1
OpenAlex ID: W2042634486
description: scientific article; zbMATH DE number 1565963