共查询到19条相似文献,搜索用时 218 毫秒
1.
证明了若 G是 3连通无爪图 ,且 G的每个同构于 A的导出子图都满足 ( a1,a2 ) ,则 G是泛连通图 (除了 u,v∈ V( G) ,d( u,v) =1时 ,G中可能不存在 ( u,v)—k路外 )。由此立得C.Thomassen猜想 :每个 4连通线图均是 Hamilton图 相似文献
2.
3.
4.
极大等周边连通图的充分条件 《山东科学》2016,29(4):75-79
k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{[X,X-]:XV(G),X≥k,X-≥k},其中X-=V(G)\X。令βk(G)=min{[X,X-]:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。 相似文献
5.
文章讨论了无爪图的Hamilton连通性 ,给出邻集并与最大度的条件下Hamilton连通图的新的充分条件,证明了下述定理 :设G是一个3 -连通简单无爪图 ,连通度为k。如果对于G的每一个k阶独立集S满足 :对 u,v∈S,都有(1)k>3时,│N(u)∪N(v)│≥n-Δ(s) -k +2,(2)k=3时,│N(u)∪N(v)│≥n -Δ(s),则G是Hamilton连通的。 相似文献
6.
徐新萍 《南京大学学报(自然科学版)》2005,22(1):28-35
关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|. 相似文献
7.
具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图. 相似文献
8.
图是极大限制边联通的充分条件 《山东科学》2015,28(3):80-83
设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|[X,X]|:|X|=k,G[X]连通},其中X=V(G)\X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。 相似文献
9.
《太原师范学院学报(自然科学版)》2016,(2)
k等周边连通度是一个比边连通度更可靠的网络可靠性参数.连通图G的k等周边连通度定义为γ_k(G)=min{|[X,X]|:X■V(G),|X|≥k,|X|≥k},其中珡X=V(G)\X.令βk(G)=min{|[X,X]|:X■V(G),|X|=k}.图G是γ_k-最优的如果γ_k(G)=βk(G).令G是一个阶至少为8的图.文章证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥3;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥7,那么G是γ4-最优的. 相似文献
10.
殷志祥 《安徽理工大学学报(自然科学版)》1993,(1)
本文证明了如果G是2连通无爪图,G不是圈,n=|v(G)|>q,G的每个导出子图A都满足φ(a_1,a_2),且G中不存在W′作为其导出子图,则G是泛圈图。 相似文献
11.
设G是一个简单图,任意e∈E(G),定义e=uv在G中的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。 相似文献
12.
设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的. 相似文献
13.
苗丽 《太原师范学院学报(自然科学版)》2012,11(1):19-22
文章给出了满足一定条件的图的λ6-最优性的领域交条件.设图G是连通图,若对G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥10且|X5|≤5,则G是λ6-最优的;若对于连通图G中任意一对不相邻顶点u,v,都有|N(u)∩N(v)|≥10且对图中每个三角形T至少存在一个顶点v∈V(T)使得d(v)≥v2+5,则G是λ6-最优的. 相似文献
14.
对于图G(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数. 相似文献
15.
设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.证明了当顶点数、最小度以及max{dG(u),dG(v)}(其中u,v是图中任意两个不相邻顶点)满足一定条件时,G是分数k-消去图,该结论在一定意义上是最好的. 相似文献
16.
文章给出了λ4-最优图的一个充分条件.设G是阶为n≥11的λ4-连通图,若对G中任意一对不相邻顶点u,v,有|N(u)∩N(v)|≥6且G|N(u)∩N(v)|至少包含16条边,则G是λ4-最优的. 相似文献
17.
游泰杰 《贵州师范大学学报(自然科学版)》1991,(2):40-44
本文主要讨论变换半群的子群的性质和结构,得到的主要结果是:定理1 设B是A的一个非空子集,H是M(B)的一个子群,则有M(A)的子群G使得G_B=H且G与G_B同构。定理2 (1)设G是M(A)的一个子群,e是G的单位元,则G是M(A)的一个极大子群当且仅当G_Ae=∑_(Ae)。(2)M(A)的任何两个不同的极大子群之交是空集。 相似文献
18.
王斌 《西南师范大学学报(自然科学版)》2009,34(1)
图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e.给出了边-超欧拉图的一个度数和条件,即:设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d(u)+d(v)≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G(G关于e的剖分图)可以被收缩成K2.3或K2.5. 相似文献
19.
文章给出了二部图是λ4-最优的一个领域交条件.设n为一个不小于8的正整数,令G=(X∪Y,E)为一个n阶二部图且ξ4(G)≤n/2.若G有一个饱和X或Y中所有顶点的匹配且对任意的u,v∈X和u,v∈Y都有|N(u)∩N(v)|≥4,则G是λ4-最优的. 相似文献