圖的符號邊控制數

敖國艷,紅霞,霍紅,吉日木圖

(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