圈与圈克罗内克乘积图罗马{3}-控制

高 红， 黄 佳 欢， 刘 仁 邦， 杨 元 生

(1.大连海事大学 理学院，辽宁 大连 116026；2.大连理工大学 计算机科学与技术学院，辽宁 大连 116024 )

0 引 言

给定图G=(V，E)，V是图G的顶点集合，E是图G的边集合．集合N(v)={u|uv∈E}称为顶点v的开邻域．图G的顶点个数称为阶．顶点v的度dG(v)为N(v)中包含的顶点个数，最大/小度记为Δ(G)/δ(G)．

本文研究圈与圈克罗内克乘积图的罗马{3}-控制数，给出圈与圈克罗内克乘积图罗马{3}-控制数的上界和下界．通过构造可递推的罗马{3}-控制函数可以得到圈与圈克罗内克乘积图罗马{3}-控制数的上界．结合前人给出的一般图罗马{3}-控制数的下界，可以得到圈与圈克罗内克乘积图罗马{3}-控制数的下界．

1 圈与圈克罗内克乘积图Cn×Cm

圈Cn与圈Cm克罗内克乘积图Cn×Cm是一个有mn个顶点的四正则图，其顶点集合和边集合分别为V(Cn×Cm)={vi，j|0≤i≤n-1，0≤j≤m-1}，E(Cn×Cm)={ei，j|ei，j=(vi，jvi-1，j+1)，0≤i≤n-1，0≤j≤m-1}∪{e′i，j|e′i，j=(vi，jvi+1，j+1)，0≤i≤n-1，0≤j≤m-1}，其中下标i和j分别对n和m取模．图1(a)表示图C3×C6，图1(b)表示其上的一个罗马{3}-控制函数，图中的数字表示的是f(vi，j)．

设G=Cn×Cm，f为图G上的罗马{3}-控制函数，则f可表示为

例如：

表示C3×C6上的罗马{3}-控制函数，其图形如图1(b)所示．

(a)C3×C6

2 Cn×Cm罗马{3}-控制数的界

2.1 Cn×Cm罗马{3}-控制数的下界

若G=Cn×Cm，则图G的阶数为mn，最大度Δ(G)=4，由定理1可得下面的推论．

推论1若G=Cn×Cm，当m，n≥3时，则有γ{R3}(G)≥mn/2．

2.2 Cn×Cm罗马{3}-控制数的上界

定理2对于任意的正整数m≥3，G=C3×Cm的罗马{3}-控制数上界为

γ{R3}(C3×Cm)≤9m5;m≡0,1,2,3,4,7,8,9,13,14,19(mod20)9m5+1;m≡5,6,10,11,12,15,16,17,18(mod20)ìîíïïïïïï

证明首先定义一个C3×C20上的罗马{3}-控制函数g(vi，j)(0≤i≤2，0≤j≤19)，

函数g也可以表示为下面更直观的形式：

情况1当m≡0，1，7，14(mod 20)时，构造C3×Cm上的罗马{3}-控制函数为f(vi，j)=g(vi，j mod 20)，图2显示的是C3×C21上的f．

图2 C3×C21上的fFig.2 f on C3×C21

此时，f的权重为

w(f)=m20×36=9m5; m≡0(mod20)m-120×36+2=9m+15=9m5; m≡1(mod20)m-720×36+13=9m+25=9m5; m≡7(mod20)m-1420×36+26=9m+45=9m5; m≡14(mod20)ìîíïïïïïïïïïïïïïï

情况2当m≡2，3，4，5(mod 20)时，构造C3×Cm上的罗马{3}-控制函数f如下：

图3显示的是C3×C24上按照上式定义的罗马{3}-控制函数f．

图3 C3×C24上的fFig.3 f on C3×C24

此时，f的权重为

w(f)=m-220×36+4=9m+25=9m5;m≡2(mod20)m-320×36+6=9m+35=9m5;m≡3(mod20)m-420×36+8=9m+45=9m5;m≡4(mod20)m-520×36+10=9m+55=9m5+1;m≡5(mod20)ìîíïïïïïïïïïïïïïïïï

情况3当m≡8，9，10，15，19(mod 20)时，构造C3×Cm上的罗马{3}-控制函数f如下：

图4(a)显示的是C3×C10上按照上式定义的罗马{3}-控制函数f．

(a)C3×C10上的f

此时，f的权重为

w(f)=m-820×36+13+2=9m+35=9m5; m≡8(mod20)m-920×36+13+4=9m+45=9m5; m≡9(mod20)m-1020×36+13+6=9m+55=9m5+1; m≡10(mod20)m-1520×36+26+2=9m+55=9m5+1; m≡15(mod20)m-1920×36+33+2=9m+45=9m5; m≡19(mod20)ìîíïïïïïïïïïïïïïïïïïïïï

情况4当m≡6，12，13，16，17(mod 20)时，构造C3×Cm上的罗马{3}-控制函数f如下：

图4(b)显示的是C3×C16上按照上式定义的罗马{3}-控制函数f．此时，f的权重为

w(f)=m-620×36+9+3=9m+65=9m5+1; m≡6(mod20)m-1220×36+20+3=9m+75=9m5+1; m≡12(mod20)m-1320×36+21+3=9m+35=9m5; m≡13(mod20)m-1620×36+27+3=9m+65=9m5+1; m≡16(mod20)m-1720×36+27+5=9m+75=9m5+1; m≡17(mod20)ìîíïïïïïïïïïïïïïïïïïïïï

情况5当m≡11，18(mod 20)时，构造C3×Cm上的罗马{3}-控制函数f如下：

图5显示的是C3×C18上按照上式定义的罗马{3}-控制函数f．

图5 C3×C18上的fFig.5 f on C3×C18

此时，f的权重为

w(f)=m-1120×36+18+3=9m+65=9m5+1; m≡11(mod20)m-1820×36+31+3=9m+85=9m5+1; m≡18(mod20)ìîíïïïïïïïï

由情况1～5可知

γ{R3}(C3×Cm)≤w(f)=

9m5;m≡0,1,2,3,4,7,8,9,13,14,19(mod20)9m5+1;m≡5,6,10,11,12,15,16,17,18(mod20)ìîíïïïïïïïï

□

定理3对于任意的正整数m≥4，G=C4×Cm的罗马{3}-控制数上界为

γ{R3}(C4×Cm)≤13m5; m≡0,1,2,4(mod5),m≥513m5+1; m≡3(mod5)或m=4ìîíïïïïïïïï

证明

(a)C4×C4上的f

情况2当m≥5且m≠7时，先定义函数g(vi，j)(0≤i≤3，0≤j≤4)(如图7中前5列)：

然后，构造C4×Cm(m≡0，1，2，3，4(mod 5))上的罗马{3}-控制函数f如下：

图7显示的是C4×C17上按照上式定义的罗马{3}-控制函数f．

图7 C4×C17上的fFig.7 f on C4×C17

此时，f的权重为

w(f)=m5×13=13m5; m≡0(mod5)m-65×13+16=13m+25=13m5; m≡1(mod5)m-125×13+32=13m+45=13m5; m≡2(mod5)m-85×13+22=13m+65=13m5+1; m≡3(mod5)m-95×13+24=13m+35=13m5; m≡4(mod5)ìîíïïïïïïïïïïïïïïïïïï

由情况1和2可知

γ{R3}(C4×Cm)≤w(f)=

13m5; m≡0,1,2,4(mod5),m≥513m5+1; m≡3(mod5)或m=4ìîíïïïïïïïï

□

证明由于圈与圈克罗内克乘积图具有对称性，仅给出n(mod 5)≤m(mod 5)的情况．

情况1当n≡0(mod 5)时，先定义函数g(vi，j)(0≤i≤4，0≤j≤4)如下：

然后，构造Cn×Cm(m≡0，1，2，3，4(mod 5))上的罗马{3}-控制函数f：

图8显示的是C5×C7和C5×C8上按照上式定义的罗马{3}-控制函数f．Cn×Cm中每增加5行或5列就增加一个按照函数g定义的循环块．

此时，f的权重为

(a)C5×C7上的f

情况2当n≡1(mod 5)时，先定义3个函数g1(vi，j)、g2(vi，j)、g3(vi，j)(0≤i≤4，0≤j≤4)如下：

然后，构造Cn×Cm(m≡1，2，3，4(mod 5))上的罗马{3}-控制函数f：

图9显示的是C11×Cm(m=6，7，8，9)上按照上式定义的罗马{3}-控制函数f．

此时，f的权重为

(a)C11×C6上的f

情况3当n≡2(mod 5)时，构造Cn×Cm(m≡2，3，4(mod 5))上的罗马{3}-控制函数f如下：

其中，g1、g3如情况2中的定义．图10显示的是C7×C7、C7×C9和C12×C13上按上式定义的罗马{3}-控制函数f．

此时，f的权重为

(a)C7×C7上的f

情况4当n≡3(mod 5)时，先定义函数g4(vi，j)(0≤i≤4，0≤j≤4)如下：

然后，构造Cn×Cm(m≡3，4(mod 5))上的罗马{3}-控制函数f：

其中，函数g1如情况2中的定义．图11(a)、(b)显示了C13×C8和C13×C9上按照上式定义的罗马{3}-控制函数f．

此时，f的权重为

情况5当n≡4(mod 5)时，先定义函数g5(vi，j)(0≤i≤4，0≤j≤4)如下：

然后，构造Cn×Cm(m≡4(mod 5))上的罗马{3}-控制函数f：

图11(c)显示的是C9×C9上按照上式定义的罗马{3}-控制函数f．

此时，f的权重为

14+11=

(a)C13×C8上的f

□

由推论1和定理2～4，可以得到

定理5对于任意的正整数m，n≥3，G=Cn×Cm的罗马{3}-控制数的界为

3m2≤γ{R3}(G)≤9m5+1; n=3,m≥32m≤γ{R3}(G)≤13m5+1; n=4,m≥4mn2≤γ{R3}(G)≤3mn+3m+2n5; m,n≥5

3 结 语

本文给出了圈与圈克罗内克乘积图的罗马{3}-控制数的界．通过构造圈与圈克罗内克乘积图的罗马{3}-控制函数，得到了罗马{3}-控制数的上界．结合前人给出的一般图的罗马{3}-控制数的下界，得到圈与圈克罗内克乘积图罗马{3}-控制数的下界．