Target Pebbling in Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909998356889600 |
|---|---|
| author | Adauto, Matheus Bardenova, Viktoriya Bidav, Yunus Hurlbert, Glenn |
| author_facet | Adauto, Matheus Bardenova, Viktoriya Bidav, Yunus Hurlbert, Glenn |
| contents | Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. A configuration $C$ is a supply of pebbles at various vertices of a graph $G$, and a distribution $D$ is a demand of pebbles at various vertices of $G$. The $D$-pebbling number, $π(G, D)$, of a graph $G$ is defined to be the minimum number $m$ such that every configuration of $m$ pebbles can satisfy the demand $D$ via pebbling moves. The special case in which $t$ pebbles are demanded on vertex $v$ is denoted $D=v^t$, and the $t$-fold pebbling number, $π_{t}(G)$, equals $\max_{v\in G}π(G,v^t)$. It was conjectured by Alcón, Gutierrez, and Hurlbert that the pebbling numbers of chordal graphs forbidding the pyramid graph can be calculated in polynomial time. Trees, of course, are the most prominent of such graphs. In 1989, Chung determined $π_t(T)$ for all trees $T$. In this paper, we provide a polynomial-time algorithm to compute the pebbling numbers $π(T,D)$ for all distributions $D$ on any tree $T$, and characterize maximum-size configurations that do not satisfy $D$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10460 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Target Pebbling in Trees Adauto, Matheus Bardenova, Viktoriya Bidav, Yunus Hurlbert, Glenn Combinatorics 05C57 (Primary), 05C05, 90B10, 91A43 (Secondary) Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. A configuration $C$ is a supply of pebbles at various vertices of a graph $G$, and a distribution $D$ is a demand of pebbles at various vertices of $G$. The $D$-pebbling number, $π(G, D)$, of a graph $G$ is defined to be the minimum number $m$ such that every configuration of $m$ pebbles can satisfy the demand $D$ via pebbling moves. The special case in which $t$ pebbles are demanded on vertex $v$ is denoted $D=v^t$, and the $t$-fold pebbling number, $π_{t}(G)$, equals $\max_{v\in G}π(G,v^t)$. It was conjectured by Alcón, Gutierrez, and Hurlbert that the pebbling numbers of chordal graphs forbidding the pyramid graph can be calculated in polynomial time. Trees, of course, are the most prominent of such graphs. In 1989, Chung determined $π_t(T)$ for all trees $T$. In this paper, we provide a polynomial-time algorithm to compute the pebbling numbers $π(T,D)$ for all distributions $D$ on any tree $T$, and characterize maximum-size configurations that do not satisfy $D$. |
| title | Target Pebbling in Trees |
| topic | Combinatorics 05C57 (Primary), 05C05, 90B10, 91A43 (Secondary) |
| url | https://arxiv.org/abs/2504.10460 |