排序方式: 共有47条查询结果,搜索用时 0 毫秒
1.
证明了:对任何整数t≥6和d≥2,从一条长为d的简单路通过添加t条边后得到的图的最小直径上界为[d-2/t 1] 2,如果d∈J'(t,k)={2k(t 1) 1,2k(t 1) 2,2k(t 1)-t 1}∪{2k(t 1)-t h:h=6,7,…,t};其他情形为[d-2/t 1] 1.这个证明改进了已知结果,而且[d-2/t 1] 1是最好的上界. 相似文献
2.
对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数 相似文献
3.
徐俊明 《华中科技大学学报(自然科学版)》1989,(4)
本文通过临界h棱连通图的指数概念,讨论了指数不小于h+3的p阶临界h(≥4)棱连通图的最大棱数问题。 相似文献
4.
子集S(∩)V(G)称为限制割,若任何点v∈V(G)的邻点集NG(v)都不是S的子集且G-S不连通.若G中存在限制割,则定义限制连通度κ1(G)=min{| S|S是G的一个限制割}.考虑了笛卡尔乘积图,证明了设G=G1×G2×…×Gn,若Gi是满足某些给定条件的ki连通ki正则且围长至少为5的图,其中i=1,2,…,n,则κ1(G)=2n∑i=1ki-2. 相似文献
5.
超立方体网络的边容错二部泛连通度 总被引:2,自引:0,他引:2
证明了对于至多有n-1条故障边的容错超立方体网络Qn,如果它正好有n-1条故障边但不关联于同一个顶点, 那么对于Qn中任意两点u和v,存在一条长为l的uv非故障路, 路长l满足dQn(u,v) 2≤l≤2n-1且2|(l-dQn(u,v)).这改进了许多已知结果. 相似文献
6.
首先考虑Acharya和Hegde关于算术平衡图的三个猜想,其中一个已由他们证明,本给出它和另一个猜想的简单证明,并指出第三个猜想在一般情形不是不对的,而在一个更强的条件下是正确的。然后讨论了本结果与已知结果之间的关系。 相似文献
7.
徐俊明 《中国科学技术大学学报》1999,29(2):199-201
经典的Vizing边染色定理断言:对于任何一个重数为μ且最大度为Δ的重图G,只须用μ+Δ种颜色就可以将G中的边进行染色,使得相邻边的颜色不同.该文给出它的一个简单证明 相似文献
8.
不含紧优和几乎紧优双环网络无限族 总被引:31,自引:0,他引:31
双环网络是计算机互连网络或通讯系统中重要的拓扑结构,它们的紧优性是网络设计中一个重要的研究课题,目前已找到大量含紧优和几乎紧优双环网络的无限族。我们找到不含紧优和几乎紧优双环网络的无限族,回答了李乔等人于1993年提出的一个问题。 相似文献
9.
立方体和折叠立方体的限制边连通度和超边连通度 总被引:5,自引:0,他引:5
确定了立方体的2-超边连通度和折叠立方体的1-超边连通度和限制边连通度. 相似文献
10.
对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ l - 1 l .而且针对某些Δ和l,是对Meir和Moon的结果的一种改进 相似文献