Premium
Maximum pebbling number of graphs of diameter three
Author(s) -
Bukh Boris
Publication year - 2006
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.20187
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , bound graph , pebble , discrete mathematics , graph power , line graph , geomorphology , geology
Abstract Given a configuration of pebbles on the vertices of a graph G , a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v . A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v . The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G . We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2) n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory