The \(t\)-pebbling number is eventually linear in \(t\) (Q554008)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The \(t\)-pebbling number is eventually linear in \(t\) |
scientific article |
Statements
The \(t\)-pebbling number is eventually linear in \(t\) (English)
0 references
29 July 2011
0 references
Summary: In graph pebbling games, one considers a distribution of pebbles on the vertices of a graph, and a pebbling move consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The \(t\)-pebbling number \(\pi _t(G)\) of a graph \(G\) is the smallest \(m\) such that for every initial distribution of \(m\) pebbles on \(V (G)\) and every target vertex \(x\) there exists a sequence of pebbling moves leading to a distibution with at least \(t\) pebbles at \(x\). Answering a question of Sieben, we show that for every graph \(G,\, \pi _t(G)\) is eventually linear in \(t\); that is, there are numbers \(a, b, t_0\) such that \(\pi _t(G) = at + b\) for all \(t \geq t_0\). Our result is also valid for weighted graphs, where every edge \(e = \{u, v\}\) has some integer weight \(\omega (e) \geq 2\), and a pebbling move from \(u\) to \(v\) removes \(\omega (e)\) pebbles at \(u\) and adds one pebble to \(v\).
0 references
graph pebbling games
0 references