论文部分内容阅读
图的标号问题起始于1966年A．Rosa的著名的优美树猜想。一个图的顶点标号是图的顶点集到整数集的映射，而边标号则是图的边集到整数集的映射。根据对映射的不同要求，产生了各种类型的图的标号问题。本文对图的Skolem优美标号、超幻和标号和调和标号三类问题进行研究，分别解决了这三类标号中的一些问题和猜想，取得了较好的结果。优美标号在射电天文学及计算机网络理论中有着广泛的应用。Skolem优美标号是优美标号的一个衍变，κ-星图是由κ个任意大小的星图组成的不连通图。对κ-星图的优美性、Kishore猜想当且仅当有一个星是偶星或者κ≡0，1（mod 4）时，κ-星图是Skolem优美的。Choudum和Kishore等人证明了这个猜想在κ≤5时成立。本文对任意的κ-星图的Skolem优美性进行研究，针对κ-星图和Skolem优美标号的特点，设计了相应的分支限界搜索策略；对于有一个星是偶星或者κ≡0，1（mod 4）的各种情形，分别搜索到了在该情形下Skolem优美标号的共有特点，从中总结出相应的从图的顶点集V到整数集{1，2，…，|V|}的1-1映射函数，从而证明了Kishore猜想对任意的κ都成立。超幻和标号是幻类型标号的一种衍变。Figueroa-Centeno等证明了当n为奇数且n≠5（mod 8）时，Book图Bn真不是超边幻和图，并猜想对n≥5，当且仅当n是偶数或n≡5（mod 8）时，Bn是超边幻和图。本文证明了当n为大于等于6的偶数时，Bn是超边幻和图。本文还研究了Kn（?）del图W3，n和Flower Snark及其相关图Fn的超点幻和标号，证明了当且仅当n≡0（mod 4）时，Kn（?）del图W3，n是超点幻和图；并证明了所有的Flower Snark及相关图Fn都是超点幻和图。调和标号是为解决纠错码的问题而由优美标号衍变而来的。徐士达证明了当且仅当p≠2（mod 4）时，三角蛇图是调和图。本文证明了所有的双三角蛇图都是调和图。Deb和Limye提出猜想：所有的多贝壳图都是调和图，并证明了对平衡2贝壳图和平衡3贝壳图Deb猜想成立。杨元生等人证明了对平衡4贝壳图Deb猜想成立。本文证明了对平衡5贝壳图Deb猜想也成立。