有向图中不相交的准核(英文)

有向图D的一个顶点集X被称为D的一个核,如果X是一个独立集并且X之外的每一个点都能经一步到达X.有向图D的一个顶点集X被称为D的一个准核,如果X是一个独立集并且X之外的每一个点都能经一步或两步到达X.在这篇文章中,我们给出了一个有向图有一对不相交的准核的一个必要条件和若干充分条件.

S—控制圈的一个充分条件

设Ｇ是ｋ—连通的ｎ阶图，ｋ≥２，若对于Ｇ中的满足（对任意的任意（ｋ＋１）—独立集Ｘ，有则Ｇ中存在Ｓ—控制圈．

无爪图过特殊子图的路

设Ｇ是ｋ—连通无不科，Ｓ是Ｇ的子图．Ｇ中过Ｓ所有顶点的路称为Ｓ—路．证明了：若ａ３（Ｓ）≤ｋ＋１，则Ｇ含Ｓ—路，这里ａ３（Ｓ）为Ｓ的在Ｇ中两两距离至少为３的顶点的最大数目．推广了如下结论；若ａ（Ｇ２）≤ｋ＋１，则Ｇ是可迹的，这里Ｇ２为Ｇ的平方图．

基于有序细胞自动机的图像加密方案

结合Lafe给出的基于细胞自动机变换的压缩技巧,提出了一个新的基于有序细胞自动机(CA)的图像加密方案。新的方案既利用了基于细胞自动机的变换对二维图像具有良好压缩效果的特点,又用有序细胞自动机的加密技术弥补了Lafe方案中加密效果不理想的缺点,使得密钥空间至少达到2H×2512×233 554 432。模拟结果表明,该方案具有良好的细胞自动机雪崩效应的特性,即局部规则的微小改变将导致密文的大幅度变化,且具有易于实践、成本低等优点。由于有序细胞自动机具有平行结构简单、密钥量大和加密速度快的特点,所以这种加密技术非常适用于光学实现领域的应用。

K(1,4)-自由的模k泛圈图(英文)

设G是2-连通的K1,4自由图.本文证明了当δ(G)≥k+1时,G是模k泛圈图.这一结果肯定了猜想2,继而也肯定了Thomassen猜想在2-连通图中的正确性.

基于二维CA和CWQ方法的图像加密方案(英文)

细胞自动机简称CA,是具有离散的空间和时间特性的动力系统.在过去的10多年里,细胞自动机在密码系统和信息安全方面的应用得到了人们相当大的关注和兴趣.本文给出了一种结合格图结构摩尔邻域的二维CA方法和基于四叉树结构的CWQ方法的图像加密方案.首先,二维CA的加密方法可以比仅进行混淆作用的CWQ方法更有效地提高系统的安全性.其次,CWQ方法可以加强具有雪崩效应和扩散性质的二维CA方法的混淆性质.方案具有大密钥量且简单易行适用于数字图像加密等特点.

过特定顶点集S的S-D-圈与S-D-路

利用邻域交给出了图Ｇ的每个Ｓ－最大圈都是Ｓ－Ｄ－圈的一个充分条件．并给出了对任意｛ｕ，ｖ｝Ｖ（Ｇ），Ｇ的每条（ｕ。

泛圈图的一个充分条件

在文[1]中给出定理,设G是一个n-阶2-连通图且δ(G)≥t,若对于G的任意两个不相邻的点u和v,均有|N(u)∪N(v)|≥n-t成立,则G是一个泛圈图或G Kn2,2n.本文的目的在于将此定理的条件减弱,只对图中距离为2的点进行讨论,得出了泛圈图的一个充分条件.文中主要用数学归纳法对定理进行证明,先在引理中给出了几种特殊情况的证明,接着在定理的证明中讨论了一般情形.

满足xyz=--+的变换图G^(xyz)

图G的变换图G--+以V(G)∪E(G)为其顶点集,对任意的α,β∈V(G)∪E(G),α和β在图G--+中邻接的条件如下:(i)α,β∈V(G),且α和β在G中不相邻,(ii)α,β∈E(G),且α和β在G中不相邻,(iii)α∈V(G),β∈E(G),且它们在G中相关.本文主要证明除了12个图外,G--+都不是可平面图,以及对于图G,G--+≌Pn--+当且仅当G≌Pn.

2-连通图过指定边的长圈(英文)

对2 连通非完全图G,令μ(G)=min{max{dG(u),dG(v)}dG(u,v)=2}.一个著名的范定理:每一个2 连通非完全图G包含长至少为min{V(G),2μ(G)}的圈.在这篇论文中我们证明了:若G是2 连通无三角形图,则通过G的任一边存在长至少为min{V(G),2μ(G)}的圈.

拟无爪泛圈图的一个充分条件

设G是一个图.若对G中任意距离为2的点对x,y,总存在u∈N(x)∩N(y),使得N[u]■N[x]∪N[y],则称G是拟无爪图.本文给出了拟无爪图是泛圈图的一个充分条件:设G是n阶2-连通无{K4,P5,A}的拟无爪图,GCn,则G是泛圈图.

图上的对策着色和对策着色数

图G的对策色数Ⅱχg(G)是由图的点色数χg(G)拓展而来的.本文对几类特殊的图进行了讨论,分别给出了图Qn,Gn以及与圈有关图的对策色数Ⅱ,并给出了选手Alice相应获胜的对策.

一类变换图的同构问题

利用度序列的概念,证明变换图G^(--+)与H_n^(--+)同构,当且仅当G与_n同构.以及在G连通的条件下,G^(--+)与C_n^(--+)同构,当且仅当G与_n同构.

连通图的拟拉普拉斯谱半径的一个上界

对于连通图G,矩阵Q(G)=D(G)+A(G)称为图G的拟拉普拉斯矩阵,其中D(G)为图的度对角矩阵,A(G)为图的邻接矩阵.本文利用矩阵的一些性质,推导出连通图的拟拉普拉斯谱半径的一个上界.并将该上界与已有的一些结论结合具体图例作了优越性比较.

无爪图周长的一个下界

给出了k-连通的非Hamilton无爪图(k≥2)周长的一个下界.

无爪图的周长

证明了如果G是k-连通的非H am ilton无爪图,k≥2,则G包含一个长度至少为:m in{∑x∈Xd(x)+2k∶X是G的独立集,X=k}的圈.

赋权图过指定点的圈

设G是满足条件D1和D2的2-连通非Hamilton赋权图,证明了如下新结果:若G满足dw(x)+dw(y)≥m(xy E(G),x≠y),则通过图G的每个顶点存在权重大于或等于m的圈.该结果推广了非赋权图的已有结果.

六点七边图的图设计

六点七边图(不带孤立点的简单图)共有17个图.应用GDD、加权和闭包思想给出了所有六点七边图图设计的构造方法,同时在构造G-HD(7k)(k=3,4,5,6,8)时运用了阿贝尔群的性质,简化了构造过程,并用此方法举例说明如何具体讨论六点七边图图设计的存在性问题,从而得出如下结论:满足v≥k,v(v-1)≡0(mod2e),v-1≡0(modd)且v≥14时,均存在(v,G,1)-GD,其中对v=7,v=8的情况单独讨论.

二部图的四圈覆盖

设k是正整数,G=(V1,V2;E)是一个二部图,满足|V1|=|V2|≥2k+1,若对G中任意的两个顶点x∈V1,y∈V2,都有d(x)+d(y)≥83k,则G恰好被k个独立的四圈所覆盖。

浅议社会主义商品生产与商品流通的统一

社会主义商品生产的规模和程度决定着商品流通的规模和程度,对这一点我们应有充分认识。俱也必须看到,商品流通对于商品生产来说,也并不是消极和被动的。商品生产和商品流通“这两种社会职能的每一种都处于多半是特殊的外界作用的影响之下,所以都有多半是它自己的特殊的规律。但是,另一方面。