Pebbling in Dense Graphs
| dc.creator | Czygrinow, Andrzej | |
| dc.creator | Hurlbert, Glenn | |
| dc.date | 2004-06-07 | |
| dc.date.accessioned | 2026-07-07T05:08:57Z | |
| dc.date.available | 2026-07-07T05:08:57Z | |
| dc.description | A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. The pebbling number of a graph G is the minimum number pi(G) so that every configuration of pi(G) pebbles is solvable. A graph is Class 0 if its pebbling number equals its number of vertices. A function is a pebbling threshold for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not. Here we prove that graphs on n>=9 vertices having minimum degree at least floor(n/2) are Class 0, as are bipartite graphs with m>=336 vertices in each part having minimum degree at least floor(m/2)+1. Both bounds are best possible. In addition, we prove that the pebbling threshold of graphs with minimum degree d, with sqrt{n} << d, is O(n^{3/2}/d), which is tight when d is proportional to n. | |
| dc.description | 10 pages | |
| dc.identifier | https://arxiv.org/abs/math/0406123 | |
| dc.identifier | http://arxiv.org/abs/math/0406123 | |
| dc.identifier | Austral. J. Combin. 29 (2003), 201--208 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71466 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D05, 05C35, 05A20 | |
| dc.title | Pebbling in Dense Graphs | |
| dc.type | text |