圖的局部減邊控制數(shù)

樊鎖海,廖萬生,2,楊潔,徐慕蓉

(1.暨南大學(xué)數(shù)學(xué)系,廣東廣州 510632;2.江西省贛州第三中學(xué),江西贛州 341000)

圖的局部減邊控制數(shù)

樊鎖海1,廖萬生1,2,楊潔1,徐慕蓉1

(1.暨南大學(xué)數(shù)學(xué)系,廣東廣州 510632;2.江西省贛州第三中學(xué),江西贛州 341000)

引入局部減邊控制函數(shù)和局部減邊控制數(shù)的概念,得到了圖的最小局部減邊控制函數(shù)的性質(zhì),給出了局部減邊控制數(shù)的最好上下界,確定了一些特殊圖的局部減邊控制數(shù).最后得到了圖的減邊控制數(shù)的最好上界.

減邊控制數(shù);局部減邊控制數(shù);邊覆蓋數(shù);匹配數(shù)

1 引言

圖的控制集理論是圖論研究中的重要課題,在編碼理論、計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等領(lǐng)域有廣泛的應(yīng)用.近年來,圖的控制集理論的研究內(nèi)容越來越豐富. Dunbar在文[1]中最早引入圖的符號控制數(shù)的概念.1998年Haynes等出版了兩部專著[23],較為系統(tǒng)地綜述了控制集理論的主要研究成果,包括圖的符號控制數(shù)、圖的減控制數(shù)等.呂新忠研究了圖的全符號控制[4].徐保根在文[5-8]中研究了圖的邊控制問題,獲得了重要成果.圖的邊控制不僅與一些實(shí)際問題相聯(lián)系(如局部占優(yōu)設(shè)計(jì)問題等),而且與某些特殊的點(diǎn)符號控制有關(guān)[9].文[8]中引入減邊控制數(shù)(G)并得到兩個(gè)下界,確定了完全圖、圈和輪圖的減邊控制數(shù).本文引入局部減邊控制函數(shù)研究減邊控制數(shù)的上界.第2節(jié)給出基本概念和主要結(jié)論,第3節(jié)給出主要結(jié)論的證明.

2 主要結(jié)論

本文考慮的圖G=(V,E)均為有限簡單連通圖.G中邊e的開鄰域N(e)是指G中所有與邊e相鄰的邊的集合,邊e的閉鄰域N[e]=N(e)∪{e};類似地G中頂點(diǎn)v的開鄰域和閉鄰域分別為N(v)和N[v].頂點(diǎn)v在G中的度d(v)=|N(v)|.圖G的最小度記為δ(G).E(v)表示與點(diǎn)v關(guān)聯(lián)的邊的集合.

2 主要結(jié)論的證明

[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]呂新忠.圖的全符號控制數(shù)[J].中國科學(xué):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]徐保根,周尚超.關(guān)于圖的減邊控制[J].江西師范大學(xué)學(xué)報(bào):自然科學(xué)版,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].北京:機(jī)械工業(yè)出版社,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.

國家自然科學(xué)基金(10671076).

樊鎖海(1967-),博士,教授,研究方向：圖論與組合最優(yōu)化.

2000MSC:05C69