DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in press

Authors:

T.M. Lewis

Thomas Michael Lewis

Furman University

email: tom.lewis@furman.edu

F. Salinas

Fabian Salinas

Department of Mathematics
Vanderbilt University
Nashville, TN, 37212

email: fabian.salinas@Vanderbilt.edu

Title:

Optimal pebbling of complete binary trees and a meta-Fibonacci sequence

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2023-06-09 , Revised: 2024-07-06 , Accepted: 2024-07-07 , Available online: 2024-09-03 , https://doi.org/10.7151/dmgt.2556

Abstract:

In 1999, Fu and Shiue published a paper on optimal pebblings of complete $m$-ary trees. Among other things, they produced OPCBT, an integer linear program that produces an optimal pebbling of a complete binary tree. Building upon their work, we give an explicit representation of the optimal pebbling number of a complete binary tree. Among other things, we show that the sequence of optimal pebbling numbers of complete binary trees indexed by their heights is related to the Conolly sequence, a type of meta-Fibonacci sequence.

Keywords:

optimal pebbling, complete binary tree, meta-Fibonacci sequence

References:

  1. R.A. Beeler, T.W. Haynes and K. Murphy, $1$-restricted optimal rubbling on graphs, Discuss. Math. Graph Theory 39 (2019) 575–588.
    https://doi.org/10.7151/dmgt.2102
  2. R.A. Beeler, T.W. Haynes, M.A. Henning and R. Keaton, Total domination cover rubbling, Discrete Appl. Math. 283 (2020) 133–141.
    https://doi.org/10.1016/j.dam.2019.12.020
  3. R.A. Beeler, T.W. Haynes and R. Keaton, Domination cover rubbling, Discrete Appl. Math. 260 (2019) 75–85.
    https://doi.org/10.1016/j.dam.2019.01.037
  4. C. Belford and N. Sieben, Rubbling and optimal rubbling of graphs, Discrete Math. 309 (2009) 3436–3446.
    https://doi.org/10.1016/j.disc.2008.09.035
  5. 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
  6. F.R.K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math. 2 (1989) 467–472.
    https://doi.org/10.1137/0402041
  7. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms (MIT Press, Cambridge, MA, 2009).
  8. C.A. Cusack, M. Powers and A. Bekmetjev, Doppelgangers and Lemke graphs, Discrete Math. 341 (2018) 2686–2693.
    https://doi.org/10.1016/j.disc.2018.06.028
  9. C.A. Cusack, A. Bekmetjev and M. Powers, Two-pebbling and odd-two-pebbling are not equivalent, Discrete Math. 342 (2019) 777–783.
    https://doi.org/10.1016/j.disc.2018.10.030
  10. A. Czygrinow, G. Hurlbert, G.Y. Katona and L.F. Papp, Optimal pebbling number of graphs with given minimum degree, Discrete Appl. Math. 260 (2019) 117–130.
    https://doi.org/10.1016/j.dam.2019.01.023
  11. H.-L. Fu and C.-L. Shiue, The optimal pebbling number of the complete m-ary tree, Discrete Math. 222 (2000) 89–100.
    https://doi.org/10.1016/S0012-365X(00)00008-X
  12. Z.-T. Gao and J.-H. Yin, The optimal pebbling of spindle graphs, Open Math. 17 (2019) 582–587.
    https://doi.org/10.1515/math-2019-0094
  13. E. Győri, G.Y. Katona, F.L. Papp and C. Tompkins, The optimal pebbling number of staircase graphs, Discrete Math. 342 (2019) 2148–2157.
    https://doi.org/10.1016/j.disc.2018.06.042
  14. E. Győri, G.Y. Katona and L.F. Papp, Optimal pebbling number of the square grid, Graphs Combin. 36 (2020) 803–829.
    https://doi.org/10.1007/s00373-020-02154-z
  15. E. Győri, G.Y. Katona and F.L. Papp, Optimal pebbling and rubbling of graphs with given diameter, Discrete Appl. Math. 266 (2019) 340–345.
    https://doi.org/10.1016/j.dam.2018.06.014
  16. D.S. Herscovici, B.D. Hester and G.H. Hurlbert, Optimal pebbling in products of graphs, Australas. J. Combin. 50 (2011) 3–24.
  17. G. Hurlbert, General graph pebbling, Discrete Appl. Math. 161 (2013) 1221–1231.
    https://doi.org/10.1016/j.dam.2012.03.010
  18. Y. Li and Y. Ye, The $2$-pebbling property of squares of paths and Graham's conjecture, Open Math. 18 (2020) 87–92.
    https://doi.org/10.1515/math-2020-0009
  19. A. Lourdusamy and T. Mathivanan, The domination cover pebbling number for some cyclic graphs and path graphs, Ars Combin. 138 (2018) 51–61.
  20. L. Pachter, H.S. Snevily and B. Voxman, On pebbling graphs, Congr. Numer. 107 (1995) 65–80.
  21. C.-L. Shiue, Distance restricted optimal pebbling in cycles, Discrete Appl. Math. 279 (2020) 125–133.
    https://doi.org/10.1016/j.dam.2019.10.017
  22. C.-L. Shiue, Capacity restricted optimal pebbling in graphs, Discrete Appl. Math. 260 (2019) 284–288.
    https://doi.org/10.1016/j.dam.2019.01.002
  23. C.-L. Shiue and H.-L. Fu, The optimal pebbling number of the caterpillar, Taiwanese J. Math. 13 (2009) 419–429.
    https://doi.org/10.11650/twjm/1500405346
  24. C.-L. Shiue, H.-H. Chiang, M.-M. Wong and H.M. Srivastava, The optimal t-pebbling number of a certain complete m-ary tree, Rev. R. Acad. Cienc. Exactas F\'{\i}s. Nat. Ser. A Mat. RACSAM 113 (2019) 2889–2910.
    https://doi.org/10.1007/s13398-018-0503-2
  25. N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences (2024).
    https://oeis.org
  26. C. Xue and C. Yerger, Optimal pebbling on grids, Graphs Combin. 32 (2016) 1229–1247.
    https://doi.org/10.1007/s00373-015-1615-5
  27. Y. Ye, M. Liu and J. Gao, The optimal pebbling number of square of paths and cycles, Ars Combin. 114 (2014) 363–371.
Close