几类乘积图的圈覆盖

文献［１］提出猜想：每个２─连通ｎ阶简单图都有一个圈覆盖Ｃ,使得｜ｃ｜≤（２ｎ－１）／３。此猜想至今尚未完全证实。本文对路、圈、完全图的若干笛卡尔乘积图和张量乘积图证实了猜想是正确的。     

极大欧拉生成子图为Hamilton圈的图

对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界.     

有圈二部图覆盖的一个结果

H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.     

TT''''-free图的最长圈

本文提出了两类新的禁用子图T和T＇.一个图G称为TT＇-free图,若G中不含同构于T或T＇的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈（简记为D-圈）,若E（G-C）=φ.本文证明了：顶点数不小于3的连通、局部连通TT＇-free图G最长圈为D-圈,且G是局部泛圈的.     

Halin图的圈着色

对3－连通图Halin图,确定了其圈色数,并得到较好结果。     

一类无爪泛圈图

本文证明了如下结果:G 是 n(≥8)阶,2—连通无爪图,且对 G 的每一个生成子图 A、A~+,满足(a_1,a_2),则 G 为泛圈图(除圈外)。     

泛圈图的一个充分条件

本文证明了:如果G是n(≥9)阶2连通无爪图,且G的每个导出子图Z_1,满足当u,v∈V(G)d_(z_1)(u,v)=2时有|N(u)UN(v)|≥n-3,则G是泛圈图或圈.其中Z_1≌(K_2UK_1)VK_1.     

完全图的最小6-圈覆盖和8-圈覆盖

提出了完全图最小圈覆盖的覆盖数下界,运用递归构造的方法,把顶点数v的研究范围归结到区间[m,3m-1]中的部分数值上来,并就圈长m=6,8的情形给出了完全解．     

无桥图最短偶子图覆盖的上界

偶子图覆盖问题是图论研究领域的的重要内容之一,为研究最小偶子图覆盖猜想,利用整数流与偶子图覆盖的联系,借助于整数4-流在图的某个圈中扩充的结论,给出并证明了无桥图的最小偶子图覆盖的一个新的上界,改进了范更华给出的结论。     

不含4-圈图的森林分解

研究了不含4-圈图的森林分解问题.利用权转移法,得到了任意一个不含4-圈的NC-图能分解成2个森林和1个线性森林.     

两类平面图的指数集

完全确定了极大可平面图与极大外可平面图的指数集。     

极大平面图与外可平面图的同构不动边

图Ｇ的一条边ｅ称为Ｇ的同构不动边，如果当且仅当ｅ’＝ｅ．若ｅ＝ｕｖ是Ｇ的同构不动边，则对Ｇ—ｅ的任一自同构映射。都有π（｛ｕ，ｖ｝）＝｛ｕ，ｖ｝文中证明了，除Ｋ３Ｖ（Ｋ１＋Ｋ１；）外的极大平面图和除Ｐ２ＶＫ１，Ｐ３ＶＫ１外的２－连通外可平面图都含有同构不动边．     

几类平面图的分数染色

图G的一个分数染色是从G的独立集的集合ζ到区间[0,1]的一个映射c,使得对任意顶点x,都有∑s∈ζ,s,1 x∈s c(s)≥1,将此分数染色的值定义为∑s∈ζ c(s)．图G的分数色数xf(G)是它的所有分数染色的值的下确界,讨论了几类平面图的分数色数。     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

特殊平面图的全染色

给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一种颜色.图G的全染色数xT(G)是指使G全k染色的最小整数k.Δ(G)是G的最大度,本文对不含从4到k的圈,且3-圈不重点的平面图得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ 1.     

平面图边可重构的几个结果

本文得出几个平面图边可重构的结论:1.若 G 是平面图,δ(G)=4,且 G 没有次为5的点,则 G 是边可重构的。2.若 G 是平面图,δ(G)≥3,且 S_3为 G 中次为3的集合,又设 G—S_3为3连通的,G 无次为4的点。则 G 是边可重构的。     

特殊平面图的线性二荫度

线性k-森林是指一个图G,它的每个连通分支是长至多为k的路．图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m,用lak（G）表示．本文探讨特殊平面图的线性二荫度,得到的结论有：1）每个3-圈不重边的平面图G,有la2（G）≤[△（G）／2]＋10;2）每个3-圈不重点的平面图G,有la2（G）≤[△（G）／2]＋7;3）每点至多关联[△（G）／2]个3-面的平面图G,有la2（G）≤[△（G）／2]＋10．     

关于一类Ore图的泛圈性

从所周知，ＪＡＢｏｎｄｙ的Ｍｅｔａｌ猜测对Ｏｒｅ图是成立的。本文从一个新的角度，对Ｇ中次数较小的节点所导出的子图的结构进行了分析，得出了一类新的泛圈图。     

关于不可约的图

图的色唯一性与补图的各分支的不可约性密切相关。用P_n表示n阶路,把K_3的一个项点与P_n-2的一个一度点重迭后得到的图记为D_n。本文分别得到了D_n和P_n是不可约图的一千充分条件,并且给出了一批不可约的D_n和P_n。