段辉明,邵凯亮,张清华,曾 波

(1.重庆邮电大学理学院,重庆 400065)(2.重庆工商大学商务策划学院,重庆 400067)

多重超平面完备残差图

段辉明1,邵凯亮1,张清华1,曾 波2

(1.重庆邮电大学理学院,重庆 400065)(2.重庆工商大学商务策划学院,重庆 400067)

本文研究了任意维超平面完备残差图和多重超平面完备残差图,将Erd¨os、Harary和Klawe’s定义的平面残差图推广到任意维超平面.利用容斥原理以及集合的运算性质等方法,获得了任意维超平面完备残差图的最小阶和唯一极图,以及任意维超平面完备残差图的一个重要性质,同时获得了多重任意维超平面完备残差图的最小阶和唯一极图.

残差图;邻域;同构;独立集

1 引言

2 预备知识

定义2.1设图G=(V,E),u∈V=V(G),集合N(u)={x|x∈V(G),x与u邻接}与N∗(u)={u}∪N(u)分别叫做顶点u的邻域和闭邻域.

定义2.2设F是一个给定的图,如果对每一个顶点u∈V(G),从G中减去u的闭邻域N∗(u)得到的图与F同构[10-11],则称图G为F-残差图.递归地,定义G是m-F-残差图为,如果对于任意u∈V(G),G-N∗(u)得到的图都是(m-1)-F-残差图.当然1-F-残差图简单地叫做F-残差图.

定义2.3图G是r-1维超平面完备图,如果x∈V(G),V(G)=V1×V2×···×Vr,其中x={ (x1,x2,···,xr)|xi∈Vi,i=1,2,···,r},|Vi| =ni,i=1,2,···,r, 两个顶点x=(x1,x2,···,xr) 和y=(y1,y2,···,yr) 相邻当且仅当x/y,存在某个k=1,2,···,r,xk=yk.为方便起见,本文用HPK(n1,n2,···,nr)代替r-1维超平面完备图.

定义2.4设G1=(V1,E1),G2=(V2,E2)是两个图,G1与G2合成G=G1[G2],定义为V(G)=V1×V2={x=(x1,x2)| (x1∈V1,x2∈V2},两个顶点u=(u1,u2)和v=(v1,v2)是相邻的当且仅当u1与v1在G1相邻,或者u1=v1,u2与v2在G2中相邻.

定义2.5令G=(V,E),S⊂V=V(G),若S不存在两个点x,y∈S在G中邻接,而且|S|=k,则称S为G中的k-独立集.

定义2.6设图G1=(V1,E1),G2=(V2,E2),定义G=G1+G2,其中V(G)=V1∪V2,E(G)=E1∪E2∪E[K(V1,V2)],这里K(V1,V2)是以V1与V2为独立点集的完备二部图.

下面是文献[1]中的一个重要结论.

引理2.1[1]设G是F-残差图,则d(u)=ν(G)-ν(F)-1,∀u∈V(G),其中ν(G)是G的阶.

文中没有定义的术语……