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

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

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

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

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

1 Cm×Cn的符號邊domatic數(shù)上界

引理1[3] 圖G的符號邊domatic數(shù)是一個(gè)奇數(shù)。

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

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

證明令G=Cm×Cn，則：

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

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

(1)

下面對其中一個(gè)f進(jìn)行分析。令E1為所有滿足f(e)=-1的邊，G1為E1在G=Cm×Cn中的導(dǎo)出子圖，即G1=(V(G),E1)。下面分析導(dǎo)出子圖G1的結(jié)構(gòu)特征。

圖1 斷言2示意圖

斷言1G1不含度為4的頂點(diǎn)。

若含度為4的頂點(diǎn)，則對度為4的頂點(diǎn)關(guān)聯(lián)的邊e0而言有：

與式(1)矛盾。

斷言2G1不含度為3的頂點(diǎn)，不含度為0的頂點(diǎn)。

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

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

與式(1)矛盾。

假設(shè)存在u為度為0的頂點(diǎn)，u與v在G中相鄰，對邊uv來說，由于：

則v是度為3的頂點(diǎn)，矛盾。

斷言3G1不含度為1的頂點(diǎn)。

設(shè)u為度為1的頂點(diǎn)，u與v在G1中相鄰。根據(jù)斷言1和斷言2，v為度為1的頂點(diǎn)或者度為2的頂點(diǎn)，這樣對邊uv有：

與式(1)矛盾。

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

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

2 Cm×Cn的符號邊domatic數(shù)下界

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

證明令:

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均為偶數(shù)，對t=1,2,3，構(gòu)造函數(shù)ft：

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

3)若m,n均為奇數(shù)，構(gòu)造f1,f2,f3如下：

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

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

圖3 情形2)示意圖

圖4 情形3)示意圖

3 結(jié)語

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

[參考文獻(xiàn)]

[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]李金強(qiáng)，朱智博，成純波，等.笛卡爾乘積圖K2×Cn及C3×Cn的符號邊domatic數(shù)[J].長江大學(xué)學(xué)報(bào)(自科版), 2015, 12(7): 8～10.