本文關(guān)鍵詞：圖的鄰域全控制數(shù)研究　出處：《華東師范大學》2016年博士論文　論文類型：學位論文

  更多相關(guān)文章： 控制集問題 鄰域全控制集問題 動態(tài)規(guī)劃 標號方法 樹 Mycielski’s圖

【摘要】：設(shè)G=(V,E)為一個簡單圖.圖G的一個控制集D是V的一個子集使得V\D中的每個頂點都和至少一個D中的頂點相鄰.G的控制數(shù)γ(G)是G的控制集的最小基數(shù).圖G的一個全控制集D是V的一個子集使得V中的每個頂點都至少和一個D中的頂點相鄰.G的全控制數(shù)γt(G)是G的全控制集的最小基數(shù).圖G的一個鄰域全控制集D(?)V是G的一個控制集且滿足：對每個頂點u ∈V\D,u至少有一個鄰點在N(D)中.G的鄰域全控制數(shù)γnt(G)是G的鄰域全控制集的最小基數(shù).若G沒有孤立點,則γ(G)≤γnt(G)≤γt(G)≤2γ(G)本文對與鄰域全控制數(shù)相關(guān)的問題進行研究,主要做了以下幾部分的工作：鄰域全控制數(shù)問題是指對于給定的圖G和數(shù)l,是否有γnt(G)≤l,即是否存在一個鄰域全控制集S使得|S|≤l?在本文第二章證明了鄰域全控制數(shù)問題對二部圖和分裂圖都是NP-完全的,然后用動態(tài)規(guī)劃的方法給出了樹的鄰域全控制數(shù)的一個線性時間算法,并且把該算法推廣到了點賦權(quán)樹的賦權(quán)鄰域全控制數(shù)情形上.在本文第三章,我們給出了所有滿足γnt(T)=2γ(T)的樹T的集族τ,并對這樣的樹的結(jié)構(gòu)進行了刻畫.圖G的一個填裝是指G的一個頂點集S使得S中任意兩點在G中的距離都至少為3.一個圖G的填裝數(shù)ρ(G)是指G的填裝的最大基數(shù).用標號的方法構(gòu)造出了所有滿足γNT(G)=ρ(G)的圖G的集族以及所有控制數(shù)等于鄰域全控制數(shù)的森林集族.在本文第四章,我們考慮圖的邊數(shù)、階數(shù)和鄰域全控制數(shù)的關(guān)系,證明了若G是一個n階m條邊的連通圖且G≠K2,則M≤?(n—γnt(G))(n一γnt.(G)+3).接著考慮了圖的直徑和其補圖的鄰域全控制數(shù)的關(guān)系,證明了若G沒有孤立頂點且dim(G)≥3則γnt(G)=2.在本文第五章,我們用概率方法給出了一個n階且最小度δ≥2的圖G的鄰域全控制數(shù)的上界.然后給出了一個最小度δ(G)≥2且圍長9(G)≥5的連通圖G的鄰域全控制數(shù)的上界.在本文第六章,我們考慮圖G的Mycielski's圖μ(G)的鄰域全控制數(shù),證明了對一個沒有孤立點的圖G有γnt(μ(G))≤γnt(G)+1證明了對任意給定的正整數(shù)k1,存在一個沒有孤立點的圖G,使得差值γnt(G)一γnt(μ(G))等于k.接著考慮了μ(G)的鄰域全控制數(shù)和G的控制數(shù)之間的關(guān)系,證明了對任意圖G,γ(G)+1≤γnt(μ(G))≤γ(G)+2當γ(G)=1時：給出了γnt(μ(G))=γ(G)+1的充要條件,當γ(G)≥2時,給出了γnt(μ(G))=γ(G)+1的一個充分條件.
[Abstract]:璁綠=(V,E)涓轟竴涓畝鍗曞浘.鍥綠鐨勪竴涓帶鍒墮泦D鏄疺鐨勪竴涓瓙闆嗕嬌寰梀\D涓殑姣忎釜欏剁偣閮藉拰鑷沖皯涓，

本文編號：1343564