Pebbling in 2-paths

DOI10.1016/J.ENDM.2015.07.025zbMATH Open1347.05120arXiv1604.04045OpenAlexW2196828444MaRDI QIDQ324757FDOQ324757

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

Publication date: 17 October 2016

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.

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

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

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)

Cites Work

• \(t\)-pebbling and extensions
• Title not available (Why is that?)
• The Complexity of Graph Pebbling
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• Handbook of graph theory
• Pebbling in Split Graphs
• Pebbling in diameter two graphs and products of paths
• The Complexity of Pebbling in Diameter Two Graphs
• Title not available (Why is that?)

Cited In (8)

• Pebbling on Graph Products and other Binary Graph Constructions
• The weight function lemma for graph pebbling
• Title not available (Why is that?)
• About paths with two blocks
• On the target pebbling conjecture
• 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)