共查询到20条相似文献,搜索用时 62 毫秒
1.
设G是n阶2-连通图,3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L,若d(u)且如果dL(u,v)=2有(v)=min{,|M3(u)|/2}这里M3(u)={v|dc(u,v)≤3},则G包含长至少为c的圈. 相似文献
2.
3.
图论中的一个重要问题是Hamilton圈的存在性问题.由于一般的Hamilton图的充要条件难于获得,故一些作者便退一步在某些给定类型的图中寻求长度尽可能大的圈.例如,Dirac即证明了2-连通图中存在着经过某一指定顶点集N(u)UN(v)U{u,v}的圈,从而得到了如下的定理(可参看[3]的介绍): 定理A.设G是个n阶的2-连通图,P是G中的一条最长路,u及v是P的两端点,d(u)+d(v)=f.若4≤f相似文献
4.
徐新萍 《数学的实践与认识》2009,39(10)
设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果. 相似文献
5.
在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3. 相似文献
6.
关于哈密尔顿连通图的一个基本结果是Ore给出的:设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的.设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度.本文利用独立集的度和得到如下结果:设s和t是正整数,G是(2s 2t 1)-连通n阶图.若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1.则G是哈密尔顿连通的.同时也得到图的哈密尔顿性的其它相关结果.两个独立集S和T称为强不交的,如果S∪T也是独立集. 相似文献
7.
证明了,若G是一个p-阶3-连通无爪图,p≠10,11,15,并对G中任意两个不相邻的点u和v,满足|N(u)∪N(v)|≥(p-1)/2,则G是泛圈图. 相似文献
8.
给出了如下定理的一个新的简短的证明:若G是一个满足k≥2的k连通赋权图,则G或者包含一个权至少为2m/(k 1)的圈,或者包含一个Hamilton圈,如果以下条件成立:(1)任意k 1个相互独立的顶点的赋权度和至少为m;(2)在G的每个导出爪,导出修正爪和导出P4中,所有边的权都相等. 相似文献
9.
设G=(V, E; w)为赋权图,定义G中点v的权度dGw(v)为G中与v相关联的所有边的权和.该文证明了下述定理: 假设G为满足下列条件的2 -连通赋权图: (i) 对G中任何导出路xyz都有w(xy)=w(yz); (ii)对G中每一个与K1,3或K1,3+e同构的导出子图T, T中所有边的权都相等并且min{max{dGw(x), dwG(y)}:d(x,y)=2,x,y∈ V(T)}≥ c/2. 那么, G中存在哈密尔顿圈或者存在权和至少为 c 的圈. 该结论分别推广了Fan[5], Bedrossian等人[2]和Zhang等人[7]的相关定理 相似文献
10.
11.
图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数. 相似文献
12.
广义de Bruijn和Kautz有向图的距离控制数 总被引:1,自引:0,他引:1
对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?).图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者.本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件.从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= .在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= . 相似文献
13.
设G是一个图.G的顶点u和v的距离是u和v之间最短路的长度.Wiener指数是G中所有无序顶点对之间距离之和,而Hyper-Wiener指数定义为WW(G)=?∑u,v∈V(G)d(u,v)+?∑u,v∈V(G)d2(u,v),式中的和取遍G的所有顶点对.本文总结了图的Hyper-Wiener指数的最近结论. 相似文献
14.
可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图. 相似文献
15.
16.
17.
18.
该文利用邻域并条件讨论图的点泛圈性,证明了当min{│N(u)∪N(v)│u,v∈V(G), 相似文献
19.