李金強(qiáng)，朱智博，成純波，姚萍萍，李向軍 （長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北荊州434023）

記G＝（V（G），E（G））為一個圖，V（G）和E（G）分別是G的頂點集和邊集。若e∈E（G），用NG（e）表示G中與e相鄰的邊的集合，稱為e的邊鄰域，稱NG［e］＝NG（e）∪｛e｝為e的閉邊鄰域。當(dāng)所指的圖G很明確時，在記號中可以省略下標(biāo)。Kn，Cn分別表示階為n的完全圖和圈。G×H表示G和H的笛卡爾乘積，其頂點集是V（G）×V（H），對x，y∈V（G），a，b∈V（H），（x，a）與（y，b）相鄰當(dāng)且僅當(dāng)x＝y(tǒng)且ab∈E（H）或a＝b且xy∈E（G）。這里，筆者只考慮有限簡單（無環(huán)，無平行邊）無向圖，未說明的符號和術(shù)語同文獻(xiàn)［1］。文獻(xiàn)［2］中引入了圖的符號邊控制數(shù)的概念。

定義1［2］設(shè)G是一個非空圖，如果存在一個雙值函數(shù)f：E（G）→｛1，－1｝，使得對任意e∈E（G）均有≥1成立，則稱f為圖G的一個符號邊控制函數(shù)。圖G的符號邊控制數(shù)定義為：

domatic數(shù)通過控制集的數(shù)目來刻畫。對V（G）的一個劃分，若所有類都是一個控制集合，這個劃分稱為G的domatic劃分，domatic劃分的最大類數(shù)為domatic數(shù)［3］。Volkman L與Zelinka B［4］引入符號domatic數(shù)（ds（G）），是一個針對圖頂點的符號控制概念，Li等［5］類似考慮針對邊的符號控制問題，定義符號邊domatic數(shù)。

定義2［5］G是一個非空圖，G的符號邊控制函數(shù)集合為｛f1，f2，…，fd｝，若滿足對任意e∈E（G），≤1，則稱為符號邊控制集。圖G的符號邊domatic數(shù)為：

即G的最大符號邊控制集含有符號邊控制函數(shù)的個數(shù)為G的符號邊domatic數(shù)。

對任意給定的圖，確定其符號邊domatic數(shù)是相當(dāng)困難的，轉(zhuǎn)而計算某些特殊圖的符號邊domatic數(shù)是很有價值的。Li等［5］確定了圈、星、扇、完全圖及笛卡爾乘積圖Pm×Pn的符號邊domatic數(shù)。下面，筆者研究確定笛卡爾乘積圖K2×Cn，C3×Cn的符號邊domatic數(shù)。

引理1［5］圖G的符號邊domatic數(shù)是一個奇數(shù)。

引理2［5］若γ′s（G）為圖G符號邊控制數(shù)，ε（G）為圖G邊數(shù)，則d′s（G）γ′s（G）≤ε（G）。

引理3［5］令δ′（G）＝min，則d′s（G）≤δ′（G）。

1 笛卡爾乘積圖K2×Cn的符號邊domatic數(shù)

考慮圖K2×Cn，其頂點可看作2×n點陣，記為 ｛xij：i∈ ｛0，1｝，j∈ ｛0，1，…，n－1｝｝。

定理1 對圖K2×Cn，d′s（K2×Cn）為其符號邊domatic數(shù)，則d′s（K2×Cn）≤3。

證明 設(shè)d＝d′s（K2×Cn），由于δ′（K2×Cn）＝min＝5，根據(jù)引理3可知d≤5。

假設(shè)d＝5，｛f1，f2，f3，…，fd｝為對應(yīng)的符號邊控制集，e0為任意邊，則：

故任意邊e0滿足：

根據(jù)對稱性，不妨設(shè)f（x0，0x0，1）＝－1。若要使＝1對邊e0＝x0，0x0，1成立，則存在唯一e′∈N［e0］使得f（e′）＝－1，由對稱性，考慮f（x0，1x1，1）＝－1，f（x0，1x0，2）＝－1這2種情況。

若f（x0，1x1，1）＝－ 1，則f（x0，1x0，2）＝f（x0，2x0，3）＝f（x0，2x1，2）＝f（x1，1，x1，2）＝1，令e0＝x0，2x1，2， 則與＝1相矛盾（見圖1（a））。

若f（x0，1x0，2）＝－ 1， 則f（x0，1x1，1）＝f（x0，2x1，2）＝f（x1，0x1，1）＝f（x1，1，x1，2）＝1，令e0＝x1，1x1，2，則＝1相矛盾（見圖1（b）），即證d≤4。

圖1 定理1證明示意圖

再結(jié)合引理1知，定理1得證。

下面用［a］表示不超過a的最大整數(shù)，［a］U表示不小于a的最小整數(shù)，腳標(biāo)加法都為取modn的運算，示意圖中粗邊取值為－1，細(xì)邊取值為1。

定理2 對任意正整數(shù)n≥3，d′s（K2×Cn）＝3。

證明 當(dāng)n≥3時，令：

f1，f2，f3如圖2所示，容易驗證f1，f2，f3都是K2×Cn的符號邊控制函數(shù)，且對任意e∈E（K2×Cn），（e）＝1，故 ｛f1，f2，f3｝是K2×Cn的符號邊控制集，從而d′s（K2×Cn）≥3。結(jié)合定理1，可得d′s（K2×Cn）＝3。

2 笛卡爾乘積圖C3×Cn的符號邊domatic數(shù)

圖2 K2×Cn符號邊控制函數(shù)示意圖（n為奇數(shù)）

考慮圖C3×Cn，其頂點可看作3×n點陣，記為。第一腳標(biāo)相同的點導(dǎo)出圖為Cn，第二腳標(biāo)相同的點導(dǎo)出圖為C3。文獻(xiàn)［6］中確定了C3×Cn的符號邊控制數(shù)。

引理4［6］對于任意正整數(shù)n（n≥3），都有：

定理3 對任意正整數(shù)n（n≥3），都有：

證明 當(dāng)n≡0（mod 5）時，對j＝0，1，2，…，；i＝1，2，3，4，5，令W（i，j）是C3×Cn中 以為頂點的K1，3子圖，其中x1，5j＋i是W（i，j）的3度點。記：

是C3×Cn中的一條路。令E（i，j）＝E（W（i，j））∪E（P（i，j））。

根據(jù)引理2和引理4知，d′s（C3×Cn）≤5。對i＝1，2，3，4，5，令：

容易驗證f1、f2、f3、f4、f5都是C3×Cn的符號邊控制函數(shù)，且對任意e∈E（C3×Cn）＝1，故｛f1，f2，f3，f4，f5｝是C3×Cn的符號邊控制集，故d′s（C3×Cn）＝5。

當(dāng)n＝1，2，3，4（mod 5）時，根據(jù)引理4，結(jié)合引理2知，d′s（C3×Cn）≤3，對i＝1，2，3，令：

容易驗證f1、f2、f3都是C3×Cn的符號邊控制函數(shù)，且對任意e∈E（C3×Cn）＝1，故｛f1，f2，f3｝是C3×Cn的符號邊控制集，故d′s（C3×Cn）＝3。

綜上，定理3得證。

3 結(jié)語

研究確定了笛卡爾乘積圖K2×Cn及C3×Cn的符號邊domatic數(shù)，對任意正整數(shù)n≥3，圖K2×Cn符號邊domatic數(shù)d′s（K2×Cn）＝3，圖C3×Cn符號邊domatic數(shù)d′s（C3×Cn）＝。對一般的正整數(shù)m（m≥4），確定Cm×Cn符號邊domatic數(shù)是值得進(jìn)一步研究的問題。

［1］Bondy J A，Murty U S R.Graph theory with applications ［M］.London：Macmillan，1976.

［2］Xu B G.On signed edge domination numbers of graphs ［J］.Discrete Math，2001，239：179～198.

［3］Cockayne E J，Hedetniemi S T.Towards a theory of domination in graphs ［J］.Networks，1977，7：247～261.

［4］Volkmann L，Zelinka B.Signed domatic number of a graph ［J］.Discrete Applied Math，2005，150：261～267.

［5］Li X J，Xu J M.The signed edge－domatic number of a graph ［J］.Graphs and Combinatorics，2013，29（6）：1881～1890.

［6］李向軍，袁旭東 .C3×Cn的符號邊控制數(shù) ［J］.廣西師范大學(xué)學(xué)報（自然科學(xué)版），2006（1）：49～52.