关于香蕉树的奇优美标号

在图论的研究中,图的标号问题是在二十世纪六十年代提出的 ,人们根据应用的需要提出了许多关于简单图的标号猜想.在猜想和实际应用中,涉及到最多的是树.Chen et al定义了香蕉树,在此讨论了该树的奇优美标号以及在一些情况下的伪优美标号.     

探讨斐波纳契毛毛虫树的边标号

为了探讨斐波纳契毛毛虫树的边标号,采用不同于原定义的图标号的方法 -先从边对每个图进行标号。利用先从边标号的特点,主要讨论了1-斐波纳契毛毛虫树的边二分奇优美标号,边优美标号及边魔幻全标号。最后讨论了1-斐波纳契毛毛虫超级同构图的二分奇优美标号。这样的方法省去了大量繁复工作,大大提高了图标号的效率。     

关于一类树的优美性

在n阶树用0,1,2,…,n-1,不同的n个数对顶点标号,使得每一条边的标号也不相同(相关联一对顶点的标号差的绝对值不相同),即{1,2,…,n},称这种标号是优美标号;根据优美图的定义,研究了优美树问题中,Rosa猜想树是优美树;本文研究了一类树T_(k_3)~1,的优美性。     

树的优美标号

1963年,G·Ringel 提出“所有树都是优美图”的著名猜想。它是图论中迄今尚未解决的难题之一。本文把树看成若干个“星”的串接和并接,从结构上对树的优美标号进行了探讨,对相当广泛的树类,给出了它们的优美标号。     

图的标号问题的计算机算法

时至今日,寻找一个图是否有优美标号和序贯标号的充要条件的问题仍是开的。 实际中,寻找一个稍大一点的图的优美标号和序贯标号是一件困难的事。本文对这两件工作给出了一种统一的算法,使得我们利用电子计算机可解决:一、验证一个图是否有优美标号和序贯标号。二、若有,则给出所有的优美标号和序贯标号。 本文用BASIC语言给出了本算法的一个程序。     

轮形图和扇形图的优美性

设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的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

一类二部图的奇优美性

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足:1)L为G的顶点集V到{0,1,…,2|E|-1}的一个单射;2)由L'(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L'是从G的边集E到{1,3,…,2|E|-1}的一个双射.根据奇优美图的定义,研究了一类二部图G*的奇优美标号.     

偶圈冠图r-C_n的奇优美性及奇优美性算法

图G的一个奇优美标号是指存在一个双射函数L:V(G)→{0,1,2,…,2|E|-1}使得任意边e=uv∈E(G),由L′(e)=|L(u)-L(v)|决定的边标号L′为E(G)到{1,3,…,2|E|-1}的双射。根据奇优美图的定义,文章讨论了偶圈冠图r-Cn的奇优美标号问题,证明了当n≡0(mod 4)时,偶圈冠图r-Cn是奇优美图,给出的新奇优美标号算法不同于现有的文献结果。     

优美树的优美标号

本文着重探讨了优美树的优美对偶标号函数、泛优美标号函数及可广义优美标号函数。得到“任何树T皆含有优美子树H,并且D(T)=D(H)、△(T)=△(H)”的结论。给出了几种构造优美树的方法。     

一种证明(k,d)-强优美树的新方法

在现有研究的很多图优美问题中,发现了一种叫做悬挂和拆分的新方法.利用此新方法可以构造出较大规模的具有(k,d)-强优美标号,并证明了新方法所构造出的(k,d)-强优美树的正确性,且由(k,d)-强优美标号可导出强奇优美标号.此新方法较易转化为优良的算法,为(k,d)-强优美标号应用于网络提供了可行的理论保证.     

n个P2之并与n个P3之并的优美性

证明了两结果：（１）当ｎ≡０，１ｍｏｄ４时，ｎ个Ｐ２之并是优美的，当ｎ≡２，３ｍｏｄ４时，ｎ个Ｐ２之并是非优美的；（２）ｎ个Ｐ３之并是优美的。     

关于图B（m,n）的优美性

证明了：当ｍ≡１或２（ｍｏｄ４）时，Ｂ（ｍ，ｎ）＝Ｃ＿ｍ∪Ｐ＿ｎ是优美图，其中Ｃ＿ｍ＝Ａ＿１Ａ＿２…Ａ＿ｍＡ＿１，Ｐ＿ｎ＝Ａ＿１Ｂ＿１Ｂ＿２…Ｂ＿ｎ（ｍ≥３，ｎ＞０）。     

关于2G与路的并的优美标号

设G是有q条边的优美二部图,优美标号为θ,pm是有m条边的简单路,C=k 0〈k〈q,k≠θ（v）,v∈V（G{）},a=maxC,b=minC,h=min q-a＋2,b{}＋2.图G∪G∪Pm是两个图G与一条简单通路的不交并.证明了：当m=1或m≥h时,图G∪G∪Pm是优美的.应用此结论,得到：对所有的s≥2,t≥2,当m=1或m≥3时,图Ks,t∪Ks,t∪Pm是优美的.     

图C_n·P_3的优美标号与调和标号

设C_n·P_3(n≥3)是由圈C_n上一点与路P_3的起点粘合而得到的图。本文研究图C_n·P_3的优美标号与调和标号,得到一些结果。     

7关于(s《c4,n》)∪Pm的优美性

研究了(s)∪Pm的优美性,证明了:(1)m=s-1时,(s)∪pm是优美的;(2)s=2t,m≥3+s时,(s)∪Pm是优美的.其中:图是将n个c4中的每一个c4的一个顶点粘接到一起得到的新图,Pm是m+1个顶点的简单路.(s)∪pm是s个与一个...     

两类并图的优美标号

讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为q,a=max{k|0相似文献   

几类和扇有关图的优美性

证明下面的结论:对任意自然数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.     

图F(t)m的k-强优美性

文章通过对图F(t)m的k-强优美性研究,利用k-强优美图的定义,给出对任意自然数t≥1,m≥2,当k=[m/2]时,F(t)m是k-强优美图,非连通图F(t)m∪Gk-1是优美图.当m≥2p+2时,非连通图F(t)m∪Kn,p是优美图,其中,Fm是有m+1个顶点的扇形图,F(t)m是合并t个扇Fm,F2m,…,F2t-1m的中心顶点构成的连通图,Gk-1是有k-1条边的优美图.     

关于R(8, 1×nl,n2)型图的优美性

讨论了R（8,1×nl,n2）型图的优美性,用构造性的方法给出了R（8,1×nl,n2）型图的优美标号,证明了图R（8,1×nl,n2）是交错图。     

关于Lee猜想

Lee提出如下猜想:对任意整数n＞1和S(n)中置换f,P(Pn,f)是优美的.采用组合方法对4类置换证明此猜想的正确性.当f=(1,2,…,n),(n,n-1,…,2,1),(m,m 1,m 2,m 3),(m,m 3,m 2,m 1)时,路置换图P(Pn,f)是优美的.