两个圈笛卡尔乘积的罗马控制数

胡夫涛，于紫嫣，孙美钰

安徽大学数学科学学院，安徽 合肥 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和……