共查询到20条相似文献,搜索用时 15 毫秒
1.
图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猜想成立. 相似文献
2.
图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猜想成立。 相似文献
3.
图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猜想成立. 相似文献
4.
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猜想成立. 相似文献
5.
广义友谊图乘积上的Graham pebbling猜想 总被引:1,自引:1,他引:0
连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立. 相似文献
6.
金芳蓉定义了图 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 猜想成立. 相似文献
7.
图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\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想. 相似文献
8.
图 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. 相似文献
9.
图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猜想成立。 相似文献
10.
如果完全二部图Km,n的边集可以划分为Km,n的Pv-因子, 则称Km,n存在Pv-因子分解. 当v是偶数时, Ushio 和 Wang 给出了Km,n存在Pv因子分解的充分必要条件. Ushio在其综述文章中提出了当v是奇数时Km,n存在Pv-因子分解的猜想. 已经证明当v=4k-1时Ushio猜想成立. 对于正整数k, 本文证明Km,n存在P4k+1-因子分解的充分必要条件是: (1) 2km ≤ (2k+1)n, (2) 2kn ≤ (2k+1)m, (3) m+n ≡0 (mod 4k+1), (4) (4k+1)mn/[4k(m+n)]是整数. 即证明: 对于任何正整数k, 当v=4k+1时Ushio猜想成立,从而最终完成了Ushio猜想成立的证明. 相似文献
11.
12.
如果完全二部图Km,n的边集可以划分为Km,n的Pv-因子,则称Km,n存在Pv-因子分解. 当v是偶数时, Ushio和Wang 给出了Km,n存在Pv-因子分解的充分必要条件. Ushio同时提出了当v是奇数时Km,n存在Pv-因子分解的猜想, 但是至今为止仅知当v=3时Ushio猜想成立. 对于正整数k,本文证明Km,n存在P4k8722;1-因子分解的充分必要条件是: (1) (2k8722;1)m ≤2kn, (2) (2k8722;1)n ≤ 2 km, (3) m+n ≡ 0 (mod 4k8722;1), (4) (4k8722;1)mn/[2(2k8722;1)(m+n)]是整数. 即证明了对于任意正整数k, 当v=4k8722;1时Ushio猜想成立. 相似文献
13.
图G的交叉数是刻画图的非平面性的一个重要参数.它是指图G在平面上的所有画法中边与边之间交叉数目的最小值.确定具体图类的交叉数是图的交叉数问题中一个经典的研究方向.Zarankiewicz于1954年提出了完全二部图交叉数的猜想:■.1971年,Kleitman证明了当min{m,n}≤6时,上式成立.由于其难度,完全二部图交叉数的研究进展是较缓慢的.至今,完全二部图K7,n(n≥11)的交叉数都还未确定.然而,我们发现研究近完全二部图的交叉数可了解在完全二部图中加边与完全二部图交叉数的增长程度之间的关系.因此,为了促进完全二部图交叉数的研究,本文借助旋系与交叉数之间的关系、图的结构性质以及图的顶点度局部修改法确定了五个近完全二部图的交叉数. 相似文献
14.
15.
16.
17.
本主要从理论上讨论赋权二部图的权的变化对最优解的影响,并在原最大权匹配的基础上给出求解权值变化后的最大权匹配的算法。 相似文献
18.
19.
在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD),并提出了一个猜想:任意有正数条边的图都可以升分解.本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解,其中Hm2是至多含m2条边的Km1m2的子图. 相似文献
20.
确定图的交叉数是NP-完全问题.目前有关完全二部图与星图的积图的交叉数结果并不多.引入了一些新的收缩技巧,建立了积图K3,3□Sn与完全三部图K3,3□Sn之间的交叉数关系.从而,为进一步完全确定积图K3,3□Sn的交叉数提供了一条新途径. 相似文献