吴建强

（广东工业大学华立学院计算机工程系，广东增城 511325）

图Gn的优美表示

吴建强

（广东工业大学华立学院计算机工程系，广东增城 511325）

将给出三个结果：（i）如果图G是上的整数和图，那么0∈S当且仅当图G至少有一个（n－1）度顶点；（ii）图G（G≠K2）是至少有两个零点的整数和图当且仅当G≅K2·Gn；（iii）设图G（G≠K2）是S⊂Z上的整数和图.若图G至少有两个零点，则

整数和图；零点；图Gn的优美表示；图k2·Gn

在论文［1］中，Frank Harary给出了如下两个定义：

定义1设Z是整数集，S⊂Z，S上的整数和图是图G＝〈V，E〉，其中V＝S，且对于任意的u，v∈S，有uv∈E当且仅当u＋v∈S.

定义2如果图G与S（S⊂Z）上的整数和图同构，则称图G是整数和图.

设Nn＝｛1，2，…，n｝，将Nn上的整数和图记为Gn［1］.由完全图K2

［2］的两个顶点与Gn的每个顶点邻接所构成的图记为K2·Gn.图G5与K2·G5如图1与图2所示.另外，约定Z表示整数集，Z＊表示非零整数集，N表示自然数集，N＋表示正整数集.本文所讨论的图均为有限简单图［2］.

图1 图G5

图2 图K2·G5

定理1设图G是S⊂上的整数和图，则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，则存在某个正整数a，1≤a≤n，使得sa＝0.显然，有sa＋si＝0＋si＝si∈S（i＝1，2，…，a－1，a＋1，…，n），又已知图G是S上的整数和图，则由定义1可知，vavi∈E（G）（i＝1，2，…，a－1，a＋1，…，n），即degva＝n－1，因此图G至少有一个（n－1）度顶点.

充分性.如果图G至少有一个（n－1）度顶点，则存在某个正整数a，1≤a≤n，使得degva＝n－1，即vavi∈E（G），i＝1，2，…，a－1，a＋1，…，n.已知图G是S上的整数和图，根据定义1，有

此时，如果0∉S，即si≠0（i＝1，2，…，n），则用数学归纳法可以证明：对于任意自然数m，都有

从而有｛msa＋sb｜m∈N｝⊆S.这与S是有限集矛盾，故0∈S.

下面用数学归纳法证明：若0∉S，则（2）式对于任意自然数m都成立.

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

（ii）假设对任意自然数m，当m＜k（k＞1，k∈N＋）时，（2）式都成立.由……