The 2-pebbling property and a conjecture of Graham's
type: Item
instance of: scholarly article
title: The 2-pebbling property and a conjecture of Graham's
zbMATH Open document ID: 0971.05063
author: Hunter Snevily
author: James A. Foster
published in: Graphs and Combinatorics
publication date: 2001-10-30T00:00:00Z
review text: Assume that a set of ``pebbles'' are distributed onto the vertices of an undirected graph \(G\) (where a vertex may receive one or more pebbles, or none). A move consists in removing two pebbles from a given vertex and to place one pebble at an adjacent vertex. We say that a pebble can be moved to a vertex \(v\) when there is a sequence of moves such that in the final configuration \(v\) has at least one pebble. The pebbling number \(f(G)\) of \(G\) is the least \(m\) such that for every distribution of \(m\) pebbles a pebble can be moved to any vertex. A graph \(G\) has the 2-pebbling property if two pebbles can be moved to any vertex, provided that originally there are at least \(2f(G)- q+1\) pebbles, where \(q\) is the number of vertices having at least one pebble. All cycles (as shown in this paper) and all trees satisfy this property, while few graphs not fulfilling it are known. The Graham conjecture states that \(f(G\times H)\leq f(G)f(H)\), where \(\times\) denotes the Cartesian product. The authors prove this conjecture when (1) \(G\) and \(H\) are cycles (up a finite number of unsettled cases) and (2) \(G\) has the 2-pebbling property and \(H\) is a tree.
reviewed by: Raffaele Scapellato
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1491663
zbMATH Keywords: Lemke graph
zbMATH Keywords: pebble
zbMATH Keywords: pebbling number
zbMATH Keywords: 2-pebbling property
zbMATH Keywords: Graham conjecture
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1491663