Pebbling in Powers of Paths

DOI10.1016/J.DISC.2023.113315MaRDI QIDQ6386032arXivFDO

Authors L. Alcón, Glenn H. Hurlbert

Publication date 17 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2023.113315

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

arXiv classification

math.CO

Abstract: The $t$-fold pebbling number, $p{i}_t(G)$, of a graph $G$ is defined to be the minimum number $m$ so that, from any given configuration of $m$ pebbles on the vertices of $G$, it is possible to place at least $t$ pebbles on any specified vertex via pebbling moves. It has been conjectured that the pebbling numbers of pyramid-free chordal graphs can be calculated in polynomial time. The $k^{mth}$ power $G^{(k)}$ of the graph $G$ is obtained from $G$ by adding an edge between any two vertices of distance at most $k$ from each other. The $k^{mth}$ power of the path $P_n$ on $n$ is an important class of pyramid-free chordal graphs. Pachter, Snevily, and Voxman (1995), Kim (2004), and Kim and Kim (2010) calculated $pi(P_n^{(k)})$ for $2lekle4$, respectively. In this paper we calculate $p{i}_t(P_n^{(k)})$ for all $n$, $k$, and $t$. For a function $D:V(G)ightarrowmathbbN$, the $D$-pebbling number, $pi(G,D)$, of a graph $G$ is defined to be the minimum number $m$ so that, from any given configuration of $m$ pebbles on the vertices of $G$, it is possible to place at least $D(v)$ pebbles on each vertex $v$ via pebbling moves. We make the conjecture that every $G$ and $D$ satisfies $pi(G,D)lep{i}_{|D|}(G)-(s(D)-1)$, where $s(D)$ counts the number of vertices $v$ with $D(v)>0$. We prove this for trees and $P_n^{(k)}$, for all $n$ and $k$. The pebbling exponent $e_{p}i(G)$ of a graph $G$ was defined by Pachter, et al., to be the minimum $k$ for which $pi(G^{(k)})=n(G^{(k)})$. Of course, $e_{p}i(G)lemdiameter(G)$, and Czygrinow, Hurlbert, Kierstead, and Trotter (2002) proved that almost all graphs $G$ have $e_{p}i(G)=1$. Lourdusamy and Mathivanan (2015) proved several results on $p{i}_t(C_n^2)$, and Hurlbert (2017) proved an asymptotically tight formula for $e_{p}i(C_n)$. Our formula for $p{i}_t(P_n^{(k)})$ allows us us to compute $e_{p}i(P_n)$ asymptotically tightly.

This page was built for publication: Pebbling in Powers of Paths

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