共查询到20条相似文献,搜索用时 156 毫秒
1.
党恺谦 《东北大学学报(自然科学版)》1993,(6)
设 G为 n阶 2连通无爪图,δ=min{d(x)|x∈V(G)},δ~*=min{max(d(x),d(y))|x.y∈V(G).d(x.y)=3},则(i)c(G)≥min{n.2δ~*+4};(ii)当 δ~*≥(1/2)(n-δ-2)时 G是哈密顿图。 相似文献
2.
为精确估计网络的可靠度,需要最优化其图模型的限制边连通度.证明了:1,如果G是连通二部图,且δ(G)≥3,对于满足d(x,y)=2的任意两点x,y,有d(x)+d(y)≥2(n(G))/(4)+4,则G是λ3-最优的.2,若G是λ4-连通图,且|G|≥11,δ(G)≥4,对于满足d(x,y)=2的任意两点x,y,有d(x)+d(y)≥2(n(G))/(4)+6,则G是λ4-最优的. 相似文献
3.
张运清 《南京大学学报(自然科学版)》2004,21(1):77-85
令G是n阶2-连通图且d(u,v)=2 max{d(u),d(v)}≥n/2.设{x,y}不是G的2-割集.记最长的(x,y)-路的长度为p(x,y).本文证明了如下结论:(1)p(x,y)≥n-2;(2)若p(x,y)=n-2且P是最长的(x,y)-路中使得d(xp)最小的一条,那么d(xp)=2,3或者n/2,其中xp表示唯一一个不属于P的点.本文还刻画了3-连通且使得d(xp)=3的图. 相似文献
4.
5.
具有二分划(A_1;A_2)的2-连通偶图为(A_1;A_2)Hamilton连通的一个充分条件 总被引:2,自引:2,他引:0
车向凯 《东北大学学报(自然科学版)》2000,21(1):104-106
给出具有二分划(A1,A2)的n阶2连通偶图G(A1,A2)为(A1,A2)Hamilton连通的定义,其中|A1|=|A2|·采用反证法,将图G分为若干情形,利用图G是2连通的偶图,及|A1|=|A2|,证明了,若n≤2δ+2δ-2时,则G是(A1,A2)Hamilton连通图,其中δ=min{d(x)|x∈V(G)},δ=min{max(d(x),d(y))|d(x,y)=2,x,y∈V(G)}· 相似文献
6.
王洪 《吉首大学学报(自然科学版)》1985,(2)
给定正整数p、q、δ,对于点数为p、线数为q、最小度为δ的(p、q、δ)图 ,本文讨论了它们的线连通度λ和连通度k之间的关系。当δ<〔(p-1)/2〕或δ≥2/3(p-1)时,给出了λ-k的上界;当〔(p-1)/2〕≤δ<2/3(p-1)时,对于q足够大的情形,也给出了λ-k的上界;并且给出了达到这些上界的极图。同时还证明了λ-k的下界在上述一切情形下均为零,且这个下界可达。 相似文献
7.
每点都与3度点相邻的最大临界3棱连通图的结构 总被引:4,自引:1,他引:3
徐俊明 《中国科学技术大学学报》1987,(4)
没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构. 相似文献
8.
记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G)mxt∈E(G)|,NC2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2},1989年Faudree等证明了:若3连通n阶图G,NC≥(2n 1)/3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC2≥(2n 1)/3,则G是哈密尔顿连通图或G=ψ。 相似文献
9.
记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G),xy(?)E(G)},NC_2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2}。1989年Faudree等证明了:若3连通n阶图G,NC≥(2n+1)/3,则G是哈密尔顿连通图。据此进一步研究NC_2≥(2n+1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC_2≥(2n+1)/3,则G是哈密尔顿连通图或G=φ。 相似文献
10.
记δ和α分别为图G=(V,E)的最小度和独立数,1991年Faudree等人和尹家洪分别得到:“若2连通n阶图G的不相邻的任意两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图”和“若2连通n阶图G的长为2的任意两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图”。这里得到结果:若2连通n阶图G的满足1≤|N(x)∩N(y)|≤α-1的不相邻的任两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图。此结果推广Faudree等人和尹家洪的结果。 相似文献
11.
12.
一个图G(V,E)的控制数γ(G)是V的这样一个子集S的最小基数,使得G中每一个顶点或者在S中或者和S中的一些顶点邻接。本文讨论了控制数为2的n阶简单连通图的邻接谱半径下界,给出了谱半径达到最小时的极图。 相似文献
13.
田叶 《河北师范大学学报(自然科学版)》2012,(4):332-335,354
对于图G=(V,E),如果V\S中的每个顶点都和S中至少1个顶点相邻,且G[V\S]是连通的,则称V的子集S是图G的外连通控制集.外连通控制集的最小基数~γc(G)称为图G的外连通控制数.给出了树删去1条边后对应的外连通控制数的可达下界,定义了关于边删除的~γc-严格图及~γc-稳定图,并对其相关性质进行了讨论. 相似文献
14.
定义在图G的顶点集V(G)上的函数f:V(G)→{0,1,2,3}称为G的双罗马控制函数,如果每个赋值为0的顶点至少与一个赋值为3或两个赋值为2的顶点相邻,并且每个赋值为1的顶点至少与一个赋值为2或3的顶点相邻。图的双罗马控制函数的权为所有顶点的赋值之和。双罗马控制函数的最小权称为双罗马控制数。利用顶点数、围长、周长以及最小度得到了含圈图的双罗马控制数的若干上下界。 相似文献
15.
不含孤立点的图G称为全控制边临界的,如果对任意两个不相邻顶点u和v, 有γt(G uv)<γt(G).也称这样的图为γt-临界的. 如果该图G的全控制数为k,称G为k-γt-临界的.一个γt-临界图G称为强γt-临界的, 如果对任意顶点v∈V(G)存在G的一个基数为γt(G)-1的控制集D使得G[D]除v外不含孤立点.研究了强γt-临界图的性质,给出了一个由小的强γt-临界图构造大强γt-临界图的方法. 相似文献
16.
侯新民 《中国科学技术大学学报》2006,36(6):604-606
设G为n阶连通图,集合S称为图G的全控制集,如果V(G)的每个顶点都和S中某点相邻。图G的全控制数,记为γt(G),是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1,n-1的树T,γt(T)=min{(2n/3),n-l,[n/2]+l-1},这里l表示树T中叶子的数目。 相似文献
17.
邢抱花 《安庆师范学院学报(自然科学版)》2015,(2):1-3,9
连通图G的Wiener指数是指图G中所有点对的距离之和,Harary指数是指图G中所有点对的距离的倒数之和。本文主要研究了单圈图与双圈图的粘合图以及双圈图与双圈图的粘合图的Wiener指数的下界和Harary指数的上界的问题,并刻画了对应的极值图。 相似文献
18.
19.
设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14. 相似文献
20.
图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的色.应用概率的方法得到了n个点的k-正则图G的一个点可区别全色数的较小上界. 相似文献