关于C_4蛇并图■的优美性

给出C4蛇并图n∪i=1-C4的一类非连通图,并证明这类非连通图是优美图,且是交错图。     

拟正则图的最大边边连通度(英文)

定义了图的边边连通度,设计了一类具有最大边边连通度的拟正则图。     

一类Hamilton无爪图

对任一2-连通无爪图G,如果存在v_0∈V(G),|N(v_0)|=|V(G)|-1,则对任意两个顶点a,b∈N(v_0),G中存在以a,b为其端点的Hamilton路.并由此证明了2-连通且局部连通的无爪图是Hanilton图.     

强N_2-局部连通无爪图的Hamilton性

运用反证法的证明技巧,对任一无爪图G及其圈C,证明了只要C上有一个接触点是强N_2-局部连通的,则C一定不是最长圈.即证明了强N_2-局部连通无爪图是Hamilton图.     

非H-无爪图最长圈的若干性质

设G是2-连通无爪图,C是G的最长圈,R=G-C非空.证明了C满足以下5个性质;1)不存在c∈Nc(R),使G[N(c)]连通;2)不存在c∈Nc(R)和y∈V(G)(y≠c),使G[N(c)U{y}]连通且|N(y)∩N(c)|≥3;3)不存在c∈Nc(R)和y∈V(G),使G[N(c)∪{y}连通且G[N(y)]连通;4)不存在c∈Nc(R)和y∈K_1,使|N(y)∩(N(K_2)-{c}|≥2(其中K_1是G[N(c)]的含c~+,c~-的一个分支,K_2是另一个分支);5)不存在c∈Nc(R)和y∈V(G),使|N(y)∩K_1|≥2且有连接K_2与y的路P满足:对P的任一中途点u,或u∈V(C)或u~+u~-∈E(G).     

n阶4、5度循环图的计数

将所有ｎ阶４度连通循环图所构成的集合记为Ｇ＿ｎ，Ｇ＿ｎ的元素个数记为｜Ｇ＿ｎ｜。文中首先导出了｜Ｇ＿ｎ｜的计算公式。然后将Ｇ＿ｎ中的图按图的同构关系分为一些等价类，进一步再将所有等价类按一定规则划分为Ⅰ型和Ⅱ型。记Ⅰ型等价类的个数为Ｔ，文中证明了ｎ阶４度不同构的连通循环图的个数有Ｔ个（当ｍ为偶时Ｔ为０），其中ｍ为小于ｎ且与ｎ互素的正整数个数的一半。同时文中也给出了ｎ阶５度不同构的连通循环图的类似的计算公式。     

单圈图的线图的全色数

设Ｈ是简单连通图，Ｇ＝Ｌ（Ｈ）表示Ｈ的线图，本文给出了单圈图的全色数。     

关于图的上可嵌入性与非邻节点度和的一个注记

进一步研究了2(或3)-边连通简单图的上可嵌入性与非邻节点度和的关系,得到如下结果:2-边连通简单图G为上可嵌入的条件及其下界表达式,而这个界是最好的,不能再继续改进;对于3-边连通的简单图,本文还给出了更为清楚的表达式.     

一类循环图的计数(英文)

讨论了 ４度循环图的结构。所有ｎ阶４度非同构的连通循环图被分为两类： Ⅰ类和Ⅱ类。给出了计算Ⅰ类循环图的计算公式,改进了关于ｎ阶４度非同构的循环图的计数公式。     

积图P_2×C_6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数．得到了P_2×C_6的邻点可区别全色数．     

邻集交和汉密尔顿连通性

设G是阶为u(≥3),独立数为α的简单图,本文证明了:如果对于G中不相邻点u,υ都有|N(u)∩N(υ)|≥α,则G是汉密尔顿连通的,除非G同构于一类特殊图.     

3-强连通竞赛图外弧泛圈的顶点数

Yeo证明了每个3-强连通竞赛图至少包含2个外弧3-泛圈顶点,本文证明了每个3-强连通竞赛图至少包含3个顶点v1,v2,v3,使得v1,v2的所有外弧是3-泛圈的,v3的所有外弧是4-泛圈的。     

正则k-覆盖图

图G的k-正则生成子图称为G的一个k-因子,若图G的每条边都含于G的一个k-因子中,称图G足k-覆盖的。对任意给定的正整数γ、λ和k(λ≥2),基于文[1,2]的已知结论,本文给出了所有γ-正则λ-边连通图是k-覆盖图的充分必要条件。     

积图P2×C6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数.得到了P2×C6的邻点可区别全色数.     

排列图的若干k*-连通性

排列图An,k是星图的推广,但它的阶却比星图有更好的灵活性.证明了:当n≥5,n-k≥3时,排列图An,k为3*-连通图;当n ≥ 6,n-k≥3时,排列图An,k为4*-连通图.     

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.     

排列图的若干k~*-连通性

排列图An,k是星图的推广,但它的阶却比星图有更好的灵活性.证明了:当n5,n-k3时,排列图An,k为3*-连通图;当n6,n-k3时,排列图An,k为4*-连通图.     

爪心独立图的模k泛圈性

证明了2-连通的爪心独立图G,如果对任意的非爪心点v,有d(v)≥k 1,对任意的爪心点u,存在v∈N(u),使得d(v)≥k 2,那么G是模k点泛圈的.     

两类图的W-宽直径

图的直径与宽直径是并行与分布式网络通信延迟的度量,据此研究了两类图的W-宽直径,在n点圈Cn中添加t条边得到图C(n,t),讨论了图C(n,t)的2-宽直径的最小值问题,并得到其上下界,进而提出了h(n,t)精确取值的猜想;在分析联图连通度的基础上,导出了联图的W-宽直径上界估计式。     

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。