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

(1.重慶郵電大學(xué)理學(xué)院,重慶 400065)(2.重慶工商大學(xué)商務(wù)策劃學(xué)院,重慶 400067)

多重超平面完備殘差圖

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

(1.重慶郵電大學(xué)理學(xué)院,重慶 400065)(2.重慶工商大學(xué)商務(wù)策劃學(xué)院,重慶 400067)

本文研究了任意維超平面完備殘差圖和多重超平面完備殘差圖,將Erd¨os、Harary和Klawe’s定義的平面殘差圖推廣到任意維超平面.利用容斥原理以及集合的運(yùn)算性質(zhì)等方法,獲得了任意維超平面完備殘差圖的最小階和唯一極圖,以及任意維超平面完備殘差圖的一個(gè)重要性質(zhì),同時(shí)獲得了多重任意維超平面完備殘差圖的最小階和唯一極圖.

殘差圖;鄰域;同構(gòu);獨(dú)立集

1 引言

2 預(yù)備知識

定義2.1設(shè)圖G=(V,E),u∈V=V(G),集合N(u)={x|x∈V(G),x與u鄰接}與N?(u)={u}∪N(u)分別叫做頂點(diǎn)u的鄰域和閉鄰域.

定義2.2設(shè)F是一個(gè)給定的圖,如果對每一個(gè)頂點(diǎn)u∈V(G),從G中減去u的閉鄰域N?(u)得到的圖與F同構(gòu)[10-11],則稱圖G為F-殘差圖.遞歸地,定義G是m-F-殘差圖為,如果對于任意u∈V(G),G-N?(u)得到的圖都是(m-1)-F-殘差圖.當(dāng)然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, 兩個(gè)頂點(diǎn)x=(x1,x2,···,xr) 和y=(y1,y2,···,yr) 相鄰當(dāng)且僅當(dāng)x/y,存在某個(gè)k=1,2,···,r,xk=yk.為方便起見,本文用HPK(n1,n2,···,nr)代替r-1維超平面完備圖.

定義2.4設(shè)G1=(V1,E1),G2=(V2,E2)是兩個(gè)圖,G1與G2合成G=G1[G2],定義為V(G)=V1×V2={x=(x1,x2)| (x1∈V1,x2∈V2},兩個(gè)頂點(diǎn)u=(u1,u2)和v=(v1,v2)是相鄰的當(dāng)且僅當(dāng)u1與v1在G1相鄰,或者u1=v1,u2與v2在G2中相鄰.

定義2.5令G=(V,E),S?V=V(G),若S不存在兩個(gè)點(diǎn)x,y∈S在G中鄰接,而且|S|=k,則稱S為G中的k-獨(dú)立集.

定義2.6設(shè)圖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為獨(dú)立點(diǎn)集的完備二部圖.

下面是文獻(xiàn)[1]中的一個(gè)重要結(jié)論.

引理2.1[1]設(shè)G是F-殘差圖,則d(u)=ν(G)-ν(F)-1,?u∈V(G),其中ν(G)是G的階.

文中沒有定義的術(shù)語與符號參閱文獻(xiàn)[1-8].

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

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

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

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

引理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,點(diǎn)x=(x1,x2,···xr)與y=(y1,y2,···,yr)彼此不相鄰,定義為xi/yi,i=1,2,···,r,因此對于任意一點(diǎn)v=(v1,v2,···,vr)∈G,則有

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

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

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

證因?yàn)閂(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-獨(dú)立集,則有

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

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

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

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

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

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

因此

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

因此有

證畢.

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

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

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

由引理3.4可得

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

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

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

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

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

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

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

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

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

R5：uk=其中,則有唯一點(diǎn),滿足

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

R7：x?與Y中的點(diǎn)彼此不鄰接.

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

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

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

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

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

設(shè)x=(x1,x2,···,xr)∈N(v1),根據(jù)N(v1)的點(diǎn)的性質(zhì),可以重新命名規(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是一個(gè)排列,其中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)中的點(diǎn),其中vk=(k,k,···,k),k=1,2,···,r. 如果有NH(v) 的點(diǎn)x未命名,其中H=HPK(n1,n2,···,nr),n1,n2,···,nr≥r≥3,則可以任意找一點(diǎn)v∈H,根據(jù)H-N?(v)中的點(diǎn)的命名規(guī)則命名,即可以根據(jù)命名規(guī)則3.1和3.2命名.對于N(v)中點(diǎn)的命名可以根據(jù)N?(v)的點(diǎn)命名,只須設(shè)v=(0,0,···,0),所以N(v)的點(diǎn)的命名規(guī)則也被確定.

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

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

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

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

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

R2：a1,a2,···,al是一個(gè)序列,其中 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確定的點(diǎn)x一定是屬于.如果不增加此條件,根據(jù)圖G的點(diǎn)的命名的唯一性原則,只能確定中的點(diǎn)x,增加此條件后在找一點(diǎn)x?,而點(diǎn)x?可以分別在H1與H2重新命名.

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

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

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

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

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

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

R2：a1,a2,···,al是一個(gè)序列,其中 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),且,由上面的結(jié)論,可設(shè)k=r,則可以得到式子(3.3)的最后一個(gè)式子命名規(guī)則.

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

R2：a1,a2,···,ar-1是一個(gè)序列,其中 {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中的所有的點(diǎn)被Hr與N?(vk)點(diǎn)完全決定,可以命名為V(G)={ (x1,x2,···,xr)| 0≤xi≤ni},G中的兩點(diǎn)x=(x1,x2,···,xr) 和y=(y1,y2,···,yr) 彼此不鄰接當(dāng)且僅當(dāng)xiyi,i=1,2,···,r.

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

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

4 任意維超平面完備殘差圖的一個(gè)重要的性質(zhì)

這一節(jié)主要是討論任意維超平面完備殘差圖的結(jié)構(gòu),主要有下面的結(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.

為了證明此定理,先定義有關(guān)超平面的點(diǎn)獨(dú)立集的坐標(biāo)變換.

定義4.1如果H=HPK(n1,n2,···,nr),V(H)={ (x1,x2,···,xr)| 1≤xi≤ni,i=1,2,···,r},假設(shè)獨(dú)立集S1={v1,v2,···,vr,v0} 與S2={u1,u2,···,ur,u0},且S1與S2都是(r+1)-獨(dú)立集.S2與S1坐標(biāo)變換定義如下,如果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,存在一個(gè) (r+1)- 獨(dú)立集{u1,u2,···,ur,u},可以和任何一個(gè) (r+1)-獨(dú)立集 {v1,v2,···,vr,v}進(jìn)行坐標(biāo)變換.

下面證明定理4.1.

設(shè)v0,v1,···,vr是圖G中的r+1 獨(dú)立集. 若Hi=G-N?(vi)(n1,n2,···,nr),i=0,1,···,r. 設(shè)G1=＜H0∪H1∪H2∪···∪Hr＞,假設(shè)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),因?yàn)镚1-N?(vi)=HiHPK(n1,n2,···,nr),則有

以及

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

如果G1=G,再根據(jù)定理3.2知,G是最小階的HPK(n1,n2,···,nr)-殘差圖.如果G1/G,設(shè)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鄰接的.因?yàn)镠0=G-N?(v0),所以有{v1,v2,···,vr}?V(H0),由條件可知v∈H0以及{v1,v2,···,vr,v}是H0的(r+1)-獨(dú)立集,且v也是與任意的w∈W鄰接的,若不然,v不與w?∈W鄰接,則有以及{v0,v1,···,vr}?V(H)是H(r+1)-獨(dú)立集,因此存在w?∈H,即,這與引理3.2矛盾,故有W?N?(v).

因?yàn)閚1,n2,···,nr≥r+2 ≥ 5,因此存在兩點(diǎn)u,v∈H0,使得 {v1,v2,···,vr,u,v}?V(H)是(r+2)-獨(dú)立集,則W?N?(u)∩N?(v).現(xiàn)在假設(shè)是(r+2)-獨(dú)立集,則H0中存在另一點(diǎn){v1,v2,···,vr,u,v}與之進(jìn)行坐標(biāo)變換.根據(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).又因?yàn)槿我鈝∈W,則有V(G1)?N?(w).設(shè)＜W＞=F,則有G=G1+F以及

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

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

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

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

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

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

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

引理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-獨(dú)立集,則有

證當(dāng)k≥r+1,由引理3.3可知

則上面不等式成立.下面假設(shè)1≤k≤r,則存在v∈G和u∈H,且有{v1,v2,···,vk,v}{u1,u2,···,uk,u}分別是G和H中(k+1)-獨(dú)立集.設(shè)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-獨(dú)立集,且有

因?yàn)镚11(n1,n2,···,nr),由引理 3.4 知

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

引理5.4假設(shè)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-獨(dú)立集,則有

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

引理5.5假設(shè)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-獨(dú)立集,則有

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

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

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

利用歸納假設(shè)有

定理5.2假設(shè)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).

證設(shè)G是m-HPK(n1,n2,···,nr)-殘差圖,H=HPK(n1+m,n2+m,···,nr+m),n1,n2,···,nr≥r≥3,ν(G)=ν(H).當(dāng)m=1 時(shí),由定理 3.2 可知,(n1+1,n2+1,···,nr+1).利用數(shù)學(xué)歸納法,假設(shè)m-1≥1成立.對于m,存在點(diǎn)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ù)歸納假設(shè)有G1(n1+m-1,n2+m-1,···,nr+m-1).由于v是G中任意一點(diǎn),根據(jù)定義2.2知,G是最小階的HPK(n1+m-1,n2+m-1,···,nr+m-1)-殘差圖,設(shè)=ni+m-1≥ni≥r≥ 3,i=1,2,···,r,由定理 3.2 可知(n1+m,n2+m,···,nr+m). 證畢.

[2]楊世輝,段輝明.奇階完備殘差圖[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),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].運(yùn)籌學(xué)學(xué)報(bào),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]段輝明,曾波,李永紅.關(guān)于m-HPK(n1,n2,n3,n4)-殘差圖[J].數(shù)學(xué)雜志,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

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

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