ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Optimal t-pebbling on paths and cycles

  • School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Funds:  Supported by the Fundamental Research Funds for the Central Universities and the NNSF of China (61272008,11271348,10871189).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2015.03.002
More Information
  • Author Bio:

    XIA Zhengjiang, male, born in 1987, PhD candidate. Research field: combinatorics and graph theory.

  • Corresponding author: PAN Yongliang
  • Received Date: 14 November 2014
  • Accepted Date: 10 March 2015
  • Rev Recd Date: 10 March 2015
  • Publish Date: 30 March 2015
    Abstract

  • Abstract

    A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbours. For t≥1, the optimal t-pebbling number of a graph G, f′t(G), is the minimum number of pebbles necessary so that from some initial distribution of them it is possible to move t pebbles to any target vertex by a sequence of pebbling moves. f′(G)=f′1(G) be the optimal pebbling number of G. Here the optimal t-pebbling numbers of the path Pn and the cycle C5 were given, respectively. In the final section, it was obtained that f′9t(P2×P3)=20t, f′9t+1(P2×P3)=20t+3, and 20t+2r+1≤f′9t+r(P2×P3)≤20t+2r+2, for 2≤r≤8, the last equality holds for r=5,6,7,8.

    Abstract

    A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbours. For t≥1, the optimal t-pebbling number of a graph G, f′t(G), is the minimum number of pebbles necessary so that from some initial distribution of them it is possible to move t pebbles to any target vertex by a sequence of pebbling moves. f′(G)=f′1(G) be the optimal pebbling number of G. Here the optimal t-pebbling numbers of the path Pn and the cycle C5 were given, respectively. In the final section, it was obtained that f′9t(P2×P3)=20t, f′9t+1(P2×P3)=20t+3, and 20t+2r+1≤f′9t+r(P2×P3)≤20t+2r+2, for 2≤r≤8, the last equality holds for r=5,6,7,8.
    • FullText(HTML)
  • loading
    • References(8)
  • [1]
    Bunde D P, Chambers E W, Cranston D. Pebbling and optimal pebbling in graphs[J]. J Graph Theory, 2008, 57: 215-238.
    [2]
    Chung F R K. Pebbling in hypercubes[J]. SIAM J Discrete Math, 1989, 2(4): 467-472.
    [3]
    Friedman T, Wyels C. Optimal pebbling of paths and cycles[DB/OL]. arXiv, 2003: arXiv: math/0506076.
    [4]
    Hersovici D, Hester B D, Hurlbert G H. Optimal pebbling in products of graphs[J]. Australasian Journal of Combinatorics, 2011, 50: 3-24.
    [5]
    Hersovici D, Hester B D, Hurlbert G H. t-pebbling and extentions[J]. Graphs and Combinatorics, 2013, 29: 955-975.
    [6]
    Hoffmann M, Matousek J, Okamoto Y. The t-pebbling number is eventually linear in t[J]. The Electronic Journal of Combinatorics, 2011, 18: 153-156.
    [7]
    Moews D. Pebbling graphs[J]. J Combin Theory, Ser B, 1992, 55: 244-252.
    [8]
    Pachter L, Snevily H S, Voxman B. On pebbling graphs[J]. Congr Numer, 1995, 107: 65-80.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Bunde D P, Chambers E W, Cranston D. Pebbling and optimal pebbling in graphs[J]. J Graph Theory, 2008, 57: 215-238.
    [2]
    Chung F R K. Pebbling in hypercubes[J]. SIAM J Discrete Math, 1989, 2(4): 467-472.
    [3]
    Friedman T, Wyels C. Optimal pebbling of paths and cycles[DB/OL]. arXiv, 2003: arXiv: math/0506076.
    [4]
    Hersovici D, Hester B D, Hurlbert G H. Optimal pebbling in products of graphs[J]. Australasian Journal of Combinatorics, 2011, 50: 3-24.
    [5]
    Hersovici D, Hester B D, Hurlbert G H. t-pebbling and extentions[J]. Graphs and Combinatorics, 2013, 29: 955-975.
    [6]
    Hoffmann M, Matousek J, Okamoto Y. The t-pebbling number is eventually linear in t[J]. The Electronic Journal of Combinatorics, 2011, 18: 153-156.
    [7]
    Moews D. Pebbling graphs[J]. J Combin Theory, Ser B, 1992, 55: 244-252.
    [8]
    Pachter L, Snevily H S, Voxman B. On pebbling graphs[J]. Congr Numer, 1995, 107: 65-80.
    Recommended articles
    TrendMD
    Volume 45 Issue 3 page: 186-192
    Cover

    Article Metrics

    Article views (35) PDF downloads(68)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return