关于图的几类控制参数的研究-应用数学专业论文.docxVIP

STUDY ON SOME TYPES OF DOMINATION PARAMETERS OF GRAPHS A Dissertation submitted in fulfillment of the requirements of the degree of MASTER OF SCIENCE from Shandong University of Science and Technology by Chen Hongyu Supervisor: Associate Professor Chen Xuegang College of Information Science and Engineering May 2007 声 明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名： 日 期： AFFIRMATION I declare that this dissertation, submitted in fulfillment of the requirements for the award of Master of Science in Shandong University of Science and Technology, is wholly my own work unless referenced of acknowledge. The document has not been submitted for qualification at any other academic institute. Signature: Date: 山东科技大学硕士学位论文摘要 山东科技大学硕士学位论文 摘要 山东科技大学硕士学位论文摘要 山东科技大学硕士学位论文 摘要 1 1 2 2 摘 要 本论文共分六章： 第一章是综述部分，介绍了图的控制参数的发展状况和相关的一些工作。 第二章研究了给定控制数? ? 3 的连通二部图当最大度 ? ?G? ? n?? ?1时的最大边数 ? (n??)2 ? 4(n??) ? 是 ? ? 。 ? 4 ? 第三章讨论了独立控制双临界图的存在性及其一些性质，并且给出了由较小的独立 控制双临界图构造独立控制双临界图的方法。 第四 章刻划了 2-分支 控制数与控制数和连通控制数相等的一类树，即给出了 ?2 ?T? ? ? ?T? 和?2 ?T? ? ? ?T? 的充要条件。 c c c 第五章刻划了连通控制数和 2-分支控制数相等的树和单圈图，即给出了当图G是树 或单圈图时，? ?G? ? ?2 ?G? 成立的充要条件。 c c 第六章研究了 k-分支限制控制数的一些性质，并给出了当图 G 是树或单圈图时限制 控制数与 k-分支限制控制数相等的充要条件（ k=1,2）。 关键词：控制数，独立控制数， k-分支控制数，连通控制数，限制控制数， k-分 支限制控制数 Abstract There are six chapters in this thesis. The first chapter is overview, in which we introduce the developing status about Domination Parameter and some related work that we have done. In the second chapter, we show that the maximum number of edges that a connected bipartite graph with  n vertices, domination number  ? ? 3  and the maximum degree ? ?G? ? n? ? ?1  can have is ? (n??)2 ? 4(n??) ? ? ? 。 ? 4 ? In the third chapter, we discuss whether some particular classes of graphs are independent domination bicritical and study the properties of independent domination bicritical graphs, then ways of constructing an independent domination bicritical graph from smaller independent dom