Modified linear programming and class 0 bounds for graph pebbling

Daniel W. Cranston (), Luke Postle (), Chenxiao Xue () and Carl Yerger ()
Additional contact information
Daniel W. Cranston: Virginia Commonwealth University
Luke Postle: University of Waterloo
Chenxiao Xue: Davidson College
Carl Yerger: Davidson College

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 7, 114-132

Abstract: Abstract Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble 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. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least $$\frac{5}{3}n - \frac{11}{3}$$ 5 3 n - 11 3 edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to $$2n - 5$$ 2 n - 5 , which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.

Keywords: Pebbling; Class 0; Linear programming; Lemke (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0060-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:1:d:10.1007_s10878-016-0060-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0060-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().