强笛积图的边联结数

本文研究了强笛卡尔积图的边联结数，求得了路与路、路与圈、圈与圈、路与完备图、圈与完备图、路与完备偶图、圈与完备偶图、完备图与完备图、完备图与完备偶图、完备偶图与完备偶图的强笛卡尔积的边联结数。     

二分图的无关分解

二分图的覆盖求解是一经典图论问题,该问题的求解可应用于并行阵列的重组和超大规模集成电路的修复,本文提出了二分图的无关分解概念,并给出两种具体算法及其结果。     

二分图中存在哈密顿[k,k+1]因子的条件

主要研究在均衡二分图G中哈密顿[k，k＋1]因子的存在性．根据图论中因子和度的理论，针对均衡二分图，研究图G的阶、最小度、顶点之间距离三者之间的关系．通过对每一对距离为2的顶点度的限制，分情况讨论并给出图G存在包含哈密顿圈C的[k，k＋1]因子的充分条件．如果G的每一对距离为2的顶点u，v口有max{dG（u），dG（v）}≥n/4＋2，则对G的任意哈密顿圈C，G有[k，k＋1]因子包含圈C．在很大程度上改进了已有的包含哈密顿圈C的度的条件，进一步完善了包含哈密顿圈C的因子理论，算例表明此结论的有效性．     

有向循环图G（n,a1,a2）中哈密顿圈的存在性判别及其结构

本文详尽讨论了有向循环图Ｇ（ｎ，ａ１，ａ２）存在哈密顿圈的充分必要条件，并揭示了其中哈密顿圈的组合结构。我们还构造了一个Ｏ（ｎ＾３）算法，当Ｇ（ｎ，ａ１，ａ２）为哈密顿图时，算法可求出它的所有哈密顿圈。     

奇数度循环图的分解

研究了奇数度循环图，指出：若连通循环图Ｃｎ（ｊ１，ｊ２，．．．，ｊｒ）（ｊｒ≠ｎ／２）可分解为ｒ个哈密尔顿回，则连通循环图Ｃｎ（ｊ１，ｊ２，．．．，ｊｒ，ｎ／２）可分解为ｒ个哈密尔顿回与ｎ／２条互不相交的边。     

某些偶数度循环图的同构因子分解

根据连通循环图的性质，证明了循环图的同构因因子分解，对于某些偶数度循环图结论成立，得到了Ｃｎ（ｊ１，ｊ２，…，ｊｒ）及Ｃｎ（１，２，…，ｒ）的同构因子分解条件。     

4度循环图的同构因子分解

本文证明了对４度循环图的同构因子分解，可分性条件是充分条件。     

关于正则图的路分解

在3-正则图的{P3,P4}分解的基础上,结合偶次图的圈分解,证明了任意的4-正则图存在{P4,P5}分解,任意的5-正则图存在{P5,P6}-的分解。同时还提出了k-正则图路分解的猜想。     

图的（g,f）—因子分解

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数，且ｇ≤ｆ图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｈ，使对任意ｘ∈Ｖ（Ｈ）有ｇ（ｘ）≤ｄＨ（ｘ）≤ｆ（ｘ）若图Ｇ的边集能划分为若干边不相交的（ｇ，ｆ）－因子，则称Ｇ是（ｇ，ｆ）－可因子化的，给出一个图是（ｇ，ｆ）－可因子化的一个充分条件，改进了有关结果。     

图的正交（g,f）——因子分解

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每一个ｘ∈Ｖ（Ｇ）有２≤ｇ（ｘ）≤ｆ（ｘ）,证明了若Ｇ是（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图,则对Ｇ中任意一个给定的有ｍ条边的子图Ｈ,Ｇ有一个（ｇ,ｆ）－因子分解与Ｈ正交。     

图的(g,f)—因子分解

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数，且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）—因子是Ｇ的一个支撑子图Ｈ，使对任意ｘ∈Ｖ（Ｈ）有ｇ（ｘ）≤ｄＨ（ｘ）≤ｆ（ｘ）．若图Ｇ的边集能划分为若干个边不相交的（ｇ，ｆ）—因子，则称Ｇ是（ｇ，ｆ）—可因子化的．给出了一个图是（ｇ，ｆ）—可因子化的一个充分条件，改进了有关结果．     

关于图的(g,f)-因子分解的若干结果

对目前关于图的因子分解研究中的3个问题进行了讨论,得到了以下结果(1)设Z= {x∈V(G) dG(x) - mg(x)≤t(x), 或mf(x) - dG(x)≤t(x);t (x) = f (x)– g (x) > 0}.当Z≠SymbolFCp时,g和f可以不全为偶数,能使(mg, mf)-图有(g, f)-因子分解.(2)G是具有2n个顶点的m-正则图,m ≥n.若(P1,P2,…,Pr)是m的一个划分,则G的边集E(G)能划分成r个部分E1,E2,…,Er,使G[Ei]是G的Pi-因子,其中Pi ≡ 0 (mod 2),I= 2,…, r;P1 ≡m (mod 2).(3)G是具有2n个顶点的m-正则图,m≥n.若G不含有K3,则G有1-因子分解.