Graph pebbling number and model

Document Type : Research Paper

Authors

Faculty of Mathematical Sciences, Yazd University, Yazd

Abstract

There are many topics in graph theory that can be called ``moving objects around a graph". For example; In network optimization, shipments are transferred from some vertices (resources) to other vertices (demand) according to the costs allocated to the edges, so that this can be done in the cheapest way. A pebble motion in a graph involves removing two pebbles from the vertex of a graph and then placing a pebble at the adjacent vertex. If a distribution (or configuration) of pebbles allows us to move at least one pebble to each vertex by repeatedly applying pebble movements, then that distribution is called a pebble of the graph. One of the most basic questions is how many pebbles are needed to ensure that any configuration with this number can target a pebble at any particular target. The smallest number of stones that meet this condition is called the graph pebble number. In this paper, after examining the roots of the number theory of the pebble graph model, which in turn is a productive subject, we will study the pebble number for specific graphs and also consider an optimization approach to this subject called weight functions.

Keywords

Main Subjects

References

[1] J. Asplund, G. Hurlbert and F. Kenter, Pebbling on graph products and other binary graph construc-tions, Australas. J. Combin., 71 (2018) 246–260.
[2] 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.
[3] Fan R. K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math., 2 (1989) 467–472.
[4] D. W. Cranston, L. Postle, Ch. Xue and C. Yerger, Modified linear programming and class 0 bounds for graph pebbling, J. Comb. Optim., 34 (2017) 114–132.
[5] B. Crull, T. Cundiff, P. Feltman, G. H. Hurlbert, L. Pudwell, Z. Szaniszlo and Z. Tuza, The cover pebbling number of graphs, Discrete Math., 296 (2005) 15–23.
[6] Ch. A. Cusack, M. Powers and A. Bekmetjev, Doppelgangers and Lemke graphs, Discrete Math., 341 (2018) 2686–2693.
[7] A. Czygrinow, G. Hurlbert, H. A. Kierstead and W. T. Trotter, A note on graph pebbling, Graphs Combin., 18 (2002) 219–225.
[8] G. Hurlbert, General graph pebbling, Discrete Appl. Math., 161 (2013) 1221–1231.
[9] G. Hurlbert, Graph pebbling, Handbook of Graph Theory, 2nd ed., Chapman and Hall/CRC, Kalamazoo, MI, 2014 1428–1449.
[10] G. Hurlbert, The weight function lemma for graph pebbling, J. Comb. Optim., 34 (2017) 343–361.
[11] F. Kenter, D. Skipper and D. Wilson, Computing bounds on product graph pebbling numbers, Theoret. Comput. Sci., 803 (2020) 160–177.
[12] G. Hurlbert and F. Kenter, Graph Pebbling: A Blend of Graph Theory, Number Theory and Optimiza-tion, Notices AMS, 68 (2021) 1900–1913.
[13] D. Moews, Pebbling graphs, J. Combin. Theory Ser. B, 55 (1992) 244–252.
[14] L. Postle, N. Streib and C. Yerger, Pebbling graphs of diameter three and four, J. Graph Theory, 72 (2013) 398–417.
Mathematics and Society
Volume 7, Issue 4 - Serial Number 4
December 2022
Pages 11-32

Files

History

  • Receive Date: 10 May 2022
  • Revise Date: 12 March 2023
  • Accept Date: 13 March 2023
  • Publish Date: 20 February 2023

Share

How to cite

Statistics