图Gn的优美表示

2012-11-02 07:11吴建强
大学数学 2012年4期
关键词:标号归纳法正整数

吴建强

(广东工业大学华立学院计算机工程系,广东增城 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)式都成立.由此假设可得(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,因此存在某个正整数l,l≠a,1≤l≤n,使得(k-1)sa+sb=sl,从而由(1)式可知

即当m=k时,(2)式仍成立.

在图G中,若某个顶点与其它顶点均邻接,则称这个顶点为图G的零点.

定理1表明:当图G是整数集S⊂Z=n≥2)上的整数和图时,若图G有零点,则0∈S,否则0∉S.

设S⊂Z,m∈Z*,规定mS={mx|x∈S}.

引理若图G是S⊂Z上的整数和图,则图G也是mS(m∈Z*)上的整数和图.

证设S={ai|i=1,2,…,n;n∈N+},则mS={mai|i=1,2,…,n;n∈N+}.在S与mS之间建立如下1-1映射:

再由定义1可知,S上的整数和图与mS上的整数和图同构[2],由此得引理.

定理2图G(G≠k2)是至少有两个零点的整数和图当且仅当G≅k2·Gn.

证充分性.若图G≅k2·Gn,则由定义1可知,图G是数集{-1,0,1,2,…,n}上的整数和图,且至少有两个零点(标号为0及-1的两个顶点都是零点).

必要性.假设图G(G≠k2)是至少有两个零点的整数和图,根据定义2,可设图G是S⊂Z上的整数和图,其中S={si∈Z|i=1,2,…,n+2},V(G)={|i=1,2,…,n+2}且表示标号为si的顶点.据定理1可知,0∈S,因而图G的零点中有一个标号是0.将另外一个零点的标号设为x(x∈S,x≠0).对于任意的t∈S,t≠x,显然有vxvt∈E(G),则由定义1得

为了确定整数集S,首先,用反证法证明:对于任意一个a∈S-{0,x},存在一个相应的正整数m0,使得m0x+a=0,即

假设对于任意的m∈N+,都有

则用数学归纳法可以证明:对于任意正整数m,都有

从而有{mx+a|m∈N+}⊆S,这与S是有限集矛盾.

下面用数学归纳法证明:若(5)式对于任意正整数m都成立,则(6)式对于任意正整数m也都成立.

(i)由(3)式可知x+a∈S,即当m=1时,(6)式成立.

(ii)假设当m=k(k∈N+)时,(6)式成立,即kx+a∈S.据(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.

其次,用数学归纳法可以证明:对于任意的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)式仍成立.

再次,确定整数集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}中绝对值最大的整数矛盾.于是,由A=S可,因而m1=n,所以

图K2·Gn是整数集S′={-1,0,1,2,…,n}上的整数和图(由定义1可知)且S=-xS′,x∈Z*,据引理可得,图K2·Gn也是S上的整数和图,而据前面的假设,图G是整数集S上的整数和图,故图G≅K2·Gn.

定理1给出了图Gn的一条重要性质,也给出了图Gn结构的一个优美表示[1].此定理对于研究一般的整数和图很有用.例如,由定理可知,在零点数不小于2的所有非k2图中,只有图k2·Gn才是整数和图,而其余图都不是整数和图.

由定理2的必要性的证明可得:

定理3设图G(G≠k2)是S⊂Z上的整数和图,=n+2,n∈N+.若图G至少有两个零点,则

由定理2的充分性的证明可知,图k2·Gn是至少有两个零点的整数和图.假设图k2·Gn是S⊂Z上的整数和图,则根据定理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].李慰萱译.上海:上海科学技术出版社,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

猜你喜欢
标号归纳法正整数
关于包含Euler函数φ(n)的一个方程的正整数解
物理方法之归纳法
数学归纳法学习直通车
被k(2≤k≤16)整除的正整数的特征
周期数列中的常见结论及应用*
方程xy=yx+1的全部正整数解
用“不完全归纳法”解两道物理高考题
非连通图2D3,4∪G的优美标号
数学归纳法在高考试题中的应用
非连通图D3,4∪G的优美标号