關(guān)于優(yōu)美性的研究

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

（東北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林長春130024）

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

（東北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林長春130024）

研究了形如p（n1，n2，…，nm）∪p2n不交并圖的優(yōu)美性.證明了如果T.Gracl猜想成立，則形如p（n1，n2，…，nm）∪p2n不交并圖的優(yōu)美性在一定的條件下成立，并給出了當(dāng)n＝3，4，5，6，7，8，9時(shí)，p（n1，n2，…，nm）∪p2n的優(yōu)美標(biāo)號(hào).

優(yōu)美標(biāo)號(hào)；優(yōu)美圖；并圖.

1 預(yù)備知識(shí)

圖論中一個(gè)比較有趣的問題是所謂的圖標(biāo)號(hào)問題.圖標(biāo)號(hào)理論在射電天文學(xué)領(lǐng)域、組合設(shè)計(jì)和編碼理論中有著廣泛的應(yīng)用［1－9］.

優(yōu)美標(biāo)號(hào)是圖標(biāo)號(hào)問題中首先提出的，其定義如下：

對于圖G＝（V，E），如果對每一個(gè)v∈V，存在一個(gè)非負(fù)整數(shù)θ（v）（稱為頂點(diǎn)v的標(biāo)號(hào)）滿足：

（ⅰ）?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為優(yōu)美圖.稱θ為G的一個(gè)優(yōu)美值，或稱優(yōu)美標(biāo)號(hào).

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

2 當(dāng)n＝3～9時(shí)，優(yōu)美猜想成立

具體例子見圖1—7.

圖1 p23的優(yōu)美標(biāo)號(hào)

圖2 p24的優(yōu)美標(biāo)號(hào)

圖3 p25的優(yōu)美標(biāo)號(hào)

圖4 p26的優(yōu)美標(biāo)號(hào)

圖5 p27的優(yōu)美標(biāo)號(hào)

圖6 p28的優(yōu)美標(biāo)號(hào)

圖7 p29的優(yōu)美標(biāo)號(hào)

3 主要結(jié)果

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

證明 Ⅰ 證明p（n1，n2，…，nm）中的點(diǎn)xi，j的標(biāo)號(hào)各不相同.

（?。﹎＋nm為偶數(shù).當(dāng)i＋j為偶數(shù)時(shí)，標(biāo)號(hào)從E逐漸減小，最小為θ（xm＋1，nm－1）；當(dāng)i＋j為奇數(shù)時(shí)，標(biāo)號(hào)從0逐漸增大，最大為θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝2n－2.

（ⅱ）m＋nm為奇數(shù).當(dāng)i＋j為偶數(shù)時(shí)，標(biāo)號(hào)從E逐漸減小，最小為θ（xm＋1，nm）；當(dāng)i＋j為奇數(shù)時(shí)，標(biāo)號(hào)從0逐漸增大，最大為θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝2n－2.

綜合以上兩種情況可知：對于任意的i1，i2，j1，j2，當(dāng)i1≠i2或j1≠j2時(shí)，θ（xi1，j1）≠θ（xi2，j2），即對于p（n1，n2，…，nm）中不同的點(diǎn)標(biāo)號(hào)不同.

Ⅱ 由pn2的優(yōu)美性知pn2中的點(diǎn)xi（i＝1，2，…，n）的標(biāo)號(hào)各不同.

Ⅲ 證明pn2中點(diǎn)的標(biāo)號(hào)與p（n1，n2，…，nm）中的各不相同.

因?yàn)?/p>

又

而

所以

又因?yàn)閚m≥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中點(diǎn)的標(biāo)號(hào)與p（n1，n2，…，nm）中的各不相同.

綜上所述，p（n1，n2，…，nm）∪pn2中不同點(diǎn)的標(biāo)號(hào)不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一個(gè)單射，使得V（G）→｛0，1，2，…，E｝，且E（G）?｛1，2，…，E｝，是一個(gè)一一映射.因此p（n1，n2，…，nm）∪pn2是優(yōu)美圖.

推論 對于任意自然數(shù)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是優(yōu)美圖.

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

n＝3時(shí)的情形.

首先，證明p（n1，n2，…，nm）中的點(diǎn)xi，j的標(biāo)號(hào)各不相同.

（1）m＋nm為偶數(shù).當(dāng)i＋j為偶數(shù)時(shí)，標(biāo)號(hào)從E逐漸減小，最小為θ（xm＋1，nm－1）；當(dāng)i＋j為奇數(shù)時(shí)，標(biāo)號(hào)從0逐漸增大，最大為θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝4.

（2）m＋nm為奇數(shù).當(dāng)i＋j為偶數(shù)時(shí)，標(biāo)號(hào)從E逐漸減小，最小為θ（xm＋1，nm）；當(dāng)i＋j為奇數(shù)時(shí)，標(biāo)號(hào)從0逐漸增大，最大為θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝4.

綜合以上兩種情況可知：對于任意的i1，i2，j1，j2，當(dāng)i1≠i2或j1≠j2時(shí)，θ（xi1，j1）≠θ（xi2，j2）.即對于p（n1，n2，…，nm）中不同的點(diǎn)標(biāo)號(hào)不同.

其次，證明p23中點(diǎn)xi（i＝1，2，3）的標(biāo)號(hào)不同.由標(biāo)號(hào)可知θ（x1）≠θ（x2）≠θ（x3）.

最后，證明p23中點(diǎn)的標(biāo)號(hào)與p（n1，n2，…，nm）中的各不相同.

因?yàn)?/p>

且

所以

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

θ（xi）≠θ（xk，j），?i，j，k∈Z.所以p23中點(diǎn)的標(biāo)號(hào)與p（n1，n2，…，nm）中的各不相同.

綜上所述，p（n1，n2，…，nm）∪p23中不同點(diǎn)的標(biāo)號(hào)不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一個(gè)單射，使得V（G）→｛0，1，2，…E｝，且E（G）?｛1，2，…，E｝是一個(gè)一一映射.因此p（n1，n2，…，nm）∪p23是優(yōu)美圖.

給出p（n1，n2，…，nm）∪p23的優(yōu)美標(biāo)號(hào)：

先將p（n1，n2，…，nm）∪p23的頂點(diǎn)進(jìn)行編號(hào)（見圖8）.

圖8 p（n1，n2，…，nm）∪p23的優(yōu)美標(biāo)號(hào)

圖9 p（n1，n2，…，nm）∪p29的優(yōu)美標(biāo)號(hào)

（1）給x1，1和x1，2標(biāo)號(hào)為.然后按以下公式給第一行的其他頂點(diǎn)標(biāo)號(hào)為θ（x1，j）＝θ（x1，j－2）＋（－1）j（j＝3，4，…，n1）.

（2）設(shè)第i行已標(biāo)號(hào)，對第i＋1行標(biāo)號(hào)為：

（3）若p（n1，n2，…，nm）的各行頂點(diǎn)均已標(biāo)號(hào)，上述算法停止，否則轉(zhuǎn)入（2）.

（4）給p23中的xi（i＝1，2，3）進(jìn)行如下標(biāo)號(hào)：

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

給出p（n1，n2，…，nm）∪p29的優(yōu)美標(biāo)號(hào)：

先將p（n1，n2，…，nm）∪p29的頂點(diǎn)進(jìn)行編號(hào)（見圖9）.

（1）給x1，1和x1，2標(biāo)號(hào)為.然后按公式給第一行的其他頂點(diǎn)標(biāo)號(hào).

（2）設(shè)第i行已標(biāo)號(hào)，對第i＋1行標(biāo)號(hào)為：

（3）若p（n1，n2，…，nm）的各行頂點(diǎn)均已標(biāo)號(hào)，上述算法停止，否則轉(zhuǎn)入（2）.

（4）給p29中的xi（i＝1，2，3）進(jìn)行如下標(biāo)號(hào)：

4 當(dāng)n＝3～9時(shí)，p（n1，n2，…，nm）∪p2n的優(yōu)美標(biāo)號(hào)

具體情況見圖10—16.

圖10 p（2，3，4，9）∪p23的優(yōu)美標(biāo)號(hào)

圖11 p（2，3，12）∪p24的優(yōu)美標(biāo)號(hào)

圖12 p（2，3，4，9，12，16）∪p25的優(yōu)美標(biāo)號(hào)

圖13 p（2，3，4，9，12，16，20）∪p26的優(yōu)美標(biāo)號(hào)

圖14 p（2，3，4，9，12，16，20，25）∪p27的優(yōu)美標(biāo)號(hào)

圖15 p（2，3，4，9，12，16，20，25，28）∪p28的優(yōu)美標(biāo)號(hào).

圖16 p（2，5，32）∪p29的優(yōu)美標(biāo)號(hào)

［1］ 馬杰克.優(yōu)美圖［M］.北京：北京大學(xué)出版社，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］ 梁志和.關(guān)于圖標(biāo)號(hào)問題［J］.河北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2000，24（3）：300-303.

［5］ 楊燕呂，王廣選.圖pm∪pn的優(yōu)美性初探［J］.北京工業(yè)大學(xué)學(xué)報(bào)，1993，19（4）：15-26.

［6］ 張志尚，王春月，張慶成.關(guān)于w～n∪w～n∪pm的優(yōu)美性［J］.東北師大學(xué)報(bào)：自然科學(xué)版，2010，42（4）：30-34.

［7］ 馬鳳敏，吳曉春，張偉，等.關(guān)于n長路的（a，b；n）-優(yōu)美標(biāo)號(hào)［J］.東北師大學(xué)報(bào)：自然科學(xué)版，2012，44（4）：31-42.

［8］ 張志尚，黃文強(qiáng).兩類并圖的優(yōu)美性［J］.東北師大學(xué)報(bào)：自然科學(xué)版，2013，45（2）：30-34.

［9］ 吳躍生，王廣富，徐保根.非連通圖（P2∨ˉKn）（r1，r2，…，rn＋2）∪Gr的優(yōu)美性［J］.東北師大學(xué)報(bào)：自然科學(xué)版，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 ［學(xué)科代碼］ 110·7470

A

（責(zé)任編輯：陶 理）

1000-1832（2015）03-0055-05

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

2014-02-01

國家自然科學(xué)基金資助項(xiàng)目（61172094）；吉林省自然科學(xué)基金資助項(xiàng)目（20130101068）.

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