关于树的控制问题与强乘积图约束数的研究

发布时间：2018-03-10 08:13

  本文选题：控制数　切入点：填充数　出处：《兰州大学》2015年博士论文　论文类型：学位论文

【摘要】：图的控制数是图的基本的不变量之一,也是反映网络性能的一个参数.图的约束数是指让图的控制数增大所需删除的最少边的数目.它能衡量在通信线路发生故障情况下互联网络脆弱性.然而,图的控制数和约束数的计算已经分别被证明是NP-完全和NP-困难问题.许多学者都致力于图的最小控制集与最小约束边集的结构和性质的研究,以及计算特殊图类的控制数与约束数的精确值或者给出它们界.一般来说,计算一个图的约束数比计算其控制数更为困难.本论文的研究内容包括树的控制问题和强乘积图的约束数.其中,对树控制问题的研究又为强乘积图约束数的计算提供一定的理论支撑.本文共分为五章.第一章首先介绍一些本文用到的基本概念和记号.然后分别介绍树的构造与刻画和乘积图约束数的研究背景,问题的提出以及研究进展.最后介绍本文所得到的主要结果.在第二章中,根据与最小控制集的关系,我们把图的顶点可分为普遍点、空白点和可变点三类.(图的普遍点是指属于图所有最小控制集的点,空白点是指不属于图任何最小控制集的点,可变点是指既不是普遍也不是空白的点.)我们通过定义了9种图的操作分别给出了仅包含可变点,仅包含非普遍点和仅包含非可变点的树的构造.在第三章中,我们给出了一棵树的约束数为2的一个充分条件和一个充要条件：如果树T的顶点数至少为3且它的所有顶点都是可变的,那么T的约束数为2；非平凡树T的约束数为2当且仅当T的所有γ-可孤立点构成T的一个最大2-填充,(图的一个顶点被称为是γ-可孤立点,如果去掉该点后图的控制数恰好减少1).另外,我们还得到了一个图和一棵树的强乘积图最小控制集的一些性质.在第四章中,我们得到两条路的强乘积图约束数的精确值.即,对任意两个正整数m≥2和讫≥2,若(r(m),r(n))=(1,1)或(3,3)则b(Pm(?)Pn)=7-r(m)-r(n)；否则b(Pm(?)Pn)=6-r(m)-r(n)其中,r(T)是一个关于正整数t的函数,定义为r(t)=1若t≡1(mod 3)；r(t)=2若t≡2(mod 3)；r(t)=3若t三0(mod 3).在第五章中,我们得到一个完全图与一条路的强乘积图约束数的精确值.即,对任意两个正整数m≥1和n≥2,有b(Km(?)Pn)=[m/2]若n≡0(mod 3)；m若n≡2(mod 3)；[3m/2]若n≡1(mod 3)在这个结果的基础上,我们进一步得到了一个完全图和一类特殊的星状树的强乘积图约束数的精确值.在第六章中,我们给出了一些在不同条件下一个非空图与一棵树的强乘积图约束数的上界.并且引用第五章的结果作为例子,指出我们所得到的上界都是紧的.
[Abstract]:The domination number is one of the basic invariants of graphs, but also reflect the performance of the network. A parameter constraint graph number refers to the number of graph control the minimum number of edges required increase delete. It can measure the failures of Internet vulnerability in the communication line. However, the number and the number of control calculation the constraint graph has been proved to be NP- complete and NP- problems. The structure and properties of the minimum dominating set and minimal constraint, many scholars are committed to the edges of the graph set, and the exact value or give them control number and the bounded number constraint computation of special graphs. In general, the number of constraints is calculated a map of the calculation of the number ratio control is more difficult. The number of constraints is the research contents of this thesis include the tree control problem and strong product graphs. Among them, the calculation of the research provide some control problems for tree and strong product graphs of the number of constraints On the support. This paper is divided into five chapters. The first chapter introduces some basic concepts and mark used in this paper. The research background and then introduces the structure and the number of product description and constraint tree, the progress and the problem of the research. Finally, the main results obtained in this paper. In the second chapter, according to the relationship with the minimum control set, we put the vertices of a graph can be divided into common point, point blank and variable point three. (generally refers to the point of graph graph all minimum dominating set point, point blank that does not belong to any minimum set point control chart, variable point is that neither universal nor blank the point.) we defined 9 kinds of graph operations are given only contain variable, contains only non common point and contains only non variable point tree structure. In the third chapter, we give the number of constraints of a tree is 2 a sufficient condition and a 涓�鍏呰�佹潯浠讹細濡傛灉鏍慣鐨勯《鐐规暟鑷冲皯涓，

本文编号：1592483