圖的反符號(hào)星k控制數(shù)

徐保根，孔祥陽(yáng)，陳悅

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西南昌330013)

圖的反符號(hào)星k控制數(shù)

徐保根，孔祥陽(yáng)，陳悅

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西南昌330013)

反符號(hào)星k控制函數(shù);反符號(hào)星k控制數(shù);反符號(hào)星控制函數(shù);反符號(hào)星控制數(shù)

在1998年美國(guó)圖論學(xué)者W T Haynes等人出版了專(zhuān)著，該著作較為全面而又系統(tǒng)地總結(jié)了近些年在圖論方面的一些重要研究成果。但這些成果幾乎都是關(guān)于圖的點(diǎn)控制問(wèn)題，與圖的邊控制問(wèn)題相關(guān)的結(jié)果卻比較少。為了將圖的控制理論內(nèi)容進(jìn)行進(jìn)一步健全和豐富，我們將由對(duì)圖的點(diǎn)控制問(wèn)題的研究轉(zhuǎn)向?qū)D的邊控制問(wèn)題的研究，我們已經(jīng)得到了一些研究成果，例如，符號(hào)邊控制，符號(hào)星控制和符號(hào)圈控制等。在本文中，我們將引入一個(gè)新概念，即圖的反符號(hào)星k控制概念。

本文所考察的圖均為無(wú)向簡(jiǎn)單圖，文中的符號(hào)和術(shù)語(yǔ)若無(wú)特別說(shuō)明則均與文獻(xiàn)相同。

下面我們將圖的反符號(hào)星控制概念進(jìn)行推廣，從而引入一種新的圖的邊控制概念。

對(duì)于空?qǐng)D，所以反符號(hào)星k控制概念既是對(duì)反符號(hào)星控制概念的一種推廣，也是對(duì)符號(hào)星k控制概念的一種推廣。關(guān)于圖的反符號(hào)星控制數(shù)，文［6］中指給出了如下結(jié)果:

本文在對(duì)文［7］中的結(jié)果進(jìn)行了推廣——給出了一般圖的反符號(hào)星k控制數(shù)的若干上界，在此基礎(chǔ)上，給出了n階路Pn和n階圈Cn的反符號(hào)星k控制數(shù)的表達(dá)式。

定理1對(duì)于任意n階圖G，當(dāng)δ≥1，1≤k≤n－1時(shí)，有

其中:δ=δ(G)，Δ=Δ(G)分別表示圖G的最小度和最大度。

其中:δ=δ(G)和Δ=Δ(G)分別為圖G的最小度和最大度。

另外，我們還可得到

可見(jiàn)結(jié)論是成立的，定理證畢。

根據(jù)定理2，我們可得到如下推論:

推論對(duì)任意n階r－正則圖G，若r≥1，且1≤k≤n，則有

最后我們給出n階路Pn和n階圈Cn的反符號(hào)星k控制數(shù)的表達(dá)式。

可以驗(yàn)證:f為Pn的一個(gè)反符號(hào)星k控制函數(shù)且有

結(jié)合(3)知結(jié)論(Ⅰ)成立。同理可知結(jié)論(Ⅱ)也成立，定理證畢。

［1］HAYNES T W，HEDETNIEMI S T，SLATER P J.Domination in graphs［M］.New York:Marcel Dekker，INC，1998.

［2］XU BAOGEN.On signed edge domination numbers of graphs［J］.Discrete Math，2001，239(1/2/3):179－189.

［3］XU BAOGEN.Two classes of edge domination in graphs［J］.Discrete Appl Math，2006，154(10):1 541－1 546.

［4］XU BAOGEN.On signed cycle domination in graphs［J］.Discrete Math，2009，309(4):1 007－1 012.

［5］BONDY J A，MURTY V S R.Graph Theory with Applications［M］.Elsevier，Amsterdam，1976.

［6］趙華，徐保根，趙金鳳，帥春萍.關(guān)于圖的反符號(hào)星控制數(shù)［J］.華東交通大學(xué)學(xué)報(bào)，2008，25(5):84－87.

［7］徐保根，李春華.圖的符號(hào)星k控制數(shù)［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2009，25(4):638－641.

(責(zé)任編輯 王建華)

Reverse Signed Star k－subdomination Numbers of Graphs

Xu Baogen，Kong Xiangyang，Chen Yue

(School ofBasic Sciences，East China Jiaotong University，Nanchang 330013，China)

signed star k－dominating function;signed star k－domination number;signed star dominating function;signed star domination number

O157.5

A

1005－0523(2010)04－0068－03

2010－04－25

國(guó)家自然科學(xué)基金項(xiàng)目(10661007);江西省教育廳科研項(xiàng)目(GJJ09215)

徐保根(1963－)，男，教授，研究方向?yàn)閳D論與組合數(shù)學(xué)。