吳建強

（廣東工業(yè)大學華立學院計算機工程系，廣東增城 511325）

圖Gn的優(yōu)美表示

吳建強

（廣東工業(yè)大學華立學院計算機工程系，廣東增城 511325）

將給出三個結果：（i）如果圖G是上的整數(shù)和圖，那么0∈S當且僅當圖G至少有一個（n－1）度頂點；（ii）圖G（G≠K2）是至少有兩個零點的整數(shù)和圖當且僅當G?K2·Gn；（iii）設圖G（G≠K2）是S?Z上的整數(shù)和圖.若圖G至少有兩個零點，則

整數(shù)和圖；零點；圖Gn的優(yōu)美表示；圖k2·Gn

在論文［1］中，F(xiàn)rank Harary給出了如下兩個定義：

定義1設Z是整數(shù)集，S?Z，S上的整數(shù)和圖是圖G＝〈V，E〉，其中V＝S，且對于任意的u，v∈S，有uv∈E當且僅當u＋v∈S.

定義2如果圖G與S（S?Z）上的整數(shù)和圖同構，則稱圖G是整數(shù)和圖.

設Nn＝｛1，2，…，n｝，將Nn上的整數(shù)和圖記為Gn［1］.由完全圖K2

［2］的兩個頂點與Gn的每個頂點鄰接所構成的圖記為K2·Gn.圖G5與K2·G5如圖1與圖2所示.另外，約定Z表示整數(shù)集，Z＊表示非零整數(shù)集，N表示自然數(shù)集，N＋表示正整數(shù)集.本文所討論的圖均為有限簡單圖［2］.

圖1 圖G5

圖2 圖K2·G5

定理1設圖G是S?上的整數(shù)和圖，則0∈S當且僅當圖G至少有一個（n－1）度頂點.

證設V（G）＝｛vi｜i＝1，2，…，n｝，S＝｛si｜i＝1，2，…，n｝，且vi＝si（即頂點vi的標號是si），i＝1，2，…，n.

必要性.如果0∈S，則存在某個正整數(shù)a，1≤a≤n，使得sa＝0.顯然，有sa＋si＝0＋si＝si∈S（i＝1，2，…，a－1，a＋1，…，n），又已知圖G是S上的整數(shù)和圖，則由定義1可知，vavi∈E（G）（i＝1，2，…，a－1，a＋1，…，n），即degva＝n－1，因此圖G至少有一個（n－1）度頂點.

充分性.如果圖G至少有一個（n－1）度頂點，則存在某個正整數(shù)a，1≤a≤n，使得degva＝n－1，即vavi∈E（G），i＝1，2，…，a－1，a＋1，…，n.已知圖G是S上的整數(shù)和圖，根據(jù)定義1，有

此時，如果0?S，即si≠0（i＝1，2，…，n），則用數(shù)學歸納法可以證明：對于任意自然數(shù)m，都有

從而有｛msa＋sb｜m∈N｝?S.這與S是有限集矛盾，故0∈S.

下面用數(shù)學歸納法證明：若0?S，則（2）式對于任意自然數(shù)m都成立.

（i）當m＝0時，（2）式顯然成立.由（1）式可知，sa＋sb∈S，即當m＝1時，（2）式也成立.

（ii）假設對任意自然數(shù)m，當m＜k（k＞1，k∈N＋）時，（2）式都成立.由此假設可得（k－2）sa＋sb∈S.若（k－1）sa＋sb＝sa，即（k－2）sa＋sb＝0，則有0∈S，這與0?S矛盾，故（k－1）sa＋sb≠sa.再由假設可得（k－1）sa＋sb∈S，因此存在某個正整數(shù)l，l≠a，1≤l≤n，使得（k－1）sa＋sb＝sl，從而由（1）式可知

即當m＝k時，（2）式仍成立.

在圖G中，若某個頂點與其它頂點均鄰接，則稱這個頂點為圖G的零點.

定理1表明：當圖G是整數(shù)集S?Z＝n≥2）上的整數(shù)和圖時，若圖G有零點，則0∈S，否則0?S.

設S?Z，m∈Z＊，規(guī)定mS＝｛mx｜x∈S｝.

引理若圖G是S?Z上的整數(shù)和圖，則圖G也是mS（m∈Z＊）上的整數(shù)和圖.

證設S＝｛ai｜i＝1，2，…，n；n∈N＋｝，則mS＝｛mai｜i＝1，2，…，n；n∈N＋｝.在S與mS之間建立如下1－1映射：

再由定義1可知，S上的整數(shù)和圖與mS上的整數(shù)和圖同構［2］，由此得引理.

定理2圖G（G≠k2）是至少有兩個零點的整數(shù)和圖當且僅當G?k2·Gn.

證充分性.若圖G?k2·Gn，則由定義1可知，圖G是數(shù)集｛－1，0，1，2，…，n｝上的整數(shù)和圖，且至少有兩個零點（標號為0及－1的兩個頂點都是零點）.

必要性.假設圖G（G≠k2）是至少有兩個零點的整數(shù)和圖，根據(jù)定義2，可設圖G是S?Z上的整數(shù)和圖，其中S＝｛si∈Z｜i＝1，2，…，n＋2｝，V（G）＝｛｜i＝1，2，…，n＋2｝且表示標號為si的頂點.據(jù)定理1可知，0∈S，因而圖G的零點中有一個標號是0.將另外一個零點的標號設為x（x∈S，x≠0）.對于任意的t∈S，t≠x，顯然有vxvt∈E（G），則由定義1得

為了確定整數(shù)集S，首先，用反證法證明：對于任意一個a∈S－｛0，x｝，存在一個相應的正整數(shù)m0，使得m0x＋a＝0，即

假設對于任意的m∈N＋，都有

則用數(shù)學歸納法可以證明：對于任意正整數(shù)m，都有

從而有｛mx＋a｜m∈N＋｝?S，這與S是有限集矛盾.

下面用數(shù)學歸納法證明：若（5）式對于任意正整數(shù)m都成立，則（6）式對于任意正整數(shù)m也都成立.

（i）由（3）式可知x＋a∈S，即當m＝1時，（6）式成立.

（ii）假設當m＝k（k∈N＋）時，（6）式成立，即kx＋a∈S.據(jù)（5）式及a∈S－｛0，x｝，易知對任意的k∈N＋，有（k－1）x＋a≠0，即kx＋a≠x，從而由（3）式可得

即當m＝k＋1時，（6）式仍成立.

在（4）式中，若a＝x1，則可設m0＝m1，即x1＝－m1x.

其次，用數(shù)學歸納法可以證明：對于任意的m∈｛1，2，…，m1－1，m1｝，有

（i）由（3）式可知，x＋x1∈S，即當m＝1時，（7）式成立.

（ii）假設當m＝k（k＜m1）時，（7）式成立，即kx＋x1∈S.由x1＝－m1x，有

因為k＜m1，x≠0，所以［k－（m1＋1）］x≠0，即kx＋x1≠x.于是由（3）式可得

即當m＝k＋1時，（7）式仍成立.

再次，確定整數(shù)集S.構造集合A＝｛0，x，x1，x＋x1，2x＋x1，…，（m1－1）x＋x1｝.由（7）式可知，A?S.事實上A＝S，否則假設A?S，即存在x2∈S，x2?A.由（4）式可知，存在m2∈N＋，使得x2＝－m2x.因為A＝｛0，x，－m1x，－（m1－1）x，…，－x｝（由x1＝－m1x得到）且x2?A，所以m2＞m1，從而有

這與x1是S－｛0，x｝中絕對值最大的整數(shù)矛盾.于是，由A＝S可，因而m1＝n，所以

圖K2·Gn是整數(shù)集S′＝｛－1，0，1，2，…，n｝上的整數(shù)和圖（由定義1可知）且S＝－xS′，x∈Z＊，據(jù)引理可得，圖K2·Gn也是S上的整數(shù)和圖，而據(jù)前面的假設，圖G是整數(shù)集S上的整數(shù)和圖，故圖G?K2·Gn.

定理1給出了圖Gn的一條重要性質，也給出了圖Gn結構的一個優(yōu)美表示［1］.此定理對于研究一般的整數(shù)和圖很有用.例如，由定理可知，在零點數(shù)不小于2的所有非k2圖中，只有圖k2·Gn才是整數(shù)和圖，而其余圖都不是整數(shù)和圖.

由定理2的必要性的證明可得：

定理3設圖G（G≠k2）是S?Z上的整數(shù)和圖，＝n＋2，n∈N＋.若圖G至少有兩個零點，則

由定理2的充分性的證明可知，圖k2·Gn是至少有兩個零點的整數(shù)和圖.假設圖k2·Gn是S?Z上的整數(shù)和圖，則根據(jù)定理3可以斷定

［1］Frank Harary.Sum graphs over all the integers［J］.Discrete Mathematics，1994，124：99—105.

［2］Bondy J A，Murty U S R.Graph theory with applications［M］.New york：Macmillan Press，1976.

［3］哈拉里F.圖論［M］.李慰萱譯.上海：上?？茖W技術出版社，1963.

［4］盧開澄，盧華明.圖論及其應用［M］.2版.北京：清華大學出版社，1995.

［5］王朝瑞.圖論［M］.3版.北京：北京理工大學出版社，2001.

An Elegant Description of GraphGn

WuJian－qiang
（Computer Engineering Department，Guangdong University of Technology Huali College，Zengcheng Guangdong 511325，China）

We will give the following three results：（i）IfG＝＜V，E＞，＝n≥2andGis a sum graph overSthat is an integer set，then 0∈Sif and only if there is a vertexx（x∈V）withdG（x）＝n－1；（ii）The graphG（G≠k2）is an integral sum graph with two or more 0－vertex if and only ifG?k2·Gn；（iii）Assume a graphGis an integral sum graph overS（S?Z），＝n＋2，n∈N＋，If the graphGhas at least two 0－vertex，thenS＝｛mx｜m＝－1，0，1，2，…，n，andx∈Z＊｝.

the integral sum graph；0－vertex；an elegant description of the structure of graphGn；the graphk2·Gn

O15

A

1672－1454（2012）04－0064－04

2009－12－28；［修改日期］2010－05－28