鄧毅雄
(華東交通大學軟件學院,江西南昌330013)
Deng Yixiong
(School of Software,East China Jiaotong University,Nanchang 330013,China)
本文討論的圖都是簡單無向圖,文中未加說明的術語和符號參閱文獻[1][2]。
L.W.Beineke等[3]引入了queens-圖的概念,并且證明了在一定條件下的完全塊圖、樹、Kn×Pm、Pn×Pm,C2n×Pm等是queens-圖,并解決了二部及多部圖的問題。到目前,這方面的研究成果比較少,另外的結果有:證明了θ-圖是queens-圖,并給出了B(m,n,r)圖是queens-圖的充分必要條件[4];討論了queens-圖的構造問題,也得到了一些queens-圖[5]。
設A是(0,1)-矩陣。一個圖稱為A的queens-圖,記為Q(A),如果這個圖的點與A中的1相對應,圖的兩個點鄰接當且僅當A中對應的1同在某線或?qū)蔷€上。(這里的“線”是指矩陣的行或列。)
我們稱一個圖G是queens-圖,如果存在某(0,1)-矩陣A,使得G是A的queens-圖。注意到,給出一個(0,1)-矩陣,很容易獲得其對應的queens-圖,但是,給出一個圖G,判斷它是否為queens-圖,卻常常不是一件容易的事情。所以,這方面研究的一個主要問題是:哪些圖是queens-圖?
文獻[3]給出了下面兩個引理:
引理1[3]圖G是queens-圖當且僅當它的點可以對應坐標(i,j),并且兩個不同的點(i,j)和(k,l)鄰接當且僅當1i=k,或 2j=l,或 3i+j=k+l,或4i-j=k-l。
引理2[3]如果圖G是queens-圖,那么G不包含導出子圖K1,5。
引理1給出的4個條件,依次分別指的是兩個點在同一行、列、主對角線和斜對角線上,用于queens-圖的驗證和判斷。引理2給出的queens-圖的必要條件是基于矩陣只有4條“線”,它在判斷一個圖不是queens-圖時,非常有用。
確定一個圖G是否為queens-圖,就是構造對應的(0,1)-矩陣A,也就是確定1的位置,或者說是1的坐標(i,j),而1的位置就是圖G的點的位置,所以,圖G是否為queens-圖,就是看能否構造滿足定義或者說滿足引理1要求的點的坐標(i,j)。
另外,如果queens-圖G對應的(0,1)-矩陣為A,那么A的轉(zhuǎn)置矩陣AT對應的queens-圖仍然是G。
懸掛邊是度為1的點所關聯(lián)的邊。我們注意到,去掉一個queens-圖的懸掛點,就相當于在其對應的(0,1)-矩陣中把該懸掛點所對應的元素“1”改為元素“0”,而這不會影響其它的元素。特別由于它是懸掛點,這個元素的改變,不會影響其它點的結構關系,所以我們有:
引理3 如果G是queens-圖,那么去掉G的若干懸掛點所得之子圖仍然是queens-圖。易知:
引理4 完全圖Kn、圈Cn是queens-圖。
定義 圖G的r-正則冠圖Ir(G)是指在G的每個點上都粘接r條懸掛邊所得之圖,而圖G的r-弱冠圖Ir(G)是指在G的每個點上至多粘接r條懸掛邊所得之圖。圖G的1-正則冠圖稱為王冠圖,記為I(G)。
當G=Kn時,稱Ir(Kn)為完全r-冠圖;而當G=Cn時,稱Ir(Cn)為r-皇冠圖,記為Cn⊙rK1。
根據(jù)引理3,易于得到:
定理1 如果冠圖Ir(G)是queens-圖,那么圖G也是queens-圖。
由定理1引出問題:如果圖G也是queens-圖,那么冠圖Ir(G)是queens-圖嗎?顯然,一般情況下并不是這樣的,這個命題一般是不成立的。下面的定理2給出了一個必要條件,定理3和定理4給出了兩類滿足這個問題的圖。
所謂零圖是沒有邊的圖。注意到,當r≥4時,如果G不是零圖,冠圖Ir(G)含有導出子圖K1,5,結合引理2,有
定理2 當G不是零圖時,如果冠圖Ir(G)是queens-圖,那么r≤3。
定理3完全r-冠圖I(rKn)是queens-圖當且僅當r=1,2,3。
首先,r≤3是Ir(G)是queens-圖的必要性由定理1獲知。其次,我們證明當r=3時,完全r-冠圖Ir(Kn)是queens-圖。事實上?
,令各點的坐標分別為
首先,ui(i=0,1,…,n-1)的橫坐標均為0,他們相互鄰接構成Kn。
注意到,對ui與wi0,它們的橫坐標與縱坐標之和為0+(3i+1)=(4i+1)+(-i-1),則ui與wi0鄰接;對ui與wi1,它們的縱坐標均為 3i,則ui與wi1鄰接;對ui與wi2,它們的橫坐標減縱坐標為0-3i=(9n+2i-5)-(9n+5i-5),則ui與wi2鄰接。
另外,注意到0≤i≤n-1,wi0、wi1、wi2之間橫坐標、縱坐標,以及橫坐標與縱坐標之和分別均不相同,并且wi0、wi1、wi2的橫坐標減縱坐標分別為5i+2、5n+i-2、-3i(i=0,1,…,n-1),這3組數(shù)據(jù)之間相互不可能存在相等的情況,根據(jù)引理1,wi0、wi1、wi2互不鄰接;很容易驗證,當j≠i時,wi0、wi1、wi2與uj也均不鄰接。
綜上,完全 3-冠圖I3(Kn)是如上坐標對應的queens-圖。
最后,由引理3,我們從完全3-冠圖I3(Kn)是queens-圖,立即得到完全2-冠圖I2(Kn)和完全1-冠圖I1(Kn)都是queens-圖。
由引理3和定理3,得
推論1 當r≤3時,完全r-弱冠圖是queens-圖。
定理4 皇冠圖Cn⊙rK1是queens-圖當且僅當r=1或r=2。
證明 首先我們注意到,當r>2時,Cn⊙rK1含有導出子圖K1,5,根據(jù)引理2,Cn⊙rK1不是queens-圖。類似于定理3的證明,我們只要證明Cn⊙rK1是queens-圖即可。
設V(Cn)={u0,u1,…,un-1},與ui(i=0,1,…,n-1)鄰接的2個懸掛點為wij(j=0,1),而Cn⊙2K1的各點的坐標定義如下:
下面驗證情形1給出的坐標按照定義得到的queens-圖恰好就是圖Cn⊙2K1。
首先,對于u2i與u2i+1(i=0,1,...,k-2),由于i-3i=(i+1)-(3i+1),所以點u2i與u2i+1(i=0,1,...,k-2)鄰接;由于(k-1)+(3k-3)=0+(4k-4),所以u2k-2與u2k-1鄰接;而u0與u2n-1的橫坐標均為0,所以u0與u2n-1鄰接,故ui(i=0,1,…,2k-1)恰構成圈Cn。
由于ui和wi0(i=0,1,…,2k-1)的縱坐標對應分別相同,所以ui與wi0鄰接;且容易驗證,當i≠j(i、j=0,1,…,2k-1)時,ui與wj0不鄰接。
注意到,由wi1,ui(i=0,1,...,2k-3)的橫坐標與縱坐標之和相同,即 (-4k-i+3)+(4k+3i-3)=2i,所以wi1與ui鄰接;而u2k-2與w2k-2,1各自的橫坐標與縱坐標之差均為 -2k+2,u2k-1與w2k-1,1各自的橫坐標與縱坐標之差均為 -4k-4,所以u2k-2與w2k-2,1,u2k-1與w2k-1,1分別鄰接;且容易驗證,當i≠j(i、j=0,1,…,2k-1)時,ui與wj1不鄰接。
同樣根據(jù)引理1,可以證明wi0、wi1(i=0,1,...,2k-1)均不相互鄰接。
類似可以驗證情形2。
綜上,Cn⊙2K1是queens-圖。
由引理3和定理4,得:
推論2 當r=1或r=2,皇冠圖Cn⊙rK1的弱冠圖是queens-圖。
[1]HARARY F.Graph theory[M].NewYork:Addison Wesley,Publishing Company,1969:1-274.
[2]BONDY J A,MURTY U S R.Graph theory with application[M].NewYork:Elsevier Science Publishing Company,1976:1-65.
[3]BEINEKE LW,BROERE I,HENNING MA.Queens graphs[J].Discrete Mathematics,1999,206(1-3):63-75.
[4]鄧毅雄,熊金泉,等.關于Queens-圖的若干結果[J].華東交通大學學報,2003,20(1):82-85.
[5]鄧毅雄,周尚超,等.Queens-圖的構造[J].華東交通大學學報,2004,21(4):119-121.
[6] GALLIAN J A.A survey:recent results,conjectures,and open problems in labeling graphs[J].Graph Theory,1989,13(4):491-504.
[7]胡紅亮.圖Cn及其r-冠的新的優(yōu)美標號[J].純粹數(shù)學與應用數(shù)學,2010,26(6):454-457.
[8]斯琴巴特爾,等.關于皇冠Qn調(diào)和的相關性質(zhì)[J].大學數(shù)學,2010,26(12):71-75.