本文關(guān)鍵詞：（n-4）—正則圖的約束數(shù)的界

  更多相關(guān)文章： 約束數(shù) 控制數(shù) 反證法 (n-4)-正則圖

【摘要】：圖的約束數(shù)概念最早是作為衡量網(wǎng)絡(luò)連接失敗脆弱性的一個重要參數(shù)由Fink et al在1990年正式提出的,由于圖的約束數(shù)問題的解決依賴于圖的控制數(shù),而圖的控制數(shù)是圖論中一個經(jīng)典而重要的內(nèi)容,受到學術(shù)界的廣泛關(guān)注,因而對圖的約束數(shù)問題的研究具有很大的學術(shù)價值.同時,由于一般圖的控制數(shù)問題很早之前就被Garey和Johnson[2]證明是NP-完全的,因此要解決任意圖的約束數(shù)問題也是非常困難的.但對于一些特殊結(jié)構(gòu)的圖,已經(jīng)有很多很好的成果.正則圖作為一類特殊的圖,其約束數(shù)問題的解決自然會引起關(guān)注.在文獻[10]中,Fink et al證明了b(Kn)=「n/2]；b(Kn1,n2,n3…,nt)=2t-1,其中n1=n2=n3=…=nt=2.在2012年,Hu和Xu[3]證明了對于任意的(n-3)-正則圖均有b(G)=n-3.然而對于k-正則圖(3≤k≤n-4),這些正則圖的約束數(shù)的值的研究還沒有取得任何進展.本文遵循此思路,重點研究(n-4)-正則圖的約束數(shù)問題.本文共有四章內(nèi)容,主要是研究(n-4)-正則圖的約束數(shù)問題.第一章給出了文章用到的基本概念,已有的結(jié)論以及主要結(jié)果.第二章主要證明：任意(n-4)-正則圖的控制數(shù)為2,且其約束數(shù)的上界為(n-4).第三章主要證明：(n-4)-正則圖約束數(shù)的下界為(n一7).最后一章節(jié)主要給出了一些值得繼續(xù)深入研究的問題.
【關(guān)鍵詞】：約束數(shù) 控制數(shù) 反證法 (n-4)-正則圖
【學位授予單位】：南京師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要5-6
• Abstract6-7
• 第1章 緒論7-9
• 1.1 基本概念7-8
• 1.2 k-正則圖的約束數(shù)問題及已有的結(jié)論8
• 1.3 本文的主要研究結(jié)果8-9
• 第2章 (n-4)-正則圖的約束數(shù)的上界9-11
• 2.1 (n-4)-正則圖的控制數(shù)9-10
• 2.2 本章主要結(jié)論10-11
• 第3章 (n-4)-正則圖的約束數(shù)的下界11-46
• 3.1 本章主要結(jié)論11-12
• 3.2 引理證明12-19
• 3.3 定理證明19-46
• 第4章 可進一步研究的問題46-47
• 參考文獻47-48
• 致謝48

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 宋曉新;關(guān)于3正則圖的三匹配交猜想(I)[J];數(shù)學研究;2002年04期

2 宋曉新;關(guān)于3正則圖的三匹配交猜想 (Ⅱ)(英文)[J];數(shù)學季刊;2002年04期

3 嚴謙泰;關(guān)于2K階K正則圖強協(xié)調(diào)性的研究[J];安陽師范學院學報;2003年02期

4 嚴謙泰;關(guān)于5-正則圖的強協(xié)調(diào)性[J];大學數(shù)學;2003年02期

5 閆桂英,許保光,吉日木圖;關(guān)于3-正則圖的路分解[J];系統(tǒng)科學與數(shù)學;2004年02期

6 鐘波,謝挺;關(guān)于正則圖的路分解[J];西華大學學報(自然科學版);2005年04期

7 周后卿;徐立新;;正則圖的強積的秩[J];吉首大學學報(自然科學版);2007年01期

8 梁志和;;完全圖循環(huán)分解成2-正則圖[J];應(yīng)用數(shù)學學報;2008年06期

9 南小康;;3-正則圖的1-因子與割邊數(shù)[J];蘭州大學學報(自然科學版);2008年S1期

10 李光暖;許寶剛;;關(guān)于正則圖存在平衡劃分的一些結(jié)果[J];高校應(yīng)用數(shù)學學報A輯;2009年03期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 ;Hamilton Circuits in Cubic Polyhex Graphs[A];中國運籌學會第六屆學術(shù)交流會論文集（下卷）[C];2000年

2 師海忠;;正則圖連通圈:多種互連網(wǎng)絡(luò)的統(tǒng)一模型[A];中國運籌學會第十屆學術(shù)交流會論文集[C];2010年

中國博士學位論文全文數(shù)據(jù)庫 前6條

1 文飛;若干圖類的譜特征問題研究[D];新疆大學;2015年

2 程希明;只有三個不同特征值的圖[D];中國科學技術(shù)大學;2016年

3 汪定國;正則圖的獨立集與團橫貫[D];上海大學;2013年

4 張翠;s-正則圖和Hamilton圖[D];北京交通大學;2011年

5 劉奮進;圖鄰接譜確定問題的一些研究[D];新疆大學;2012年

6 邵澤輝;Ramsey理論中圖的構(gòu)造與計算[D];華中科技大學;2008年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 秦艷麗;9度1—正則Cayley圖的分類[D];廣西大學;2015年

2 李玉萍;三正則雙軌道圖的連通性和極大非正則圖[D];新疆大學;2015年

3 王兆;五正則圖的斜能量研究[D];青海師范大學;2015年

4 嚴卉;（n-4）—正則圖的約束數(shù)的界[D];南京師范大學;2015年

5 顏娟;第Ⅱ類正則圖的色特征[D];新疆大學;2006年

6 蘭培挺;一些4-正則圖最優(yōu)擴張的演化[D];北京交通大學;2007年

7 趙承業(yè);三正則圖及其相關(guān)圖的交叉數(shù)問題[D];大連理工大學;2002年

8 王丹;正則圖的交叉數(shù)[D];大連理工大學;2002年

9 郝欣;具有相同路徑層矩陣不同構(gòu)的r-正則圖[D];大連理工大學;2004年

10 周后卿;正則圖在某些二元運算下的秩[D];湖南師范大學;2006年

，

本文編號：696696