徐保根，罗 茜，丁宗鹏

（华东交通大学基础科学学院江西南昌330013）

1 引言及定义

文中所指的图均为无向简单图，文中未说明的符号和术语同文献[1]。

设G为一个图，对于任意v，则NG(v)表示v点在G中的邻域，dG(v)= ||NG(v)表示v点在G中的度，NG[v]=NG(v)∪{v}称为v点的闭邻域，δ和Δ分别为图G的最小度和最大度，有时，NG[v]和dG(v)分别简记为N[v]和d(v)。

设G和H为两个点不交的图，在G∪H中将G的每个顶点与H的每个顶点均邻接起来，所得的图称为G与H的联图，记为G∨H。

对于两个点不交的图G和H，则G与H的乘积图记为G×H，其定义为

E

设G为一个图，D⊆V(G)，如果对于V(G)D中的每个顶点v，存在u∈D，使得u与v在G中邻接，则称D为G的一个控制集，容量最小的控制集包含的点数称为G的控制数，记为γ(G)。

图的控制理论是图论中的重要分支，美国图论学者W.T.Haynes等[2]在1998年出版的专著较为系统地综述了这一领域的一些主要研究成果。在1977年，E.J.Cockayne和S.T.Hedetniemi[3]引入了图的集控制概念并研究图的集控制数，B.Zelinka[4-5]在图的集控制方面做了大量工作，得出了集控制数与图的其它参数之间的关系，如集控制数与线性点荫度的关系[4]等。

定义1[3]设G是一个图，如果V(G)能划分为t个两两不交的控制集Di(i=1，2，...，t)，则称G有t-控制集划分。图G的集控制数记为d(G)，其定义为:d(G)=max｛t|存在G的t-控制集划分｝。

对于任何图G，由于D=V(G)本身就是G的一个控制集，故d(G)总是存在的，并且不难证明下面的结论。

引理1[6]对任意图G，均有d(G)≤1+δ(G)。且v1邻接v2，或者v1=v2且u1邻接u2｝。

在本文中，我们主要研究乘积图与联图的集控制问题，给出这两种图集控制数的界限，并确定了一些特殊性图的集控制数，这包括Km×Kn和Pm×Pn等。……