完全$r$部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).本文证明对于一个完全γ部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立.作为一个推论,当G和H均为完全γ部图时,Graham猜想成立.

GRAHAM'S CONJECTURE ON COMPLETE $r$-PARTITE GRAPHS

The pebbling number of a graph $G, f(G)$, is the least $n$ such that, however $n$ pebbles are placed on the vertices of $G$, a pebble can be moved to any vertex by a sequence of pebbling moves, each pebbling move taking two pebbles from one vertex and placing one on an adjacent vertex. Ronald Graham conjectured that for all contected graphs $G$ and $H$, $f(G\times H)\leq f(G)f(H)$. In this paper we prove that the conjecture holds when $G$ is a complete $r$-partite graph and $H$ satifies the $2-pebbling$ property. As a conclusion, it is obtained that Graham's conjecture holds if $G$ and $H$ are complete multipartite graphs.