1. 引言
图的标号理论在编码﹑雷达﹑通信网络﹑射电天文学、密码设计、导弹控制码设计等方面均有广泛的应用。现实生活中的许多问题都可抽象为图的标号问题。在天文学和晶体学中的一些问题的解决需要研究图的标号,特别是优美标号。如在天文学中天文台希望发射的信号互相不发生干扰,发射的信号频率互不相同,并且这些信号的频率差距也互不相同。这些问题可化为图的优美标号来解决。优美图是图论中重要的研究领域之一,有较好的应用价值和广阔的研究前景。1963年G. Ringel提出了一个猜想 [1] ,1960年A. Rosa给出了第一篇论文 [2] 。1972年,S. W. Gomomb明确给出了优美图的定义 [3] 。近年来,在图的标号理论,特别是优美图方面,国内外获得了很多研究成果 [4] 。我们在图的标号理论方面也得到了一些结果 [5] - [10] 。
本文仅考虑没有孤立点的简单图,文中用V(G)和E(G)分别表示图G顶点集和边集,简记为V(G) = V和E(G) = E。本文将讨论图
的优美性。文中未提及的术语见 [11] 。
定义1 称图
是k-优美(k-graceful)图,如果对任何正整数k,
使得由
所导出的函数对所有的边
,其映射
是一个双射。则称f为G的一个k-优美标号。显然k-优美图,当k = 1时,就是通常所说的优美图。
用Pn和Sm分别代表n个顶点的路和m个顶点的星,设
,
,不妨在图Pn和Sm中分别设,
,
。用Pn和Sm构造一个新图,记为
,其中图
是把Pn中的一个1度点与Sm的r个()顶点依次相连后得到的图,文中设在
中只有Pn的1度点v1与Sm中的r个顶点依次相连。在
中,若
(
),记
,否则记
,记
。如图1~3所示。
本文得到了图Gi (I = 1, 2, 3)是优美图,且G0是k-优美图,从而推广了 [12] 中的结果。
2. 主要结果及证明
定理2.1 图Gi (i = 0, 1, 2)是优美图,且G0是k-优美图。
在图Gi (i = 0, 1, 2)中,有
,
,
。在G0中,由于
,不妨设,
;在G1中,由于
,不妨设,
;在G0中,由于
,不妨设
。
2.1. 证明G0是k-优美图
分两种情况证明G0是k-优美图。
情况1
定义G0的顶点标号f为:
,
,
,
,
,
,
,
,
.
由f的定义有,f是V(G0)到
的一个单射。
图G0中,
,
,
,
。
,由
易推得,
,若
,有
,且有
。事实上,设
,
,
,
。于是有
,
,
,
.
由集合Ii (i = 1, 2, 3, 4),有
,
,且
,若
,有 f(e1) ≠ ( f(e2)
。于是得f是G0的k-优美标号。
情况2
定义G0的顶点标号f为:
,
,
,
,
,
,
,
,
.
类似情况1的论证,在情况中易验证f是G0的k-优美标号。
2.2. 证明G1是优美图
分两种情况证明G1是优美图。
情况1
定义G1的顶点标号f为:
,
,
,
,
,
,
,
,
.
情况2
定义G1的顶点标号f为:
,
,
,
,
,
,
,
,
.
类似2.1的论证,易验证标号f是G1的优美标号。
2.3. 证明G2是优美图
分两种情况证明G2是优美图。
情况1
定义G2的顶点标号f为:
,
,
,
, ,
,
,
,
.
情况2
定义G2的顶点标号f为:
,
,
,
,
,
,
,
,
.
类似2.1的论证,标号f是G2的优美标号。
定理2.1证毕。
参考文献