Skip to main content
SpringerLink
Log in

Pebbling numbers of some graphs

  • Published:
Science in China Series A: Mathematics Aims and scope Submit manuscript

Abstract

Chung defined a pebbling move on a graphG as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graphG, f(G), is the leastn such that any distribution ofn pebbles onG allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphsG andH, f(G xH) ≤ f(G)f(H). In the present paper the pebbling numbers of the product of two fan graphs and the product of two wheel graphs are computed. As a corollary, Graham’s conjecture holds whenG andH are fan graphs or wheel graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chung, F. R. K., Pebbling in hyercubes, SIAM J. Discrete Math., 1989, 2: 461–472.

    Article  Google Scholar 

  2. Feng, R., Kim, J., Graham’s pebbling conjecture of product of complete bipartite graphs, Science in China, Ser. A, 2001, 44(7): 817–822.

    Article  MATH  MathSciNet  Google Scholar 

  3. Moews, D., Pebbling graphs, J. Combin. Theory, Ser. B, 1992, 55: 244–252.

    Article  MATH  MathSciNet  Google Scholar 

  4. Herscovici, D. S., Higgins, A. W., The pebbling number of C5 × C5, Discrete Math., 1998, 189: 123–135.

    Article  MathSciNet  Google Scholar 

  5. Pachter, L., Snevily, H. S., Voxman, B., On pebbling graphs, Congr. Numer., 1995, 107: 65–80.

    MATH  MathSciNet  Google Scholar 

  6. Snevily, H. S., Foster, J. A., The 2-pebbling property and a conjecture of Graham, Graphs and Combinatories, 2000, 16: 231–244.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Author notes

  1. Rongquan Feng

    Present address: School of Mathematical Sciences, Peking University, 100871, Beijing, China

Authors and Affiliations

  1. Department of Mathematics, Catholic University of Daegu, 713-702, Kyongsan, Korea

    Ju Young Kim

Authors
  1. Rongquan Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ju Young Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rongquan Feng.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Feng, R., Kim, J.Y. Pebbling numbers of some graphs. Sci. China Ser. A-Math. 45, 470–478 (2002). https://doi.org/10.1007/BF02872335

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02872335

Keywords

Search

Navigation