Optimal pebbling of graphs

被引：7

作者：

Muntz, Jessica ^{[1
]}

Narayan, Sivaram

Streib, Noah

Van Ochten, Kelly

机构：

[1] Cent Michigan Univ, Dept Math, Mt Pleasant, MI 48858 USA

[2] Oberlin Coll, Dept Math, Oberlin, OH 44074 USA

来源：

DISCRETE MATHEMATICS | 2007年 / 307卷 / 17-18期

关键词：

simple graph; diameter; optimal pebbling number; bounds;

D O I：

10.1016/j.disc.2006.11.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Consider a distribution of pebbles on the vertices of a graph G. A pebbling move consists of the removal of two pebbles from a vertex and then placing one pebble at an adjacent vertex. The optimal pebbling number of G, denoted f(opt) (G), is the least number of pebbles, such that for some distribution of f(opt)(G) pebbles, a pebble can be moved to any vertex of G. We give sharp lower and upper bounds for f(opt)(G) for G of diameter d. For graphs of diameter two (respectively, three) we characterize the classes of graphs having f(opt)(G) equal to a value between 2 and 4 (respectively, between 3 and 8). (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：2315 / 2321

页数：7