Pebbling graphs (Q1204476)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Pebbling graphs |
scientific article; zbMATH DE number 130571
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Pebbling graphs |
scientific article; zbMATH DE number 130571 |
Statements
Pebbling graphs (English)
0 references
10 March 1993
0 references
The pebbling number \(f(G)\) of a graph \(G\) is the least \(n\) such that, however \(n\) pebbles are placed on the vertices of \(G\), we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Ronald Graham conjectured that for all graphs \(G\) and \(H\), \(f(G\times H)\leq f(G)\cdot f(H)\). This paper proves that this conjecture is true if \(G\) and \(H\) are trees.
0 references
pebbling graphs
0 references
product digraph
0 references
partition
0 references
pebbling number
0 references
trees
0 references
