正则图的Upper减控制数

《正则图的Upper减控制数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、正则图的Upper减控制数UpperMinusDominationNumberofRegularGraphs指导教师学位类另U吕新忠理学硕士学科专业菱缠堡迨学位授予单位——浙江师范大学论文答辩日期2010年4月7日正则图的Upper减控制数摘要Ⅲ帅111ll⋯Ⅲ11111洲111ll

2、

3、11111llllY1804504图G=(ME)上的函数，：V一{一1，0，1】．被称为是图G上的一个减控制函数，如果对任意的点t，∈V，都有，(ⅣM)=∑，(u)≥1．减控制函数，是图G上的极小减控制函数，如果不存在减控制函数夕：V_{一l，o，1)，，≠夕，使得对任意的点"∈K

4、g(v)≤／(v)都成立．图G的减控制数通常表示为，y一(G)，它为G上所有的减控制函数之中权重的最小数值；图G的Upper减控制数记为F一(G)，它是图G上所有的极小减控制函数之中权重的最大数值．也即是：，y一(G)=min{u(／)I，为G上的减控制函数)和r_(G)=max{w(f)I，为G上的极小减控制函数)．图G=(KE)上的函数．，：E一{一1，o，1)被称为是图G上的减边控制函数，如果对于图G的每一条边e∈E都有，(Ⅳ【e1)=∑／(e’)≥1．图G的e'eNIH减边控制数通常表示为‰／(G)，它为图G上所有的减边控制函数之中权重的最小数值；图G的U

5、pper减边控制数记为r，m(G)，它是图G上所有的极小减边控制函数之中权重的最大数值．也即是：7一(G)=m饥扣(，)I，为G上的减边控制函数)和r-(G)=max{w(f)I，为G上的极小减边控制函数)．本文通过对图的结构性质的分析，得到了正则图的Upper减控制数。主要结论如下：(1)对任意的礼阶三正则图G都有r_(G)≤兰n，且此界是可达的，并构造oI出一类r弋G)=三n的图；对任意的礼阶四正则图G都有r-(G)≤南n；对任意的竹阶五正则图G都有r_(G)≤三佗；(2)对任意的礼阶七一正则图G都有r一(G)≤妄}高n；(3)对于任意的有m条边的三正则图G都

6、有r二(G)≤了2m．关键词：三正则；四正则；五正则；k一正则；减控制数；减边控制数Ⅱ一UPPERMINUSDOMINATIONNUMBEROFREGULARGRAPHSABSTRACTLetG=(KE)beagraph，Afunctionf：V_{-1，0，1)definedontheverticesofGisaminusdominatingfunction，ifthesumofitsfunctionvaluesoveranyclosedneighborhoodisatleastone．Thatis，foreveryvertext，∈V，(ⅣM)=∑f(u)≥1

7、．Aminusdominatingfunctionfisminimal，iftheredoesnotexistanyminusdominatingfunctiong：V_(一1，0，1)，f≠g，forwhichg(v)≤f0,)foreveryveRext，∈V．TheminusdominationnumberofagraphG，denoted，y一(G)istheminimumWeightofalltheminusdominatingfunctionsofG：TheupperminusdominationnumberofagraphG，denotedF_(G)

8、，equalsthemaximumweightofalltheminimalminusdominatingfunctionsofG．Thatis，y_(G)=min{w(f)Ifis口minusdominatingfunctiononG)and’r弋G)=max{w(f)Jfis口minimalminusdominatingfunctiononG—LetG=(KE)beagraph，Afutictionf：E_{-1，0，1)definedontheedgesofGisaminusedgedominationfunction，iftIIesumofitsfunct

9、ionvaluesoveranyclosedneighborhoodisatleastone．Thatis，(Ⅳ【e】)=∑f(e7)≥1foreverye∈E·TheminusedgedominationnumberofagraphG，denotedt(G)istheminimalweightofalltheminusedgedominatingfunctionsofG；TheupperminusedgedominationnumberofagraphG，denotedr幺(G)，isthemaximumweightofalltheminimalminusedg

10、edomi