独立点数为3的图的Z3-连通性

Jaeger猜想为"5-边连通图是Z3-连通的",此猜想对于独立点数为2的图是成立的.利用收缩、点分裂、反证等方法,证明了此猜想对于独立点数为3且点连通度不大于5的图也是成立的.     

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

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

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

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

短圈覆盖与处处无零4-流

【目的】针对一些特殊的图类验证Tutte的4-流猜想。【方法】用子图的处处无零4-流构造原图的处处无零4-流。【结果】1) 若图 *，其中Gi存在处处无零4-流，1≤i≤n，且 * 与Gl最多有两条公共边，2≤l≤n，则G存在处处无零4-流；2) 若图G=H∪F，其中H是G的一个存在处处无零4-流的子图，F是G的一个阶数不超过4的无桥连通子图，则G存在处处无零4-流；3) 若图G的每条边都包含在一个长度不超过4的圈中，则G存在处处无零4-流。【结论】上述的第2个结果是Catlin的一个引理的推广；Imrich和Skrekovski关于笛卡尔积图的处处无零4-流的结果是上述第3个结果的一个直接推论。     

没有任意非零3-流图的一个新下界

在文献[2] 中Tutte介绍了任意非零流并且被广泛的研究.在这篇文章中,给出了图没有处处非零3-流时边数的新极值.     

平面图的无圈边染色

一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.     

极大欧拉生成子图边数的几个定理

利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .     

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

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

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

多重图的处处无零整数流

【目的】探讨多重图与它的基图的处处无零整数流的存在性之间的关系。【方法】用原图的处处无零整数流构造新图的处处无零整数流。【结果】1）若一个多重图的基图存在处处无零k-流，则它也存在处处无零k-流；2）如果两个多重图有共同的基图，并且它们的任意一条公共边都是基图中某个边的平行边，那么这两个多重图的处处无零k-流的存在性一致。【结论】得到的结果不但有助于对处处无零整数流这一概念的理解，还可应用到简单图的处处无零整数流的研究中。     

特殊卡氏积图的连通性

为了进一步证明Jaeger的猜想＂5-边连通图是Z3-连通的＂的正确性,通过研究特殊图类Flower snark Gk与Cm的卡氏积图Gk×Cm的Z3-连通性,从而旁证了以上猜想。文中给出一种新的约化方法在图Gk×Cm中找Z3-可收缩子图,并最终把它收缩成一点。     

图的字典积的整数流

得到对连通图G1和阶数大于3的图G2,他们的字典积G1[G2]有非零4-流.特别当G2是二部图时,G1[G2]有非零3-流.通过一个完全不同的方法,也得到了如果G1有非零3-流且具有完美匹配或G2有非零3-流,那么G1[G2]有非零3-流.     

边重构问题——连通图的支撑树系列基边向量总表

本文讨论连通图的支撑树系列基边向量总表的有关性质,并用来研究边重构问题,得出一个边3连通图是边可重构的一个充要条件和一族连通图是合法的主子图族的一个充要条件(见§6.5和§6.6)     

一个实用的检验Kn(3,p)的算法

设Ｋｎ是ｎ个顶点的完全图，若对Ｋｎ的每条边着以红色或蓝色，并且图中既不包含红色团Ｋ３也不包含蓝色团Ｋｐ，这样就得到一个二色边图Ｋｎ，同时将这种染色所得的图记为Ｋｎ（３，ｐ），把使Ｋｎ（３，ｐ）成立的最大值记为Ｒ（３，ｐ），Ｒ（３，ｐ）＝ｒ（３，ｐ）－１，ｒ（３，ｐ）是Ｒａｍｓｅｙ数，本给出一个实用的算法，可以对给定连通图检验Ｋｎ（３，ｐ）是否成立 。     

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

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

图的邻点可区别边划分(英)

研究了图的邻点可区别边划分所需要的最少边色数. 通过对图的度进行分类讨论, 证明了不包含$K_{2}$且最小度$\geqslant188$的图有邻点可区别点染色3边划分. 这个结论比已有结果更优越     

简单图的支配数和上可嵌入性(英文)

设图G是n阶简单连通图.如果G的支配数为1,则G是上可嵌入的.如果G是2-边连通且G的支配数为2,则G是上可嵌入的.如果G是3-边连通且G的支配数为3,则G的最大亏格介于|(β(G)-2)/2|和|β(G)/2|之间,其中β(G)=|E(G)|-|V(G)|+1.论文得到了一些在控制数和边连通度条件下的最大亏格的界.     

关于3-连通图的一个猜测的反例

1978年,Dirac 给出了从2-连通图 G 中的最长路判断 G 的周长下界的一个定理.在1983年的西安图论讲习班上,朱永津提出了一个与 Difac 定理形式相似但条件较强结论也较强的猜测.通过发现一个反例,本文得到了这一猜测的否定解答。