平方圈的（d，1）—全標號

白丹

摘 要：一個圖 的 -全標號是 到整數(shù)集合的一個映射 ，使得本文主要研究了平方圈 的 -全標號，得到了平方圈中 為某些特殊值時， 的 -全數(shù)的確切值。

關(guān)鍵詞：平方圈 ， -全標號， -全數(shù)

1.引言

在無線電頻道分配問題中，因為傳輸機彼此間的距離各不相同，它們當中有些距離是非常近的，而某些則不是。所以，當我們向這些傳輸機分配無線電頻譜時，如果兩個傳輸機非常接近，那么為了避免干擾，我們不能向它們分配相近的頻率，而為了節(jié)約資源，我們必須盡可能在不產(chǎn)生干擾的前提下節(jié)約電頻譜資源，我們將這個問題抽象到一個圖當中，將每一個傳輸機視為該圖的點，如果兩點代表的傳輸機距離非常接近，則該兩點在圖中相鄰，如果兩點代表的傳輸機距離接近，則該兩點在圖中距離為2，也就是說在電頻譜分配時，如果兩點在圖中距離為2，則得到的頻率應(yīng)該相異，如果兩點在圖中相鄰，則得到的頻率應(yīng)該至少相差2，這就是著名的 -標號，曾在文獻[2]中得到了研究。

-全標號是Whitelesey，Georges，和Mauro所研究的圖 的剖分圖的 標號的自然推廣。Havet和Yu給出了 -全標號的定義。令 是正整數(shù)，圖 無環(huán)無重邊的有限非空圖。

如果一個 -全標號在集合 中取值，則稱為 - -全標號。圖 的 -全標號的跨度是圖 中任意任意兩個標號的差的絕對值的最大值。圖 的 -全數(shù)是圖 的所有的 -全標號中跨度的最小值，記作 。

2 有關(guān)的結(jié)論及相關(guān)定義

平方圈 是以圈 的頂點為頂點集合，兩個頂點相鄰當且僅當這兩個頂點在圈 中的距離不超過2。對于圖 中的任意一點 ，我們用 表示那些與頂點 相關(guān)聯(lián)的邊構(gòu)成的邊集合，用 表示從 到 的所有整數(shù)，其中 ，如果 ，則 。對于文中其它沒有介紹到的概念可參見[1]，為了證明本文定理，首先我們將給出關(guān)于 -全標號的一些現(xiàn)有結(jié)果。

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

引理2.2[3] 如果圖 是一個 -正則圖，那么 。

引理2.3[3] 對于完全圖 ， 。

引理2.4[3] 對于完全圖 ，如果 ，則 。

引理2.5[3] 圖 是滿足 的連通圖，如果 且 為奇圈，則 ；否則 。

3 主要結(jié)論及證明

對于 或 ，我們發(fā)現(xiàn) 與 同構(gòu)， 與 同構(gòu)，根據(jù)引理2.4，我們得到如下定理：

定理3.2 對于任意的正整數(shù) ， ， ，對于任意的正整數(shù) ， ，

對于 ，我通過觀察 的結(jié)構(gòu)知道它是正則圖，我們通過標號法與反證法找到了它的 -全數(shù)的確切值。

為了證明之后的定理，我們首先證明以下的引理成立。

引理3.3 對于圖 ，當 時，如果 存在一個 - -全標號，則 中的任何頂點都只能在 中選擇標號。

證明：我們用反證法來完成，設(shè) 且標號為 ，注意到在 中共有 個數(shù)，我們分以下三種情況來討論：

情況1.1如果 ，則有 ，此時我們總認為有 成立，因此至多有 個標號可以在 中表現(xiàn)，與 矛盾。

情況2.2如果 ，則有 ， ，因此至多有 個標號可以在 中表現(xiàn)，與 矛盾。

情況2.3如果 ，則有 ，因此至多有 個標號可以在 中表現(xiàn)，與 矛盾。

引理成立。

定理3.4 對于任意的正整數(shù) ，當 時， 。

證明：為了書寫方便，我們用 表示 的頂點集合，當函數(shù) 作用在 的頂點和邊上時，我們分別用 和 來表示。

我們可以按照以下的方式構(gòu)造 的一個 - -全標號。

根據(jù)引理3.3，通過反證法可以得到 ，假設(shè) 存在一個 - -全標號，由引理3.3可知 中的所有頂點只能用 中的數(shù)進行標號，不失一般性，我們可以假設(shè) ， ， ，此時我們考慮邊 的標號應(yīng)該滿足 ，得到 ，與定理中條件 矛盾，所以 ，定理得證。

定理3.5 對于任意的正整數(shù) ，當 時， 。

為了通過反證法可以得到 ，我們首先可以通過與引理3.3相似的證明方法得到以下斷言。

斷言1 對于圖 ，當 時，如果 存在一個 - -全標號，則 中的任何頂點都只能在 中選擇標號。

根據(jù)斷言1，假設(shè) 存在一個 - -全標號，由斷言 可知 中的所有頂點只能用 中的數(shù)進行標號，因為在 中任意連續(xù)的3個頂點構(gòu)成一個3-圈，所以我們需要用三個不同的數(shù)對連續(xù)的三個頂點進行標號，我們假設(shè)存在一條邊滿足與它相關(guān)聯(lián)的兩個頂點的標號分別為1和 ，那么這條邊的標號 就應(yīng)當滿足 ，得 ，與我們定理條件中的假設(shè) 矛盾，所以標號1和 不能同時出現(xiàn)在連續(xù)的三個頂點上。同理，標號0和 ，標號0和 ，標號1和 ，標號1和 ，標號2和 ，標號2和 ，標號2和 也不能同時出現(xiàn)在連續(xù)的三個頂點上，所以對于任意連續(xù)的3個頂點我們只能用 或 進行標號。

根據(jù)標號的對稱性，我們可以假設(shè) ， ， ，此時由于 ，我們得到 ，這時 和 標號一樣，與 和 相鄰矛盾，定理得證。

定理3.6 對于任意的正整數(shù) ，當 時， 。

與定理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.