图的符号边控制数

敖国艳,红霞,霍红,吉日木图

(1.内蒙古民族大学离散数学研究所,内蒙古通辽 028043; 2.内蒙古民族大学数学学院,内蒙古通辽 028043)

图的符号边控制数

敖国艳1,2,红霞1,2,霍红1,2,吉日木图1,2

(1.内蒙古民族大学离散数学研究所,内蒙古通辽 028043; 2.内蒙古民族大学数学学院,内蒙古通辽 028043)

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文确定了图、Hn和的符号边控制数．

图;符号边控制函数;符号边控制数

DO I：10.3969/j.issn.1008-5513.2013.04.010

1 引言

2 主要结果

[1]Bondy J A,Murty U SR.Graph Theory w ith App lica Tions[M].London:Macm illan,1977.

[2]徐保根.图的控制理论[M].北京:科学出版社,2008.

[3]Xu Baogen.On signed edge dom ination numbers of graphs[J].Discrete Math.,2001,239:179-189.

[4]Zhang Z,Xu Baogen,Li Y,et al.A note on the lower bounds of signed dom ination number of a graph[J]. D iscrete M ath.,1999,195:295-298.

[5]Xu Baogen.Two classes of edge dom ination in graphs[J].Discrete Applied Mathematics,2006,154:1541-1546.

[6]徐保根,李春华.图的符号星K控制数[J].纯粹数学与应用数学,2009,25(4):638-641.

[7]尚华辉,苗连英,苗正科,等.关于图的弱符号控制数的下界[J].纯粹数学与应用数学,2010,26(4):691-695.

[8]Akbari S,Bolouk i S,Hatam i P,et al.On the signed edge dom ination number of graphs[J].Discrete M ath., 2009,309(3):587-594.

[9]Xu Baogen.Two classes of edge dom ination in graphs[J].Discrete Applied Mathematics,2006,154:1541-1546.

[10]徐保根,李印权.关于图的符号边全控制数[J].数学的实践与认识,2009,39(5):138-144.

[11]王军秀.特殊图类的符号控制数[J].纯粹数学与应用数学,2005,21(1):59-61.

Signed edge dom ination num bers of graphs

Ao Guoyan1,2,Hong Xia1,2,Huo Hong1,2,Jirimutu1,2

(1.Institute of Discrete M athematics,Inner M ongolia University for Nationalities
2.College of Mathematics,Inner M ongolia University for Nationalities,Tongliao 028043,China)

The signed edge dom ination number of a graph has its im port and applying background.It is known that com pu ting it is NP-com p lete,so it is usefu l to determ inate the exact value of it.In this paper,we determ ine the signed edge dom ination numbers of graph F∗n+1、Hnand P∗n.

graph,signed edge dom ination function,signed edge dom ination numbers

O157.5

A

1008-5513(2013)04-0397-06

2013-05-06.

国家自然科学基金(61262018,61261025);内蒙古自治区高等学校科学研究项目(NJZY 11198).

敖国艳(1988-),硕士,研究方向：图论及其应用.

2010 M SC:05C69