皮爾森圖的總和權可選擇問題

陳苗潔

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

關鍵詞：皮爾森圖；總和權；可選擇

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

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

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

定理1：皮爾森圖是1-2邊權可選擇

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

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

定理2：完全圖不是1-2邊權可選擇。

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

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

本文證明了皮爾森圖是滿足1-2猜想也是滿足1-2-3猜想的，皮爾森圖的成立，對估計猜想的成立是有重要意義的，同時我們還證明了增加3這個數值是有必要的，或者對點再增加一個權值是有必要的。

參考文獻：

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