论文部分内容阅读
图的pebbIing数问题是近年来图论上的热点问题。在过去的二十年里,它深深地吸引着数学家们的眼球。用它可以解决一些在数论上不易解决的问题,并且它与数论有着密切的联系。图G的pebbling数f(G)是最小的整数m,使得不论m个pebbIes如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebbIe移到任意一个顶点上,其中的pebbling移动是从一个顶点处移走两个pebbles而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×日)≤f(G)f(日)。本文针对图的pebbling数进行了研究,介绍了图pebbling的研究背景;并简单介绍了图pebbling数的发展及现状,介绍了图的2-pebbling性质。在前人研究的基础上,本文重点研究了刺图和中间图的pebbling数,研究的是完全图的刺图和星图的中间图的pebbling数:求出了它们各自的pebbling数;并且验证了它们都满足2-pebbling性质;最后,证明了对于一个完全图的刺图或一个星图的中间图G和一个满足2-pebbling性质的图日的乘积来说,Graham猜想成立;并且求出了完全图的刺图乘积的pebbling数的界和星图的中间图乘积的pebbling数的界。