圖的反符號圈控制＊

吳方勝, 呂新忠

(浙江師范大學數理與信息工程學院,浙江金華 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.