论文部分内容阅读
优美图是图论中极有趣的研究课题之一，而Skolem优美图是由优美图衍生出来的一个变种。Skolem优美图的研究始于1991年Lee的一篇论文，在这篇论文中，Lee明确给出了Skolem优美图的定义。 对一个给定的简单图G=（V（G），E（G）），|V（G）|和|E（G）|分别是图G的顶点数和边数，令|V（G）|=p，|E（G）|=q，如果存在一个一一映射f：V（G）→{1，2，…，p}，使得对所有边（u，v）∈E（G），由f′（u，v）=|f（u）-f（v）|所导出的映射函数f′：E（G）→{1，2，…，q}是一一对应关系，则称f是图G的一个Skolem优美标号，图G被称为Skolem优美图。 本文研究星图的Skolem优美性。令k-星图St（n1，n2，…nk）为一个由K1，n1，K1，n2，…，K1，nk，k个子图组成的不连通图，其中K1，nj是一个有nj+1个顶点的星（1≤j≤k）。 Kishore证明了k-星图是Skolem优美的必要条件：至少有一个星是偶星（边的个数为偶数的星）或者k≡0，1（mod 4）。很显然，1-星图是Skolem优美图。Lee和Wui证明了2-星图和3-星图是Skomlem优美的当且仅当至少有一个星是偶星。Denham证明了所有的4-星图都是Skolem优美的。Choudum和Kishore证明了所有的5-星图都是Skolem优美的。 本文设计了计算机辅助下求解k-星图Skolem优美标号的算法，并利用星的对称性，对顶点进行合理的分组，采用顶点的分布规律制约边的分布规律的策略，给出了搜索k-星图的Skolem优美标号的有效的分支限界条件，最终给出了当至少有一个星是偶星或者k≡0，1（mod 4）的条件下，k-星图的一种Skolem优美标号，即证明了k-星图是Skolem优美的充分条件：至少有一个星是偶星或者k≡0，1（mod 4）时是k-星图是Skolem优美的。同时这又是它的必要条件，所以，对星图Skolem优美性的研究全部结束。