图的局部减边控制数

樊锁海,廖万生,2,杨洁,徐慕蓉

(1.暨南大学数学系,广东广州 510632;2.江西省赣州第三中学,江西赣州 341000)

图的局部减边控制数

樊锁海1,廖万生1,2,杨洁1,徐慕蓉1

(1.暨南大学数学系,广东广州 510632;2.江西省赣州第三中学,江西赣州 341000)

引入局部减边控制函数和局部减边控制数的概念,得到了图的最小局部减边控制函数的性质,给出了局部减边控制数的最好上下界,确定了一些特殊图的局部减边控制数.最后得到了图的减边控制数的最好上界.

减边控制数;局部减边控制数;边覆盖数;匹配数

1 引言

图的控制集理论是图论研究中的重要课题,在编码理论、计算机科学、通信网络、监视系统和社会网络等领域有广泛的应用.近年来,图的控制集理论的研究内容越来越丰富. Dunbar在文[1]中最早引入图的符号控制数的概念.1998年Haynes等出版了两部专著[23],较为系统地综述了控制集理论的主要研究成果,包括图的符号控制数、图的减控制数等.吕新忠研究了图的全符号控制[4].徐保根在文[5-8]中研究了图的边控制问题,获得了重要成果.图的边控制不仅与一些实际问题相联系(如局部占优设计问题等),而且与某些特殊的点符号控制有关[9].文[8]中引入减边控制数(G)并得到两个下界,确定了完全图、圈和轮图的减边控制数.本文引入局部减边控制函数研究减边控制数的上界.第2节给出基本概念和主要结论,第3节给出主要结论的证明.

2 主要结论

本文考虑的图G=(V,E)均为有限简单连通图.G中边e的开邻域N(e)是指G中所有与边e相邻的边的集合,边e的闭邻域N[e]=N(e)∪{e};类似地G中顶点v的开邻域和闭邻域分别为N(v)和N[v].顶点v在G中的度d(v)=|N(v)|.图G的最小度记为δ(G).E(v)表示与点v关联的边的集合.

2 主要结论的证明

[1]Dunbar J.Signed domination in graphs[J].Graph Theory,Combinatorics and Applications,1995,1:311-322.

[2]Haynes T W,Hedetniemi S T,Slater P J.Domination in Graphs[M].New Yerk:Marceldekker,1998.

[3]Haynes T W,Hedetniemi S T,Slater P J.Fundamentals of Domination in Graphs[M].New Yerk:Marcel Dekker,1998.

[4]吕新忠.图的全符号控制数[J].中国科学:A辑,2007,37(5):573-578.

[5]Xu B G.On signed edge domination numbers of graphs[J].Discrete Mathematics,2001,239(1/2/3):179-189.

[6]Xu B G.On edge domination numbers of graphs[J].Discrete Mathematics,2005,294(3):311-316.

[7]Xu B G.Two classes of edge domination in graphs[J].Discrete Applied Mathematics,2006,154(10):1541-1546.

[8]徐保根,周尚超.关于图的减边控制[J].江西师范大学学报:自然科学版,2007,31(1):21-25.

[9]Yu Y J,Wei Y D,Wang J.Carbon nanotube-based quantum spin pump[J].New Journal of Physics,2006,73:1-10.

[10]Douglas B W.Introduction to Graph Theory[M].北京:机械工业出版社,2005.

Local minus edge domination numbers of graphs FAN Suo-hai1,LIAO Wan-sheng1,2,YANG Jie1,XU Mu-rong1

(1.Department of Mathematics,Jinan University,Guangzhou510632,China; 2.Ganzhou No.3 Middle School,Ganzhou341000,China)

Local minus edge domination functions and local minus edge domination numbers of graphs are introduced to study minus edge domination numbers of graphs.The property of minimum local minus edge domination functions is given,the best bound of local minus edge domination numbers is obtained,local minus edge domination numbers of some special graphs are determined.Finally the best upper bound of minus edge domination numbers of graphs is given.

minus edge domination number,local minus edge domination number,edge cover number,matching number

O157.5

A

1008-5513(2009)04-0625-05

2008-01-08.

国家自然科学基金(10671076).

樊锁海(1967-),博士,教授,研究方向：图论与组合最优化.

2000MSC:05C69