图的匹配设计的矩阵构造法

完全图Ｋ_ｎ（完全二部图Ｋ_ｎ,ｎ）的一个ｋ－匹配的集合Ｍ,若满足：Ｋ_ｎ（Ｋ_ｎ,ｎ）的每一对独立边恰出现在Ｍ的λ个元素中,则称Ｍ为一个匹配设计,记为ＭＡＴＣＨ（ｎ,ｋ,λ）（ＢＩＭＡＴＣＨ（ｎ;ｋ,λ））一设计．本文定义两个匹配设计对应的矩阵,并以此构造出某些新的匹配设计．     

含偶长圈的7点7边图的图设计

设λKν是ν阶λ重完全图，G是一个无孤立点的有限简单图,λKν的一个G-分拆(或G-设计，记为G-GDλ(ν))是指一个序偶(X，β)，其中X是完全图Kν的顶点集，β是Kν中同构于G的子图(称为区组)的族，使得Kν中每条边恰好出现在β的λ个区组中，本文完全解决了含偶长圈的十个7点7边图的图设计存在性问题。     

广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

赋权二部图最大匹配的灵敏分析

本主要从理论上讨论赋权二部图的权的变化对最优解的影响，并在原最大权匹配的基础上给出求解权值变化后的最大权匹配的算法。     

Sm ∨ Kn,n的边色数和均匀全色数

本文得到了m 1阶星和完全等二部图联图的边色数和均匀全色数.     

广义K（4,n）图和Griozsch图Gn边着色分类

本文给出了四点完全图Ｋ４的广义图Ｋ（４，ｎ）和Ｇｒｉｏｚｓｃｈ图的广义图Ｇｎ的一种边关色法，从而解决了它们的分类问题。     

完全等部二分图kn,n的迭线图Lm(kn,n)的谱特征

研究了完全等部二分图Ｋｎ,ｎ的迭线图Ｌ＾ｍ（Ｋｎ,ｎ）的谱特征,证明了当ｎ≥７时,Ｌ＾ｍ（Ｋｎ,ｎ）以谱为特征。     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

具有唯一K_k- 因子的最大图

这里考虑的是简单图.图 G 的 K_k-因子是 G 的这样一种支撑子图,它的每个连通片皆同构于 k 个节点的完全图 K_k.本文给出:如果 G 具有唯一的 K_k-因子,则|E(G)|≤n~2·k(k-1)/2;进而,对于|E(G)|=n~2·k(k-1)/2的图 G 完全确定了 G 的结构.     

关于二部图Km1m2-Hm2的升分解

在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD)，并提出了一个猜想：任意有正数条边的图都可以升分解．本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解，其中Hm2是至多含m2条边的Km1m2的子图．     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

图Pn∨Km,n的全色数

对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.     

图的色多项式系数之和问题的研究

本文给出了任何简单图G(V,E)的色多项式P(G，λ)=∑i=1^vαiλ^i系数之和的公式：∑i=1^vαi={0ε≠0 1ε=0;并进行了证明，从而为判别一个多项式不是图的色多项式提供了一个必要条件．同时也分别给出了树、2-树、圈、轮图和完全图的色多项式系数绝对值之和的表达式．最后证明了任何简单连通图的色多项式系数绝对值之和∑i=1^v|αi|与边ε成正比，且必满足2^v-1≤∑i=1^v|αi|≤пi=1^vi．     

两类图的匹配等价类

完全刻画了Ｐｍ和Ｋ１∪Ｇｍ以及它们的补图的匹配等价图类。     

I形图的匹配等价图类

完全刻画了In以及它的补图的匹配等价图类。     

关于二部图K(m,n)-2的色唯一性

设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞(（ｎ－ｍ）^２＋８)^1/2＋１/２（ｎ－ｍ）^２＋４，则Ｋ（ｍ，ｎ）－２是色唯一图；２．当ｍ≥３时，Ｋ（ｍ，ｍ）－２，Ｋ（ｍ，ｍ＋１）－２和Ｋ（ｍ，ｍ＋２）－２均是色唯一图．     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。     

Pm ∨Kn,Cm ∨Kn的点可区别的边染色

本文通过给出联图的定义,研究了两类联图的点可区别边色数,并给出了具体的染色方法,得到了路和完全图、圈和完全图的联图的点可区别边色数.     

完全三部图K(n-k,n,n)的色唯一性

通过对图的特征子图个数的比较,给出了图K(n-k,n,n)色唯一性的数值条件.     

K1,r—free图的次限制树多项式算法

设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ〉０整数。Ｇ中存在生成对Ｔ，使得Δ（Ｔ）小于ｄ吗．这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法。本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅｅ时，则有Ｏ（ｎ＾２）的算法求出Ｇ生成树Ｔ，使Δ（Ｔ）≤ｒ，并用一个例子显示了这一结果是最好可能的。