关于图的(全){k}-控制划分数的研究.pdf

《关于图的(全){k}-控制划分数的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国料孽教求大誊硕士学位论又关于图的(全)

2、rof．XinminHouApril，2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：晕车毖中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文

3、被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。

4、囱公开口保密——年作者签名：罕牟妊签字日期：致12．厶。垒趋“髫一虹逝一名期签日师字导签摘要本文致力于研究图的{忌)一控制划分数以及全{七]．一控制划分数。控制划分的英文为“domatic”，该词来源于“dominating”与“chromatic”，即“控制”与“染色”。一方面，图的控制划

5、分数的定义依赖于控制集的概念；另一方面，控制划分数的概念又与染色数有着相似之处。图的控制划分数这一概念最早由Cockayne与Hedetniemi提出。之后，Cockayne等人又利用全控制集的概念提出了图的全控制划分数。作为对控制划分数和全控制划分数的推广，Sheikholeslami与Volkmann提出了_[尼)．控制划分数与全{尼)一控制划分数的概念。本文内容将安排如下。在第一章中，我们将简单宏观的介绍控制划分的相关概念及背景。第二章将主要介绍(全)控制划分相关的基本概念及定义，以及前人的一些主要结

6、果。第三章将引入(全)控制划分数的推广概念及定义，介绍Sheikholeslami与Volkmann等人的若干结论以及本人的一些研究成果。在第四及第五章中，本人将利用第三章中介绍的一些性质及结论分别确定轮图及完全图的(全)f庇’一控制划分数。第六章将对全文进行总结，并提出一个相关的开放性问题。关键词：{克]-一控制划分数，全让]．一控制划分数，轮图，完全图原书空白页不缺内容ABSTRACTThispaperisfocusontheresearchon{尼>一domaticnumberandtotal{七)-

7、domaticnumberofgraphs．Theword‘‘domatic’’wascreatedfromthewords“dominating’’and“chromatic”ThedomaticnumberofagraphisdefinedUS—ingtheconceptofdomiatingset；ontheotherhand，thisconceptissomewhatanalogoustothechromaticnumberofagraph．Theconceptofdomaticnumberofag

8、raphwasfirstintroducedbyCockayneandHedetniemi．Later，Cockayne，Dawes，andHedetniemiintroducedthetotaldomaticnumberofagraphusingtotaldominatingset．Asageneralizationofdomaticnumberandtotaldomaticnumber，SheikholeslamiandVolkmannintroducedtheconceptof．[尼>一domatic

9、numberandtotal{七)·domaticnumberofgraphs．Thispaperwillbearrangeda,sfollows．Inthefirstchapter，wewillintroducetheconceptionofdomaticandsomebackgroundgenerally．Thesecondchapterisanintroductionto(total)domaticnumb