關于優美性的研究

張文慧，劉 萍，張 雪，張曉琢，張慶成

（東北師范大學數學與統計學院，吉林長春130024）

張文慧，劉 萍，張 雪，張曉琢，張慶成

（東北師范大學數學與統計學院，吉林長春130024）

研究了形如p（n1，n2，…，nm）∪p2n不交并圖的優美性.證明了如果T.Gracl猜想成立，則形如p（n1，n2，…，nm）∪p2n不交并圖的優美性在一定的條件下成立，并給出了當n＝3，4，5，6，7，8，9時，p（n1，n2，…，nm）∪p2n的優美標號.

優美標號；優美圖；并圖.

1 預備知識

圖論中一個比較有趣的問題是所謂的圖標號問題.圖標號理論在射電天文學領域、組合設計和編碼理論中有著廣泛的應用［1－9］.

優美標號是圖標號問題中首先提出的，其定義如下：

對于圖G＝（V，E），如果對每一個v∈V，存在一個非負整數θ（v）（稱為頂點v的標號）滿足：

（ⅰ）?u，v∈V，如果u≠v，那么θ（u）≠θ（v）.

（ⅱ）max｛θ（v）｜v∈V｝＝｜E｜.

（ⅲ）?e1，e2∈E，如果e1≠e2，則θ′（e1）≠θ′（e2）.其中θ′（e）＝｜θ（u）－θ（v）｜，e＝uv.

則稱G為優美圖.稱θ為G的一個優美值，或稱優美標號.

1983年，T.Gracl提出猜想，設pn是n個點的路，則所有的都是優美圖.這個猜想至今沒有被證實或否定，所以研究形如p（n1，n2，…，nm）∪不交并圖的優美性就有了意義.本文證明了，如果T.Gracl猜想成立，則形如p（n1，n2，…，nm）∪不交并圖的優美性在一定的條件下成立，并給出了當n＝3，4，5，6，7，8，9時，p（n1，n2，…，nm）∪的優美標號.這一結論在一定意義下，對T.Gracl猜想的證明有所推動.

2 當n＝3～9時，優美猜想成立

具體例子見圖1—7.

圖1 p23的優美標號

圖2 p24的優美標號

圖3 p25的優美標號

圖4 p26的優美標號

圖5 p27的優美標號

圖6 p28的優美標號

圖7 p29的優美標號

3 主要結果

定理 若所有的p2n都是優美圖，則對于任意自然數m，n和n1，n2，…，nm（m≥1，2≤n1≤n2≤…≤nm），若nm≥4n－4，則p（n1，n2，…，nm）∪pn2是優美圖.

證明 Ⅰ 證明p（n1，n2，…，nm）中的點xi，j的標號各不相同.

（?。﹎＋nm為偶數.當i＋j為偶數時，標號從E逐漸減小，最小為θ（xm＋1，nm－1）；當i＋j為奇數時，標號從0逐漸增大，最大為θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝2n－2.

（ⅱ）m＋nm為奇數.當i＋j為偶數時，標號從E逐漸減小，最小為θ（xm＋1，nm）；當i＋j為奇數時，標號從0逐漸增大，最大為θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝2n－2.

綜合以上兩種情況可知：對于任意的i1，i2，j1，j2，當i1≠i2或j1≠j2時，θ（xi1，j1）≠θ（xi2，j2），即對于p（n1，n2，…，nm）中不同的點標號不同.

Ⅱ 由pn2的優美性知pn2中的點xi（i＝1，2，…，n）的標號各不同.

Ⅲ 證明pn2中點的標號與p（n1，n2，…，nm）中的各不相同.

因為

又

而

所以

又因為nm≥4n－4，且nm＝2k＋1，所以nm≥4n－3.因而θ（xm＋1，2）－θ（xm，nm）≥（－1）m·（4n－3），θ（xi）≠θ（xk，j），?i，j，k∈Z.pn2中點的標號與p（n1，n2，…，nm）中的各不相同.

綜上所述，p（n1，n2，…，nm）∪pn2中不同點的標號不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一個單射，使得V（G）→｛0，1，2，…，E｝，且E（G）?｛1，2，…，E｝，是一個一一映射.因此p（n1，n2，…，nm）∪pn2是優美圖.

推論 對于任意自然數m和n1，n2，…，nm（m≥1，2≤n1≤n2≤…≤nm），若nm≥4n－n，且n＝3，4，5，6，7，8，9，則p（n1，n2，…，nm）∪pn2是優美圖.

證明 我們僅對n＝3，n＝9的情形進行證明，其他情形類似.

n＝3時的情形.

首先，證明p（n1，n2，…，nm）中的點xi，j的標號各不相同.

（1）m＋nm為偶數.當i＋j為偶數時，標號從E逐漸減小，最小為θ（xm＋1，nm－1）；當i＋j為奇數時，標號從0逐漸增大，最大為θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝4.

（2）m＋nm為奇數.當i＋j為偶數時，標號從E逐漸減小，最小為θ（xm＋1，nm）；當i＋j為奇數時，標號從0逐漸增大，最大為θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝4.

綜合以上兩種情況可知：對于任意的i1，i2，j1，j2，當i1≠i2或j1≠j2時，θ（xi1，j1）≠θ（xi2，j2）.即對于p（n1，n2，…，nm）中不同的點標號不同.

其次，證明p23中點xi（i＝1，2，3）的標號不同.由標號可知θ（x1）≠θ（x2）≠θ（x3）.

最后，證明p23中點的標號與p（n1，n2，…，nm）中的各不相同.

因為

且

所以

而nm≥8且nm＝2k＋1，所以nm≥9，θ（xm＋1，2）－θ（xm，nm）≥5·（－1）m.

θ（xi）≠θ（xk，j），?i，j，k∈Z.所以p23中點的標號與p（n1，n2，…，nm）中的各不相同.

綜上所述，p（n1，n2，…，nm）∪p23中不同點的標號不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一個單射，使得V（G）→｛0，1，2，…E｝，且E（G）?｛1，2，…，E｝是一個一一映射.因此p（n1，n2，…，nm）∪p23是優美圖.

給出p（n1，n2，…，nm）∪p23的優美標號：

先將p（n1，n2，…，nm）∪p23的頂點進行編號（見圖8）.

圖8 p（n1，n2，…，nm）∪p23的優美標號

圖9 p（n1，n2，…，nm）∪p29的優美標號

（1）給x1，1和x1，2標號為.然后按以下公式給第一行的其他頂點標號為θ（x1，j）＝θ（x1，j－2）＋（－1）j（j＝3，4，…，n1）.

（2）設第i行已標號，對第i＋1行標號為：

（3）若p（n1，n2，…，nm）的各行頂點均已標號，上述算法停止，否則轉入（2）.

（4）給p23中的xi（i＝1，2，3）進行如下標號：

n＝9時的情形（證明類似于n＝3時）.

給出p（n1，n2，…，nm）∪p29的優美標號：

先將p（n1，n2，…，nm）∪p29的頂點進行編號（見圖9）.

（1）給x1，1和x1，2標號為.然后按公式給第一行的其他頂點標號.

（2）設第i行已標號，對第i＋1行標號為：

（3）若p（n1，n2，…，nm）的各行頂點均已標號，上述算法停止，否則轉入（2）.

（4）給p29中的xi（i＝1，2，3）進行如下標號：

4 當n＝3～9時，p（n1，n2，…，nm）∪p2n的優美標號

具體情況見圖10—16.

圖10 p（2，3，4，9）∪p23的優美標號

圖11 p（2，3，12）∪p24的優美標號

圖12 p（2，3，4，9，12，16）∪p25的優美標號

圖13 p（2，3，4，9，12，16，20）∪p26的優美標號

圖14 p（2，3，4，9，12，16，20，25）∪p27的優美標號

圖15 p（2，3，4，9，12，16，20，25，28）∪p28的優美標號.

圖16 p（2，5，32）∪p29的優美標號

［1］ 馬杰克.優美圖［M］.北京：北京大學出版社，1991：65-121.

［2］ KOH K M，ROGERS D G，TAN T.A graceful arboretum：a survey of graceful trees［M］.Singapore Southeast Bull Math，1979：278-287.

［3］ HARARY F.Sum graphs and difference graphs［J］.Cong Number，1990，72：101-108.

［4］ 梁志和.關于圖標號問題［J］.河北師范大學學報：自然科學版，2000，24（3）：300-303.

［5］ 楊燕呂，王廣選.圖pm∪pn的優美性初探［J］.北京工業大學學報，1993，19（4）：15-26.

［6］ 張志尚，王春月，張慶成.關于w～n∪w～n∪pm的優美性［J］.東北師大學報：自然科學版，2010，42（4）：30-34.

［7］ 馬鳳敏，吳曉春，張偉，等.關于n長路的（a，b；n）-優美標號［J］.東北師大學報：自然科學版，2012，44（4）：31-42.

［8］ 張志尚，黃文強.兩類并圖的優美性［J］.東北師大學報：自然科學版，2013，45（2）：30-34.

［9］ 吳躍生，王廣富，徐保根.非連通圖（P2∨ˉKn）（r1，r2，…，rn＋2）∪Gr的優美性［J］.東北師大學報：自然科學版，2014，46（3）：38-42.

On the gracefulness of graph p2n

ZHANG Wen-hui，LIU Ping，ZHANG Xue，ZHANG Xiao-zhuo，ZHANG Qing-cheng
（School of Mathematics and Statistics，Northeast Normal University，Changchun 130024，China）

A study has been done in this thesis on the gracefulness of a graph like disjoint union of p（n1，n2，…，nm）∪pn2.It is proved that the graph like disjoint union of p（n1，n2，…，nm）∪pn2is graceful under some condition if the hypothesis of T.Gracl is true.Moreover，we give the graceful labelings of p （n1，n2，…，nm）∪pn2when n＝3，4，5，6，7，8，9.In some sense，this work is also helpful for proving the hypothesis of T.Gracl.

graceful graph；graceful labeling；gear graph

O 157.5 ［學科代碼］ 110·7470

A

（責任編輯：陶 理）

1000-1832（2015）03-0055-05

10.16163／j.cnki.22-1123／n.2015.03.012

2014-02-01

國家自然科學基金資助項目（61172094）；吉林省自然科學基金資助項目（20130101068）.

張文慧（1989—），女，碩士研究生，主要從事圖論及李代數研究；通訊作者：張慶成（1960—），男，博士，教授，主要從事李代數、圖論和組合設計研究.