关于图的三类控制参数的分析.pdfVIP

硕士学位论文 ⑩MASTER’STtIEsfS 摘 要 本文主要研究了三类图的控制参数：图的下完美邻域数、图的受限控制数 和图的。控制数，并分为三章分别进行了讨论。 对于图的下完美邻域数，本文给出了e(c)=1(G)的充分必要条件，并讨 论了一些特殊图类的下完美邻域数的上界，特别对于树采用了对所有点分层 的方法进行了较细致的讨论，并给出了紧上界O(T)≤『；]．主要结论有： 定理2．4：图G中，o(c)=7(c)当且仅当e(c)=i(G)． 定理2．儿：若丁是阶为n的树，扎≥3，则口(丁)≤『i77,]． 对于图的受限控制数，本文主要讨论了其以边数为参数的上下界。主要结 论有： 命题3 且仅当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)的关系，给出 个问题．另外还讨论了％(G)+1l一。(G)不随Q变化的图类，在一定程度上解 决了[7]文后提出的公开问题2．主要结论有： 定理4．13：对于G=(U E)的任一个极大n一无赘集厶，存在一个基数≤ILl 的极大无赘集． 推论4．14：若G=(KE)，则ir(G)≤ir。(G)． 硕士学位论文 ⑧MASTER’STHEsIS ；o≤1时，％(G)+％(虿)≤2n一4． 关键词：图的下完美邻域数， 图的受限控制数， 图的n控制数 儿 ABSTRACT of of threekinds Thisthesis studies mainly dominatingparametersgraphs： nunl— of refraineddomination thelower number neighborhoodgraphs，the perfect themwith the numberof discusses betof and Q—dominationgraphs．and graphs three ． respectivechapters． number thesis the thelower of On perfectneighborhoodgraphs，thisgives the bound and conditionsof discusses sufficient necessary upper