陳苗潔

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

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

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

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

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

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

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

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

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

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

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

本文證明了皮爾森圖是滿足1-2猜想也是滿足1-2-3猜想的，皮爾森圖的成立，對估計猜想的成立是有重要意義的，同時我們還證明了增加3這個數(shù)值是有必要的，或者對點再增加一個權(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.