基于最省刻度尺构造极小优美图的图论方法

[目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.[方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{a_i},满足0=a₁2<…m=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差a_j-a_i,则称{a_i}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.[结果]由n≥5时K_n不是优美图和n≥1时图K₄+K_n,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K₃∨K_1,3,n-3e,K_3,n∨K₃-e和K_2,3,n     

三类特殊图的优美性

用构造的方法给出图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))的优美标号,并证明了图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))都是优美图.     

一类图的优美性

本文引进齿顶边星图Ｗｎ（ｍ１，ｍ２，…，ｍｎ）的概念，证明了Ｗｎ（ｍ１，ｍ２，…，ｍｎ）是优美图，而当ｍ１＝ｍ２＝…＝ｍｎ＝Ｋ时，解决了陆书环先生提出的猜想。     

优美图所有优美标号的生成算法

给出了由n条边生成的所有优美图的所有优美标号的生成算法,并把代数理论和计算机工具引入了优美图的研究.利用该算法,可以根据需要得到优美图及其优美标号.     

一类二部图的奇优美性

设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*的奇优美标号.     

3类图的优美标号

用构造的方法给出图1-3n-K3,P(n,2,n-1)和I(K_(1,1,n))的优美标号,从而证明了1-3n-K_3,P(n,2,n-1)和I(K_(1,1,n))都是优美图.     

图2Cn的优美性

给出二个偶圈的不交并及与圈相关的一类图的优美性及其优美标号。     

双圈图的优美性

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

图的优美性

本文定义了一类特殊结构的图ωm1,m2,…,mn,证明了当m1,m2,…,mn≡0(mod4)时,ωm1,m2,…,mn是优美图和交错图.它是一类优美图n-C4m=ω4m,4m,…,4m()n个的推广.     

2类包含K4的优美图及其注记

利用计算机为辅助工具,分别给出了2类包含图K4的图K4+Gn+1和K4+Kn,n的优美标号,从而证明了图K4+Gn+1和K4+Kn,n是优美图,并由K4+Kn,n的优美性给出了边数为m的极小优美图的顶点数f(m)的范图是{(1+√8m+1)/2}≤f(m)≤{2(√m+3-1)).     

全图的优美性研究

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

和轮相关图的优美性

 证明了对任意自然数n≥1,p≥1,当m=2p+3,2p+4时,非连通图W_m∪K_n,p和W_m,2m+1∪K_n,p是优美图;当i=1,2时,图W_2p+2+i∪G⁽ⁱ⁾_p是优美图。当m≥3,n≥s时,W_m,2m+1∪St(n)是优美图;当m=2n+5时,图W_m,2m+1∪(C₃∨K_n)是优美图。     

一类新图的奇优美性的研究

设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*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

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)都是优美图.     

太阳图的优美性

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

关于K_（1，2，n）和K_（1，1，1，n）的优美性

分别给出了完全３部图Ｋ１，２，ｎ和完全４部图Ｋ１，１，１，ｎ的一种优美标号，从而证明了Ｋ１，２，ｎ和Ｋ１，１，１，ｎ是优美图．     

一类链图的优美性

对于由k个完全二部图K2,m1,K2,m2,…,K2,mk(其中k,n,m1,m2,…,mk为大于1的正整数)经过不同的粘接方法而得到的链图T1、链图T2、链图T5的优美性进行了研究。在此基础上对由链图T1和长为n的路Pn的一个端点粘接得到的链图T3和链图T2与长为n的路Pn的一个端点粘接得到的链图T4的优美性进行了研究。用构造的方法给出了这几类图的优美标号,得出这些图都是优美图。这样将m1,m2,…,mk的值均为2的范围扩大到大于1的正整数,从而拓宽了优美图及其应用的道路。最后提出了将链图T1、T2、T3、T4、T5分别首尾粘接而得到的一些图是优美图的猜想。