皮爾森圖的總和權(quán)可選擇問(wèn)題

陳苗潔

摘 要：本文給出了皮爾森圖的一個(gè){1，2}賦權(quán)，從而證明了皮爾森圖滿足1-2-3猜想和1-2猜想。即皮爾森圖不用借助點(diǎn)，只需邊1，2兩種權(quán)足夠。而對(duì)完全圖則不是1-2邊權(quán)可選擇。

關(guān)鍵詞：皮爾森圖；總和權(quán)；可選擇

對(duì)任意圖，邊有任意k個(gè)實(shí)數(shù)可選擇作為點(diǎn)權(quán)，點(diǎn)有任意L個(gè)實(shí)數(shù)可選擇作為邊權(quán)，一個(gè)點(diǎn)的點(diǎn)權(quán)加上所有與它相關(guān)聯(lián)的邊權(quán)叫做這個(gè)點(diǎn)的總和權(quán)，若對(duì)點(diǎn)權(quán)和邊權(quán)存在一個(gè)選擇，使得任意相連的點(diǎn)的總和權(quán)不同，我們稱作是（k，L）總和權(quán)可選擇的。特別地，若k=0，L=2，且實(shí)數(shù)僅為1，2，我們稱為1-2邊權(quán)可選擇。當(dāng)k=0，L=3時(shí)，且實(shí)數(shù)為1，2，3時(shí)，這就是Karónski， Luczak and Thomason[1]2004年提出來(lái)的1-2-3猜想，當(dāng)k=L=2時(shí)，且實(shí)數(shù)為1，2時(shí)，這就是PrzybyIo and Wozniak[2]2008年提出來(lái)的1-2猜想。2011年王彩蓮和朱緒鼎，[3]提出了任意沒(méi)有孤立邊的圖是（1，3）總和權(quán)可選擇的，任意圖是（2，2）總和權(quán)可選擇的。這個(gè)兩個(gè)猜想的目前最好結(jié)果是他們證明的任意圖是（2，3）總和權(quán)可選擇的[4]。關(guān)于總和權(quán)可選擇的相關(guān)問(wèn)題[5]。

在數(shù)學(xué)中的圖論領(lǐng)域，皮爾森圖是圖論中的“明星”，是一個(gè)有10個(gè)點(diǎn)，15條邊的簡(jiǎn)單無(wú)向圖，每個(gè)點(diǎn)都有3條邊跟它相鄰，任意兩個(gè)不相鄰的點(diǎn)都存在唯一的點(diǎn)跟它們都相鄰。對(duì)圖論中的很多問(wèn)題，皮爾森圖時(shí)常起到例子和反例的作用。Donald Knuth認(rèn)為皮爾森圖作為一個(gè)例子，它是一個(gè)了不起的構(gòu)造，一個(gè)結(jié)論，如果對(duì)這個(gè)圖是正確的，大致可以樂(lè)觀的猜測(cè)對(duì)一般圖可能也是正確的。

對(duì)任意邊賦權(quán)1或2，存在一種選擇，使得相連的點(diǎn)，邊權(quán)和不同，我們稱為1-2邊權(quán)可選擇。接下來(lái)，我們給出了一個(gè)選擇，證明皮爾森圖是1-2邊權(quán)可選擇。

定理1：皮爾森圖是1-2邊權(quán)可選擇

證明：邊15，邊01，邊12，邊70，邊79，邊76，邊89，邊84，邊85賦權(quán)1，其余賦權(quán)2，則各個(gè)點(diǎn)的總和權(quán)為0（4），1（3），2（5），3（6），4（5），5（4），6（5），7（3），8（3），9（4），滿足了相鄰的點(diǎn)總和權(quán)不同。從而證明皮爾森圖是1-2邊權(quán)可選擇。

它可看做是3不用的1-2-3邊權(quán)可選擇，故滿足1-2-3猜想。還可看做所有點(diǎn)全部賦值1或所有點(diǎn)全部賦值2的1-2總和權(quán)可選擇，故滿足1-2猜想。而對(duì)于完全圖完全沒(méi)有這樣的性質(zhì)。完全圖是一個(gè)具有n個(gè)頂點(diǎn)的圖，任意兩個(gè)頂點(diǎn)有邊相鄰，故完全圖有n（n+1）/2條邊。下面證明完全圖不是1-2邊權(quán)可選擇。

定理2：完全圖不是1-2邊權(quán)可選擇。

證明：假設(shè)完全圖是1-2邊權(quán)可選擇，由于完全圖n個(gè)點(diǎn)互相有邊相鄰，所以每個(gè)點(diǎn)都有n-1條邊跟它相鄰，故每個(gè)點(diǎn)的邊權(quán)和最少是n-1，最多是2n-2，但是從n-1到2n-2最多只有n個(gè)整數(shù)，而n個(gè)點(diǎn)的邊權(quán)和各不相同，故要求邊權(quán)和最少的是n-1，邊權(quán)和最大的是2n-2，則要求邊權(quán)和最少的點(diǎn)每條邊賦權(quán)1，邊權(quán)和最大的點(diǎn)每條邊賦權(quán)2，由于這兩個(gè)點(diǎn)相鄰，所以矛盾，假設(shè)不成立。

從這個(gè)定理我們可以看出，每條邊至少應(yīng)該有三個(gè)可選擇的權(quán)值，才能使相鄰的點(diǎn)邊權(quán)和不同。

本文證明了皮爾森圖是滿足1-2猜想也是滿足1-2-3猜想的，皮爾森圖的成立，對(duì)估計(jì)猜想的成立是有重要意義的，同時(shí)我們還證明了增加3這個(gè)數(shù)值是有必要的，或者對(duì)點(diǎn)再增加一個(gè)權(quán)值是有必要的。

參考文獻(xiàn)：

[1]Karo'nski M，LuczakT，ThomasonA（2004）Edge weights and vertex colour. J Comb Theory， Ser B 91：151–157

[2]PrzybyIo J， Wo'zniak M（2010）On a 1， 2 conjecture. Discrete Math Theor Comput Sci 12（1）：101–108

[3]T.-L.Wong and X. Zhu， Total weight choosability of graphs， Journal of Graph Theory 66（2011），198–212.

[4]T.-L. Wong and X. Zhu， Every graph is（2， 3）-choosable， submitted.

[5]Haili Pan and Daqing Yang， On total weight choosability of graphs， J Comb Optim（2013）25：766-783.