两个圈笛卡尔乘积的罗马控制数
2022-03-21胡夫涛于紫嫣孙美钰
胡夫涛，于紫嫣，孙美钰
安徽大学数学科学学院，安徽 合肥 230601
图的控制数的研究历史可追溯到公元1850年。图的控制问题和相关子集问题的研究是图论研究中心热点，引起了人们广泛的研究，相关研究成果详见专著[2-5]。在图的控制论中，图的罗马控制数问题是一个基本问题，并且具有数学和历史的双重意义。REVELLE[6]在1997年介绍了罗马控制问题；IANSTEWART[7]在1999年讨论了君士坦丁为保卫罗马帝国而采取的策略，并提出一个新的控制数，即罗马控制数；COCKAYNE等[8]给出了图中罗马控制的定义；此外，还有很多的罗马控制相关结果，例如文献[9，10]。图论研究中染色问题研究(文献[11])和图的控制有很相似的地方，图论研究也有很多重要的应用[12]。
2个图的笛卡尔乘积是构造大的图模型的重要工具。人们对常见的网络，如路和路、路和圈、圈和圈的笛卡尔乘积，都有很深入的研究，在图的控制数方面有很多研究成果：文献[13]研究了路和圈的笛卡尔乘积的成对控制数；文献[14]研究了圈和圈的全控制数和成对控制数；文献[15]给出了一个算法求解圈与圈笛卡尔乘积的罗马控制数精确值。对正整数n≥3，笔者通过严格的理论证明确定了P2×Cn,C3×Cn,C4×Cn,C5×Cn的罗马控制数精确值和G6,n的罗马控制数上界。
1 基本性质
引理 1[8]对任意图G,γ(G)≤γR(G)≤2γ(G)。
引理3[8]设f=(V0,V1,V2)是任意γR-函数，则：
1)G[V1],V1的子图最大度为1；
2)V1和V2在G中无边；
3)V0中的点最多连接V1中2个点；
4)V2是G[V1∪V2]的一个控制集。
引理4[8]设G是阶为n的连通图，则γR(G)=γ(G)+1当且仅当V中一点v的度为n-γ(G)。引理5[8]任意图G的阶为n，最大度为Δ，则：
2 主要结果
设Cn和Pn分别表示为阶为n的圈和路，且它们的顶点集记为：
V(Cn)=V(Pn)=[n]={1,2,…,n}
记Gm,n=Cm×Cn为2个圈Cm和Cn的笛卡尔乘积，设它们的顶点集为：
V(Cm×Cn)=V(Pm×Cn)={vi,j:1≤i≤m,1≤j≤n}
对任意j∈[n]，记：
2.1 P2×Cn的罗马控制数精确值
定理1设正整数n≥3，则:
注：黑实心点函数值为2，空心点函数值为0。图1 构造的P2×C8的罗马控制函数Fig.1 Constructed RDF of P2×C8
易见f=(V0,V1,V2)是P2×Cn的一个罗马控制函数，其中V0=V(P2×Cn)(V1∪V2)。因此：
利用反证法，假设存在P2×Cn的一个γR-函数f=(V0,V1,V2)，使得γR(P2×Cn)=2|V2|+|V1|=n。因为V2中的一个点最多控制3个V0中的点，所以4|V2|+|V1|≥V(P2×Cn)=2n，从而得到4|V2|=2n，且|V1|=0。因此每个V2中的点都与V0中的3个点邻接，且V0中每个点只与V2中唯一一点邻接。根据对称性，不妨设v1,1∈V2，则v2,3∈V2，对应v1,5∈V2，如此下去总会得到v1,n∈V2或者v1,n与V2中2个点相邻，得到矛盾。因此当n≡1,2,3(mod 4)时，γR(P2×Cn)=n+1。
综上，有：
2.2 G3,n的罗马控制数精确值
注：黑实心点函数值为2，红实心点函数值为1，空心点函数值为0。图2 构造的G3,8的罗马控制函数Fig.2 Constructed RDF of G3,8
易见f=(V0,V1,V2)是G3,n的一个罗马控制函数，其中V0=V(G3,n)(V1∪V2)。因此：
所以：
2.3 G4,n的罗马控制数精确值
定理3设正整数n≥3，则γR(G4,n)=2n。
证明设：
V2={v1,i,v3,j:i=0(mod 2),j=1(mod 2),i,j∈[n]}V1=φV0=V(G4,n)(V1∪V2)
则易见f=(V0,V1,V2)是G4,n的一个γR-函数，从而γR(G4,n)≤2n。图3为构造的G4,8的罗马控制函数。
注：黑实心函数值为2，空心点函数值为0图3 构造的G4,8的罗马控制函数Fig.3 Constructed RDF of G4,8
图4 |V2∩|=2且f(v2,i+1)=2时的重新赋值Fig.4 Reassign when |V2∩|=2 and f(v2,i+1)=2
所以：
γR(G4,n)=2n
2.4 G5,n的罗马控制数精确值
性质1设正整数n≥3和l≥1，则：
γR(G5l,n)=2ln,n≡0(mod 5)
γR(G5l,n)≤2ln+2l,n≡1,2,3,4(mod 5)
证明设：
v8,p,…,v5l-2,p,v1,q,v6,q,…,v5l-4,q:i≡1(mod 5),j=2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}
注：黑实心点函数值为2，空心点函数值为0。图5 构造的G5,10的罗马控制函数Fig.5 Constructed RDF of G5,10
因此：
定理4设正整数n≥3，则:
证明根据性质1，有：
γR(G5,n)=2n，n≡0(mod 5)
γR(G5,n)≤2n+2，n≡1,2,3,4(mod 5)
因此只需考虑n≢0(mod 5)的情形。
设f=(V0,V1,V2)为G5,n的所有γR-函数中|V1|数最小的，其中f=2|V2|+|V1|，根据定义：
V2={v4,i,v2,j,v5,k,v3,p,v1,q:i≡1(mod 5),j≡2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}
当n≢0(mod 5)时，v1,n∉V2，此时v1,1∈V0不与任何V2中的点相邻，矛盾。
V2={v4,i,v2,j,v5,k,v3,p,v1,q:i≡1(mod 5),j≡2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}
2.5 G6,n罗马控制数上界
定理5设正整数n≥6，则:
证明设：
k≡3(mod 6),p≡4(mod 6),q≡5(mod 6),r≡0(mod 6)
注：黑实心点的函数值为2，空心点的函数值为0。图6 构造的G6,8的罗马控制函数Fig.6 Constructed RDF of G6,8
G6,n的罗马控制数上界是可以达到的，因为里面涉及的情况非常多，在以后的研究中将进一步考虑其它Gm,n未确定的罗马控制数。
