图的符号控制数的下界

徐保根，丁宗鹏，罗 茜

（华东交通大学基础科学学院，江西南昌 330013）

图的符号控制数的下界

徐保根，丁宗鹏，罗 茜

（华东交通大学基础科学学院，江西南昌 330013）

图；符号控制函数；符号控制数

1 引言及定义

本文中所指的图均为无向简单图，文中未说明的符号和术语同文献[1]。

图的控制理论是图论中的重要分支，美国图论学者W.T.Haynes等人在1998年出版的专著[2]较为系统地综述了这一领域的一些主要研究成果，E.J.Cockayne等[3]引入了图的控制多种变化形式。近来人们已经将图的点控制概念转向研究图的边控制问题[4]，并获得了一些初步的研究成果[5-7]，尤其是对图的符号控制和符号边控制，得到许多新的结论[8]。在本文中，将继续探讨图的符号控制数的新下界，并刻划满足γs(G)=|V(G)|的所有图G。

2 主要结果及其证明

本节主要给出图的符号控制数的若干新的下界，并刻划了满足γ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控制数[J].纯粹数学与应用数学，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].北京：科学出版社，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

国家自然科学基金项目(11061014）；江西省教育厅科研项目（GJJ09235）

徐保根（1963－），男，教授，研究方向为图论与组合数学。