平方圈的（d，1）—全标号

白丹

摘 要：一个图 的 -全标号是 到整数集合的一个映射 ，使得本文主要研究了平方圈 的 -全标号，得到了平方圈中 为某些特殊值时， 的 -全数的确切值。

关键词：平方圈 ， -全标号， -全数

1.引言

在无线电频道分配问题中，因为传输机彼此间的距离各不相同，它们当中有些距离是非常近的，而某些则不是。所以，当我们向这些传输机分配无线电频谱时，如果两个传输机非常接近，那么为了避免干扰，我们不能向它们分配相近的频率，而为了节约资源，我们必须尽可能在不产生干扰的前提下节约电频谱资源，我们将这个问题抽象到一个图当中，将每一个传输机视为该图的点，如果两点代表的传输机距离非常接近，则该两点在图中相邻，如果两点代表的传输机距离接近，则该两点在图中距离为2，也就是说在电频谱分配时，如果两点在图中距离为2，则得到的频率应该相异，如果两点在图中相邻，则得到的频率应该至少相差2，这就是著名的 -标号，曾在文献[2]中得到了研究。

-全标号是Whitelesey，Georges，和Mauro所研究的图 的剖分图的 标号的自然推广。Havet和Yu给出了 -全标号的定义。令 是正整数，图 无环无重边的有限非空图。

如果一个 -全标号在集合 中取值，则称为 - -全标号。图 的 -全标号的跨度是图 中任意任意两个标号的差的绝对值的最大值。图 的 -全数是图 的所有的 -全标号中跨度的最小值，记作 。

2 有关的结论及相关定义

平方圈 是以圈 的顶点为顶点集合，两个顶点相邻当且仅当这两个顶点在圈 中的距离不超过2。对于图 中的任意一点 ，我们用 表示那些与顶点 相关联的边构成的边集合，用 表示从 到 的所有整数，其中 ，如果 ，则 。对于文中其它没有介绍到的概念可参见[1]，为了证明本文定理，首先我们将给出关于 -全标号的一些现有结果。

引理2.1[3] 对任意图 ， ，其中 表示图 的最大度。

引理2.2[3] 如果图 是一个 -正则图，那么 。

引理2.3[3] 对于完全图 ， 。

引理2.4[3] 对于完全图 ，如果 ，则 。

引理2.5[3] 图 是满足 的连通图，如果 且 为奇圈，则 ；否则 。

3 主要结论及证明

对于 或 ，我们发现 与 同构， 与 同构，根据引理2.4，我们得到如下定理：

定理3.2 对于任意的正整数 ， ， ，对于任意的正整数 ， ，

对于 ，我通过观察 的结构知道它是正则图，我们通过标号法与反证法找到了它的 -全数的确切值。

为了证明之后的定理，我们首先证明以下的引理成立。

引理3.3 对于图 ，当 时，如果 存在一个 - -全标号，则 中的任何顶点都只能在 中选择标号。

证明：我们用反证法来完成，设 且标号为 ，注意到在 中共有 个数，我们分以下三种情况来讨论：

情况1.1如果 ，则有 ，此时我们总认为有 成立，因此至多有 个标号可以在 中表现，与 矛盾。

情况2.2如果 ，则有 ， ，因此至多有 个标号可以在 中表现，与 矛盾。

情况2.3如果 ，则有 ，因此至多有 个标号可以在 中表现，与 矛盾。

引理成立。

定理3.4 对于任意的正整数 ，当 时， 。

证明：为了书写方便，我们用 表示 的顶点集合，当函数 作用在 的顶点和边上时，我们分别用 和 来表示。

我们可以按照以下的方式构造 的一个 - -全标号。

根据引理3.3，通过反证法可以得到 ，假设 存在一个 - -全标号，由引理3.3可知 中的所有顶点只能用 中的数进行标号，不失一般性，我们可以假设 ， ， ，此时我们考虑边 的标号应该满足 ，得到 ，与定理中条件 矛盾，所以 ，定理得证。

定理3.5 对于任意的正整数 ，当 时， 。

为了通过反证法可以得到 ，我们首先可以通过与引理3.3相似的证明方法得到以下断言。

断言1 对于图 ，当 时，如果 存在一个 - -全标号，则 中的任何顶点都只能在 中选择标号。

根据断言1，假设 存在一个 - -全标号，由断言 可知 中的所有顶点只能用 中的数进行标号，因为在 中任意连续的3个顶点构成一个3-圈，所以我们需要用三个不同的数对连续的三个顶点进行标号，我们假设存在一条边满足与它相关联的两个顶点的标号分别为1和 ，那么这条边的标号 就应当满足 ，得 ，与我们定理条件中的假设 矛盾，所以标号1和 不能同时出现在连续的三个顶点上。同理，標号0和 ，标号0和 ，标号1和 ，标号1和 ，标号2和 ，标号2和 ，标号2和 也不能同时出现在连续的三个顶点上，所以对于任意连续的3个顶点我们只能用 或 进行标号。

根据标号的对称性，我们可以假设 ， ， ，此时由于 ，我们得到 ，这时 和 标号一样，与 和 相邻矛盾，定理得证。

定理3.6 对于任意的正整数 ，当 时， 。

与定理3.5相同的反证方法，我们可以得到 ，因此定理得证。

参考文献

[1] D.B. West， Introduction to graph theory， second ed. Prentice-Hall， Upper Saddle River， NJ， 2001.

[2] D. Chen， W. Wang， （2，1）-total labelling of outplanars， J. Discrete Applied Mathematics， 2006， 306（12） 1217-1231.

[3] F. Havet， M. L. Yu， （p，1）-Total labelling of graphs， Disc. Math. 308（2008） 496-513.