若干图的（d，1）全标号和（2，1）标号的研究

论文摘要

图的标号问题起始于1966年A．Rosa的著名优美树猜想。一个图的顶点标号是图的顶点集到整数集的映射，边标号是图的边集到整数集的映射。根据对映射的不同要求产生了各种类型的标号问题。本文对（d,1）全标号、（2，1）标号进行了研究。Yeh等人最先考虑（2，1）标号问题。（2，1）标号问题来自计算机网络里广播频道设置问题。用非负的整数表示频道，让相近的位置接受不同的频道，并且非常近的位置为了不相互干扰，它们的频道至少相差2．（d,1）全标号是根据（2，1）标号衍变而来。Havet等人给出对于任意的r-正则图G，λdT（G）≥d+r．本文证明了对于任意r-正则非二部图G，λd≥r≥3T（G）≥d+r+1．本文对广义Petersen图、Flower Snark及其相关图和Glodberg Snark及其相关图的（d,1）全标号数进行了研究，得出如下结论：（1）当n是偶数，k是奇数时，λd≥2T（P（n，k））=d+3．（2）当n是奇数或k是偶数时，λd≥3T（P（n，k））=d+4．（3）当n是偶数时，λd≥2T（Hn）=λd≥2T（Gn）=d+3．（4）当n是奇数时，λ2T（Hn）=λ2T（Gn）=5，λd≥3T（Hn）=λd≥3T（Gn）=d+4．（5）λ2T（Gk）=λ2T（TGk）=5，λd≥3T（Gk）=λd≥3T（TGk）=d+4．对Flower Snark及其相关图的（2，1）标号数进行了研究，得出如下结论：（1）当n>3时，λ（Hn）=λ（Gn）=6．（2）当n=3时，λ（H3）=7，λ（G3）=6．

论文目录

• 摘要
• Abstract
• 引言
• 1 基本概念
• 1.1 图
• 1.2 子图与生成子图
• 1.3 正则图
• 1.4 二部图
• 1.5 完备图和补图
• 1.6 图的同构
• 1.7 图的乘积
• 1.8 路径
• 1.9 树
• 1.10 常见图和标记
• 2 标号问题的研究现状
• 2.1 （2,1）标号的起源和发展
• 2.2 （d,1）全标号的起源和发展
• 2.3 广义Petersen图,Flower Snark图和Goldberg Snark图
• 2.4 本文工作
• 3 Flower Snark等图类的（d,1）全标号
• 3.1 r-正则非二部图的（d,1）全标号
• 3.2 Flower Snark及其相关图的（d,1）全标号
• 3.3 广义Petersen图（d,1）全标号
• 3.4 Goldberg Snark及其相关图的（d,1）全标号
• 4 Flower Snark及其相关图的（2,1）标号
• 4.1 基本引理
• n的（2,1）标号'>4.2 H_n的（2,1）标号
• n的（2,1）标号'>4.3 G_n的（2,1）标号
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢