白丹

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

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

1.引言

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

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

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

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

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

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

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

引理2.3[3] 對(duì)于完全圖 ， 。

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

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

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

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

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

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

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

引理3.3 對(duì)于圖 ，當(dāng) 時(shí)，如果 存在一個(gè) - -全標(biāo)號(hào)，則 中的任何頂點(diǎn)都只能在 中選擇標(biāo)號(hào)。

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

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

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

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

引理成立。

定理3.4 對(duì)于任意的正整數(shù) ，當(dāng) 時(shí)， 。

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

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

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

定理3.5 對(duì)于任意的正整數(shù) ，當(dāng) 時(shí)， 。

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

斷言1 對(duì)于圖 ，當(dāng) 時(shí)，如果 存在一個(gè) - -全標(biāo)號(hào)，則 中的任何頂點(diǎn)都只能在 中選擇標(biāo)號(hào)。

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

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

定理3.6 對(duì)于任意的正整數(shù) ，當(dāng) 時(shí)， 。

與定理3.5相同的反證方法，我們可以得到 ，因此定理得證。

參考文獻(xiàn)

[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.