共查询到20条相似文献,搜索用时 15 毫秒
1.
设σ(k ,n)表示最小的正整数m ,使得对于每个n项正可图序列 ,当其项和至少为m时 ,有一个实现含k+ 1个顶点的团作为其子图 .Erd s等人猜想 :σ(k ,n) =(k - 1 ) ( 2n-k)+ 2 .Li等人证明了这个猜想对于k≥ 5,n≥ k2 + 3是对的 ,并且提出如下问题 :确定最小的整数N(k) ,使得这个猜想对于n≥N(k)成立 .他们同时指出 :当k≥ 5时 ,5k- 12 ≤N(k)≤ k2 + 3.Mubayi猜想 :当k≥ 5时 ,N(k) =5k - 12 .在本文中 ,我们证明了N( 8) =2 0 ,即Mubayi猜想对于k =8是成立的 相似文献
2.
3.
4.
定义了一类极大外平面图:(r,k)--扇。证明了当G是以r个顶点的圈Qr为标定界环的(r,k)一扇,G'是以Qr为标定界环的任意极大外平面图时,G和G'有公共四染色;同时对△(G)=r-3的极大外平在图也得到相同的结论。从而证明了四色定理的等价命题在给定条件下成立。 相似文献
5.
组合学的一个新概念--圆组合 总被引:2,自引:0,他引:2
1962年笔者在《数学通报》指出下述结果[1 ] :设n ,k为自然数 ,a ,b为实数或复数时 ,就有等价恒等式(a b) n =∑nk=0nk an-kbk,(二项式定理 )an bn =∑[n2 ]k=0( - 1 ) k nk (a b) n- 2k(ab) k,(等价二项式定理 )其中记号nk =n(n- 1 ) (n- 2 )… (n -k 1 )k!,nk =n(n -k- 1 ) (n -k- 2 )…(n- 2k 1 )k!.同时还发现等价恒等式的数字表、证明、性质以及应用上具有相似之处 .由于 nk 是组合记号 ,推测 nk 可能是另一组合记号 ,于是猜想 nk 中蕴藏着组合学的一个新概念 .40年韶光弹指过 ,近年笔者探讨孪生组合等式的问题[2 ,3,4] ,才能清楚地… 相似文献
6.
设σ(k,n)表示最小的正整数m,使得对于每个n项正可图序列,当其项和至少为m时,有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想:σ(k,n)=(k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5,n≥(^k2))+3是对的,并且提出如下问题:确定最小的整数N(k),使得这个猜想对于n≥N(k)成立。他们同时指出:当k≥5时,[5k-1/2]≤N(k)≤(^k2) 3.Mubayi猜想:当k≥5时,N(k)=[5k-1/2]。在本文中,我们证明了N(8)=20,即Mubayi猜想对于k=8是成立的。 相似文献
7.
设G是一个顶点集为V(G),边集为E(G))的简单图.S_k(G)表示图G的拉普拉斯特征值的前k项部分和.Brouwer et al.给出如下猜想:S_k(G)≤e(G)+((k+1)/2),1≤k≤n.证明了当k=3时,对边数不少于n~2/4-n/4的图及有完美匹配或有6-匹配的图,猜想是正确的. 相似文献
8.
与四色定理等价的几个命题 总被引:3,自引:0,他引:3
本文论述了与四色宣等价的几个新命题,从而给出了平面三角剖分及圈上的4染色集的一些新性质,钭平面图的4可染色问题转化为圈上的4染色来研究,这将更便于用计算机来寻找关于四色定理的更简单的证明方法,也为探索四色定理的理论证明提供了新的途径和方法。 相似文献
9.
极大平面图的组合运算 总被引:6,自引:0,他引:6
一、引言有关平面4色问题的综合论述见文[1]和文[2].目前这一问题因有计算机辅助证明而得到解决,但这种证明繁杂.又由于等价的命题多,联系的方面广,因而对此问题进行新的理论探讨,便不会是毫无意义.把平面4色问题化成只与圈上的4染色集性质有关的问题来解决,这种思想在文[3]中已经有了,只可惜该文最后所提出的猜想不真(对长度为4的圈已不成立.此事我们将另文评述).本文以极大平面图的组合序列为基础,得出一些只与圈上的4染色集的性质有关的等价于平面4色猜想的命题. 相似文献
10.
文 [1 ]给出了一个关于kn的不等式猜想 ,猜想的右侧不等式是 :正整数n ,k >1 ,则nk 2时 ,( 1 )式成立 .为证明上述结论 ,先给出两个引理引理 1 [贝努利 (Bernoulli)不等式 ]若x >- 1且k是正整数 ,则 ( 1 +x) k≥ 1 +kx .等号当且仅当x =0时成立 .利用二项式定理易证引理 1 .引理 2 [2 ] 若 - 1 相似文献
11.
研究图的伴随分解及其补图的色等价性.采用伴随多项式的性质讨论图的伴随分解式,通过图的伴随分解式确定其补图的色性.证明了形图簇的伴随多项式的分解定理,从上述定理得到了这类图簇的补图的色等价性.结论通过图的伴随分解研究其补图的色等价性,是有效的途径与方法,从图的伴随分解式容易看出其补图的色等价图的结构规律. 相似文献
12.
《纯粹数学与应用数学》2017,(1)
该文定义了图_n~2,并研究了该图的奇优美和奇强协调性.利用构造法分别给出了图_n~2在n=4k(k≥2)、n=4k+2时的奇优美算法,在n=4k(k≥2)时,的奇强协调算法,进而证明了图_n~2在n=2k(k≥3)时是奇优美图,在n=4k(k≥2)时是奇强协调图等结论,从而推动了对图的奇优美性和奇强协调性的研究.最后提出猜想:当n=4k+2时,图_n~2不是奇强协调图. 相似文献
13.
林育青 《纯粹数学与应用数学》2017,33(1)
该文定义了图(C)2n,并研究了该图的奇优美和奇强协调性.利用构造法分别给出了图(C)2n在n=4k(k≥2)、n=4k+2时的奇优美算法,在n=4kk≥2)时,的奇强协调算法,进而证明了图(C)2n在n=2k(k≥3)时是奇优美图,在n=4k(k≥2)时是奇强协调图等结论,从而推动了对图的奇优美性和奇强协调性的研究.最后提出猜想:当n=4k+2时,图(C)2n不是奇强协调图. 相似文献
14.
在文献[1]里,Michael.O.Albertson和David Berman对任意图G定义了一个函数f(G): 他们猜想当G是平面图时,f(G)的下界至少是1/2。如果这个猜想成立,则可以利用这结果,而不用四色定理来解决Erds-Vising问题.(在文献[2],251页,问题36).同时他们提出了对于其它类型图G,f(G)的下界问题.本文首先引进了子图序列概念,并用它作为工具来估计f(G)的下界.主要给出了在亏格大于零的定向曲面上图G的f(G)下确界。 相似文献
15.
16.
<正> Nash-Williams猜想([1];[2]p.202):一个无环的有向图D,它的最小出入度为k,顶点数为p,当5≤p≤2k时,D中有弧不重的两个Hamilton有向圈. 本文将指出:当5≤p≤2k时,D中必有弧不重的一个Hamilton有向圈和一个Hamilton通路. 相似文献
17.
本文利用色多项式的性质,讨论了具有色多项式∏i∑kui/k(k/ui-k)(λ)k的图的结构,给出了具有这种色多项式的全部色等价图. 相似文献
18.
关于图的点可区别边染色猜想的一点注 总被引:1,自引:0,他引:1
图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确. 相似文献
19.
关于Whitney和Tutte猜想 总被引:5,自引:0,他引:5
whitney和Tutte把平面四色问题化为只与圈上的4染色集有关的问题来研究,从而探讨四色问题的理论证明;提出了一个蕴含着四色定理的猜想。本文研究开集的组合不变性,从而证明Whitney和Tutte的猜想不成立。 相似文献
20.
对简单图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是正确的. 相似文献