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

  更多相關(guān)文章： 控制集問(wèn)題 鄰域全控制集問(wèn)題 動(dòng)態(tài)規(guī)劃 標(biāo)號(hào)方法 樹(shù) Mycielski’s圖

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

本文編號(hào)：1343564