圖的符號控制數(shù)的下界

徐保根，丁宗鵬，羅 茜

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

圖的符號控制數(shù)的下界

徐保根，丁宗鵬，羅 茜

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

圖；符號控制函數(shù)；符號控制數(shù)

1 引言及定義

本文中所指的圖均為無向簡單圖，文中未說明的符號和術(shù)語同文獻(xiàn)[1]。

圖的控制理論是圖論中的重要分支，美國圖論學(xué)者W.T.Haynes等人在1998年出版的專著[2]較為系統(tǒng)地綜述了這一領(lǐng)域的一些主要研究成果，E.J.Cockayne等[3]引入了圖的控制多種變化形式。近來人們已經(jīng)將圖的點(diǎn)控制概念轉(zhuǎn)向研究圖的邊控制問題[4]，并獲得了一些初步的研究成果[5-7]，尤其是對圖的符號控制和符號邊控制，得到許多新的結(jié)論[8]。在本文中，將繼續(xù)探討圖的符號控制數(shù)的新下界，并刻劃滿足γs(G)=|V(G)|的所有圖G。

2 主要結(jié)果及其證明

本節(jié)主要給出圖的符號控制數(shù)的若干新的下界，并刻劃了滿足γs(G)=| |V(G)的所有圖G。

[1]BONDY JA，MURTYV S R.Graph theory with applications[M].New York：Elsevier，1976.

[2]HAYNES T W ，HEDETNIEMI S T ，SLATER P J.Domination in graphs[M].New York：Marcel Dekker，INC，1998.

[3]COCKAYNE E J，MYNHART C M.On a generalization of signed domination functions of graphs[J].Ars Combin，1996，43：235-245.

[4]徐保根，李春華.圖的符號星K控制數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2009，25（4）：638-641.

[5]XU BAOGEN.On signed edge domination numbers of graphs[J].Discrete Math，2001，239：179-189.

[6]XU BAOGEN.On signed cycle domination in graphs[J].Discrete Math，2009，309（4）：1007-1012.

[7]XU BAOGEN.On minus domination and signed domination in graphs[J].Journal of Mathematical Research&Exposition，2003，23（4）：585-590.

[8]徐保根.圖的控制理論[M].北京：科學(xué)出版社，2008.

The Lower Bounds of Signed Domination Numbers in Graphs

Xu Baogen，Ding Zongpeng，Luo Xi
(School of Basic Sciences，East China Jiaotong University，Nanchang 330013，China)

graph；signed dominating function；signed domination number

O157.5

A

1005-0523（2011）03-0069-04

2011-04-07

國家自然科學(xué)基金項(xiàng)目(11061014）；江西省教育廳科研項(xiàng)目（GJJ09235）

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