Pebbling Number of Polymers

Document Type : Research Paper

Authors

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

10.22052/ijmc.2024.254873.1864

Abstract

‎Let $G=(V,E)$ be a simple graph‎. A function $f:V\rightarrow \mathbb{N}\cup \{0\}$ is called a configuration of pebbles on the vertices of $G$ and the quantity $\vert f\vert=\sum_{u\in V}f(u)$‎ ‎is called the weight of $f$ which is just the total number of pebbles assigned to vertices‎. ‎A pebbling step from a vertex $u$ to one of its‎ neighbors $v$ reduces $f(u)$ by two and increases $f(v)$ by one‎. ‎A pebbling configuration $f$ is said to be solvable if for every vertex $ v $‎, ‎there exists a sequence (possibly empty) of pebbling moves that results in a pebble on $v$‎. ‎The pebbling number $ \pi(G) $ equals the minimum number $ k $ such that every pebbling configuration $ f $ with $ \vert f\vert = k $ is solvable‎. Let $ G $ be a connected graph constructed from pairwise disjoint connected graphs $ G_1,...,G_k $ by selecting a vertex of $ G_1 $‎, ‎a vertex of $ G_2 $‎, ‎and identifying these two vertices‎. ‎Then continue in this manner inductively‎. ‎We say that $ G $ is a polymer graph‎, ‎obtained by point-attaching from monomer units $ G_1,...,G_k $‎. In this paper‎, ‎we study the pebbling number of some polymers‎. ‎

Keywords

Main Subjects

References

[1] F. R. K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math. 2 (1989) 467–472, https://doi.org/10.1137/0402041.
[2] L. Pachter, H. S. Snevily and B. Voxman, On pebbling graphs, Congr. numer 107 (1995) 65–80.
[3] K. Milans and B. Clark, The complexity of graph pebbling, SIAM J. Discrete Math. 20 (2006) 769–798, https://doi.org/10.1137/050636218.
[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi and T. M. Lewis, Restricted optimal pebbling and domination in graphs, Discrete Appl. Math. 221 (2017) 46–53, https://doi.org/10.1016/j.dam.2016.12.029.
[5] S. Alikhani and N. Ghanbari, Sombor index of polymers, MATCH Commun. Math. Comput. Chem. 86 (2021) 715–728.
[6] S. Alikhani and S. Soltani, The distinguishing number and the distinguishing index of graphs from primary subgraphs, Iranian J. Math. Chem. 10 (2019) 223–240, https://doi.org/ 10.22052/IJMC.2019.152413.1400.
[7] S. Bou, A. S. Klymchenko and M. Collot, Fluorescent labeling of biocompatible block copolymers: synthetic strategies and applications in bioimaging, Mater. Adv. 2 (2021) 3213–3233, https://doi.org/10.1039/D1MA00110H.
[8] S. Alikhani and F. Aghaei, More on graph pebbling number, arXiv:2402.10017v1 [math.CO], submitted,
[9] H. S. Snevily and J. A. Foster, The 2-pebbling property and a conjecture of Graham’s, Graphs Combin. 16 (2000) 231–244, https://doi.org/10.1007/PL00021179.
[10] D. S. Herscovici, Graham’s pebbling conjecture on products of cycles, J. Graph Theory 42 (2003) 141–154, https://doi.org/10.1002/jgt.10080.
[11] S. Alikhani and F. Aghaei, More on the 2-restricted optimal pebbling number, arXiv:2308.11028v1 [math.CO], submitted.
[12] S. Alikhani, S. Jahari, M. Mehryar and R. Hasni, Counting the number of dominating sets of cactus chains, Optoelectron. Adv. Mater. Rapid Commun. 8 (2014) 955–960.
[13] D. P. Bunde, E. W. Chambers, D. Cranston, K. Milans and D. B. West, Pebbling and optimal pebbling in graphs, J. Graph Theory 57 (2008) 215–238.
[14] G. Hurlbert, The weight function lemma for graph pebbling, J. Comb. Optim. 34 (2017) 343–361, https://doi.org/10.1007/s10878-016-9993-z.
[15] E. Deutsch and S. Klavzar, Computing Hosoya polynomials of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 627–644.
Iranian Journal of Mathematical Chemistry
Volume 16, Issue 1
In progress
March 2025
Pages 39-49

Files

Share

How to cite

Statistics