笛卡尔乘积图的配对控制数.pdf

《笛卡尔乘积图的配对控制数.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据DominationNumberofSomeCartesianAuthor：壁坠垒塾g塾垒iY坠垦望指导老师：呈差查Supervisor：丛垒堡翊i曼专业：麴堂Major：丛璺坐宝磐垒堂§学MasterofScienceMarch，2015万方数据笛卡尔乘积图的配对控制数摘要设图G=(UE)是一个没有孤立点的无向简单图．如果y的一个非空子集D满足y＼D中的每个顶点都有一个邻点在D中，则称D是图G的一个控制集．迸一步，如果D是图G的一个控制集并且由D导出的子图CDl中有一个完美匹配，则称_D是图G的一个配对控制集．一个图G的配对控制

2、数，即图G的最小的配对控制集的大小，记为％(G)．配对控制数最初是由Haynes和Slater提出的，同时他们证明了对于一般图，确定其配对控制数是NP-完全的．本文确定了一些特殊图的配对控制数，主要内容分为四章．第一章介绍了配对控制数的背景以及本论文所涉及的有关定义，并对路和圈的笛卡尔乘积的配对控制数的研究现状做了一个综述．第二章根据圈和圈的笛卡尔乘积的结构，利用反证法，确定了佗圈和5圈的笛卡尔乘积的笛卡尔乘积的配对控制数．第三章给出仡圈和m(m=2．3)路和n路和m(m=3，4，5)圈的配对控制数．第四章对本文进行了总结并给出笛卡尔乘积

3、图配对控制数的一些可研究问题．关键词：笛卡尔乘积图：控制数；全控制数；配对控制数万方数据ThepaireddominationnumberofsomeCartesianproductgraphsABSTRACTLetG=(KE)beasimpleundirectedgraphwithoutisolatedvertices．AsetDcVisadominatingsetofGifeveryvertexinVIDisadjacenttoatleastoneveltcxinD．Apaired—dominatingsetofagraphGisad

4、ominatingsetofverticeswhoseinducedsubgraphhasaperfectmatching，whilethepaired-dominationnumber,denotedby％(G)，istheminimumcardinalityofapaired—dominatingsetinG．ThepaireddominationnumberwasfirstproposedbyHaynesandSlater，andtheyprovedthattheproblemofdeterminingthepaireddomina

5、tionnumberofgeneralgraphsisNP—complete．Inthisthesis，wedeterminedthepaireddominationnumberofsomespecialgraphsInthefirstchapter,WCintroducethebackgroundandsomedefinitions，andgiveabriefsurveyofthepaireddominationnumberofthecartesianproductofpathswithcy-cles．Inthesecondchapte

6、r,wemainlydeterminethepaireddominationnumberoftheCartesianproductofCk口Gaccordingtothestructuralcharacteristicsofthecartesianproductofcycleswithcycles．Inthethirdchapter,wedeterminethepaireddominationnumberoftheCartesianproductofG口B。(m=2，3)andCfm口R(m=3，4，5)Inthefourthchapte

7、r,wesummarizethispaperandproposesomefurtherquestionofpaireddominationnumberofthecartesianproduct．KEYWORDS：Cartesianproductgraph；dominationnumber；totaldominationnumber；paireddominationnumberII万方数据目录摘要⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．IABSTRACT．⋯⋯⋯．⋯⋯．．．．．．．．．．．⋯．．．．．．．．．．．．．．．．．．．

8、．．．．．．．．．．⋯．．．．Ⅱ目录⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．III1绪论．．⋯⋯．．．．．．．····⋯···⋯··-⋯⋯··⋯⋯⋯··⋯········⋯···一