A Note on Graph Pebbling
| dc.creator | Czygrinow, Andrzej | |
| dc.creator | Hurlbert, Glenn | |
| dc.creator | Kierstead, Hal | |
| dc.creator | Trotter, Tom | |
| dc.date | 2004-06-03 | |
| dc.date.accessioned | 2026-07-07T05:08:50Z | |
| dc.date.available | 2026-07-07T05:08:50Z | |
| dc.description | We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let k(d) denote the least positive integer so that every graph G with diameter at most d and connectivity at least k(d) is Class 0. The existence of the function k was conjectured by Clarke, Hochberg and Hurlbert, who showed that if the function k exists, then it must satisfy k(d)=Ω(2^d/d). In this note, we show that k exists and satisfies k(d)=O(2^{2d}). We also apply this result to improve the upper bound on the random graph threshold of the Class 0 property. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/math/0406053 | |
| dc.identifier | http://arxiv.org/abs/math/0406053 | |
| dc.identifier | Graphs and Combinatorics 18 (2002), 219--225 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71419 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35 | |
| dc.title | A Note on Graph Pebbling | |
| dc.type | text |