Improved pebbling bounds
- 作者：Melody Chan ; Anant P. Godbole
- 关键词：Graph pebbling ; Pebbling number ; Dominating set ; Efficient dominating set
- 刊名：Discrete Mathematics
- 出版年：2008
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：6 June 2008
- 卷：308
- 期：11
- 页码：2301-2306
- 文件大小：137 K
摘要
Consider a configuration of pebbles distributed on the vertices of a connected graph of order n. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted me="mml1">method=retrieve&_udi=B6V00-4NPG0FY-6&_mathId=mml1&_user=1067359&_cdi=5632&_rdoc=29&_acct=C000050221&_version=1&_userid=10&md5=53ce05c7e25ebeae342798fcd51ab8d0" title="Click to view the MathML source" alt="Click to view the MathML source">f(G), is the minimal number of pebbles such that every configuration of me="mml2">method=retrieve&_udi=B6V00-4NPG0FY-6&_mathId=mml2&_user=1067359&_cdi=5632&_rdoc=29&_acct=C000050221&_version=1&_userid=10&md5=b6fefb4857ad933f8e047f7ceda0227f" title="Click to view the MathML source" alt="Click to view the MathML source">f(G) pebbles on G is solvable. We derive several general upper bounds on the pebbling number, improving previous results.