圈的中间图pebbling数和Graham猜想

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的1个pebble移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动,把1个pebble移到图G的任意一个顶点上.图G的中间图M(G)就是在G的每一条边上插入一个新点,再把G上相邻边上的新点用一条边连接起来的图.对于任意两个连通图G和H,Graham猜测f(G×H)≤f(G)f(H).首先研究了圈的中间图的pebbling数,然后讨论了一些圈的中间图满足Graham猜想.

几类二部图的pebbling数

Chung定义了图G上的一个pebbling移动是从一个顶点移走两个pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).作者们验证了三类二部图的2-pebbling性质以及当H为此类二部图,G为一个2-pebbling性质的图时,Graham猜想成立.

多扇图的Pebbling数和Graham猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)≤f(G)f(H)。多扇图Fn1,n2,…,nm是指阶为n1+n2+…+nm+1的联图P1∨(Pn1∪Pn2∪…∪Pnm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图Fn1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。

路和圈的最优一般Pebbling数

图G的一个一般pebbling移动是从一个顶点移走p(p≥2)个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的一般pebbling数fgl(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列一般pebbling移动把一个pebble移到图G的任意一个顶点上.图G的一个分布是可解的,当通过一系列一般pebbling移动,能把一个pebble移到其任意一个顶点上.图G的最优一般pebbling数fgl'(G)是可解分布中最小的,即利用fgl'(G)个pebble以构造一个可解分布,且这时需要的pebble个数最少.本文采用反证法,通过去掉一个顶点,改变路(或圈)为其子图,并选择一个可解分布.而这时所用的pebble数要比其最优一般pebbling数小,得到矛盾,这样就证明了路和圈的最优一般pebbling数.

轮图中间图的pebbling数

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

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

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

C_3×C_n的最优pebbling数

图G上的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上.图G的最优pebbling数fopt(G)是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任何一个指定的顶点上.本文给出了C3×Cn的最优pebbling数.

路和偶圈中间图的一般Pebbling数

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

P_2×P_n的最优pebbling数(英文)

一个pebbling移动是从一个顶点移走两个pebbles,而把其中的一个移到与其相邻的一个顶点上.图G的最优pebbling数fopt(G)是最小的正整数n,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任何一个指定的顶点v上.文章给出了一个比较简单的P2×Pn的最优pebbling数的证明.

几类图的pebbling数

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

扇图的一般Pebbling数

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

圈的强刺图的最优Pebbling数

图G上的一个pebbling移动是从一个顶点处移走两个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的最优pebbling数f'(G)是指最小的整数p,满足从G的p个pebble的某种放置方式开始,总可以通过一系列的pebbling移动把一个pebble移到G的任一个顶点v上.文章主要研究圈的强刺图Cn**的最优pebbling数.

星形图乘积的pebbling数

图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.

直径粘接图的pebbling数

图G的pebbling数f(G)是指在一个图G的顶点上以任意方式放置若干个pebble数目的最小值,满足通过一系列的pebbling移动使得任一指定目标顶点能得到一个pebble,而pebbling移动是从一个顶点处移走两个pebble并把其中的一个移到与其相邻的一个顶点上.文章定义了将两个图的直径端点之一粘接生成的一类粘接图,主要计算了一些粘接图的pebbling数,发现了两类满足pebbling数直径下界的图.

完全二部图的t-pebbling数

图G的t-pebbling数ft(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列pebbling移动把t个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点上移走两个pebble,而把其中的一个移到与其相邻的一个顶点上,本文确定了完全二部图t-pebbling数,作为推论给出了完全K部图的t-pebbling数。

几类图的pebbling数

金芳蓉定义了图G上的一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).计算了两个扇图的积和两个轮图的积的pebbling数,作为推论,当G和H同时是扇图或轮图时,Graham猜想成立.

路的中间图的最优pebbling数

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

完全二部图乘积上的Graham pebbling猜想

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

关于0类图的一个注记

在图G的顶点上放置一些Pebble,图G的一个Pebbling移动是从一个顶点移走两个Pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的Pebbling数f(G)是最小的正整数n,使得不管n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把一个Pebble移到图G的任意一个顶点上.Graham猜测:对于任意的连通图G和H,有f(G×H)≤f(G)f(H).若f(G)=|V(G)|,称G是0类的(Class 0).证明了有关0类图的一个结果.作为推论,得到了P×C5和P×P都是0类图,其中P是Petersen图.

完全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)。本文证明对于一个完全r部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立。作为一个推论,当G和H均为完全r部图时,Graham猜想成立。