几类图的pebbling数

图G的pebbling数 f （G ）是最小的整数n ,使得不论n个pebbles如何放置在图G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebbles,而把其中的一个移到与其相邻的一个顶点上。文章给出图Fn？Pk、Wn？Pk和双轮图Wm？Pk-1？Wn的peb？bling数。     

一些乘积图的覆盖数

在图上进行小石块的移动的步骤为从一个点上取走两个小石块,并在它的某个邻点上放一个小石块.显然存在某个自然数,当图的所有点上的小石块的总数大于或等于它时,无论小石块在图上是如何初始分布的,都可以经过一系列的上述步骤,使得每个点上都至少有一个小石块.对一个图而言,满足此条件的最小的自然数即为此图的覆盖数.解决了字典乘积图和一些强乘积图的覆盖数问题,并给出了任意一个图的关键点与直径的两个端点之间的关系.     

路的中间图的最优pebbling数

图G上的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上．图G的最优pebbling数fopf（G）是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列pebbling移动把一个pebble移到任何一个指定的顶点上．本文给出了路的中间图M（Pa）的最优pebbling数．     

连通图中水晶覆盖数的一些结果

通过对简单图中水晶覆盖数的研究，给出了几类图的水晶覆盖数，部分解决了文献[2]中提出的一个开放问题，得到了连通图的水晶覆盖数的紧的界。     

刺图乘积上的Graham猜想

 证明了对于一个完全图的刺图和一个具有2-pebbling性质的图,Graham猜想成立。作为一个推论,当G和H均为完全图的刺图时,Graham猜想成立。     

图中水晶覆盖数的上下界

通过对简单图中水晶覆盖数的研究，得出了连通图G和连通图G-e间水晶覆盖数的关系，进而得到了连通图水晶覆盖数的上界和下界．     

轮图中间图的pebbling数

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.文章研究轮图中间图的pebbling数.     

中间图的pebbling数

证明路、完全图和星图三种特殊图中间图的pebbling数问题.根据生成子图的性质得到路的中间图的pebbling数为2n n-2;利用数学归纳法得到完全图的中间图的pebbling数为[n(n 1)]/2;根据Chung的定理11提出引理1,并利用引理1得到星图中间图的pebbling数为3n 3.     

C5的刺图的Pebbling数和2-Pebbling性质

连通图G的Pebbling数f(G)是最小的整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到图G任意一个目标顶点上.其中,1个Pebbling移动是从一个顶点上移走2个Pebble,而把其中一个移到与其相邻的一个顶点上,获得了C5的刺图的Pebbling...