图中含有控制圈的一个充分条件

本文证明了:设G是n阶且围长g≥9的连通图,G-D<,1>(G)是2-连通的.如果对任意边,e,f∈E(G),d(e,f)=3有d(e)+d(f)≥n-g+2,则G中含有一个控制圈.     

关于图中的D—圈

H.J.Veldman给出了简单图含有D-圈的一个充分条件,本文也给出了一个充分条件,从而推广了H.J.Veldman的结果。     

大围长图中控制圈的一个局部条件

设Ｇ是围长大于或等于５的连通图．本文证明了；如果对Ｇ中每个顶点ｖ，距离ｖ为２和３的顶点导出的子图的独立数不大于最小度的两倍减３，那么Ｇ中有控制圈．     

一类由圈长分布确定的图

阶为ｎ的图Ｇ的圈长分布是序列（ｃ１，ｃ２，…，ｃｎ），其中ｃｉ是Ｇ中长为ｉ的圈的数目．本文证明了下述结果：设Ａ　Ｅ（Ｋｎ），｜Ａ｜３，ｎ≥｜Ａ｜十３，，则Ｋｎ—Ａ是由它的圈长分布确定的．     

S—控制圈的一个充分条件

设Ｇ是ｋ—连通的ｎ阶图，ｋ≥２，若对于Ｇ中的满足（对任意的任意（ｋ＋１）—独立集Ｘ，有则Ｇ中存在Ｓ—控制圈．     

泛圈图的一个充分条件

设G是一个n阶2—连通图且δ(G)≥4,本文证明了:若对于G中任意距离为2的两点u和ν均有|N(u)∪N(ν)|≥n-4.则G是泛圈图或n=8且G≌K_(4.4)。     

图中K个边不交的圈的存在性问题

记h(k)是使得满足ε=ν+h(k)的有限的无向图G包含k个边不交的圈的最小整数,P.Erds和L.Pósa证明了h(2)=4且对于任意正整数k≥1,存在充分小的正常数c1和充分大的正常数c2,使得c1klog2k≤h(k)≤c2klog2k。现把充分大的正常数c2的界缩紧到2.1相似文献   

关于图的圈的一个充分条件

设G为n(≥3)阶2连通图,δ≤δ~*≤Δ,对任意x∈V(G),记D(x)={y|y∈V(G)\{x},d(x,y)≤2},D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*},本文证明:如果|D~*(x)|相似文献   

一类圈图的计数原理

用母函数、事件、乘法原理研究了一类一圈图的计数,给出了这类图的个数的母函数及其显式,对个数的显式进行了构图验证,指出了这些有圈图所对应的分子结构式。     

一类图中D—闭迹存在的充分条件

设G是一个简单图,(?)e∈E(G),定义e=uv的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为u和v的度。本文的主要结果是:设G是n≥3阶几乎无桥的简单连通图,且G≠K_(1(?)n-1),G不含C_3和C_4,若对任何三个相互点不交的边e_0,e_1和e_2,d(e_0)+d(e_1)+d(e_2)≥n+7,则G有一个D-闭迹,从而G的线图L(G)是哈密顿图。     

Hamilton—图的一个充分条件

设G为n阶2-连通图,α为G的独立数.如果对于G中任意3个顶点的独立集{v_1,v_2,v_3}都有d(v_1)+d(v_2)+d(v_3)≥max{n+2,3α-2},则G是Hamilton-图。     

k-连通无爪图中的生成圈和控制圈

用张存铨在文[2]中的方法!本文通过疏远边的度和给出k-连通无瓜图中存在汉密尔顿圈和控制圈的充分条件,作为文中定理的推论,证明了若对任意■∈E(G) d(k)+d(v)≥3n/k-6,则G有汉密尔顿圈;若对任意■∈E(G) d(k)+d(v)≥3n/(k+1)-3,则G有控制圈,这里G是k-连通无爪图。     

有向图的控制圈

采用有向图控制圈的研究方法对有向图控制圈进行了研究 ,证明了 :设 D为 n阶 ( n≥7)强连通有向简单图 ,且对 D的任意弧 ( x,y)有 d-( x) + d+ ( y) >n- 4,那么 D含有控制圈     

图中有H圈的充分条件

文献[1]中指出了图是H图的一个新的充分条件,本文的目的在于给出该文结果的一个简单的证明,它使我们得到了更广泛的一个充分条件。在本文中,总是假定图是阶大于2的无重边无环的。如G=(V,E)是一个图,X,Y是它的两个不相连的顶点集,则记[X,Y]为G的这样的部分子图:其边集是G中那些两端点分别在X,Y中的边的全体,其顶集为X∪Y。其他术语与通常的相同。