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

吳建強(qiáng)

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

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

吳建強(qiáng)

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

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

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

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

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

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

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

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

圖1 圖G5

圖2 圖K2·G5

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

證設(shè)V（G）＝｛vi｜i＝1，2，…，n｝，S＝｛si｜i＝1，2，…，n｝，且vi＝si（即頂點(diǎn)vi的標(biāo)號(hào)是si），i＝1，2，…，n.

必要性.如果0∈S，則存在某個(gè)正整數(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至少有一個(gè)（n－1）度頂點(diǎn).

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

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

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

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

（i）當(dāng)m＝0時(shí)，（2）式顯然成立.由（1）式可知，sa＋sb∈S，即當(dāng)m＝1時(shí)，（2）式也成立.

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

即當(dāng)m＝k時(shí)，（2）式仍成立.

在圖G中，若某個(gè)頂點(diǎn)與其它頂點(diǎn)均鄰接，則稱(chēng)這個(gè)頂點(diǎn)為圖G的零點(diǎn).

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

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

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

證設(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ù)和圖同構(gòu)［2］，由此得引理.

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

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

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

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

假設(shè)對(duì)于任意的m∈N＋，都有

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

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

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

（i）由（3）式可知x＋a∈S，即當(dāng)m＝1時(shí)，（6）式成立.

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

即當(dāng)m＝k＋1時(shí)，（6）式仍成立.

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

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

（i）由（3）式可知，x＋x1∈S，即當(dāng)m＝1時(shí)，（7）式成立.

（ii）假設(shè)當(dāng)m＝k（k＜m1）時(shí)，（7）式成立，即kx＋x1∈S.由x1＝－m1x，有

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

即當(dāng)m＝k＋1時(shí)，（7）式仍成立.

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

這與x1是S－｛0，x｝中絕對(duì)值最大的整數(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ù)前面的假設(shè)，圖G是整數(shù)集S上的整數(shù)和圖，故圖G?K2·Gn.

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

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

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

由定理2的充分性的證明可知，圖k2·Gn是至少有兩個(gè)零點(diǎn)的整數(shù)和圖.假設(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(xué)技術(shù)出版社，1963.

［4］盧開(kāi)澄，盧華明.圖論及其應(yīng)用［M］.2版.北京：清華大學(xué)出版社，1995.

［5］王朝瑞.圖論［M］.3版.北京：北京理工大學(xué)出版社，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