TY - JOUR
ID - 25997
TI - Bounds for the pebbling number of product graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Pleanmani, Nopparat
AU - Nupo, Nuttawoot
AU - Worawiset, Somnuek
AD - Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand
Y1 - 2022
PY - 2022
VL - 11
IS - 4
SP - 317
EP - 326
KW - Graph pebbling
KW - Graham's conjecture
KW - product graph
KW - corona
DO - 10.22108/toc.2021.128705.1855
N2 - Let $G$ be a connected graph. Given a configuration of a fixed number of pebbles on the vertex set of $G$, a pebbling move on $G$ is the process of removing two pebbles from a vertex and adding one pebble on an adjacent vertex. The pebbling number of $G$, denoted by $\pi(G)$, is defined to be the least number of pebbles to guarantee that there is a sequence of pebbling movement that places at least one pebble on each vertex $v$, for any configuration of pebbles on $G$. In this paper, we improve the upper bound of $\pi(G\square H)$ from $2\pi(G)\pi(H)$ to $\left(2-\frac{1}{\min\{\pi(G),\pi(H)\}}\right)\pi(G)\pi(H)$ where $\pi(G)$, $\pi(H)$ and $\pi(G\square H)$ are the pebbling number of graphs $G$, $H$ and the Cartesian product graph $G\square H$, respectively. Moreover, we also discuss such bound for strong product graphs, cross product graphs and coronas.
UR - https://toc.ui.ac.ir/article_25997.html
L1 - https://toc.ui.ac.ir/article_25997_501663d1ee8baceb41a23ea159ff00d0.pdf
ER -