共查询到20条相似文献,搜索用时 46 毫秒
1.
徐济超 《数学的实践与认识》1991,(1)
记 Ω(G)和π(G)分别为图 G 的全体支撑树和全体悬挂点所成之集.对于子集 S(?)V(G),定义Ω~(S)(G)(?){T∈Ω(G)|π(T)(?)S}.若 G 是赋权图,记Ω_min~(S)(G)为 Ω~(s)(G)中全体最小支撑树所成之集.Chartrand 猜想:若有 T_1,T_2∈Ω(G),其相应的悬挂点数分别为m 和 n,且 m相似文献
2.
3.
吕涛军 《应用数学与计算数学学报》1989,3(2):95-96
本文仅考虑无向简单图。所谓图G的哈密顿路图是指这样的图,它与G有相同的节点集,其中任意两个节点有边相连当且仅当它们在G中有哈密顿路相连。用H(G)表示图G的哈密顿路图。递归地,由H~k(G)=H(H~(k-1)(G))(k≥2)可以定义k-哈密顿路图。用ε(G)表示图G的边数。如果G(?)H~k(G),则称图G为k-自哈密顿路图,简称为k-SHP图(k-Self Hamil-tonian Path Graph(k≥1)。若k=1,则称G为SHP图。 相似文献
4.
设G是一个n阶简单图.G的第二类Zagreb指数定义为M2(G)=■didj.其中di表示顶点i的度.Xu等(2014)提出了一个关于第二类Zagreb指数的猜想:在所有阶数为n、边数为m的图中,M2(G)最大的图是拟完全的.借助于门槛图的Ferrers表的性质,本文将上述猜想转化为组合矩阵论优化问题,并给出该猜想的一个代数证明. 相似文献
5.
6.
《高校应用数学学报(A辑)》2015,(3)
设G是一个简单无向图,s 3是一个正整数.文章中,若K1,s-匹配数为m(G)的n阶连通图G满足n(s+1)m(G),则G的第m(G)大L-特征值μm(G)s+1,然后证明了类似结论对于Q-谱也成立.最后给出了几个判断图的哈密顿性的Q-特征值条件. 相似文献
7.
§1.引言 设T是有p个点的一个竞赛图,T称为是弧k回路的,若T的每一条弧在一个长度为k的回路上.T也称为是弧哈密顿的,若T是弧p回路的.在第二次全国图论学术交流会上,邵品琮和张存铨提出下列猜想: 相似文献
8.
凌捷 《高校应用数学学报(A辑)》1989,4(4):590-592
在“东南亚第十一届组合图论与计算机学术会议”上,K.M.Koh与D.G.Rogers等人提出了一个猜想:“对所有n≥3,舵图H_n为优美图”。本文证明了这一猜想为真。 相似文献
9.
10.
图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G. 相似文献
11.
李晓东 《数学的实践与认识》2001,31(3):347-350
图的全染色是染色理论的重要内容 ,全染色猜想 :设 G是一个简单图 ,则 XT( G)≤△ ( G) +2是一个至今未解决的问题 .本文证明了对于一些图类全染色猜想是正确的 . 相似文献
12.
介绍了熊黎明等人所做的对满足h=n-△(G)的2-连通图的哈密顿指数的一个界限,并将这个界限给予改进并证明,而且还对满足条件的2-连通图做了更进一步的刻划. 相似文献
13.
图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广. 相似文献
14.
路与完全图的笛卡尔积图和广义图K(n,m)的关联色数 总被引:4,自引:0,他引:4
Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数. 相似文献
15.
对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的. 相似文献
16.
《中国科学:数学》2017,(5)
Gyrfs(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gyrfs等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gyrfs等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)m(k+1)+n,其中T为(m,n)-mop. 相似文献
17.
广义友谊图乘积上的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猜想成立. 相似文献
18.
19.
如果在—个κ连通图G中删掉任意一个顶点后得到的图都不再是κ连通,则称G为临界κ连通.Chartrand,Kaugars和Lick证明了每一个临界κ连通图(κ≥2)都含有一个度数小于(3κ-1)/2的顶点.Hamidoune进一步证明了每一个临界k连通图都至少含有两个这样的顶点,并且这一下界是最优的.在本文中,我们证明如果一个临界κ连通图恰好含有两个度数小于(3κ-1)/2的顶点,则这两个顶点的度数一定是κ. 相似文献
20.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献