图的孤立韧度与分数k-消去图

设G是一个图,k(?) 2是一个整数,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.图G的孤立韧度I(G)定义为:若G是完备图,I(G)=+∞;否则,I(G)=,其中i(G—S)表示G—s中的孤立点数目.本文证明了当I(G)>k,并且δ(G)(?)k+1时,G是分数k-消去图.

图的1-因子、f-因子和(g,f)-因子

设G是一个图且有一个1-因子F，g和f是定义在V（G）上的非负整数值函数且对每个X∈V(G)有g（X）＜f(X)≤dG（x），且f(v(G))为偶数．（i）若对每个xy∈F有f(x)=f(y)且G－{x,y}有一个（g，f)-因子，则G有一个（g，f)-因子；（ii）若对每个xy∈F有f(X）=f（y）且G-{X，y}有f-因子，则G有f-因子.

两类满足A(H)=3的图

本文利用文[3]的方法给出了两类满足A(H)=3的图,从而肯定了满足A(H)=3的图是不唯一的。本文还给出了满足A(H)=3的最小图。

一类满足A(H)=3的新图

本文利用文献 [3]的方法构作了一类满足 A( H) =3的新图 ,从而肯定了满足 A( H) =3的图并非唯一 ,且有无穷多个 .

关于f—复盖图

如果图G的每一条边都属于一个f一因子,则称图G是f-复盖的。本文给出了一个图是f-复盖的充分必要条件,并且证明了若图G是m-复盖的及n-复盖的,m,n,k有同样的奇偶性且m<k<n,则G是-k复盖的。

图角在特征值中的应用

在文献[2]中Peter Rowlinson首次引入图角的概念,对图的特征值给出了一种新形式的刻画,本文在此基础上,对几类图变换,用角刻画出了其特征值的相应变化规律。

图的限制性边连通度等于其最小边度的一个充分条件

设 G是有限简单无向图 .D,g和δ分别表示 G的直径、围长和顶点最小度 .本文证明 :如果 D≤g-2且 δ≥ 3 ,那么 λ′=ξ,这里 λ′=λ′(G)和 ξ=ξ(G)分别表示 G的限制性边连通度和最小边度 .

连通3—控制临界图的小度点数

本文给出连通３—控制临界图度小于等于２的顶点个数的最小上界为３。

求最大权伪对集的一个算法

图的可以含有环的对集称为图的伪对集。William 和 Anderson 给出了求图的最大基数伪对集的一个算法。本文给出了求图的最大权伪对集的一个算法,它是 Edmonds 算法的一个推广。

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .