由圈得到的一类优美图

刘瑞元在〔1〕中证明一个 n(n≥6)个顶点的圈增加两条弦所得图优美,本文证明圈增加若干弦所得图优美.定理具有4k+r 个顶点的圈 C(r=0,1,2,3),可增加 t(1≤t≤2k)条弦,使所得图 C′优美.定理的证明分4种情况:r=0,l,2,3.引理1 具有4k 个顶点的圈 C,可加上t(0≤t≤2k)条弦,使所得图 C′优美。引理2 具有4k+1个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理3 具有4k+2个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理4 具有4k+3个顶点的圈 C,可增加t(1≤t≤2k+1)条弦,使所得图 C′优美.     

Cn与1Cn的优美标号

设k1,k2,…,kn是非负整数,Cn=v1v2…vnv1是有n个顶点n条边的圈,则称图Cn+{v1v11,v1v12,…,v1v1k1,v2v21,…v2v2k2,…,vnvn1,…,vnvnkn}为(k1,k2,…,kn)轮环图,简记为C(k1,k2,…,kn)·本文研究了圈Cn与图C(k1,k2,…,kn)的优美性,给出图Cn与1Cn在n=4k与n=4k+3时的优美标号算法,从而证明了它们都是优美图等结论.     

图C~2_n的优美性

给出了图C2n的定义,并对其优美标号进行研究,得到了当n=4k(k≥2)时图C2n是优美图的结论。     

非连通图(P3∨(Km))∪G及(C3∨(Km))∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨(Km))∪G及(C3∨(Km))∪G是优美图的一个充分条件.证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨(Km))∪(k∪j=1Kn,t)和(C3∨(Km))∪(k∪j=1Kn,t)是优美图;当k=1,2,2≤n＜2m+1时,图(P3∨(Km))∪k∪j=1P(j)n,(C3∨(Km))∪k∪j=1P(j)n和(P3∨(Km))∪Pn∪St(t)是优美图;当2≤n≤2m +1时,(C3∨(Km))∪Pn∪St(t)是优美图.本文的结果推广了现有的一些结论.     

非连通图（P3∨■）∪G及（C3∨■）∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨■)∪G及(C3∨■)∪G是优美图的一个充分条件。证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨■)∪(∪kj=1Kn,t)和(C3∨■)∪(∪kj=1Kn,t)是优美图;当k=1,2,2≤n<2m+1时,图(P3∨■)∪∪kj=1P(j)n,(C3∨■)∪∪kj=1P(j)n和(P3∨■)∪Pn∪St(t)是优美图;当2≤n≤2m+1时,(C3∨■)∪Pn∪St(t)是优美图。本文的结果推广了现有的一些结论。     

C_(2j+1)∪C_(2k)类与P_n~k类调和图

证明了 Seoud等当 k≥ 3时 C3 与 C2 k的不相交并 C3 ∪ C2 k为调和图的猜想 ,并扩展该结果 ,证明了 C5 ∪ C2 k( k≥ 2 )是调和图 ;给出猜想 C2 j+ 1 ∪ C2 k( j≥ 1,k≥ 2且 ( j,k)≠ ( 1,2 ) )是调和图 .证明了幂图 P4n( 8≤ n≤ 17)与 P5 n( 14≤ n≤ 17)是调和图 ,否定了 Seoud等关于当且仅当 1≤ k≤ 3时 Pkn( 1≤ k≤ n -1)是调和图的猜想 .给出了相反的猜想 :当 n≥ n0 ( k)时 Pkn是调和图 ( n0 ( k)为依赖于 k的足够大的整数 )     

非连通图Wmk∪G的优美性

文章证明了对任意自然数n≥1,p≥1,k≥1,当m1=2p+3或2p+4时,图W(k)m1∪Kn,p为优美图,其中Wm1(k)为由k个轮Wmi(i=1,2,…,k)的中心顶点合并后构成的连通图;当m1≥3,n≥[m1/2]时,非连通图Wm1(k)∪St(n)为优美图;对任意自然数p≥1,图W2p+2+i(k)∪Gip为优美图,其中,Gpi表示p条边的i-优美图(i=1,2);对任意自然数n≥1,当m1=2n+5时,图Wm1(k)∪(C3∨■)为优美图。     

图wn*pk的优美性

提出图wn*pk的概念,并在n≡0(mod 2)且n≥4,k≡1(mod 2),k≡0(mod 2)和n≡1(mod 2)且n≥5,k≡1(mod 2),k≡0(mod 2)时,证明图wn*pk是优美的.     

一类图C_n~2的优美性

给出了图Cn2的定义,并对其优美标号进行研究,得到了当n=4k+1(k≥1)时,图Cn2是优美图的结论。     

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

给出了两类非连通图(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个顶点的星形树。     

两类图的优美性

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

一类优美树的构造

给出了将一类优美树序列列接到路上，生成优美树的一种构造方法。     

两类粘接图的优美性

文章定义了两类新的图——粘接图A1和A2的优美性,用构造的方法给出了这两类图的优美标号,并证明了它是优美图.     

3C4k的优美性

本文给出了３Ｃ４ｋ的优美标号，这是ＡｎｏｔｏｎＫｏｔｚｉｇ猜想的一种情况。     

龙图的优美性

根据复杂网络研究的需要,定义(k,m)-龙图和一致(k,m)-龙图作为复杂网络的模型.并且主要对(k,m)-龙图的优美性进行研究,其中证明方法可算法化.     

Cm-1∪Cm的优美性研究

给出了Ｃｍ－１∪Ｃｍ为优美图的必要条件，并证明了ｍ＝ｏ（ｍｏｄ４）时的优美性     

关于树的二分优美标号

已知树的二分优美标号可以得到一些逼近优美树猜想的结果.给出了树的二分优美标号定义,发现了一类非二分优美树,得到了一些构造大型二分优美树的方法.定义了树的k-二分优美,并且对自然数k p2-1证明了任何顶点的优美树都是k-二分优美的.     

优美树的扩充

在任意直径为4和5的优美树的基础上进行了研究,找到了两个法则,一个加法法则,一个乘法法则,并提出了优美树群的概念。接着又提出了优美树群中的元素的合成是可以封闭的,那么一棵优美树分解成一系列子树是否是优美的,本文给出肯定的答复。然后给出"一刀切"的判断方法去判断一些树是优美的。     

2类优美图

用构造法证明了Q^2mxn和u·Q^2mxn都是优美图。     

2类优美图

用构造法证明了Q²_m×n 和u·Q²_m×n 都是优美图。