几类亚随意匹配图

Dauidc P.Sumner在[1]中首次引进了随意匹配图概念;尔后孟吉翔同志又在[2]中引入了亚随意匹配图的概念,並提出了几类亚随意匹配图,本文在此基础上又导出了另几类亚随意匹配图。本文中所论及的图都指有限简单连通图,未说明的术语或记号均与[3]同,     

几类亚随意匹配图

David P.Sumner 在[1]中首次引进了随意匹配图的概念,并且证明了,随意匹配图有且仅有 k_(m,n)和 k_(2n)(n≥1);尔后,孟吉翔同志在[2]中引入了亚随意匹配图的概念。在文[2]、[3]中提出了几类亚随意匹配图。本文在此基础上又得到了几类更广泛的亚随意匹配图。从而,文[2]、[3]的几个主要定理都成为本文的特殊情形。本文中所论及的图都是指有限简单连通图,未说明的术语或记号均与[4]同。     

几类图完美匹配的数目

图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目.     

几类图簇匹配多项式的因式分解定理及其应用

通过研究几类图簇的匹配多项式的因式分解,给出了证明图的非匹配唯一性的一种新方法,并得到了这几类图簇的匹配等价图的结构性质.     

几类特殊图完美匹配数目的递推求法

匹配计数理论是图论的核心内容之一,此理论有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-难问题.用划分、求和、嵌套递推的方法给出了几类图完美匹配数目的显式表达式.     

几类非匹配型分配格

给出了具有完美匹配的平面二部图的交不可约内环的概念及其等价刻画,利用这一概念和Kuratowski定理,证明了几类特殊有限偏序集的滤子格是非匹配型的.     

几类图的树宽

利用图的树宽分解定理,得到圈Cn的r-冠图Ir（Cn）、方型网图F（m;n）（m=1,2,3）、蛛网图W（m,n）和图Pm Pn的树宽.     

几类自中心图

称基回数为3且不含2度顶点的自中心图为基本图。本文证明基回数为3的自中心图只有四种不同构的基本图、给出两类图是自中心图的充要条件。此外,证明正多面体,K—方体图都是自中心图。     

几类图的星色数

本文研究了一些图形的星色数。并对图含有割边、割点时与其子图星色数间的关系进行了探讨。     

几类边友好图

证明n-荷兰风车和Dn,4是边友好图,并且给出梯图Ln是边友好图的充要条件以及一阶网图F（1,n）是边友好图的充分条件.     

几类整谱图

研究二部半正则图的补图、二部补图的特征多项式公式，给出几个特殊图类的谱，得到几类整谱图的充要条件及一些新的整谱图类。     

几类图的连续边着色

设G是简单图，用颜色1，2，3，…，对G的正常边着色，如果每一个顶点上表现的颜色都构成一个连续的整数集合，那么就称这个边着色是连续的，图G的亏度def（G）是粘在G上使它可连续边着色的悬挂边的最小数目，对几类图的亏度进行了研究。     

完全多部图中的色正规图类

设G是简单图,用P(G,λ)表示图G的色多项式。简单图H称为与G是色等价的(记作H∽G),如果P(H,λ)=P(G,λ)。简单图类L称为色正规图类,若对任意H,G∈L使H∽G,都有H与G同构(记作H≌G)。本文证明完全三部图类和完全四部图类是色正规图类。     

几类图的相邻顶点可区别的全染色

给出了几类特殊图相邻顶点可区别的全色数,如双路间和二部(V1,V2)间叠加匹配形成的系列图、双圈(prism)、双轮.并得到边连通度λ(G)=1的图相邻顶点可区别的全染色的性质.     

路并的匹配等价图数

两个图G和H的匹配多项式相等,则称它们匹配等价.用δ(G)表示图G的所有不同构的匹配等价图的个数.计算了一些路的并图的匹配等价图的个数.首先将整数m(≥2)按它所含的最大奇因数分成3-系和2k(k=1.2,…)-系,再按它所含2的方幂分为级.设A是不小于2的整数组成的可重集,B_i(i=1,2,…,t)是同系整数构成的可重集,且A=B_1∪B_2∪…∪B_t,则δ(■P_i)=■δ(■P_i),若x∈B_i,y∈B_j(i≠j),则x与y是互不相同系的整数.设B={m_1~(k_1),m_2~(k_2),…,m_n~(k_n)}是同系整数构成的可重集,其中m_i(≥2)是第i级的,有k_i(≥0)个,则n =1,δ(■P_i)=1;n≥2,δ(■P_i)=sum from i_m-0 to k_n sum from i_(m-1)-0 to k_(n-1) i_m…sum from i_2-0 to k_2 i_3 1.作为推论,计算了路并补图的匹配等价图的个数.     

两类图的边色数

设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。     

几类特殊的M2-等可覆盖图

若图G的每个极小H-覆盖都是它的最小H-覆盖,则称图G为H-等可覆盖的．得出了M2-等可覆盖图的必要条件,并刻画了以下几类特殊M2-等可覆盖图的特征：匹配、路、圈、完全图、完全二部图、轮图和扇图．     

一些图的关联着色

1993年．Brualdi和Massey猜想每一个图G可以用△（G）＋2种色正常关联着色．尽管Algor和Alon通过一个例子否定了该猜想,但是对一些特殊图类该猜想可能成立．通过给出块图和单圈图的关联色数。证明了猜想对这两类图成立,并讨论了图G和H的冠图的关联色数．     

一类图的匹配唯一性

研究了图的匹配唯一性,给出了T(3,4,n)∪(s∪i=0Cpi)(n 5)及补图匹配唯一的充要条件.     

二分图对集的可扩性

设G是一个连通二分图,G=(X,Y;E),本文主要证明了当|X|=|Y|,若δ(G)≥2n+1(1≤n≤|X|2,n∈N),且对G的任两个距离3的顶点u,v有d(u)+d(v)≥|X|+2n时,G是2n-可扩充的