皮尔森图的总和权可选择问题

陈苗洁

摘 要：本文给出了皮尔森图的一个{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.