共查询到20条相似文献,搜索用时 62 毫秒
1.
证明了如下结论:设n为偶数,r和k为奇效,n>r>k>0,λ≥2为整数,λ~*=2[λ/2]+1,r-λ~*k>0,G是有n个点、边连通度为λ的r-正则图,若n<(r+2)(k+1),则G是k-对等图。 相似文献
2.
关于三部图K(m,n,r)-A(|A|=2)色唯一性的几个结果 总被引:1,自引:1,他引:0
设G是简单图,用P(G,λ)表示图G的色多项式.令K(m,n,r)表示完全三部图。G=K(m,n,r)-A(|A|=2),3≤m≤n≤r.证明了若图Y使得P(Y,λ),则Y=K(m+α,n+β,r-(α+β))-S,其中α,β是整数,且|S|=e=(r-m)α+(r-n)β-2(α^2+αβ+β^2)≥0.且e=2时,G和Y同构,同时给出了α,β的范围。 相似文献
3.
设r≥4且r是偶整数.阶为2n的偶图G被称为唯一r-偶泛圈图,如果对每个偶整数t,r≤t≤2n,G恰含一个长为t的圈,且G不含长小于,的圈.若G是唯一r-偶泛圈圈,则称G是r-UB-图.证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n+m的r-UB-图. 相似文献
4.
连通图G所谓的l-边-连通度(Z—edge—connectivity),就是使图C成为至少l个分支所必须去掉的最少边数,记作λl(G),即λ1(G)=min{|E’|:E’真包含E(G),ω(G—E’)≥l}.研究了完全2-分图的l-边-连通度,得到了定理:设G=G[V1,V2]是一个完全2-分图,|V1|=r,|V2|=s,r+k=s,k≥0为整数.则图G的(k+2)-边-连通度为(k+1),即λk+2(G)=r(k+1). 相似文献
5.
图G的m-限制边割是删除它以后G不连通,且留下的每个分支的阶至少为m的边子集;m-限制边割的最小基数称为m-限制边连通度。设G是连通(k-2)-正则图,阶至少为2k(k≥5)。证明了G的k-限制边连通度存在当且仅当G不属于一种特殊图类G^* k-2. 相似文献
6.
马学强 《山东师范大学学报(自然科学版)》2006,21(3):14-17
设n和r是正整数使得r≥n+1≥4.一个图被称为K1,n-free图,如果它不含导出子图K1,n。证明了:若G是一个有圈H的图且r|V(G)|为偶数,G—E(H)是连通的K1,n-free图且G—E(H)的顶点最小度至少是(n(r+1)-3/r-2)[rn-2/2(n-1)]-n-1/r-2([rn-2/2(n-1)])^2+n-3那么G有r-因子F包含H中的所有的边. 相似文献
7.
设Sn是具有n个顶点各等长圈数不超过2的简单图的集合.若Sa中不存在图G'使|E(G')|〉|E(G)|,则称G是简单的最大圈分布(2)图(简记为简单MCD(2)图).用f*(n,2)表示具有n个顶点的简单MCD(2)图的边数.证明了对每个整数11≤n≤14,有f*(n,2)=n+[1/2(√11n-20 -2)],其中[a]是小于等于a的最大整数。 相似文献
8.
即是k-覆盖又是k-消去的图称为k-对等图.本文研究了有约束条件的r-正则图和k-对等图之间的关系,给出了有约束条件的r-正则图是k-对等图的关于顶点数和边连通度的充分条件. 相似文献
9.
吴建良 《山东大学学报(理学版)》2005,40(6):27-30
设G为一简单图,它的最大平均度mad(G)=max{2|E(H)|/|V(H)|:H为G的非空子图}.如果△(G)≥7和mad(G)≤4,或者△(G)≥5和mad(G)≤18/5,或者△(G)≥3和mad(G)〈3,则G的线性荫度为[△(c)/2]. 相似文献
10.
设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图。令K(m,n,r)表示完全三部图,证明了(1)设m≤n≤r,0≤r-m≤4,若m≥2,则除去K(2,2,6)、K(2,3,6)、K(3,3,7)、K(3,4,7)外,K(m,n,r)是色唯一图。(2)若n≥4,0≤k≤2,则K(n-k,n,n k)是色唯一图。 相似文献
11.
12.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图. 相似文献
13.
14.
关于Km,n并图的优美性 总被引:2,自引:0,他引:2
对于自然数k,m,n,本文给出一类非连通图↑k∪↓i=1Kmi.ni;通过构造标号函数的方法,证明了当max{mi,ni}≥3,min{mi,ni}≥2(i=1,2,…,k)时这类图既是优美图,也是交错图;从而给出构造一类任意个图的并图是优美图的一种方法,拓宽了优美图及其应用的道路。 相似文献
15.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图. 相似文献
16.
再论图Pn^3的优美性 总被引:3,自引:0,他引:3
给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的. 相似文献
17.
给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 . 相似文献
18.
杜万根 《烟台大学学报(自然科学与工程版)》2013,26(4)
棱柱图(~P)n是由2个回路v1,v2,v3,…,vn和u1,u2,u3,…,un,加上边uivi后所组成的图形.图n∪i=1(~P)4是n个(~P)4的不交并图,图n∪i=1(~P)8是n个(~P)8的不交并图,证明了2类非连通图n∪i(~P)4和n∪i=1(~P)8是优美图且是交错图. 相似文献
19.
杜万根 《烟台大学学报(自然科学与工程版)》2013,(4):240-242
棱柱图n是由2个回路v1,v2,v3,…,v n和u1,u2,u3,…,un,加上边uivi后所组成的图形.图∪ni=14是n个4的不交并图,图∪n i=18是n个8的不交并图,证明了2类非连通图∪n i=14和∪n i=18是优美图且是交错图. 相似文献