共查询到17条相似文献,搜索用时 781 毫秒
1.
图的圈长分布和圈长分布唯一的图 总被引:1,自引:0,他引:1
阶为n的图G的圈长分布是指序列(c1,c2,…,cn),其中ci是G中长为i的圈数.若不存在,使G’与G有相同的圈长分布,则称图G是圈长分布唯一图.本文确定了Kn-A(|A|=j,n≥|A|+3)的最小、最大的4圈和5圈数.证明了当n≥9时,Kn-A(|A|=4)以及当n≥14时,Kn-A(|A|=5)都是圈长分布唯一图. 相似文献
2.
陆宗元 《上海师范大学学报(自然科学版)》1994,(1)
阶为n的图G的圈长分布是序列(C1,C2,…,Cn),其中Ci是图G中圈长为i的圈数.本文得到了如下结果:设则是由它的圈长分布确定的.并给出了Kn,n-A3在各种情形下的圈数计算公式. 相似文献
3.
施永兵 《上海师范大学学报(自然科学版)》1995,(2)
设Sn是n个顶点的没有等长圈的简单图的集合.若G∈Sn且Sn中不存在图G'使|E(G')|>|E(G)|,则称图G是简单MCD图.若简单MCD图G是2连通的,则称G是2连通简单MCD图.本文证明了不存在具有28个顶点的含有同胚于K4的子图的2连通简单MCD图.于是结合DiscreteMath.126(1994),我们完全证明了下述定理:存在n个顶点的含有同胚于K4的子图的2连通简单MCD图当且仅当n∈{10,11,14,15,16,21,22}. 相似文献
4.
阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数.设A真包含E(Kn,n+8),在情况①G=Kn,n+8(n≥13);②G=Kn,n+8-A(|A|=1,n≥15);③G=Kn,n+8-A(|A|=2,n≥17);④G=Kn,n+8-A(|A|=3,n≥19)时,图G由其圈长分布唯一确定. 相似文献
5.
图的升分解问题的两个新结果 总被引:2,自引:0,他引:2
孙磊 《曲阜师范大学学报》1998,24(2):51-55
Alavi等人在1987年定义了图的一种新分解,即“升分解”(AscendingSubgraphDecomposition),并且猜想:任意有正数条边的图都可升分解.该文证明了下面两个新结果:(1)Hi是i条边的Kn的子图,当n+1≤i≤2n-2n/3[]2-2时,G=Kn-Hi可升分解为K1,1,K1,2,…,K1,n-5,K1,n-4,Gn-3(n≥6),其中K1,n-4Gn-3.(2)Hi是i条边的Kn的子图,当i≥2n-2n/3[]2时,G=Kn-Hi不一定有定理1形式的升分解. 相似文献
6.
任韩 《武汉科技大学学报(自然科学版)》1995,(1)
设G=(V,E)为n阶2-连通的1-坚韧图。将G的节点分类:g={v∈V|dG(v)≥n/2}而H=(G\g)。如果H满足Ore-条件:x,y∈V(H),(x,y)∈E(H)dH(x)+dH(y)≥|V(H)|,则有:(i)G是Hamilton的;(ii)若G不是偶图,则G至多丢失长为n-1的圈. 相似文献
7.
点泛圈偶图 总被引:1,自引:0,他引:1
郭李仁 《安徽师范大学学报(自然科学版)》1997,20(1):7-11
设G是连通偶图,(X1,X2)是其顶点的二分类,|X1|=|X2|=n,δ(G)≥t≥3,且对于Xi中的任意两点u和v,均有|N(u)∪N(v)|≥n-(t-2),i=1,2,文中对t≤6的情况,证明G是点泛圈偶图。 相似文献
8.
陈婵 《杭州师范学院学报(社会科学版)》1999,(6)
Sachs,Kozyrev和Grinber,指出平面图。有Hamliton圈的一个必要条件是∑sum fromi=3(i-2)φ_i=∑sumfromi=3(i- 2)φ'_i=n-2,其中φ_i和φ'_i分别为Hamilton 圈内、外度为i的面数.本文探讨面的度相等的平面图的面数,面并成顶点在边界上的连通区域与 Hamilton 圈. 相似文献
9.
李建平 《中国科学技术大学学报》1997,(3)
设G是n阶1-坚韧图,X是G的顶点子集合,定义α(X)=max{|S||S是诱导子图G[X]中的顶点独立集},σk(X)=min{ki=1d(xi)|{x1,x2,…,xk}是独立集}和c(X)=max{|V(C)∩X||C是G中的圈}。我们得到如下主要结果:设G是n阶1-坚韧图,并且σ3(X)≥n,则c(X)≥min{|X|,|X|+δ(X)-α(X)+1|,并且这下界是最好的,这里δ(X)是不小于13σ3(X)的最小正整数. 相似文献
10.
刘建农 《青岛大学学报(自然科学版)》1994,7(1):44-48
A.Ital和M.Rodeh给出了两个关于图的圈覆盖的猜想:(i)任意2-边连通图G=(V,E)有困覆盖C,使l(C)≤|E|+|V|-1;(n)任意2-边连通图有困覆盖,使图的每条边至多被覆盖两次.本文证明了猜想对平面图和2-边连通没有3-边割的图成立,并给出了一与两猜想等价的条件.同时也对著名的2-圈覆盖猜想作了讨论. 相似文献
11.
唐华 《上海师范大学学报(自然科学版)》1998,(2)
分f*(n,2)表示具有n个顶点的至多有2个等长国的简单图的最大边数.证明了当n≥15时,f*(n,2)≥n+2Zk-4+[」,其中k=[(16+/42). 相似文献
12.
唐华 《上海师范大学学报(自然科学版)》2001,30(2):41-42
阶为 n的图 G的圈长分布是序列 ( c1,c2 ,…cn) ,其中 ci 是 G中长为 i的圈的数目 ,图 G的圈长分布满足 c1=c2 =… =cr- 1=0且对 i=r,r 1 ,… ,n有 ci≤ 2 ,∑ni=rci>0 ,则称图 G是围长不小于 r的 2圈分布图 ,用 fr( n,2 )表示阶为 n的围长不小于 r的 2圈分布图的最大可能的边数 .证明了对每个整数 n≥ r 2 ,有fr( n,2 )≥ n 2 k -2 r 2 4n -2 4k2 8k 4r2 -1 2 r 5,其中 k=[( 5 6 0 n 6 0 ( r2 -3 r) 85) / 3 0 ],这里 [x]表示不超过 x的最大整数 . 相似文献
13.
阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数,得到如下结果:(1)设A包含于E(Kn,n),则当Kn,n[A]≌K1,j或Kn,n[A]≌K2时,Kn,n-A是由它的圈长分布确定;(2)设A包含于E(Kn,n,|A|=4,n≥11,则Kn,n-A是由它的圈长分布确定的。 相似文献
14.
阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数,作者得到如下结果:设n≤r≤min{n 6,2n-3},则Kn,r是由它的圈长分布确定的。 相似文献
15.
阶为v的有向图D的有向圈长分布是序列(c_1,c_2,…,c_v),其中C_i是D中长为i的有向圈的数目。设0≤x_i≤v-i-1,证明了存在v个顶点的有向图D,使D的有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1),并且给出了具有有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1)的有向图的最大可能的弧数以及具有有向圈长分布为(0,0,k,k,…,k,k-1,…,3,2,1)(其中1≤k≤v-2)的有向图的最小可能弧数的上界。 相似文献
16.
施永兵 《上海师范大学学报(自然科学版)》2002,31(3):18-20
阶为υ的图G的圈长分布是序列(c1,c2,…,cυ),其中 是G中长为i的圈的数目,得到了计算给定简单偶图G的图长分布的公式。 相似文献
17.