多重超平面完備殘差圖

段輝明,邵凱亮,張清華,曾 波

(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的階.

文中沒有定義的術語與符號參閱文獻[1-8].

3 任意維超平面完備殘差圖的最小階和唯一極圖

由定義2.3可以直接得到下面引理.

引理3.1若G是HPK(n1,n2,···nr)-殘差圖,n1,n2,···nr≥r≥3,則對任意兩點u,v∈V(G),存在一點w∈G,使得u,v∈V(G)-N?(w).

對于任意維超平面殘差圖還有以下結論.

引理3.2若(n1+1,n2+1,···,nr+1),n1,n2,···,nr≥ 1,r≥ 2,則G是HPK(n1,n2,···,nr)-殘差圖.

證令V(G)=V1×V2×···×Vr,|Vi| =ni+1,點x=(x1,x2,···xr)與y=(y1,y2,···,yr)彼此不相鄰,定義為xi/yi,i=1,2,···,r,因此對于任意一點v=(v1,v2,···,vr)∈G,則有

引理3.3若G=HPK(n1,n2,···nr),{v1,v2,···,vr,v0} 是G的r+1 獨立集,則有

證假設存在點x=(x1,x2,···,xr)∈N?(v1)∩N?(v2)∩···∩N?(vr)∩N?(v0),并且與,k=0,1,···,r鄰接,由G的鄰接條件可知,存在一點,所以有1≤ik≤r,k=0,1,···,r,ik=il=h,k/=l,則一定存在k,l,使得,然而與在G中不鄰接,從而導致矛盾.證畢.

引理3.4若H=HPK(n1+1,n2+1,···,nr+1),{v,v1,v2,···,vr} 是H的 (r+1)-獨立集,且設Hi=H-N?(vi),i=1,2,···,r,則有

證因為V(H)=V(Hi)∪N?(vi),v∈V(Hi),所以

引理3.5如果HPK(n1,n2,···nr),{v1,v2,···,vk}?V(G),以及 {u1,u2,···,uk}?V(H)分別是G和H的k-獨立集,則有

證對于任意k-獨立集{v1,v2,···,vk}?V(G),這里把G的所有k-獨立集定義為一個函數(shù),記為gk,又假設gk=g(v1,v2,···,vk)=|N?(v1)∩N?(v2)∩ ···∩N?(vk)| ,則gk是一個常值函數(shù),因為當k=1時,

所以g1=g(v)為一個常數(shù).類似地,可以證明gk是一個常數(shù),且由引理3.3可得知當1＜k＜r+1 時,gk=0. 設Gk=G-N?(v1)-N?(v2)-···-N?(vk),則有GkHPK(n1-k,n2-k,···,nr-k)和ν(Gk)=(n1-k)(n2-k)···(nr-k)=vk,因此有

又由于,則存在一個映射σ：V(H)→V(G),u1和u2在H中鄰接當且僅當σ(u1)和σ(u2)在G中彼此鄰接. 假設vi=σ(ui),i=1,2,···,r,則有 {v1,v2,···,vk}?V(G)是一個k-獨立集當且僅當{u1,u2,···,uk}?V(H)是k-獨立集,因此

定理3.1若G是一個HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r≥3,則有ν(G)≥ (n1+1)(n2+1)···(nr+1).

證對于任意一點v∈G,有G-N?(v)=(n1,n2,···,nr),記

點x=(x1,x2,···,xr)和y=(y1,y2,···,yr)在F中彼此不鄰接定義為當且僅當xi/yi,i=1,2,···,r.設vk=(k,k,···,k),k=1,2,···,r,則有 {v,v1,v2,···,vr} 是G中的r+1-獨立集.由引理3.4與3.5可知

因此

下面設H=HPK(n1+1,n2+1,···,nr+1),則有

因此有

證畢.

上面得到r-1維超平面殘差圖的最小階,下面主要構造最小圖,并證明此圖是唯一的極圖.為了得到極圖,設G是一個HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r≥3,主要任務是命名G中點的名稱以及點與點的鄰接關系以及相應的命名規(guī)則.首先定義G中的點和鄰接關系,設

定義點x=(x1,x2,···,xr) 與y=(y1,y2,···,yr) 彼此不相鄰當且僅當xi/yi,i=1,2,···,r. 對任意一點u∈G, 則有G-N?(u)=HHPK(n1,n2,···,nr). 下面定義H中的點

在H中定義兩點不相鄰與在G中的定義一致,由此可以根據(jù)(3.1)式定義G的任何一個子集.又由于H=G-N?(v),要命名G中的點,首先命名N?(v)中的點.設vk=(k,k,···,k),k=1,2,···,r,則有

由引理3.4可得

再根據(jù)引理3.5可知

再由引理3.3知N?(v)∩N?(v1)∩···∩N?(vr)=φ,所以(3.2)式最后一個并集的集合為空集,所以(3.2)式應為

為了命名G中的所有點,因為H=G-N?(v)以及Hk=G-N?(vk),故下面先命名N?(vk)命名規(guī)則,設H=HPK(n1,n2,···,nr),n1,n2,···,nr≥r≥ 3,

點x=(x1,x2,···,xr) 與y=(y1,y2,···,yr) 不相鄰定義為當且僅當xiyi,i=1,2,···,r.設v=v1=(1,1,···,1),

則有下面命名規(guī)則.

命名規(guī)則 3.1R1：i1,i2,···,il,il+1,···,ir是 { 1,2,···,r}的一個排列,其中 1≤i1＜i2＜···＜il≤r,1≤il+1＜···＜ir≤r,1≤l≤r-1.

R2：a1,a2,···,al是一個序列,其中 2≤ak≤nik,k=1,2,···,l.

R3：Y={ (y1,y2,···,yr)∈F1|yirak,k=1,2,···,l}.

R4：b1,b2,···,br是一個序列,其中 1≤bk≤nik,bkak,k=1,2,···,l.

R5：uk=其中,則有唯一點,滿足

R6：x?是與u1,u2,···,ul鄰接的.

R7：x?與Y中的點彼此不鄰接.

下面說明命名規(guī)則 3.1 合理性,設x?=(x1,x2,···,xr),xik=ak,k=1,2,···,l,xil+1=···=xir=1,這里點x?是滿足C6和C7這兩條性質的,且這樣的x?是唯一的,因為x?與Y中點是彼此不鄰接的,因此有xil+1=···=xir=1.

下面需要證明的是xik=ak,x?是不鄰接y∈Y,xik僅僅只能為ak或者1,而這里xikbk,故有x?與uk鄰接的,以及xik=ak,k=1,2,···,l,命題規(guī)則是合理的.

檢驗N?(v1)的點的關鍵條件是命名規(guī)則3.1中R1,R2,R3,由于b1,b2,···,bl選擇是不唯一的,導致u1,u2,···,ul也是不唯一的,所以命名的關鍵主要是R1,R2,R3,因此這三個條件可以作為整個圖G的命名條件,于是得到下面的命名規(guī)則.

命名規(guī)則3.2命名規(guī)則3.1中的R1,R2,R3可以唯一確定N(v1)中的每一個點,相反N?(v1)中的所有的點如果都已經(jīng)確定,則命名規(guī)則3.1中R1,R2,R3也相應被確定.

命名規(guī)則3.2的前部分可直接由命名規(guī)則3.1的說明得到,下面說明結論的后半部分.

設x=(x1,x2,···,xr)∈N(v1),根據(jù)N(v1)的點的性質,可以重新命名規(guī)則3.1中的R1,R2,R3.

R1：i1,i2,···,il,il+1,···,ir,1≤i1＜i2＜···＜il≤r,1≤il+1＜···＜ir≤r,1≤l≤r-1,其中xil+1=···=xir=1,xi1,xi2,···,xi1/1.

R2：a1,a2,···,al是一個排列,其中ak=xik,2≤ak≤nik,k=1,2,···,l.

R3：Y={ (y1,y2,···,yr)∈F1|yikak,k=1,2,···,l}.

由此可以根據(jù)命名規(guī)則3.1和3.2命名所有的N?(vk)中的點,其中vk=(k,k,···,k),k=1,2,···,r. 如果有NH(v) 的點x未命名,其中H=HPK(n1,n2,···,nr),n1,n2,···,nr≥r≥3,則可以任意找一點v∈H,根據(jù)H-N?(v)中的點的命名規(guī)則命名,即可以根據(jù)命名規(guī)則3.1和3.2命名.對于N(v)中點的命名可以根據(jù)N?(v)的點命名,只須設v=(0,0,···,0),所以N(v)的點的命名規(guī)則也被確定.

因為H=G-N?(v),以及Hk=G-N?(vk),要確定G中的點,最后剩下NHk(v)中的點沒有命名規(guī)則,由式子(3.1),(3.3)可知首先命名NH1(v)中的點,有下面的命名規(guī)則.

命名規(guī)則3.3只需要把命名規(guī)則3.1和3.2中的1用0代替即可得到NH1(v)中的點的命名規(guī)則.

的點命名,即根據(jù)H=G-N?(v)的點命名規(guī)則命名,只須把命名規(guī)則3.1和3.2中的1用0代替即可.

下面命名NH2(v)∩NH2(v1)的點.由于

命名規(guī)則 3.4R1：i1,i2,···,il,il+1,···,ir一個排列.

R2：a1,a2,···,al是一個序列,其中 1≤ak≤nik,ak2,k=1,2,···,l,1∈{a1,a2,···,al}.

R3：Y={ (y1,y2,···,yr)∈F2|yik/ak,k=1,2,···,l}.

命名規(guī)則3.4只在命名規(guī)則3.2的R2增加了條件1∈{a1,a2,···,al},增加此條件的目的主要是保證條件R1,R2,R3確定的點x一定是屬于.如果不增加此條件,根據(jù)圖G的點的命名的唯一性原則,只能確定中的點x,增加此條件后在找一點x?,而點x?可以分別在H1與H2重新命名.

下面主要說明x?在H1與H2的命名是一致的,前面命名規(guī)則3.4命名了H2中的點.下面先完成H1中的命名規(guī)則：x?在H1命名為(x1,x2,···,xr).又由于x?不鄰接v2=(2,2,···,2)∈H1,因此在H1中的命名規(guī)則可以如下.

命名規(guī)則 3.5R1：i1,i2,···,il,il+1,···,ir是一個排列,其中xi1,xi2,···,xil0,1,2,xil+1=···=xil=0.

R2：a1,a2,···,al是一個序列,其中ak=xik0,1,2,k=1,2,···,l.

R3：Y={ (y1,y2,···,yr)∈F2|yik/ak,k=1,2,···,l}.

下面說明x?在H1與H2中命名是一致的,假設在H2中有一點其中=ak,k=1,2,···,l以及=···==0且ak/0,1,2,因此x??是與點v1=(1,1,···,1)∈H2不鄰接的,而,從而x??=x?,故x?在H1與H2中命名是一致的.

命名規(guī)則 3.6R1：i1,i2,···,il,il+1,···,ir是一個排列,其中xi1,xi2,···,xil/0,1,2,xil+1=···=xil=0.

R2：a1,a2,···,al是一個序列,其中 1≤at≤nit,at/k,以及 { 1,2,···,k-1}?{a1,a2,···,ak}.

R3：Y={ (y1,y2,···,yr)∈Fk|yitat,t=1,2,···,l}.

根據(jù)上面的命名規(guī)則可以確定x?=(x1,x2,···,xr),且,由上面的結論,可設k=r,則可以得到式子(3.3)的最后一個式子命名規(guī)則.

命名規(guī)則 3.7R1：i1,i2,···,ir-1,ir是一個排列,且有1≤i1＜i2＜···＜ir-1≤r,1≤ir≤r.

R2：a1,a2,···,ar-1是一個序列,其中 {a1,a2,···,ar-1}={ 1,2,···,r-1}.

R3：Y={ (y1,y2,···,yr)∈Fr|yik/ak,k=1,2,···,r-1}.

根據(jù)上面的命名規(guī)則R1,R2,R3,可以完全命名Hr,這里Hr=G-N?(vk),前面定義了N?(vk)的命名規(guī)則,這樣G中的所有的點被Hr與N?(vk)點完全決定,可以命名為V(G)={ (x1,x2,···,xr)| 0≤xi≤ni},G中的兩點x=(x1,x2,···,xr) 和y=(y1,y2,···,yr) 彼此不鄰接當且僅當xiyi,i=1,2,···,r.

根據(jù)上面的命名原則可以得到下面結論.

定理3.2若G是HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r≥ 3,ν(G)=(n1+1)(n2+1)···(nr+1),則(n1+1,n2+1,···,nr+1),且這樣的G是唯一的.

證對于G中任意兩點x和y,根據(jù)引理3.1可知,一定存在一點w,使得w與x和y都不鄰接.假設w∈Hk,其中Hk是遵循上面的命名規(guī)則,對于任意一個k,如果既有x∈Hk也有y∈Hk,則可以使用Hk命名規(guī)則來命名.設H?=G-N?(w)(n1,n2,···nr),則有x,y∈H?.因為G中的點可根據(jù)Hk中的點命名規(guī)則命名,又根據(jù)命名的唯一性可以命名G中所有的點,因為H?=G-N?(w),所以根據(jù)G命名規(guī)則命名H?的點,事實上x,y∈H?=G-N?(w),根據(jù)命名規(guī)則可知,x=(x1,x2,···,xr)和y=(y1,y2,···,yr)是彼此不鄰接的,故G中任意兩點都彼此不鄰接,所以(n1+1,n2+1,···nr+1),再由點的鄰接關系HPK(n1+1,n2+1,···nr+1)是唯一最小的r-1維超平面完備殘差圖.

4 任意維超平面完備殘差圖的一個重要的性質

這一節(jié)主要是討論任意維超平面完備殘差圖的結構,主要有下面的結果.

定理4.1若G是HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r+2 ≥ 5,則有ν(G)=k(n1+1)(n2+1)···(nr+1),G=G1+G2+···+Gk,且GiHPK(n1+1,n2+1,···,nr+1),i=1,2,···,k.

為了證明此定理,先定義有關超平面的點獨立集的坐標變換.

定義4.1如果H=HPK(n1,n2,···,nr),V(H)={ (x1,x2,···,xr)| 1≤xi≤ni,i=1,2,···,r},假設獨立集S1={v1,v2,···,vr,v0} 與S2={u1,u2,···,ur,u0},且S1與S2都是(r+1)-獨立集.S2與S1坐標變換定義如下,如果ui=vi,i=0,1,2,···,r;i/k,l,其中使得或者或者xj,或者或者yj,j=1,2,···,r,xj,yj/,i=0,1,2,···,r,則有

由定義4.1,可以直接得到下面引理.

引理4.1如果H=HPK(n1,n2,···,nr),V(H)={ (x1,x2,···,xr)| 1≤xi≤ni,i=1,2,···,r},n1,n2,···nr≥r+1 ≥ 4,則對任意u∈H,存在一個 (r+1)- 獨立集{u1,u2,···,ur,u},可以和任何一個 (r+1)-獨立集 {v1,v2,···,vr,v}進行坐標變換.

下面證明定理4.1.

設v0,v1,···,vr是圖G中的r+1 獨立集. 若Hi=G-N?(vi)(n1,n2,···,nr),i=0,1,···,r. 設G1=＜H0∪H1∪H2∪···∪Hr＞,假設G1?G是G中由H0,H1,···,Hr生成的最小子圖,顯然,vi/∈Hi,以及vi∈Hj,i,j=0,1,2.N?(vi)∩V(Hi)=φ,i=0,1,2,···,r,因此有

下證G1(n1+1,n2+1,···,nr+1),因為G1-N?(vi)=HiHPK(n1,n2,···,nr),則有

以及

再由引理3.4和引理3.5可知.

如果G1=G,再根據(jù)定理3.2知,G是最小階的HPK(n1,n2,···,nr)-殘差圖.如果G1/G,設N?(v0)∩N?(v1)∩ ···∩N?(vr)=W,則有以及G1=G-W,并且V(G1)∩W=,因此V(G1)?V(G)-W.對于任意x∈V(G)-W,有,以及(vi),對任意的i,有x∈G-N?(vi)=Hi?G1,所以V(G)-W?V(G1),以及G1=G-W,故有G1是HPK(n1,n2,···,nr)-殘差圖.

由上面證明可知任意的x∈G1都與任意w∈W鄰接.下面證明對于任意的x∈H0,x都與任意的w∈W鄰接的.因為H0=G-N?(v0),所以有{v1,v2,···,vr}?V(H0),由條件可知v∈H0以及{v1,v2,···,vr,v}是H0的(r+1)-獨立集,且v也是與任意的w∈W鄰接的,若不然,v不與w?∈W鄰接,則有以及{v0,v1,···,vr}?V(H)是H(r+1)-獨立集,因此存在w?∈H,即,這與引理3.2矛盾,故有W?N?(v).

因為n1,n2,···,nr≥r+2 ≥ 5,因此存在兩點u,v∈H0,使得 {v1,v2,···,vr,u,v}?V(H)是(r+2)-獨立集,則W?N?(u)∩N?(v).現(xiàn)在假設是(r+2)-獨立集,則H0中存在另一點{v1,v2,···,vr,u,v}與之進行坐標變換.根據(jù)上面的討論同樣可得,再由引理3.1可知對任意x∈H0,以及x∈G1,都有x是與任意w∈W鄰接的,因此有

下面證明G1是HPK(n1,n2,···,nr)-殘差圖.由于ν(G)=(n1+1)(n2+1)···(nr+1),根據(jù)定理3.2,有(n1+1,n2+1,···,nr+1).又因為任意w∈W,則有V(G1)?N?(w).設＜W＞=F,則有G=G1+F以及

由于w∈W的任意性,F是HPK(n1,n2,···,nr)-殘差圖,所以對F可以類似的討論,G2的一個最小子圖,則G2(n1+1,n2+1,···,nr+1),F=G2+F1,其中F1=F-V(G2).重復前面在G中的討論,則有

5 多重超平面完備殘差圖的最小階和唯一極圖

根據(jù)多重超平面殘差圖的定義容易得到引理5.1和5.2.

引理5.1若G=(V,E),{v0,v1,···,vr}∈G?V(G)是G中(k+1)-獨立集,則有

其中F=G-N?(v0).

引理5.2令G=(V,E),u1,u2,···,uk∈G,{v0,v1,···,vr}?V(G)是G中 (r+1)-獨立集,對每一個vi都不與uj鄰接.令Fi=G-N?(vi),i=1,2,···,l,則有

由任意維超平面殘差圖的性質也可以得到m重任意維超平面殘差圖的性質.

引理5.3若G是HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+1,n2+1,···,nr+1),n1,n2,···,nr≥r≥ 3. 令 {v1,v2,···,vk}?V(G)以及 {u1,u2,···,uk}?V(H)分別是G和H中的k-獨立集,則有

證當k≥r+1,由引理3.3可知

則上面不等式成立.下面假設1≤k≤r,則存在v∈G和u∈H,且有{v1,v2,···,vk,v}{u1,u2,···,uk,u}分別是G和H中(k+1)-獨立集.設G1=G-N?(v),H1=H-N?(u),則有G1H1(n1,n2,···,nr),{v1,v2,···,vk}?V(G1) 以及 {u1,u2,···,uk}?V(H1)分別是G1和H1的k-獨立集,且有

因為G11(n1,n2,···,nr),由引理 3.4 知

由此可知當k≥r+1,k=r,r-1,···,3,2,1.上面不定式成立的.

引理5.4假設G是 2-HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+2,n2+2,···,nr+2),n1,n2,···,nr≥r≥ 3{v1,v2,···,vk}?V(G) 和 {u1,u2,···,uk}?V(H)分別是G和H的k-獨立集,則有

證由引理3.3知,k≥r+1不等式是顯然成立的,下面假設1≤k≤r,根據(jù)引理5.3的討論,在G和H中存在點v∈G,u∈H,使得G1=G-N?(v),H1=H-N?(u),以及 {v1,v2,···,vk}?V(G1)和 {u1,u2,···,uk}?V(H1). 因為G1是HPK(n1,n2,···,nr)-殘差圖,以及H1=HPK(n1+1,n2+1,···,nr+1),因此當k≥r+1不等式成立,k=r,r-1,···,3,2,1.

引理5.5假設G是m-HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+m,n2+m,···,nr+m),n1,n2,···,nr≥r≥ 3,{v1,v2,···,vr}?V(G) 和 {u1,u2,···,uk}?V(H)分別是G和H的k-獨立集,則有

證當m=1,2,有引理5.3和引理5.4知成立的.下面對m用數(shù)學歸納法證明,假設對m-1成立,由引理3.3可知k≥r+1時,不等式成立,討論與引理5.3,5.4的討論一樣可以得到,對于m,k≥r+1,k=r,r-1,···,3,2,1是成立的.

定理5.1假設G是m-HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r≥3,則有ν(G)≥ (n1+m)(n2+m)···(nr+m).

證當m=1,由定理3.1可知,結論成立.利用數(shù)學歸納法,假設當m-1≥1成立,當為m時,G是m-HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+m,n2+m,···,nr+m).由引理5.4知,,對于G和H中的任意一點v∈G,u∈H.設G1=G-N?(v),H1=H-N?(u),則有G1是 (m-1)-HPK(n1,n2,···,nr)-殘差圖,故有

利用歸納假設有

定理5.2假設G是m-HPK(n1,n2,···,nr)-殘差圖,n1,n2,···,nr≥r≥3,以及ν(G)=(n1+m)(n2+m)···(nr+m),則有GHPK(n1+m,n2+m,···,nr+m).

證設G是m-HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+m,n2+m,···,nr+m),n1,n2,···,nr≥r≥3,ν(G)=ν(H).當m=1 時,由定理 3.2 可知,(n1+1,n2+1,···,nr+1).利用數(shù)學歸納法,假設m-1≥1成立.對于m,存在點v∈G和u∈H,有G1=G-N?(v)是 (m-1)-HPK(n1,n2,···,nr)-殘差圖,以及H1=H-N?(u)=HPK(n1+m-1,···,nr+m-1).再由引理5.5 定理 5.1,有

因此有G1是最小階的(m-1)-HPK(n1,n2,···,nr)-殘差圖.根據(jù)歸納假設有G1(n1+m-1,n2+m-1,···,nr+m-1).由于v是G中任意一點,根據(jù)定義2.2知,G是最小階的HPK(n1+m-1,n2+m-1,···,nr+m-1)-殘差圖,設=ni+m-1≥ni≥r≥ 3,i=1,2,···,r,由定理 3.2 可知(n1+m,n2+m,···,nr+m). 證畢.

[2]楊世輝,段輝明.奇階完備殘差圖[J].應用數(shù)學學報,2011,34(5)：778-785.

[3]Liao J,Yang S,Deng Y.On connected 2-Kn-residual graphs[J].Mediterranean J.Math.,2012,6：12-27.

[4]段輝明,曾波,竇智.連通的三重Kn-殘差圖[J].運籌學學報,2014,18：59-68.

[5]Liao J,Long G,Li M.Erds conjecture on connected residual graphs[J].J.Comput.,2012,7：1497-1502.

[7]Trotta B.Residual properties of simple graphs[J].Bull.Austr.Math.Soc.,2010,82：488-504.

[8]段輝明,曾波,李永紅.關于m-HPK(n1,n2,n3,n4)-殘差圖[J].數(shù)學雜志,2014,34(2)：324-334.

[9]Duan H.On connectedmmultiply 2 dimensions composite hyperplanne complete graph’s residual graphs[J].J.Discrete Math.Sci.Crytography,2014,16：313-328.

[10]Yang H S.The isomorphic factorization of complete tripartite graphsK(m,n,s)-a proof of F.Harary,R.W.Robinson and N.C.Wormald’s conjecture[J].Disc.Math.,1995,145(1-3)：239-257.

[11]Liang Z,Zuo H.On the gracefulness of the graph[J].Appl.Anal.Discrete Math.,2010,10：175-180.

MULTIPLY HYPERPLANE COMPLETE RESIDUAL GRAPH

DUAN Hui-ming1,SHAO Kai-liang1,ZHANG Qing-hua1,ZENG Bo2
(1.College of Science,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)(2.School of Business Planning,Chongqing Technology and Business University,Chongqing 400067,China)

In this paper,we study any number of dimensions hyperplane complete residual graphs and multiply any number of dimensions hyperplane complete residual graphs,and extend Erds,Harary and Klawe’s de fi nition of plane complete residual graph to hyperplane and obtain dimensions hyperplane complete residual graph.With the method of including excluding principle and set operation,we obtain the minimum order of any number of dimensions hyperplane complete residual graphs and a unique minimal any number of dimensions hyperplane complete residual graph,and an important property of any number of dimensions hyperplane complete residual graph.In addition,we obtain the minimum order of multiply any number of dimensions hyperplane complete residual graphs and a unique minimal multiply any number of dimensions hyperplane complete-residual graphs.

residually graph;close neighborhood;isomorphic;independent set

on：05C35;05C60;05C75

O157.5

A

0255-7797(2017)04-0833-12

2015-08-24接收日期：2015-12-21

國家自然科學基金(11671001;61472056);重慶自然科學基金(cstc2015jcyjA00034;cstc2015jcyjA00015);重慶市教育委員會科學技術研究(KJ1600425;KJ1500403).

段輝明(1976-),女,重慶銅梁,講師,主要研究方向：組合數(shù)學.