關(guān)于冠圖與queens-圖的若干結(jié)果

鄧毅雄

（華東交通大學(xué)軟件學(xué)院，江西南昌330013）

Deng Yixiong

（School of Software，East China Jiaotong University，Nanchang 330013，China）

本文討論的圖都是簡單無向圖，文中未加說明的術(shù)語和符號參閱文獻(xiàn)[1][2]。

L.W.Beineke等[3]引入了queens-圖的概念，并且證明了在一定條件下的完全塊圖、樹、Kn×Pm、Pn×Pm，C2n×Pm等是queens-圖，并解決了二部及多部圖的問題。到目前，這方面的研究成果比較少，另外的結(jié)果有:證明了θ-圖是queens-圖，并給出了B(m，n，r)圖是queens-圖的充分必要條件[4]；討論了queens-圖的構(gòu)造問題，也得到了一些queens-圖[5]。

1 定義及引理

設(shè)A是（0，1）-矩陣。一個圖稱為A的queens-圖，記為Q(A)，如果這個圖的點與A中的1相對應(yīng)，圖的兩個點鄰接當(dāng)且僅當(dāng)A中對應(yīng)的1同在某線或?qū)蔷€上。（這里的“線”是指矩陣的行或列。）

我們稱一個圖G是queens-圖，如果存在某（0，1）-矩陣A，使得G是A的queens-圖。注意到，給出一個（0，1）-矩陣，很容易獲得其對應(yīng)的queens-圖，但是，給出一個圖G，判斷它是否為queens-圖，卻常常不是一件容易的事情。所以，這方面研究的一個主要問題是:哪些圖是queens-圖？

文獻(xiàn)[3]給出了下面兩個引理:

引理1[3]圖G是queens-圖當(dāng)且僅當(dāng)它的點可以對應(yīng)坐標(biāo)(i，j)，并且兩個不同的點(i，j)和(k，l)鄰接當(dāng)且僅當(dāng)1i=k，或 2j=l，或 3i+j=k+l，或4i-j=k-l。

引理2[3]如果圖G是queens-圖，那么G不包含導(dǎo)出子圖K1，5。

引理1給出的4個條件，依次分別指的是兩個點在同一行、列、主對角線和斜對角線上，用于queens-圖的驗證和判斷。引理2給出的queens-圖的必要條件是基于矩陣只有4條“線”，它在判斷一個圖不是queens-圖時，非常有用。

確定一個圖G是否為queens-圖，就是構(gòu)造對應(yīng)的（0，1）-矩陣A，也就是確定1的位置，或者說是1的坐標(biāo)(i，j)，而1的位置就是圖G的點的位置，所以，圖G是否為queens-圖，就是看能否構(gòu)造滿足定義或者說滿足引理1要求的點的坐標(biāo)(i，j)。

另外，如果queens-圖G對應(yīng)的（0，1）-矩陣為A，那么A的轉(zhuǎn)置矩陣AT對應(yīng)的queens-圖仍然是G。

懸掛邊是度為1的點所關(guān)聯(lián)的邊。我們注意到，去掉一個queens-圖的懸掛點，就相當(dāng)于在其對應(yīng)的（0，1）-矩陣中把該懸掛點所對應(yīng)的元素“1”改為元素“0”，而這不會影響其它的元素。特別由于它是懸掛點，這個元素的改變，不會影響其它點的結(jié)構(gòu)關(guān)系，所以我們有:

引理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)。

當(dāng)G=Kn時，稱Ir（Kn）為完全r-冠圖；而當(dāng)G=Cn時，稱Ir(Cn)為r-皇冠圖，記為Cn⊙rK1。

2 主要結(jié)論

根據(jù)引理3，易于得到:

定理1 如果冠圖Ir(G)是queens-圖，那么圖G也是queens-圖。

由定理1引出問題:如果圖G也是queens-圖，那么冠圖Ir(G)是queens-圖嗎？顯然，一般情況下并不是這樣的，這個命題一般是不成立的。下面的定理2給出了一個必要條件，定理3和定理4給出了兩類滿足這個問題的圖。

所謂零圖是沒有邊的圖。注意到，當(dāng)r≥4時，如果G不是零圖，冠圖Ir(G)含有導(dǎo)出子圖K1，5，結(jié)合引理2，有

定理2 當(dāng)G不是零圖時，如果冠圖Ir(G)是queens-圖，那么r≤3。

定理3完全r-冠圖I（rKn）是queens-圖當(dāng)且僅當(dāng)r=1，2，3。

首先，r≤3是Ir(G)是queens-圖的必要性由定理1獲知。其次，我們證明當(dāng)r=3時，完全r-冠圖Ir(Kn)是queens-圖。事實上?

，令各點的坐標(biāo)分別為

首先，ui(i=0，1，…，n-1)的橫坐標(biāo)均為0，他們相互鄰接構(gòu)成Kn。

注意到，對ui與wi0，它們的橫坐標(biāo)與縱坐標(biāo)之和為0+(3i+1)=(4i+1)+(-i-1)，則ui與wi0鄰接；對ui與wi1，它們的縱坐標(biāo)均為 3i，則ui與wi1鄰接；對ui與wi2，它們的橫坐標(biāo)減縱坐標(biāo)為0-3i=(9n+2i-5)-(9n+5i-5)，則ui與wi2鄰接。

另外，注意到0≤i≤n-1，wi0、wi1、wi2之間橫坐標(biāo)、縱坐標(biāo)，以及橫坐標(biāo)與縱坐標(biāo)之和分別均不相同，并且wi0、wi1、wi2的橫坐標(biāo)減縱坐標(biāo)分別為5i+2、5n+i-2、-3i(i=0，1，…，n-1)，這3組數(shù)據(jù)之間相互不可能存在相等的情況，根據(jù)引理1，wi0、wi1、wi2互不鄰接；很容易驗證，當(dāng)j≠i時，wi0、wi1、wi2與uj也均不鄰接。

綜上，完全 3-冠圖I3(Kn)是如上坐標(biāo)對應(yīng)的queens-圖。

最后，由引理3，我們從完全3-冠圖I3(Kn)是queens-圖，立即得到完全2-冠圖I2(Kn)和完全1-冠圖I1(Kn)都是queens-圖。

由引理3和定理3，得

推論1 當(dāng)r≤3時，完全r-弱冠圖是queens-圖。

定理4 皇冠圖Cn⊙rK1是queens-圖當(dāng)且僅當(dāng)r=1或r=2。

證明 首先我們注意到，當(dāng)r＞2時，Cn⊙rK1含有導(dǎo)出子圖K1，5，根據(jù)引理2，Cn⊙rK1不是queens-圖。類似于定理3的證明，我們只要證明Cn⊙rK1是queens-圖即可。

設(shè)V(Cn)={u0，u1，…，un-1}，與ui(i=0，1，…，n-1)鄰接的2個懸掛點為wij(j=0，1)，而Cn⊙2K1的各點的坐標(biāo)定義如下:

下面驗證情形1給出的坐標(biāo)按照定義得到的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的橫坐標(biāo)均為0，所以u0與u2n-1鄰接，故ui(i=0，1，…，2k-1)恰構(gòu)成圈Cn。

由于ui和wi0(i=0，1，…，2k-1)的縱坐標(biāo)對應(yīng)分別相同，所以ui與wi0鄰接；且容易驗證，當(dāng)i≠j(i、j=0，1，…，2k-1)時，ui與wj0不鄰接。

注意到，由wi1，ui(i=0，1，...，2k-3)的橫坐標(biāo)與縱坐標(biāo)之和相同，即 (-4k-i+3)+(4k+3i-3)=2i，所以wi1與ui鄰接；而u2k-2與w2k-2，1各自的橫坐標(biāo)與縱坐標(biāo)之差均為 -2k+2，u2k-1與w2k-1，1各自的橫坐標(biāo)與縱坐標(biāo)之差均為 -4k-4，所以u2k-2與w2k-2，1，u2k-1與w2k-1，1分別鄰接；且容易驗證，當(dāng)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 當(dāng)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]鄧毅雄，熊金泉，等.關(guān)于Queens-圖的若干結(jié)果[J].華東交通大學(xué)學(xué)報，2003，20（1）:82-85.

[5]鄧毅雄，周尚超，等.Queens-圖的構(gòu)造[J].華東交通大學(xué)學(xué)報，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)美標(biāo)號[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26（6）:454-457.

[8]斯琴巴特爾，等.關(guān)于皇冠Qn調(diào)和的相關(guān)性質(zhì)[J].大學(xué)數(shù)學(xué)，2010，26（12）:71-75.