共查询到20条相似文献,搜索用时 471 毫秒
1.
王江鲁 《山东师范大学学报(自然科学版)》1996,11(3):13-16
图G中一个与K1,3同构的导出子图叫做G的一个爪,爪中的3度顶点叫它的爪心。用r(v)表示图G中所有以顶点v为爪心的不同爪的数目。证明了阶数≥3的连通、局部连通图G,如果G的爪心集合A是点独立集,且A↓v∈A,r(v)≤d(v)-3,则G是完全圈可扩的。 相似文献
2.
娄定俊 《中山大学学报(自然科学版)》1995,34(2):18-21
设G是具有二分类(X,Y)的2连通等部偶图。如果对G中每一个顶点v,H是G中与v距离为2和3的所有顶点导出的子图,并且对于g中每一个与v距离为3的顶点u,u在H中的度数d_H(u)不小于距离v为2的顶点的数目减去(dG(v)-2),则G是Hamilton图。其中d_H(u)的下界不能改进。 相似文献
3.
莫降涛 《广西大学学报(自然科学版)》1996,21(2):104-106
设v是图G=(V,E)的顶点,若存在顶点u∈V-{v},使子图G[N(v)∪{u}中任意一对顶点的距离不超过3,则称v是G的弱局部连通顶,点。设G是非平凡的连通无爪图,且它的任一顶点割均钫含一个弱局部连通顶点,则G包含Hamilton圈。 相似文献
4.
陈瑞袁 《福建师范大学学报(自然科学版)》1995,11(3):21-26
假定G是顶点数的n的2-连通图,G中顶点数为4且包含爪K1.3的子图称为爪型子图。本文证明了对G的任一爪型图F,任何u,v属于V(F),由距离d(u,v)=2=│N(u)UN(v)│≥2n-1/3,则G是哈密顿图。 相似文献
5.
董进全 《内蒙古大学学报(自然科学版)》1995,(1)
以γ(G)记图G的控制数,如果对v(G)中任何一对满足条件uvE(G)的顶点u,v,有γ(G+uv)<γ(G),则称G是控制临界的。γ(G)=k的控制临界图称为是k-控制临界的,得出以下两个结果:1)如果G是具有以(>>2k)个顶点的连通3-控制临界图,则G中度≤2k的顶点的个数至多为2k.2)每个连通3-控制临界图或者有一个独立3-控制集或者有一个完全3-控制集。 相似文献
6.
王冬冬 《徐州师范大学学报(自然科学版)》1997,(4)
设G是n阶3-连通无向简单图,α表示图的独立数.若对G的所有距离为2的顶点u,v,都有d(u)+d(v)≥n或|N(u)∩N(v)|≥α,则G是Hamilton连通的,除非G属于一个特殊图类. 相似文献
7.
顾国华 《东南大学学报(自然科学版)》1993,23(6):30-35
设G是n阶简单3-连通图,δ是G的最小度,uv是G的两个不相邻顶点,a(u,v)是G中包含u,v的最大独立数,本利用图G的任意两个距离为2的顶点u,v的独立数a(u,v),给出了图具有Hamilton性质的两个新的充分条件。 相似文献
8.
陈瑞袁 《福建师范大学学报(自然科学版)》1994,(2)
设G是2-连通图,对G中任一对不相邻的顶点u,v,|N(u)∪N(v)|≥s.Faudree猜测,当G的顶点数 s为奇数时,G的最长路的顶点数 本文证明猜测当s>3时是真的.进而证明了除一类图外P(G)≥min{|v(G)|,2s+l}. 相似文献
9.
唐廷载 《西华师范大学学报(哲学社会科学版)》1997,(4)
复合图G1(u)⊙uv⊙G2(v)是将简单图G1的顶点u与简单图G2的顶点v用边uv连接成的图.本文证明:若G1和G2都是有限niche图,则当连接点u,v满足一定的条件时,复合图G1(u)⊙uv⊙G2(v)也是有限niche图,且n(G1(u)⊙uv⊙G2(v))≤n(G1)+n(G2)-r其中,r=0,1,2. 相似文献
10.
徐允庆 《信阳师范学院学报(自然科学版)》1994,7(1):11-16
G是简单图,v∈V(G).用两个新顶点去代替顶点v,原来G中与v相邻的顶点现在与u或者w相邻,且d(u)+d(W)=d(v),这时称顶点v被剖分。记ρ(G)为G的谱半径,G’为G中顶点v被剖分后的新图,则ρ(G’)≤ρ(G),等式成立当且仅当d(u)=0或d(w)=0.如果G是连通的且v是G的割点,对v做适当的剖分,使得新图C’由两个分枝H_1,H_2组成,则ρ(G)≤等号成立当且仅当G是星图。 相似文献
11.
设G是单圈图,dv表示顶点v的度数.讨论了单圈图G的几个拓扑指标:mG=vVGdvm,mG=vVGdvm,m1G=vVGdvm1,这里m是不小于2的正整数,刻画了单圈图关于3个拓扑指标的最小值. 相似文献
12.
对整数k>0,r>0,图G的条件(k,r) 染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(1)相邻点获得的颜色不同;(2)|c(N(v))|≥min{|N(v)|,r}。G的条件色数是使得G有一个正常的(k,r) 染色的最小k值,记为χr(G)。本文主要研究了r取3时,几类特殊图的条件色数。 相似文献
13.
对于图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的测地数和上(下)测地数. 相似文献
14.
苗丽 《太原师范学院学报(自然科学版)》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-最优的. 相似文献
15.
设G是顶点数学不少于3的连通、局部连通图。如果G的爪心集合是点独立集,并且任意一个爪心的领域所导出的图是强2-控制的,则G是安全圈可扩的。 相似文献
16.
王兵 《安徽大学学报(自然科学版)》2004,28(1):20-23,29
距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈. 相似文献
17.
图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3. 相似文献
18.
图G=(V,E)的Wiener极性指标是图G中距离为3的无序点对的数目。图G和H的点corona图,记为G°H是取G的一个拷贝和|V(G)个H的拷贝,然后把G的每个点和其相对应拷贝的每个点相连而得到的图。图G和H的边corona图,记为G◇H,是取G的一个拷贝和|E(G)|个H的拷贝,然后把G的每条边的两个点和其相对应拷贝的每个点相连而得到的图。本文给出两个图的corona乘积图的Wiener极性指标。 相似文献
19.
对于图G内的任意两点u和v,u-v测地线是指u和v之间的最短路.I(u,v)表示位于u-v测地线上所有点的集合,对于V(G)S,I(S)表示所有I(u,v)的并,这里u,v∈S.G的测地数g(G)是使I(S)=V(G)的点集S的最小基数.文章研究了Pm×Fn和Cm×Fn的测地数,这里Pm表示m阶路,Cm表示m阶圈,Fn表示n阶扇图。 相似文献
20.
设图G是点集为V(G)={v1,v2,…,vn}的简单连通图,则G的邻接矩阵是A(G)=(aij)n×n,其中若vi和vj相邻,则aij=1,否则aij=0.由于A(G)是实对称的,因此可将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G),且A(G)的特征值也称为G的特征值.该文在仅有三个悬挂点的图的所有连通补图中,确定了其最小特征值达到最小值时的唯一图. 相似文献