双圈图的优美性

针对双圈图, 设计一种图的优美性判定算法, 并对17个点内的所有双圈图进行优美性验证, 得到了该范围内所有的优美图和非优美图. 结果表明, 在17个顶点范围内, 除∞ 型双圈图C_(m,n)外, 其余所有双圈图都是优美的, 其中(m+n)(mod 4)={1,2}. 最后给出该类图的非优美证明, 并进一步猜测当顶点数大于17时, 该结论仍成立.     

两类图的优美性

优美图是图论中的重要研究课题,但至今由于缺乏一般性的研究手段,寻找具有优美性的图类仍是这个领域内的研究重点.优美图也是图论中极有趣的研究课题之一,由于它的趣味性和应用性,从60年代中期一经提出,就得到了人们的重视,它在射电天文学、密码学、通讯网络编地址、电路设计、导弹控制码设计等领域有着广泛的应用.图G1n是由n个C4依次连接其对顶点而形成的一个圈.图Gp1n是将图G1n中n个连接点用n个长为1的路P替代后得到的图.图C2n是由n个C4依次连接其相邻点而形成的一个圈.图Gp2n是将图G2n中n个连接点用n个长为1的路P替代后得到的图.本文讨论了两类图Gp1n和Gp2n的优美性,用构造的方法给出了这两类图的优美标号,得出它们都是优美图的结论.     

"m-脚"链图的优美性

定义了"m-脚"链图(即在P2×Pn的m个顶点各粘接一条悬挂边),讨论了它的优美性,得到了6种情形下的"m-脚"链图是k-优美的二分图,并给出了相应的优美标号.     

关于优美树的一个结果

每一棵树都是二部图,从而可把树的顶点按二部图唯一地分为二部分.本文证明一部分为5个顶点的树为优美树.     

轮形图和扇形图的优美性

设L为简单无向图G的一个顶点标号,若L满足:(1)L为G的顶点集V到{0,1,…,|E|}的一个单射;(2)由L(′e)=|L(u)-L(v)|(其中e=uv)决定的边标号L′是从G的边集E到{0,1,…,|E|}的一个双射,则L称为图G的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

全图的优美性研究

本文研究完全图、完全多部图的优美性,主要得到以下结论：完全图Kn是优美图的充要条件是该图的顶点数不超过4,完全多部图K1,m,n、K2,m,n都存在优美标号算法,从而说明它们都是优美图等．     

一类图的优美性

设￣／Ｑｎ（ｎ≥３，ｎ∈Ｎ）表示王冠Ｑｎ的回路Ｃｎ上的每相邻顶点之间都加入一个顶点后得到的图，证明了图￣／Ｑｎ都是优美图。     

几类并图的优美标号

 对非连通并图的优美性进行了研究,给出了几类非连通的并图,得出了如下结果：对任意的正整数n,m,设s是不超过n/2的最大整数,P_n是n个顶点的路,St(m)是m+1个顶点的星形树,路P₂的补图与路P_n的联图记为A_n,则当n≥2时,A_2n与任意一个具有n-1条边的优美图的并图是一个优美图;当n≥5,m≥s+2时,A_n与星形树St(m)的并图是一个优美图,从而A_n与星形树St(n)的并图是一个优美图;当n≥5时,A_n与任意一条路P_n的并图是一个(n－s)-优美图。     

关于不连通优美图及优美图的构造

在本文中,我们称G是不连通图,如果G至少具有两个不是孤立点的分支。迄今为止,许多作者对优美图问题进行了大量的研究,但对不连通图的优美性讨论尚少。本文首先研究不连通图的优美性,给出了几类不连通的优美图,并提出两个猜想。其次讨论优美矩阵,得到了几个有意义的结果。最后给出几类新优美图的构造方法。     

太阳图的优美性

证明了当ｎ≡０ ，３（ｍｏｄ ４） 时，在回路Ｃｎ 的每个顶点上增加一条长为ｍ（ ｍ ≥２） 的路所组成的图是优美图．     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

平衡图及优美图的构造

利用平衡图Ｇ及优症状图Ｈ给出了几种构造新的２图－－Ｇ（Ｘ．∪ｉ＝１＾ｎＹｉ与优美图－－ｖＧ∨Ｈ的方法;证实了当ｎ≡（ｍｏｄ４）时,图Ｃｎ∪Ｐｍ及其冠是平衡的;同时还获得了其他一些平衡图与优美图。     

非连通图D_(2,6)∪G的优美标号

讨论了非连通图D2,6∪G的优美性,给出了非连通图D2,6∪G是优美图的一个充分条件,证明了若图G是特征为k且缺k+9标号值的交错图(9≤k+9≤|E(G)|),则非连通图D2,6∪G存在缺k+1和k+6标号值的优美标号.     

优美图的嵌入

研究了优美与优美图之间的一种关系，每个优美图都可嵌入到另一个优美图中．通过构造证明了：设G1是任一个优美图，则必存一个优美图G2，使得G1是G2的真子图．这一结论给出了由一个优美图构造一类优美图的一种方法，并用此方法给出了几类优美图．     

两类非连通图优美性的研究

给出了两类非连通图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)和(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1(k=1,2), 并证明了如下结论:对自然数n, m, m1, m2, m3, 设s=〖JB(［〗〖SX(〗n〖〗2〖SX)〗〖JB)］〗, n≥9, m1≥s+2, 则图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)是一个优美图; 对 k=1,2,设n, m≥3, G(k)n-1是一个具有n-1条边的k-优美图,则图(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1是一个优美图。 其中,K2是一个具有2个顶点的完全图,K2〖TX-〗是图K2的补图,K2〖TX-〗∨Cn是图K2和n圈Cn的联图, St(m)是一个具有m+1个顶点的星形树。     

关于〈G;m〉的优美性

本文证明了优美二分图的根积是优美图,并由此得出一些有意义的推论。     

K-优美图与优美图Gk-1的优美性研究

对k-优美图n,Km,n与任意一个有k-1条边的优美图Gk-1的优美关系进行了研究.证明了:当n为奇数时,图n∪Gk-1是优美图;当n为偶数时,粘接图〈n,Gk-1〉是优美图.还证明了粘接图〈Km,n,Gk-1〉是优美图.     

2类与4-圈有关图的优美性

把顺序有一个公共点的n个4圈的并图记作Fn,4;图Fn,4每个4圈的顶点ui1与ui2之间连接m条长为2的路ui1vijui2(i,j=1,2,…,n)得到的图记为m-Fn,4;将孤立顶点w与m-Fn,4的每个顶点连接一条边得到的图记为G,将图G的顶点w加n(m+1)条悬挂边所得到的图记为m-Fn,4+En(m+1).用构造的方法给出图m-Fn,4和m-Fn,4+En(m+1)的优美标号,并证明了m-Fn,4和m-Fn,4+En(m+1)都是优美图.