图的反符号圈控制＊

吴方胜, 吕新忠

(浙江师范大学数理与信息工程学院,浙江金华 321004)

本文考虑的均为无向简单图,未加定义的术语和记号参阅文献[1].

令 G=(V,E)是一个图,若 S⊆ V(G),用 G[S]表示 G中由 S生成的子图;若对圈 C有G[V(C)]=C,则称 C为 G的生成圈;若图 G1,G2满足V(G1)∩V(G2)=φ,则称图 G1,G2不相交.对任意整数 a,b,c,a≡b(modc)表示整数 a,b对模 c同余.对于一个实值函数 f:E→R和一个子集 S∈E(G),记 f(S)=

近几年来,图的控制理论研究的内容越来越广泛,各类控制概念相继产生且研究成果不断丰富[2].然而,其中多数属于图的点控制.徐保根等研究了边控制问题,并获得了一些研究成果,如符号边控制[3]、符号星控制[4]、符号圈控制[5]等.笔者研究了阶数为 n、边数为 m的图 G有γ′rsc(G)≤2n-m-2及几种特殊图的反符号控制数.在给出主要结果之前,先引入反符号圈控制的概念及相关性质.

定义 1 图 G=(V,E),称函数 f:E→{-1,+1}为 G的反符号圈控制函数,若对 G中任意生成圈 C

由定义 1易知对任意的图 G都具有以下性质:

因此

下证取等号时 G是一棵树.

充分性 充分性是显然的.

2)n为奇数.由性质 3可知 f(K3)≤-1,f(Cn)≤-1,则

故对任意的 n≥3都有

3)当 n=4k+2时 ,

[1]Bondy J A,MurtyU S R.Graph TheoryWith Applications[M].New York:Macmillan PressLTD,1976.

[2]Haynes TW,Hedetniemi S T,Slater P J.Domination in Graphs[M].New York:MarcelDekker Inc,1998.

[3]Xu Baogen.On signed edge domination numbers of graphs[J].DiscreteMath,2001,239(1/2/3):179-189.

[4]徐保根.关于图的符号星控制数[J].华东交通大学学报,2004,21(4):116-118.

[5]Xu Baogen.On signed cycle domination in graphs[J].DiscreteMath,2009,309(4):1007-1012.