The \(t\)-pebbling number is eventually linear in \(t\)
type: Item
instance of: scholarly article
title: The \(t\)-pebbling number is eventually linear in \(t\)
zbMATH Open document ID: 1222.05188
author: Jianyong Qiao
author: Sumit K. Garg
published in: The Electronic Journal of Combinatorics
publication date: 2011-07-29T00:00:00Z
full work available at URL: https://eudml.org/doc/225996
full work available at URL: v18i1p153.html
review text: 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\).
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5933976
zbMATH Keywords: graph pebbling games
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5933976