Bounds for the pebbling number of product graphs

Document Type : Research Paper

Authors

Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand

Abstract

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.

Keywords

Main Subjects

References

[1] J. Asplund, G. Hurlbert and F. Kenter, Pebbling on graph products and other binary graph constructions, Australas.
J. Combin., 71 no. 2 (2018) 246–260.
[2] F. Chung, Pebbling in hypercubes, SIAM J. Discrete Math., 2 (1989) 467–472.
[3] R. Feng and J. Y. Kim, Graham’s pebbling conjecture on product of complete bipartite graphs, Sci. China Ser. A, 44
(2001) 817–822.
[4] D. S. Herscovici and A. W. Higgins, The pebbling number of C5 × C5 , Discrete Math., 187 (1998) 123–135.
[5] G. Hurlbert, Graph pebbling, Handbook of graph theory, CRC Press, 2nd edition, Boca Raton, 2014, 1428–1454.
[6] G. Hurlbert, The graph pebbling page, http://www.people.vcu.edu/ ghurlbert/pebbling/pebb.html.
[7] W. Imrich and S. Klavzar, Product graphs: structure and recognition, Wiley-Interscience, New York, 2000.
[8] U. Knauer, Algebraic graph theory: morphisms, monoids and matrices, De Gruyter, Berlin-Boston, 2011.
[9] M. Mohorn, An introduction to graph pebbling, B. Sc. Thesis, Davidson College, May 2014.
[10] N. Pleanmani, Graham’s pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph, Discrete Math. Algorithms Appl., 11 no. 6 (2019) 1–7.
[11] N. Pleanmani, Graham’s pebbling conjecture holds for the product of a graph and a sufficiently large complete graph,
Theory Appl. Graphs, 1 (2020) 1–7.
[12] S. S. Wang, Pebbling and Graham’s conjecture, Discrete Math., 226 (2001) 431–438.
[13] D. B. West Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
Transactions on Combinatorics
Volume 11, Issue 4 - Serial Number 4
December 2022
Pages 317-326

Files

History

  • Receive Date: 15 May 2021
  • Revise Date: 23 September 2021
  • Accept Date: 01 October 2021
  • Published Online: 01 December 2022

Share

How to cite

Statistics