Skip to main content
SpringerLink
Log in

Graham’s pebbling conjecture on product of complete bipartite graphs

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

Abstract

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite 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 hypercubes, SIAM J. Discrete Math., 1989, 2: 461–472.

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Peking University, 100871, Beijing, China

    Rongquan Feng

  2. Department of Mathematics, Catholic University of Taegu-Kyongsan, 713-702, 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. Graham’s pebbling conjecture on product of complete bipartite graphs. Sci. China Ser. A-Math. 44, 817–822 (2001). https://doi.org/10.1007/BF02880130

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation