无爪图中不相邻子图P_4和K_1的度和条件下的哈密尔顿性

研究子图的度和图的哈密尔顿性的关系,证明图~$G$ 是一个~$n$ 阶~3-\,连通无爪图且最小度~$\delta(G)\geq4$, 如果图~$G$ 中任意两个分别同构于~$P_4$, $K_1$ 的不相邻子图~$H_1$, $H_2$ 满足~$d(H_1)+d(H_2)\geq n$, 则图~$G$ 是哈密尔顿连通.     

小度数循环图的计数

循环图已被用于平行计算，网络等方面．循环图研究的一个基本问题是对互不同构的循环图进行计数．对于给定的一个正整数ｎ，用Ｃ（ｎ，ｋ）表示互不同构的具有几个顶点，度数为ｋ的连通循环图的个数．文中给出了度数为 ４和５的循环图的一般结构，并对ｎ＝ｐａｑｂ（ｐ，ｑ皆为素数，ａ，ｂ＞０），给出了Ｃ（ｎ，４）的计算公式．     

循环图Cn〈j1,j2,…,jr,n／2〉的连通性

本文得到了奇数度循环图C_n是连通的充要条件及C_n不连通的情形.证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>.这一结果颇有意义.     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

无爪图的次与Hamilton连通性

本文证明了：设G是n阶、k（≥3）连通无爪图，且不含同构于B的导出子图，若存在点v_0∈V（G），使d（v_0）≥n-2k＋4，则G是Hamilton连通的．     

直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.     

I-hedrite图平面嵌入的唯一性

本文研究每一个面圈的圈长仅为2,3或4的无割点的4·正则连通平面图,称之为I-hedrite图.证明在相等意义上,I-hedrite图的平面嵌入是唯一的.这个唯一性结论意味着,两个i-hedrite图(即每一个面的度仅为2,3或4的4-正则连通平图)是相等的当且仅当它们是同构的,从而解决了i-hedrite图的同构构造在相等意义上的唯一性问题.     

非连通图G_1uG_2及G_1uG_2uK_2的优美性

将k-优美图的概念进行了推广,引入了k～l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献   

无爪图中不相邻子图P_4和K_1度和条件下的哈密尔顿连通性

研究子图的度和图的哈密尔顿性的关系,证明图G是一个n阶3-连通无爪图且最小度δ(G)≥4,如果图G中任意两个分别同构于P_4,K_1的不相邻子图H_1,H_2满足d(H_1)+d(H_2)≥n,则图G是哈密尔顿连通.     

用循环图构造可靠通讯网络

本文得到了５度、７～１５度连通循环图的连通度等于其度数的充要条件。从而可用循环图构造可靠通讯网络。     

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

3-连通(X,Y)-free图的Hamiltonian-连通性

一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的.     

循环图的1—因子化

本文证明了任意偶数阶连通循环图是1-可因子化的。 根据前两个定理这两个定理立即得证.     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是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也是独立集．     

无限循环图的超边连通性(英文)

本文证明了 ,在一切具有有限跃度序列的无限循环图中 ,只有C( 1 ) ,C( 1 ,2 )和C( 1 ,2 ,3)不是超边连通的 ,而且C( 1 )和C( 1 ,2 )是其中仅有的两个非最大边连通图 .     

一类Hamilton图

本文证明了：如果Ｇ是２连通无爪图且Ｇ中不含同构于Ｚ３．Ｄ的导出子图．则Ｇ是Ｈａｍｉｌｔｏｎ图（除Ｇ≌Ｇ１．Ｇ≌Ｇ２外）。     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

K1,4-受限图的路可扩性

图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的.     

无限循环图的同构和自同构

本文证明了两个有限度的无限有向循环图Ｄ（Ｓ）和Ｄ（Ｔ）同构当且仅当Ｔ＝±Ｓ另外，还确定了有限度的无限（有向）循环图的全自同构群