Mathematics and Computational Sciences

2-Restricted optimal pebbling number

Document Type : Original Article

Authors

Juma Gul Dehqan
Saeid Alikhani
Ali Delavar Khalafi
Fatemeh Aghaei

Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

https://doi.org/10.30511/mcs.2025.2050794.1291
Abstract
Let G=(V,E) be a simple graph. A pebbling configuration on G is a function f:V→Ν ∪{0} that assigns a non-negative integer number of pebbles to each vertex. The weight of a configuration f is w(f)=∪u∈ V ​f(u), the total number of pebbles.
A pebbling move consists of removing two pebbles from a vertex u and placing one pebble on an adjacent vertex v. A configuration f is a t-restricted pebbling configuration (tRPC) if no vertex has more than t pebbles. The t-restricted optimal pebbling number π*t​(G) is the minimum weight of a tRPC on G that allows any vertex to be reached by a sequence of pebbling moves.
The distinguishing number D(G) is the minimum number of colors needed to label the vertices of G such that the only automorphism preserving the coloring is the trivial one (i.e., the identity map).
In this paper, we investigate the 2-restricted optimal pebbling number of
trees T with D(T)=2 and radius at most 2 and enumerate their 2-restricted optimal pebbling configurations.
Also we study the 2-restricted optimal pebbling number of some graphs that are of importance in chemistry such as some alkanes.

Keywords

Pebbling number
Optimal pebbling number
$t$-restricted optimal pebbling number
$2$-restricted optimal pebbling configuration

Subjects

[1] Aghaei, F., & Alikhani, S. (2025), Pebbling number of polymers. Iran. J. Math. Chem., 16(1), 39-49. 
[2] Albertson, M., & Collins, K. (1996). Symmetry breaking in graphs. Electron. J. Combin., 3(1), R18. 
[3] Alikhani, S., & Aghaei, F. (2023). More on the 2-restricted optimal pebbling number. arXiv preprint, arXiv:2308.11028. 
[4] Alikhani, S., & Soltani, S. (2019). Trees with distinguishing number two. AKCE Int. J. Graphs Combin., 16(3), 280-283. 
[5] Alikhani, S., & Soltani, S. (2017). Distinguishing number and distinguishing index of Certain graphs. Filomat, 31:14, 4393-4404. 
[6] Bunde, D.P., Chambers, E.W., Cranston, D., Milans, K., & West, D.B. (2008). Pebbling and optimal pebbling in graphs. J. Graph Theory, 57, 215238. 
[7] Chellali, M., Haynes, T. W., Hedetniemi, S. T., & Lewis, T. M. (2017). Restricted optimal pebbling and domination in graphs. Discrete Appl. Math., 221, 46-53. 
[8] Chung, F.R.K. (1989). Pebbling in hypercubes. SIAM J. Disc. Math., 2(4), 467472. 
[9] Friedman, T., & Wyels, C. (2005). Optimal pebbling of paths and cycles. 
[10] Fu, H., & Shiue, C. (2000). The optimal pebbling number of the complete m-ary tree. Discrete Math., 222, 89100. 
[11] Haynes, T.W., Hedetniemi, S.T., & Henning, M.A. (Eds.). (2020). Topics in Domination in Graphs, 64, Springer. 
[12] Haynes, T.W., Hedetniemi, S.T., & Henning, M.A. (Eds.). (2021). Structures of Domination in Graphs, 66, Springer.
[13] Haynes, T.W., Hedetniemi, S.T., & Henning, M.A. (Eds.). (2023). Domination in Graphs: Core Concepts. Springer.
[14] Henning, M.A., & Yeo, A. (2013). Total domination in graphs. Springer. 
[15] Fu, H., Huang, K., & Shiue, C. (2013). A note on optimal pebbling of hypercubes. J. Comb. Optim., 25, 597601. 
[16] Herscovici, D.S. (2016). Using error-correcting codes to construct solvable pebbling distributions. Discrete Math.,339, 318326.
[17] Herscovici, D.S., Hester, B.D., & Hurlbert, G.H. (2011). Optimal pebbling in products of graphs. Australas. J. Combin., 50, 324. 
[18] Klavžar, S., & Zhu, X. (2007). Distinguishing number of Cartesian products of graphs. Graphs Combin., 23(1), 173-181. 
[19] Lemke, P., & Kleitman, D. (1989). An addition theorem on the integers modulo n. J. Number Theory, 31, 335345.
[20] Milans, K., & Clark, B. (2006). The complexity of graph pebbling. SIAM J. Discrete Math., 20, 769798. 
[21] Moews, D. (1998). Optimally pebbling hypercubes and powers. Discrete Math., 190, 271276. 
[22] Muntz, J., Narayan, S., Streib, N., & VanOchten, K. (2007). Optimal pebbling of graphs. Discrete Math., 307, 23152321.
[23] Pachtor, L., Snevily, H.S., & Voxman, B. (1995). On pebbling graphs. Congressus Numerantium, 107, 6580. 
[24] Shiue, C., & Fu, H. (2009). The optimal pebbling number of the caterpillar. TaiwaneseJ. Math., 13, 419429. 
[25] Ye, Y., Liu, M., & Gao, J. (2014). The optimal pebbling number of square of paths and cycles. Ars Combin., 114, 363371.
Mathematics and Computational Sciences
Volume 6, Issue 3
Summer 2025
Pages 23-32

  • Receive Date 15 January 2025
  • Revise Date 30 August 2025
  • Accept Date 30 August 2025

Home

Submit Manuscript

Reviewers

Contact Us