具有给定阶和最大度的单圈图的最大匹配能量

图的匹配能量由UTMAN等于2012年提出,定义为图的匹配多项式的根的绝对值的和. 如果一个连通图的边数与点数相等, 或有唯一的一个圈,则称为单圈图.刻画了在具有给定阶与最大度的所有单圈图中达到最大匹配能量的图.     

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

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

单圈图最小特征值的Sharp下界

设G是一个具有n个顶点的简单图，λn(G)为图G的最小特征值，而单圈图就是其边数等于点数的连通图，本文给出了单圈图最小特征值的一个Sharp下界，并同时给出达到这个下界的极图。     

单圈图和双圈图的连续边着色

设G是简单图,用颜色1,2,3,…对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图G的亏度def(G)是粘在G上使得它可连续着色的悬挂边的最小数目.在本文中,我们完全确定了单圈图和双圈图的亏度.     

化学单圈图的原子键连通性指数

图G的原子键连通性指数的定义如下:ABC(G)=∑uv∈E(G)((du+dv-2)dudv)(1/2).其中du、dv分别表示图G的边uv的2个端点u、v的度数.ABC指数已被证实为研究烷烃的稳定性以及环烷烃的应变能提供了一个很好的模型.讨论了n阶化学单圈图,给出了其ABC指数的可达的下界及其相应的极图     

哈林图的偶匹配可扩性

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

泡型图的条件匹配排除

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

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

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

关于全图补图的完美匹配

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

超能整循环图的构造

图G的能量E(G)定义为图的特征值的绝对值之和.如果图G的能量E(G)2n-2,则具有n个顶点的图G称为超能图;如果它是循环群上的Cayley图,即其邻接矩阵是一个循环矩阵,则称其为循环图.整循环图是指循环图的特征值全为整数.基于Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性.同时,利用Cartesian积图给出了一个构造超能整循环图的方法.     

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

令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 可扩性进行了刻画.     

3类图完美匹配的数目

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

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

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

2类特殊图中的完美匹配数

图的完美对集计数问题已经被证实是NP-难的,因此要得到一般图的完美匹配数目非常困难.用划分、求和、再递推的方法给出了4-1-nC_(10)和2-nT_2图完美匹配数目的计算公式.该方法可计算许多图类的所有完美匹配的数目,使得到一般的有完美匹配图的所有完美匹配数目成为可能.     

几类亚随意匹配图

David P.Sumner在[1]中引入了随意匹配图的概念;如果图G的任意匹配都能扩充为G的完备匹配,则称G为随意匹配图.他证明了当且仅当G为     

双圈图的极小广义Randi指标(英文)

图G的广义R and i′c指标定义为Rα(G)=∑uv∈E(G)Rα(uv)=∑uv∈E(G)(d(u)d(v))α,其中d(u)是顶点u的度,α是实数.胡玉梅等给出了树的广义R and i′c指标的下界及其极图,吴宝音都仍等基本上给出了单圈图的广义R and i′c指标的下界及其极图.本文讨论双圈图G的R and i′c指标.利用吴宝音都仍的方法得到:当α>0时,Rα(G)≥6.6α (n-5).4α(这里n=G).同时确定了这样的极图.     

完美匹配图的边哈密顿性

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

一种适用于SM4的改进RSM掩码方案

为了增强SM4算法抵御能量分析攻击,提出了一种改进的循环移位S盒掩码(RSM,rotating S-box masking)算法.该算法采用RSM掩码与固定值掩码相结合的方法,结合SM4算法本身的加密特性,不需要设计者对掩码进行人工操作,就可以起到循环移位S盒的目的,从而有效降低了功率消耗与中间值的关联性.安全性分析表明,本方案可以有效抵御高阶差分能量分析(DPA)攻击,是一个非常匹配SM4算法的掩码方案.     

2k-点可删的导出匹配可扩图

设G是一个简单图．称G是2k-点可删的导出匹配可扩图,如果对于V（G）的任一满足│S│=2k的子集S,G—S是导出匹配可扩的．给出了2k-点可删的导出匹配可扩图的两个充分条件,证明了这两个条件都是最好可能的．