图几类全控制参数

《图几类全控制参数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要在过去近四十年里，随着计算机科学和网络通讯技术的飞速发展，图论研究也呈现出异常活跃的趋势，而控制数理论的研究是其中发展最快的领域之一．图的控制数理论作为图论的一个重要研究方向，在相关学科领域，例如计算机科学、通信网络、组合优化、编码理论、监视系统以及运筹学等领域具有广泛的应用．随着研究的深入，各种新的控制参数不断提出和研究，而且与图论的经典理论相互交融，精彩纷呈．图的(全)控制函数就是图的经典(全)控制数的一类自然推广．由于图的(全)控制函数的引入，致使利用函数性质来研究各类(全)控制数成为可能．目前，各类全控制函数已成为图的控制理论中一个崭新的研究方向．关于全控制函数的研究主

2、要集中在四个方面。(1)确定各种控制参数的上下界，在一些特殊图上计算它们的值；(2)寻找各种控制参数之间的关系；(3)给出极端图类的结构性质的刻画；(4)各种控制参数计算复杂性的研究及其算法的设计．本文所做的工作主要包括以下两大部分：第一部分，首先给出了负全l【-控制函数是极小的充要条件；接着研究了一些特殊图如路、完全图、完全二部图中负全lc-控制数的情况；最后建立了一般图和树中负全l啦制数的下界及k=佗时，百的几个下界(有关结果被ⅨJournalofShanghaiUniversity》录用)。第二部分，得到了全符号局部控制数在一般图和正则图中的下界以及在完全二部图‰，。中的上界

3、；并求出了圈Gk和星甄，。中诏的精确值(有关结果已投Ⅸ上海大学学报》)．关键词：图；全控制函数；负全危j空制数；负全控制数；全符号局部控制数；界．ABSTRACTWithinthepastDeal"fortyyears，concurrentwiththegrowthofcomputerscienceandcommunicationnetworks，graphtheoryhasseenexplosivegrowth．Thestudyofdominationingraphsisoneofthefastestgrowinga1：easwithinit．As叭importantresear

4、chfieldingraphtheory,dominationtheoryhasmanyandvariedapplicationsinrelatedfields，suchascomputerscience，communicationnetworks，combinatorialoptimization，codingtheory,monitorsystemandoperationsresearch．Withresearchingdeeply,manydifferenttypesofdominationparametershavebeenputforwardandrese缸ched，es

5、peciallyminglewiththeclassicaltheoryofgraphtheorymutually,whichisaccompaniedbybrilliantphenomenon．(Total)dominatingfunctioningraphsisthenaturalvariationofclassical(to-tal)dominationnumber．Becauseofintroducingtheconceptof(total)dominatingfunctionintographs，itispossibletostudy(total)dominationin

6、termsoffunctionalproperties．Atpresent，thestudyonseveralkindsofdominatingfunctionsisanewandchallengableresearchfieldindominationtheory．Andmostresearchersintotaldominatingfunctionconcentratetheirattentiononthefollowingfouraspects：(1)Determiningtheboundsonseveraldominationparametersandcomputingth

7、eirvalueinsomespecialgraphs；(2)Findingtherelationshipsbetweendomination-}elatedparameters；(3)Givingcharacterizationofextremegraphs’structuralprop-erties；(4)Studyingthealgorithmiccomplexityofdomination-relatedparametersanddesigningalgori