The optimal pebbling number of the complete \(m\)-ary tree
type: Item
instance of: scholarly article
title: The optimal pebbling number of the complete \(m\)-ary tree
zbMATH Open document ID: 0982.05037
DOI: 10.1016/S0012-365X(00)00008-X
author: Hung-Lin Fu
author: Chin-Lin Shiue
published in: Discrete Mathematics
publication date: 2002-04-08T00:00:00Z
review text: A distribution \(\delta\) of pebbles onto the vertices of a graph \(G\) is called a configuration of \(G\) where \(\delta_G\) denotes the number of pebbles of \(\delta\). A pebbling move consists of removing two pebbles from a vertex and placing one pebble on an adjacent vertex. If, for any vertex \(v\) of \(G\), there exists a sequence of pebbling moves, starting from the configuration \(\delta\), which allows us to place at least one pebble on \(v\), then \(\delta\) is called a pebbling of \(G\). The optimal pebbling number \(f'(G)\) of \(G\) is given by \(f'(G)= \min\{\delta_G\mid\delta\) is a pebbling of \(G\}\). The optimal pebbling number of a path was determined by \textit{L. Pachter}, \textit{H. S. Snevily} and \textit{B. Voxman} [Congr. Numerantium 107, 65-80 (1995; Zbl 0895.05063)]. Let \(T^m_h\) denote the complete \(m\)-ary tree of height \(h\). In this paper, the authors show that \(f'(T^m_h)= 2^h\) for \(m\geq 3\) and that \[ f'(T^2_h)= \min \sum^h_{i=0} 2^i x_i\quad\text{subject to}\quad \sum^h_{i=0} \Biggl(2^i-{1\over 3}\Biggr) x_i\geq {2^{h+1}\over 3}, \] where \(x_0\in \{0,1,2,3\}\) and \(x_i\in \{0,2\}\) for \(1\leq i\leq h\). An efficient algorithm solving this last integer linear programming problem is also given.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1506820
zbMATH Keywords: pebbles
zbMATH Keywords: configuration
zbMATH Keywords: pebbling move
zbMATH Keywords: optimal pebbling number
zbMATH Keywords: complete \(m\)-ary tree
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00008-x
OpenAlex ID: W1983834820
Recommended article: The Complexity of Graph Pebbling
Recommended article: Optimal t-rubbling on complete graphs and paths
Recommended article: The optimal \(t\)-pebbling number of a certain complete \(m\)-ary tree
Recommended article: Optimal pebbling of graphs
Recommended article: Q3462997
Recommended article: Optimal pebbling number of graphs with given minimum degree
Recommended article: Pebbling and optimal pebbling in graphs
Recommended article: Q4982940
Recommended article: Q3823140
description: scientific article; zbMATH DE number 1506820