4类图完美匹配的计数

用划分,求和,再嵌套递推的方法给出了4类图完美匹配数目的显式表达式,利用所给出的方法可以计算出相同结构重复出现的许多图的所有完美匹配的数目.     

3类图完美匹配的数目

图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景．但是,一般图的完关匹配计数问题却是NP-困难的．用划分、求和、再递推的方法给出了三类特殊图完美匹配数目的计算公式．     

泡型图的条件匹配排除

一个图的条件匹配排除数是最少的边的数量,使得删除这些边形成的图既没有孤立点,也没有完美匹配和几乎完美匹配.本文给出了泡型图的条件匹配排除数和它的所有最优集.     

完美匹配图的边哈密顿性

本文研究无向简单图G中的完美匹配之间Y-变换,并根据Y-变换定义了图G的完美匹配图M(G)2 进而用纯图论的方法证明了,当G至少存在三个完美匹配时,M(G)的任一边必在M(G)的某一哈密顿圈上。此结果可以纳入(0,1)多面体的一般框架中,但我们给出的证阴是直接与构造性的.     

三个图类的完美匹配计数(英文)

对一个具有偶数个顶点的图,计算它的完美匹配数是一个广泛而且深入地研究着的课题。对大量的图类,这个课题的研究已取得许多重要而且漂亮的结果。特别地,计算那些代表着某些有机化合物的图类的完美匹配数问题在理论和应用上都有着重要意义。本文讨论了三个图类的完美匹配计数,并对所有可能的情况给出完美匹配数或计数公式。     

偶匹配可扩图的度和连通度条件(英文)

称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.     

二面体群的双凯莱图的匹配可扩性（英文）

令G为有限群,S为G的非空有限子集,G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配,则称此完美匹配的连通图Γ是n-可扩的,并对二面体群的双凯莱的2-可扩性进行了刻画.     

二面体群的双凯莱图的匹配可扩性

令G为有限群,S为G的非空有限子集，G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配，则称此完美匹配的连通图Γ是n 可扩的,并对二面体群的双凯莱的2 可扩性进行了刻画.     

关于全图补图的完美匹配

G是一个简单图,变换图G---是G的全图的补图.证明了对于给定的一个图G,G K1 K2,G---有一个完美匹配的充要条件是V(G) E(G)是偶数.     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

求一切完美匹配的一个算法

本文设计了一个求一切完美匹配的算法,它由下面的四个子算法组成:算法1 利用Edmonds.J算法,求一个完美匹配M(略)。算法2 利用类似深度搜索法的技术,求含M的某条边的一切M-交错回。算法3 求一切M-交错回。算法4 求一切完美匹配。     

具有完美匹配的单圈图第二大特征值的上界

得到了具有完美匹配的单圈图第二大特征值的一个上界．同时也给出了具有完美匹配的单圈图的第二大特征值的最大值的一个下界．     

六角系统中完美匹配的覆盖与对应

本文建立了六角系统完美匹配集与覆盖集间的对应,并研究了它的一些性质。     

具有完美匹配的图的顶点覆盖问题

对具有完美匹配的无向图的顶点覆盖问题进行了研究,提出了2个相关的问题,并对它们的难解性做出了判断.     

图的补距离矩阵谱半径的最大值

在具有给定阶和匹配数且直径不超过2的所有连通简单图中, 确定了具有最大补距离矩阵谱半径的图.     

凸六角系统（Ⅱ）

本文在凸六角系统分类的基础上给出了它的自同构群有完美匹配存在的充要冬件和计数函数的不定方程。     

K—可覆盖冠状系统的实现

一个冠状系统(coroniod system)G被称作是k-可覆盖的,如果对任何k个互相邻接的六角形,从G中删去这k个六角形以及相关联的边后得到的子图至少含有一个完美匹配,本文得到一个简捷的方法,由此可以确定是否存在k-可覆盖的冠状系统,并且确定出了这些k-可覆盖的冠状系统。     

几类整循环图的秩的界

循环图是并行计算和分布式计算中一类重要的互联网络拓扑图，整循环图在支持完美状态传递的量子自旋网络模型中具有重要作用。图的秩定义为图的邻接矩阵的秩。利用Ramanujan和，借助Euler函数和Mobius函数，研究了几类整循环图的秩，得到了这些整循环图的秩的较为精确的界。     

循环图的预解Estrada指标

Circulant graphs are an important class of network topology. Let G be a simple graph with n vertices, let A be the adjacency matrix of G, and λ₁,λ₂,…,λ_n be the eigenvalues of graph G. As a kind of centrality of complex networks, the resolvent Estrada index of G is defined as EE_r(G)=((1-λ_i)/(n-1))^-1. By Ramanujan's sum, using the Euler function and Mobius function, we characterize the lower bound of resolvent Estrada index of circulant graph, and obtain some computational formulas of integral circulant graphs.