APP下载

平方圈的(d,1)—全标号

2016-04-07白丹

卷宗 2016年2期
关键词:全数

白丹

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

关键词:平方圈 , -全标号, -全数

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.

猜你喜欢

全数
恶意弃单
洪秀柱 退还捐款