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

\(k\)-paths\(k\)-treesclass 0complexitypebbling number

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

• t-pebbling and extensions
• Handbook of graph theory
• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• scientific article; zbMATH DE number 5492403 (Why is no real title available?)
• Pebbling in diameter two graphs and products of paths
• Pebbling in Split Graphs
• 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

Cited in

(9)

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

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)