吳方勝, 呂新忠

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江金華 321004)

本文考慮的均為無向簡單圖,未加定義的術(shù)語和記號參閱文獻[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不相交.對任意整數(shù) a,b,c,a≡b(modc)表示整數(shù) a,b對模 c同余.對于一個實值函數(shù) f:E→R和一個子集 S∈E(G),記 f(S)=

近幾年來,圖的控制理論研究的內(nèi)容越來越廣泛,各類控制概念相繼產(chǎn)生且研究成果不斷豐富[2].然而,其中多數(shù)屬于圖的點控制.徐保根等研究了邊控制問題,并獲得了一些研究成果,如符號邊控制[3]、符號星控制[4]、符號圈控制[5]等.筆者研究了階數(shù)為 n、邊數(shù)為 m的圖 G有γ′rsc(G)≤2n-m-2及幾種特殊圖的反符號控制數(shù).在給出主要結(jié)果之前,先引入反符號圈控制的概念及相關(guān)性質(zhì).

定義 1 圖 G=(V,E),稱函數(shù) f:E→{-1,+1}為 G的反符號圈控制函數(shù),若對 G中任意生成圈 C

由定義 1易知對任意的圖 G都具有以下性質(zhì):

因此

下證取等號時 G是一棵樹.

充分性 充分性是顯然的.

2)n為奇數(shù).由性質(zhì) 3可知 f(K3)≤-1,f(Cn)≤-1,則

故對任意的 n≥3都有

3)當(dāng) 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]徐保根.關(guān)于圖的符號星控制數(shù)[J].華東交通大學(xué)學(xué)報,2004,21(4):116-118.

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