Pebbling in 2-paths

DOI10.1016/J.ENDM.2015.07.025MaRDI QIDQ324757zbMATH OpenOpenAlexFDO

Authors L. Alcón, M. Gutierrez, Glenn H. Hurlbert

Publication date 17 October 2016

Full work available at URL https://arxiv.org/abs/1604.04045

zbMATH Keywords

complexity\(k\)-trees\(k\)-pathsclass 0pebbling number

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57) Traffic problems in operations research (90B20)

Abstract: Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is $sfNP$-complete, even for diameter two graphs, and deciding whether the pebbling number has a prescribed upper bound is $P{i}_2^{sfP}$-complete. Recently we proved that the pebbling number of a split graph can be computed in polynomial time. This paper advances the program of finding other polynomial classes, moving away from the large tree width, small diameter case (such as split graphs) to small tree width, large diameter, continuing an investigation on the important subfamily of chordal graphs called $k$-trees. In particular, we provide a formula, that can be calculated in polynomial time, for the pebbling number of any semi-2-tree, falling shy of the result for the full class of 2-trees.

Recommendations

• Pebbling in semi-2-trees
• Pebbling in Split Graphs
• The complexity of pebbling in diameter two graphs
• The Complexity of Graph Pebbling
• t-pebbling and extensions

Cites work

• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• scientific article; zbMATH DE number 5492403 (Why is no real title available?)
• Handbook of graph theory
• Pebbling in Split Graphs
• Pebbling in diameter two graphs and products of paths
• The Complexity of Graph Pebbling
• The complexity of pebbling in diameter two graphs
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• t-pebbling and extensions

Cited in

(9)

• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• The weight function lemma for graph pebbling
• scientific article; zbMATH DE number 3952825 (Why is no real title available?)
• About paths with two blocks
• On the target pebbling conjecture
• Pebbling on graph products and other binary graph constructions
• Graph pebbling algorithms and Lemke graphs
• Pebbling in powers of paths
• Pebbling in semi-2-trees

This page was built for publication: Pebbling in 2-paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324757)