共查询到20条相似文献,搜索用时 31 毫秒
1.
令简单图G=(V,E)是有p个顶点q条边的图。假设G的顶点和边由1,2,3...,p+q所标号,且f:V∪E=「1,2,...,p+q」是一个双射。如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic)。毛毛虫图是一个树,移走它的所有端点产生一个路(称为T的脊或主干)。例如,路和星图是毛毛虫图。证明了毛毛虫图是边幻图,从而证明了顶点不超过8的树的边幻图。 相似文献
2.
图的特征值在量子化学理论中有其物理意义。利用从一个顶点向另一个顶点移动边时谱半径的变化,该文得到了给定顶点数和边独立数的所有树的谱半径的几个新的上界并且确定了达到上界的所有树。 相似文献
3.
k—覆盖图的一个充分条件 总被引:4,自引:4,他引:4
论证了整数n(n≥3)和k(k≥2),若k为奇数,则令k≥n-1,G是一个不含K1,n的2-边连通图,k│V(G)│≡o(mod2),设G的顶点最小度α(G)至少为(n^2/4(n-1)k+(3n-6)/2+(n-1)/4k,则G是k-覆盖图,并且说明了定理条件“2-边连通”不能减弱为“连通”。 相似文献
4.
杨冬梅 《沈阳黄金学院学报》1995,14(3):381-384
Jackson(1981)对一类特殊的偶图给出了其圈长的估计,设G是以(A,B)为顶点二分划的偶图,k=min(d(u)│u∈A))≥2,2≤│A│≤k,│B│≤2k-2,则最长圈C(G)=2│A│。这里对上述结果进行了改进得到下述定理,设G是以(A,B)为顶点二分划的偶图,d(x)=min(d(u)│u∈A)=k≥2,λ=min(d(u)│u∈A/(x)≥k,2≤│A│≤λ,│B│≤λ+k-2, 相似文献
5.
论证了对整数n(n≥3)和k(k≥2),若k为奇数,则令k≥n-1,G是一个不含K1,n的2边连通图,k|V(G)|≡o(mod2),设G的顶点最小度α(G)至少为(n2/4(n-1))k+(3n-6)/2+(n-1)/4k,则G是k覆盖图.并且说明了定理中条件“2边连通”不能减弱为“连通”. 相似文献
6.
7.
刘玉柱 《沈阳建筑工程学院学报(自然科学版)》1995,(1)
设G是以(A,B)为顶点二分划的偶图,d(x)=min{d(u)|nA}=k≥2,λ=min{d(u)|uA\(x)}≥k,2≤|A|≤λ,|B|≤λ+k-2,则G的周长为2|A|. 相似文献
8.
刘玉柱 《沈阳建筑工程学院学报(自然科学版)》1995,(2)
设G是以(A,B)为顶点二分划的2连通偶图.x∈A且d(x)=min{d(u)|u∈A}=k,|A|≤k,|B|≤2k.则C(G)=|A|. 相似文献
9.
刘玉柱 《沈阳建筑工程学院学报(自然科学版)》1996,12(3):363-366
设G是以(A,B)为顶点二分划的2连通偶图,x∈A且d(x)=min{d(u)│u∈A}=k,│A│≤km,│B│≤2k+,则C(G)=2│A│。 相似文献
10.
设G是以(A,B)为顶点二分划的2连通偶图,X∈A且d(x)=min(d(u)u∈A)=k,λ=min(d(u)U∈A^(x)≥k,若A≤λ,B≤λ+k,则C(G)=2(A)。 相似文献
11.
吴强 《山东大学学报(工学版)》1998,(1)
主要研究了正则图中的k-消去图与图的边连通度之间的关系,从而推广了Bolobás的结果.其结果如下:Ⅰ设G是一个r-正则图,|V(G)|为偶数,λ(G)≥2.若k为一整数,且r/λ≤k≤r-r/λ,则G为k-消去图.Ⅱ设r和k为偶数,2≤k≤r,则每一个r-正则图都为k-消去图.Ⅲ设G为r-正则图,λ(G)=λ≥2,且λ*=2[λ/2]+1.若r为奇数,k为偶数,且使得2≤k≤r-r/λ*,则G为k-消去图. 相似文献
12.
一个图G=(V,E)的一个k-全着色是从V∪E到Ik={1,2…k}上的一个映射ψ;如果对V∪E中任意两个相邻或相关联的元素e1,e2,都有ψ(e1)≠ψ(e2)时,则称ψ为G的一个正规全着色。图G的全色数定义为xT(G)=min{k|存在G的一个正规k-全着色}。令Cn为n个点的图,K↑-m为m个点的独立集,Δ为图的最大度。本文证明了在m≠n时联图Cm+Cn的全色数为Δ+1;在m+2〈n或m〉n 相似文献
13.
乔晓云 《太原重型机械学院学报》2012,(1):80-82
设G=(V,E)是n阶简单连通图,D(G)和A(G)分别表示图的度对角矩阵和邻接矩阵,L(G)=D(G)-A(G)则称为图G的拉普拉斯矩阵。利用图的顶点度和平均二次度结合非负矩阵谱理论给出了图的最大拉普拉斯特征值的新上界,同时给出了达到上界的极图,并且通过举例与已有的上界作了比较,说明在一定程度上优于已有结果。 相似文献
14.
孙良 《北京理工大学学报(英文版)》1995,4(2):111-113
设G=(V,E)是无孤立点的简单图.设T是V的子集,如对任意U∈V,存在u∈T使得uv∈E,则称T为G的全制约集.全制约集的最小基数称为G的全制约数,记作γt(G).本文证明了如G是阶数n≥3,最小度至少为2的连通图,则γt(G)≤4「(n+l)/7」 相似文献
15.
吴强 《山东工业大学学报》1995,25(2):176-181
改进了关于r-因子的结果,给出了一个图是r-消去图的充分条件,并且用例子说明此结果是最好的可能。结果如下:定理I设r≥1是奇数,G是一简单图,且V(G)为偶数,如果k(G)〉(r+1)^2/2,且(r+1)^2a(G)〈4rk(G),那么G为r-消去图。定理Ⅱ设r≥2为偶数,G是一简单图,如果k(G)〉r(r+2)/2,且(r+2)a(G)〈4k(G),则G为r-消去图。 相似文献
16.
吴强 《山东大学学报(工学版)》1995,(2)
改进了关于r-因子的结果,给出了一个图是r-消去图的充分条件.并且用例子说明此结果是最好的可能.结果如下:定理Ⅰ设r≥1是奇数,G是一简单图,且V(G)为偶数,如果k(G)>(r+1)2/2,且(r+1)2α(G)<4rx(G),那么G为r-消去图.定理Ⅱ设r≥2为偶数,G是一简单图,如果k(G)>r(+2)/2,且(r+2)a(G)<4k(G),则G为r-消去图. 相似文献
17.
白艳萍 《中北大学学报(自然科学版)》1996,(2)
在一个图G中,对于两个不相邻点u,v,用α(u,v)表示包含u和v的最大独立集的个数.本文证明了:如果G是一个包含n个顶点的3-连通图,对于G中每一对满足1≤|N(u)∩N(v)|≤α(u,v)-1的不相邻顶点u,v有max{d(u),d(v)}≥n+12,那么G是Hamiltonian连通的或者G属于特殊图类 相似文献
18.
改进了文献(7)给出了广播函数B(2^k-4)(k≥4)的下界,构造了一个n=2^k-4的极小广播图,从而得到了B(2^k-4)(k≥4)的一上界,并给出了一个mbg(28),该图的边数为48,达以了B(28)的下界值。 相似文献
19.
20.
利用“图型序列的母函数”所给出的图型序列生成函数的性质,本文导出一些重要特殊图的生成函数。n,m(-x)=1,所以有定理4设G为n阶出(或人)k正则图(每个顶点的出(或人)度均为k),则证明由条件可知,I—Ax的各行之和均为1-kx,I+x的各行之和均为1+(n-k)x,于是其中aij=1-aij由此可得定理5无向轮图的生成函数为证明因为具有n个顶点的轮图的补图是由仅有一个含自回路的顶点及n-1阶n-3正则图构成的非连通图,所以由此可得定理6 n阶无环无向路的生成函数其中△=证明 设Pn的邻接矩阵为A,则设Dn的伴随矩阵易知Dij=Dji,当j≥i时,于是代入后,经整理即得证。推论1加环有向路的生成函数推论2无环有向路的生成函数参考文献 相似文献