Premium
Pebbling Graphs of Diameter Three and Four
Author(s) -
Postle Luke,
Streib Noah,
Yerger Carl
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21648
Subject(s) - combinatorics , mathematics , vertex (graph theory) , upper and lower bounds , graph , integer (computer science) , bound graph , discrete mathematics , graph power , line graph , computer science , mathematical analysis , programming language
Given a configuration of pebbles on the vertices of a connected graph G , a pebbling move is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v . We improve on a bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most ⌊ 3 n / 2 ⌋ + 2 , and this bound is best possible. Further, we obtain an asymptotic bound of 3 n / 2 + Θ ( 1 ) for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic bound for pebbling graphs of arbitrary diameter, namely that the pebbling number for a diameter d graph on n vertices is at most( 2 ⌈ d 2 ⌉ − 1 ) n + C ′ ( d ) , whereC ′ ( d )is a constant depending upon d . This also improves another bound of Bukh.