独立点数为2的图的Z_3-连通性

设G是独立点数为2的连通简单图.主要证明两个结论:(1)当边连通为4时,G是Z_3-连通的;(2)当点连通为3时,G是Z_3-连通的当且仅当G■{K_4,W_5}且G不是一类特殊的图.     

3流猜想的等价刻画

Tutte的3流猜想是每个没有3边割的无桥图有无零3流.这里主要说明对于5边连通图这个猜想也是成立的.     

Abel群上点传递图中的处处非零3-流

Tutte猜想每个4-边连通图存在处处非零3-流.验证3-流猜想对于定义在Abel群上的点传递图是成立的,这个结果推广了Potocnik等在2005年的研究结果.     

直积图的分数色数

有关直积图的色数,在图论中有Hedetniemi猜想,该猜想是建立在连通图的基础上,并且已证明该猜想对于一些特殊图是成立的.证明了对于连通的点传递图,Hedetniemi猜想在分数染色意义下也是成立的.     

广义双循环群上Cayley图中的处处非零3-流

Tutte在研究四色问题时引入了整数流的概念,并猜想每个4-边连通图存在处处非零3-流.本文验证了3-流猜想对于定义在广义双循环群上的Cayley图是成立的.     

3-连通图的若干性质

连通度、边连通度是刻画图的连通程度的重要参照,按照图的连通程度进行分类,连通图是1-连通图,没有割点的图是2-连通图,3-连通图作为这一分类下的一类也具有若干性质。     

3-正则图的Z3-连通性

得出了3-正则图是Z3-连通的充要条件:一个连通的3-正则图G是Z3-连通的当且仅当G是正文中的图1或图2。     

3-优图研究

—个图G中所含的三结点连通导出子图的个数记为S3(G)，它在网络可靠性中起着重要作用，在同点数同边数图类中具有最大S3(G)的图称为3—优图，它所代表的网络是某种意义下的最可靠网络，3—优图的补图为3—最小图，而一个图称为3—极小图，如果在其上作任何一边的改变都不会减少其三结点连通导出子图的个数，本文提出一个构造算法，由该算法可以得到至今为止所知的所有的3—最小图，而且该算法所得的图都是3—极小图，因此猜想该算法所得的图是3—最小图。     

[4，2]-图的圈可扩性

如果图G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图。证明:顶点数≥3的连通、局部连通[4,2]-图是完全圈可扩的或者同构于K2∨K3。     

K_(1,4)-自由图的模k泛圈(英文)

对于任意自然数k ,如果图G包含模k长的每一个圈 ,那末图G被称为模k泛圈图 .本文证明了连通K1,4 -自由图G是k =3的泛圈图 ,这一结果断定了Thomason猜想在连通图中的正确性 .     

图中3-距离控制集的上界

研究了图的3-距离控制数.根据不同图的结构特征,给出几类重要图的3-距离控制数的精确值,讨论了对一般图的3-距离控制数的紧的上界,并提出了一个相关猜想.     

关于平面图3-可着色的一个定理

Borodin和Raspaud提出一个猜想：任何既没有5-圈也没有相邻三角形的平面图是3-可着色．这个猜想强化了Steinberg提出的猜想．在本文中，我们研究了没有5-，6-，9-圈并且没有相邻三角形的平面图的结构．利用这个结构，证明了这类图是3-可着色的．它加强了由Borodin及Sanders和Zhao的结果，并且又是对Borodin和Raspaud猜想的一个正面的支持．     

关于哈林图的邻和可区别染色的注记

用三种树染色算法和组合分析法, 完成对哈林图的邻和可区别边染色、 邻和可区别全染色以及邻点全和可区别全染色, 并证明1-2-3 猜想 和1-2猜想对哈林图均成立. 结果表明, 哈林图的邻点全和可区别全色数不超过3.     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

3N+1猜想与3N+3k猜想的等价性及相关性质

将数论中3N＋1猜想推广为3N＋3^k猜想．得到了3N＋1猜想与3N＋3^k猜想的等价性．得到有关3N＋3猜想的一些性质．3N＋1猜想的推广、3N＋3猜想的一些性质的建立对于研究4K＋3型奇数在3N＋3猜想压缩迭代中起到简化作用，同时也为3N＋1猜想的研究提供了新思路．     

几类乘积图的圈覆盖

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

变换图G~(*xy)的独立数

变换图的概念由全图推广而来。文章在中图的补图M(G)的定义启发下,定义了四类变换图,其中一个恰是(G),并探讨了这些变换图的独立数。研究了变换图G*-+的独立数与原图最大度的关系,以及G*++与G*+-的独立数与原图边独立数的关系。     

2类特殊偶图完美匹配的计数

图的完美匹配计数问题是匹配理论研究的一个重要课题,此问题有很强的物理学和化学背景.LovszL和Plummer M就曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.但是,一般图的完美匹配计数问题已经被证明了是NP-难问题.用划分,求和,再嵌套递推的方法给出了2类特殊偶图完美匹配数目的显式表达式,从而验证了LovászL和Plummer M猜想在这2类图上的正确性,所给出的方法,可以计算出许多偶图的所有完美匹配的数目.