本文選題：控制數　切入點：填充數　出處：《蘭州大學》2015年博士論文　論文類型：學位論文

【摘要】：圖的控制數是圖的基本的不變量之一,也是反映網絡性能的一個參數.圖的約束數是指讓圖的控制數增大所需刪除的最少邊的數目.它能衡量在通信線路發(fā)生故障情況下互聯(lián)網絡脆弱性.然而,圖的控制數和約束數的計算已經分別被證明是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 涓厖瑕佹潯浠訛細濡傛灉鏍慣鐨勯《鐐規(guī)暟鑷沖皯涓，

本文編號：1592483