笛卡爾乘積圖Cm×Cn的符號邊domatic數

董啟啟, 陳忠，李向軍 (長江大學信息與數學學院，湖北 荊州 434023)

譚來軍 (中國石油測井有限公司技術中心，陜西 西安 710077)

記無向圖G=(V,E)，V和E分別是圖G的頂點集和邊集，NG(e)表示圖G中與邊e相鄰邊的集合，NG[e]=NG(e)∪{e}，Cn表示階為n的圈。笛卡爾乘積圖Cm×Cn，其頂點集是V(Cm)×V(Cn)，對x1，y1∈V(Cm)，x2,y2∈V(Cn)，頂點(x1，x2)與(y1,y2)相鄰當且僅當x1=y1且x2y2∈E(Cn)或x2=y2且x1y1∈E(Cm)。下面筆者考慮Cm×Cn的符號邊domatic數，未說明的符號及術語詳見文獻[1]。

李金強等[4] 確定了笛卡爾乘積圖K2×Cn及C3×Cn的符號邊domatic數。對于Cm×Cn(n≥m≥4)的符號邊domatic數，下面筆者給出其上界及下界。

1 Cm×Cn的符號邊domatic數上界

引理1[3] 圖G的符號邊domatic數是一個奇數。

引理2[3] 令δ′(G)=min{|NG[e]|:e∈E(G)}，則有：

考慮笛卡爾乘積圖G=Cm×Cn，為敘述方便，將其頂點看作m×n點陣，記為{xi,j:i∈{0,1,…,m-1},j∈{0,1,…,n-1}}。Cm、Cn分別為第二角標和第一角標相同的點導出子圖，第一角標和第二角標的加減法分別為模m和模n運算。

證明令G=Cm×Cn，則：

δ′(G)=min{|NG[e]|:e∈E(G)}=7

因此，對任意邊e0，任意f∈F，滿足：

(1)

下面對其中一個f進行分析。令E1為所有滿足f(e)=-1的邊，G1為E1在G=Cm×Cn中的導出子圖，即G1=(V(G),E1)。下面分析導出子圖G1的結構特征。

圖1 斷言2示意圖

斷言1G1不含度為4的頂點。

若含度為4的頂點，則對度為4的頂點關聯的邊e0而言有：

與式(1)矛盾。

斷言2G1不含度為3的頂點，不含度為0的頂點。

根據對稱性，不妨令xi,j+1為度為3的頂點，且該頂點在G1與頂點xi,j,xi,j+2和xi-1,j+1相鄰(見圖1)。由定義1知：

則xi+1,j+1為度為0的頂點，xi,j為度為1的頂點，從而xi+1,j為度為2的頂點。因此有：

與式(1)矛盾。

假設存在u為度為0的頂點，u與v在G中相鄰，對邊uv來說，由于：

則v是度為3的頂點，矛盾。

斷言3G1不含度為1的頂點。

設u為度為1的頂點，u與v在G1中相鄰。根據斷言1和斷言2，v為度為1的頂點或者度為2的頂點，這樣對邊uv有：

與式(1)矛盾。

綜上，G1中所有頂點為度為2的頂點，從而G1為若干圈的并。令e0為非圈上邊，則有：

與式(1)矛盾。故G1不存在，所以d≠7，結合引理1，定理1得證。

2 Cm×Cn的符號邊domatic數下界

下面筆者通過構造符號邊控制集給出Cm×Cn的符號邊domatic數的下界，從而給出Cm×Cn的符號邊domatic數的取值范圍。

證明令:

x2i,2jx2i+1,2j,x2i+1,2jx2i+2,2j,x2i+1,2j+1x2i+2,2j+1}

Ri={

x2i,0x2i,n-1,x2i+1,n-1x2i+2,n-1}

1)若m,n均為偶數，對t=1,2,3，構造函數ft：

2)若m+n為奇數，即m與n奇偶性相異。由于Cm×Cn?Cn×Cm，不妨設m為偶數，n為奇數，構造f1,f2,f3如下：

3)若m,n均為奇數，構造f1,f2,f3如下：

上述3種情況的示意圖分別如圖2～圖4所示。

注：黑線、藍線、紅虛線分別代表f1,f2,f3取值-1，下同。圖2 情形1)示意圖

圖3 情形2)示意圖

圖4 情形3)示意圖

3 結語

考慮Cm×Cn的符號邊domatic數，給出其取值上下界，得到其符號邊domatic數為3 或者5，其確切符號邊domatic數的確定是下一步研究的問題。

[參考文獻]

[1]Bondy J A, Murty U S R.Graph theory with applications[M].London: Macmillan, 1976.

[2]Xu B.On signed edge domination numbers of graphs[J].Discrete Mathematics, 2001, 239(1-3): 179～189.

[3]Li X J, Xu J M.The signed edge-domatic number of a graph[J].Graphs and Combinatorics, 2013，29(6)：1881～1890.

[4]李金強，朱智博，成純波，等.笛卡爾乘積圖K2×Cn及C3×Cn的符號邊domatic數[J].長江大學學報(自科版), 2015, 12(7): 8～10.