关于图的三类控制参数的研究

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

1、华中师范大学硕士学位论文关于图的三类控制参数的研究姓名：孙玲琍申请学位级别：硕士专业：运筹学与控制论指导教师：毛经中2003.1.1⑩硕士学位论文MASTER’STtIEsfS摘要本文主要研究了三类图的控制参数：图的下完美邻域数、图的受限控制数和图的。控制数，并分为三章分别进行了讨论。对于图的下完美邻域数，本文给出了e(c)=1(G)的充分必要条件，并讨论了一些特殊图类的下完美邻域数的上界，特别对于树采用了对所有点分层的方法进行了较细致的讨论，并给出了紧上界O(T)≤『；]．主要结论有：定理2．4：图G中，o(c)=7(c)当且仅当

2、e(c)=i(G)．定理2．儿：若丁是阶为n的树，扎≥3，则口(丁)≤『i77,]．对于图的受限控制数，本文主要讨论了其以边数为参数的上下界。主要结论有：命题31：n阶m边无孤立点连通图G中，*(G)≥2(n—m)，且等号成立当且仅当G—P4命题3．2：n阶图G中，若最大度为△、则*(G)≥忐命题34：n阶图G中，若最小度6≥2，则1，(G)≥n一格．定理36：G=(VE)是一个挖点m边，m≥行，最小度6≥2的简单连通图且不包含图Jl，以，如为子图，则1，(G)≤盟掣．最后对于图的n控制数，本文主要研究了zr0(G)与ir(C)的关

3、系，给出了Nordhaus—Gaddum型％(G)+％(G)的界，从而解决了[7]文后提出的两个问题．另外还讨论了％(G)+1l一。(G)不随Q变化的图类，在一定程度上解决了[7]文后提出的公开问题2．主要结论有：定理4．13：对于G=(UE)的任一个极大n一无赘集厶，存在一个基数≤ILl的极大无赘集．推论4．14：若G=(KE)，则ir(G)≤ir。(G)．⑧硕士学位论文MASTER’STHEsIS定理4．15：若G和舀无孤立点，则当0<(￥≤j1时，，y。(G)+'。(召)≤n；当；

4、词：图的下完美邻域数，图的受限控制数，图的n控制数儿ABSTRACTThisthesismainlystudiesthreekindsofdominatingparametersofgraphs：thelowerperfectneighborhoodnumberofgraphs，therefraineddominationnunl—betofgraphsandtheQ—dominationnumberofgraphs．anddiscussesthemwiththreerespectivechapters．．Onthelowerper

5、fectneighborhoodnumberofgraphs，thisthesisgivesthesufficientandnecessaryconditionsofo(a)=7(G)，anddiscussestheupperboundofthelowerperfectneighborhoodnumberofsomespecialgraphs．Especially，thisthesisdiscussesitontreeindetailsandgivesthetightupperboundO(T)≤『；1byusingthemetho

6、dofdividingthevertexesoftreeintolevels．Thesearethemainresultsbelow：Theorem2．4：IngraphG，o(a)=7(G)ifandonlyifo(a)=i(G)．Theorem2．11：IfTisatreewith竹vertices，n≥3，thenO(T)≤f；]．Ontherefraineddominationnumberofgraphs，thisthesismainlydiscussestheboundofitbyedgenumber．Theseareth

7、emainresultsbelow：Proposition3．1：IntheconnectedgraphGwhichhasnvertices，medgesandnoisolates，％(G)≥2(n—m)，andtheboundisattainedifandonlyifG=P4Proposition3．2：InthegraphGwithnvertices．ifthemaximumdegreeis△．then*(G)≥五n耵．Proposition3．4：InthegraphGwithnvertices、iftheminimumdeg

8、ree5≥2．then1，(G)≥n一持．Theorem3．6：IfG=(VE)isasimpleconnectedgraphwith扎verticesandrnedges，m≥n，whichdoesn’tcontainJ1，如，Ja