并图的星—升分解

给出了２个和３个星图之并可以星－升分解的充分必要条件,并部分证明了一个有关的猜想。     

图的路分解

Ｇａｌａｉ提出的小路分解（ＳＰＤ）猜想：任一连通图的路分解的路数的最小数目至多为［（ｎ＋１）／２］,迄今还未完全得以解决而这个问题在运筹、网络及信息最优传递过程中有着实际的应用价值本文利用Ｌｏａｓｚ定理证明猜想在一定条件下是成立的     

一类循环图的最大团

求出了循环图Cn(a1,a2,…，ak)在转移序列满足一定条件时的最大团的阶及其个数，当项点数为最大转移数的2倍与各转移数之和形式时，最大团的阶为3，其余情况最大团的阶为2。     

关于递推团图直径的PRS-猜想

本文证明了存在一个图G 使得它的直径与其n-次团图K~n(G)的直径满足关系。diamK~n(G)=diamG n其中n≥1为整数,这就是所谓PRS-猜想。     

关于CockayneEJ的两个猜想

猜想１〔１〕当Ｋ（Ｇ）＝Ｃ２ｎ＋１时有Ｃ（Ｇ）≤ｄ（Ｇ）;猜想２〔１〕当Ｋ（Ｇ）是偶图时有Ｃ（Ｇ）≤ｄ（Ｇ）．以下通过反例说明猜想１不成立．然后证明猜想２成立．设Ｇ是无向、无环、无多重边的简单图,Ｇ＝（Ｖ,Ｅ）,其中Ｖ＝Ｖ（Ｇ）表示Ｇ的顶点集,Ｅｎ＝...     

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ－临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２。本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ〈ｎ／２，ｎΔ＝４时猜想也成立。同时给出了临界图的两个新的性质。     

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

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

图的一因子分解

本介绍了有关一因子分解的主要概念和主要结构，并举例说明这些定理条件的必要性，最后讨论一因分子解的一个猜想，给出了对这个猜想至今为止的所有结果并举例说明这猜想不是充分必要的。     

关于无爪图最大团数的一个估计

设图G＝（V，E）是一个简单连通图，称所有同边e关联的边集为e的边邻集，记为Г(e)，并称|Г(e)|为e的边度，记为d(e)。在此基础上给出了有关线图的一个充分必要条件和关于无爪图最大团的一个估计。     

关于冠图的路分解

冠图G°H是由图G和H合成的图,其中使图G的每一个顶点分别与图H的每一个拷贝的所有顶点相连.如果图G的边集合可以分解为若干个边不相交的子图H,那么称G有子图H的分解,当H是P3或P4时,就称G有{P}3,P4分解.文章讨论了一些冠图的{P}3,P4分解问题,得到冠图Pm°Pn、Pm°Cn、Cm°Pn及Cm°Cn存在{P}3,P4分解.     

图的团复形的无圈性

图Ｇ 的团复形是一个抽象复形,它的单形是Ｇ 的团,用Ｃ（ Ｇ） 表示。一个复形Ｋ 称为无圈的如果Ｈｑ（ Ｋ） ＝ ０（ｑ＞ ０） ,Ｈ０（ Ｋ） ≌Ｊ。本文证明若图Ｇ 的团复形Ｃ（ Ｇ） 无圈,则对Ｃ（ Ｇ） 作去枝运算可使Ｇ 收缩为一点（ Ｋ１） 。     

正则图分解成重星的一个充分条件

用ｇ（Ｇ）表示图Ｇ的围长。Ｓ（ｋ＿１，ｋ＿２）表示两个非１度顶点分别为ｋ＿１，ｋ＿２的重星。在［２］中证明了：（２ｋ＋１）─正则图Ｇ是Ｓ（ｋ＋１，ｋ＋１）─可分解的充分必要条件是图Ｇ含有１─因子。本文证明的主要结果是：１）设图Ｇ是ｒ（２ｋ＋１）─正则图（ｒ≥２）且ｇ（Ｃ）≥４，如果Ｇ含有ｒ─因子，则图Ｇ是Ｓ（ｋ＋１，ｋ＋１）─可分解的。２）设ｑ＝｜Ｅ（Ｓ（ｋ，ｋ））｜，如果，ｎ＝１（ｍｏｄ２ｑ），则完全图Ｋ＿ｎ是Ｓ（ｋ，ｋ）─可分解的。     

广义De Bruijn图分解问题的一些结果

广义DeBruijn图是最近提出的一种具有良好性质的网络拓扑结构，文中对这类图的分解问题作了初步的分析，构造了一类基本模块，并得出了一些关于模块效率的数值结果。     

关于图的符号团控制数

对于一个非空图G=(V,E)和一个函数f:E→{-1,+1},若SE,则记f(S)=∑_e∈Sf(e).若对于G中每个非平凡的团K均满足f(E(K))≥1,则f被称为G的一个符号团控制函数,G的符号团控制数表达为     

Mycielski图的P4分解

给定图G=(V,E),G的Mycielski图μ(G)被定义为一个新图:V(μ(G))=V∪V'∪{w},其中V'={y'｜y∈V};E(μ(G))=E∪{xy'｜xy∈E}∪{wy'｜y'∈V'},称点y'为y的复制点.文章证明了连通图G的Mycielski图存在P4分解当且仅当G的阶数能被3整除.此外我们还给出了Mycielski图的P4分解的一个多项式算法.     

有向非循环图的可反向边集合的结构与判定

讨论了有向非循环图(dag)G的可反向边集合RG的结构,给出了判断RG的充分必要条件 .这一结果将有助于设计算法搜索G中的等价类,在用得分等价原则学习贝叶斯网络结构时,可以进行局部得分,从而减少所需的数据量,提高效率.