The Complexity of Graph Pebbling

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We explore the complexity of computing the optimal pebbling number and pebbling number of a graph. We show that deciding whether the optimal pebbling number of G is at most k is NP-complete and deciding whether the pebbling number of G is at most k is Π_2-complete. Additionally, we provide a characterization of when an unordered set of pebbling moves can be ordered to form a valid sequence of pebbling moves.
24 pages, 6 figures

Keywords

Combinatorics, 05C99, 68Q17

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74724

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0503698
 http://arxiv.org/abs/math/0503698

Collections

arXiv