完全偶图的补图的特征根分布

设Ｇ为ｐ 阶连通简单图,其补图Ｇ为完全偶图Ｋｎ,ｍ 及空图Ｋ的并,笔者利用完全偶图的谱的特性,获得了图Ｇ的特征根分布     

完全偶图的补图的色多项式及色唯一性

依据理想子图的概念，得到了其补图为完全偶图及空图之并的图的色多项式，并讨论了这种图的色唯一性。     

偶自补图的计数

本文应用 De Bruijn 的幂群计数定理和偶图计数结果,解决了偶自补图的计数问题,获得了 m 个顶点独立集与 n 个顶点独立集的所有偶自补图的数目:当 m≠n 时是a_(mn)~C=Z(S_m×S_n;0,2、0,2,…),当 m=n 时是a_(mn)~C=Z([S_n]~S_2;0,2,0,2,…).文中并给出了计数偶自补图数目的实用公式.     

偶图特征的谱刻划

本文用图的谱性质刻划偶图及完全偶图的特征性质．     

完全偶图和路的强边着色

研究了完全偶图和路, 并证明了两个结论.     

完全偶图的DS-因子计数

一个图H称为一个双星（Double Star）,当H由2个不变的星K1．m1,K1,m2加上连接它们最大度点的一条边所构成．图G的一个支撑子图F称为一个双星（DS）因子,当F的每一个连通分支是一个双星．本文研究完全偶图Km,n的DS-因子计数,给出了Km,n的DS-因子计数公式．     

能量不超过4的偶图

本文将给出所有能量不超过4的连通简单偶图,并给出关于图的能量与其边的个数的一个不等式。     

关于n—可扩偶图一个极值问题的注记

本文讨论了ｎ－可扩偶图的一个极值问题，证明了任意具有ｐ≥２（ｎ＋１）个顶点、ｑ条边的有完美匹配的偶图是ｎ－可扩的充分条件是ｑ≥ｐ／２（ｐ／２－１）＋ｎ＋１。     

偶图的边共色数

给出了f（Δ）≥Δ条件下偶图的边共色数及偶图边共色数的一种算法,并确定了k-正则偶图,Kp1,p2及Kp1,p2,…,pk的边共色数.     

Hamiltonian图补图的若干充分条件

补图是图的一种重要的运算,每一类图的补图具有一些性质,Hamiltonian图作为一类重要的图,当图的顶点的度满足某些性质时,那么其必为Hamiltonian图的补图。     

完全图与完全偶图的笛卡尔乘积的联结数

本文给出了完全图与完全偶图的笛卡尔乘积的联结数计算公式,证明了如下定理;■     

图和补图的荫度

本文研究了图和补图荫度间的关系,并猜想:对p阶简单图G(V,E),有 a(G)+a(G~c)≤1+[p/2] 其中G~c表示G的补图,a(G)表示G的荫度,[x]表示不小于x的最小整数。     

关于偶图的能级

本给出所有能级不超过４的连通偶图,并给出关于图的能级与其边的个数的一个等式。     

一类G＝（p,p＋1）且R（G）＝—2图簇的补图的色唯一性

本文利用图的伴随多项式的最小根的性质,讨论了几类n个点n 1条边且R（G）＝－2的不可约图簇的补图的色唯一性的问题。     

正则图与其补图的全色数

利用全图的性质研究图的全色数.给出正则图及其补图的全色数之间的关系。得到:若 G 是 k-正则图(2≤k相似文献   

圈与完全偶图的笛卡尔乘积的联结数

本文给出了圈与完全偶图的笛卡尔乘积的联结数计算公式,证明了如下定理:这里S≥3,m≥2,n≥2,l=min{m,n},均为整数.     

赋权非完全偶图的最优分派问题及其初步应用

本文主要讨论了具有二分类的赋权非完全偶图的最优分派问题，通过寻找一个具有最大权的亚完美对集，从而也就确定了具有最大权的对集，进而判断人员是否需要调整。     

在加权完全偶图中求2边最优匹配的算法

给出不完全最优匹配的定义,并提出在加权完全偶图中求2边最优匹配的算法,最后举例说明其应用.     

导出匹配可扩偶图的度条件

称简单图Ｇ为导出匹配可扩图，若Ｇ的任一导出匹配均含于Ｇ的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。