徐保根，康洪波，赵利芬，操叶龙

(华东交通大学基础科学学院，江西 南昌 331013)

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

近几年来，图的控制理论研究的内容越来越广泛，各类控制概念相继产生且研究成果不断丰富,Haynes等[2]综述了近几些年来图的控制理论研究方面的主要研究成果。文献[3]首先提出了图的符号边控制概念，获得了符号边控制数的许多界限，并将这一概念推广到边上的多种符号控制，如符号星控制[4]、符号圈控制[5]、符号团控制[6]等等。同样地，这也产生了对应的减边控制概念，从而使得控制理论研究内容和研究成果越来越丰富，文献[7] 综述了这些研究成果。

1 若干定义

设G=(V,E)是一个图，若C为图G中的一个圈，若V(C)在G中的导出子图G[V(C)]=C。则称C为图G的一个导出圈或无弦圈。

文献[8]中首先提出并研究了图的圈符号控制。

定义1[8]设G=(V,E)是一个图，一个函数f:V→{-1,1}如果满足f(V(C))≥1对G中每一个导出圈C均成立，则称f为图G的一个圈符号控制函数，图G的圈符号控制数定义为γsc(G)=min{f(V):f为图G的一个圈符号控制函数}。

2 主要结论及其证明

首先给出满足δ≥2且γsc(G)=4-V(G)的图G的一个刻划。

证明由于δ≥2，图G至少有一个圈，从而对图G的每一个圈符号控制函数f，G中至少有两个点v∈V(G)满足f(v)=1，故γsc(G)≥4-n。

充分性是显然的。下面证明必要性。

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1},

γsc(G)=A-B=2A-n

故A=2，记A={u,v}。

论断1G的边连通度λ(G)≥2。

若G为不连通图，即G至少有两个分支，由于δ≥2，G的每个分支中至少有一个导出圈，从而至少有一个导出圈C，使C上至多有A中一个点，故f(V(C))≤-1，矛盾。

若G中有割边e=ab∈E(G)，令G1=G-e，G1至少有两个分支，由于δ(G)≥2，a点所在的分支Ga中至多有一个1度点(a点)，其它点的度至少为2，故Ga中有导出圈。同理，Gb中也有导出圈，从而至少有一个导出圈C，使C上至多有A中一个点，故f(V(C))≤-1，矛盾。因此，论断1成立。

由于λ(G)≥2，故G中任何点都在一个导出圈中，由A=2知，G中任何导出圈均为一个三角形，且均包含u和v两点(否则，存在导出圈C，f(V(C))≤0，矛盾)。因此，uv∈E(G)。

由于e边的两端点均不在A中，故f(V(C))≤0，矛盾。因此，论断2成立。

给出图的圈符号控制数的一个下界。

定理2 对于任意n阶图G，若其最小度δ=δ(G)≥2，则有

γsc(G)≥2δ-n

并且此下界是最好可能的。

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1}

记A=s，B=t，由定义知，

γsc(G)=s-t=2s-n

下面说明此下界是最好可能的。

对于一个无圈图G，我们知道γsc(G)=-V(G)，这使得对于无圈图来说，图的圈符号控制数是已知的，无需研究。下面针对有圈图给出圈符号控制数的一个下界。

定理3 对于任意n阶图G，E(G)=m，若G中至少有一个圈，则有

A={v∈V(G)f(v)=1},

B={v∈V(G)f(v)=-1}

记A=s，B=t，由定义知，

γsc(G)=s-t=2s-n

m=E(G[A])+E(A,B)+E(G[B])≤

参考文献：

[1] BONDY J A, MURTY U S R.图论及其应用 [M]. 吴望名,等译. 北京：科学出版社，1984.

[2] HAYNES T W, HEDETNIEMI S T, SLATER P J. Domination in graphs [M]. New York:Marcel Dekker Inc, 1998.

[3] XU B G. On signed edge domination numbers of graphs [J]. Discrete Math, 2001, 239: 179-189.

[4] XU B G. Two classes of edge domination in graphs [J]. Discrete Appl Math, 2006, 154: 1541-1546.

[5] XU B G. On signed cycle domination numbers in graphs [J]. Discrete Math, 2009, 309: 1007-1012.

[6] 徐保根. 关于图的团符号控制数[J].系统科学与数学, 2008, 3: 282-287.

[7] 徐保根. 图的控制理论[M]. 北京：科学出版社，2008.

[8] 帅春萍，徐保根，赵金凤，等. 关于图的符号圈点控制数 [J].华东交通大学学报，2009,26(4):91-94.