共查询到20条相似文献,搜索用时 15 毫秒
1.
任意连通图与偏k-树乘积图的树宽 总被引:1,自引:1,他引:0
一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图C与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式. 相似文献
2.
韧度与分数k-消去图 总被引:1,自引:0,他引:1
设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.文章证明了若k是整数且k≥2,t(G)≥k-1k,|V(G)|>k+1,则G是分数k-消去图.并说明该结论在一定意义上是最好的. 相似文献
3.
分数因子作为因子概念的扩展,在网络设计、网络通讯与传输、多面体组合等诸多领域有着广泛的应用.而联结数与韧度作为衡量网络坚韧度和易受攻击性的重要参数,已成为网络设计好坏的重要评判标准之一.针对这两个参数,本文给出存在连通分数1-因子的两个充分条件. 相似文献
4.
Narayanaswamy,Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V(G)+k-2,并指出这个界是紧的.该文给出了k-树图G可收缩边数目更一般的下界,由该文的结果可以推出Narayanaswamy等人的结果,进一步证明了可收缩边数目恰好为V(G)+k-2的图的特征. 相似文献
5.
6.
徐睿 《山东大学学报(自然科学版)》1997,32(4):412-419
设G是任一连通图,H是G的邻接树图,κ(H),λ(H),δ(H)分别是H的连通度,边连通度和最小次,则κ(K)=λ(H)=δ(H)。 相似文献
7.
王兵 《吉首大学学报(自然科学版)》2008,29(1):10-12
借助Bauer定理给出了一个猜想的简短证明:如果图G含有k-因子且是2-连通的,并满足σ2(G)≥n-k,那么图G是哈密顿的. 相似文献
8.
9.
文章通过研究双星图的代数连通度的极限点 ,给出树的代数连通度的极限点的分布范围 :[0,(3- 5)/2] ,以及分布情况的一个结论 : ε>0 ,至少存在一个树类 ,其代数连通度的极限为r>0 ,且r<ε。 相似文献
10.
邻接树图的连通度 总被引:1,自引:0,他引:1
徐睿 《山东大学学报(理学版)》1997,(4)
设G是任一连通图,H是G的邻接树图,κ(H),λ(H),δ(H)分别是H的连通度,边连通度和最小次,则κ(H)=λ(H)=δ(H). 相似文献
11.
12.
13.
14.
王红专 《湖南文理学院学报(自然科学版)》2007,19(4):27-28
设T是一棵似星树,即其中仅有一个顶点的度数大于2的树,并设其中最大的顶点度数为m,T的广义连通指数为R_a(t)∑uv∈E(T),其中d(u)为树T中顶点u的度,α是任意实数.通过图的变换,证明了似星树的广义连通指数Rα(T)是e1m(T)的递减函数,e1m(T)是T中连接一个1度顶点与m度顶点的边数;并由此刻画了具有最大、最小广义连通指数的似星树. 相似文献
15.
给定最大度的树的代数连通度 总被引:1,自引:0,他引:1
研究给定最大度的树在移接变形下的代数连通度的变化.这些结果可以用来刻画给定最大度和顶点个数的树中具有最小代数连通度的极图,并且给出了该极图的代数连通度的一个下界. 相似文献
16.
17.
18.
Ando 证明了如果G是极小的k-连通图,且G中不含有K1 C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任-k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边. 相似文献
19.
证明了对k-连通图G,若G的任意一个断片满足当N(F)中含有边就有|F|k/4,则G至少有2条可收缩边. 相似文献
20.
王倩 《山东大学学报(理学版)》2016,51(8):29-34
给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。 相似文献