圖[1,2]-集的性質(zhì)及算法研究.pdf

1、近年來,圖的支配理論已經(jīng)成為圖論最重要研究領(lǐng)域之一.一些學(xué)者發(fā)現(xiàn)無線網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一虛擬骨干網(wǎng)技術(shù),和圖的連通支配集有密切的關(guān)系.從那以后,支配集在研究無線網(wǎng)絡(luò)技術(shù)中占有重要的地位.
　　圖的[ j，k]-集的概念由Chellai等人在2013年提出.研究 j不小于1的[ j，k]-集的目的,來源于研究中需要一類特殊的支配集,例如,作為計(jì)算機(jī)網(wǎng)絡(luò)中的服務(wù)器集合,或作為需要監(jiān)控場(chǎng)合的監(jiān)控設(shè)備集合,不僅要求它們能夠有效地工作,而且要

2、求它們能花費(fèi)盡可能小的代價(jià)有效地工作,換句話說,不要有太多的冗余設(shè)備.
　　在本文中,我們主要研究圖的[1,2]-集和連通[1,2]-集的性質(zhì)和算法.圖G的一個(gè)支配集S被稱為[1,2]-集,如果對(duì)圖G的任意頂點(diǎn)v,滿足v∈ V(G)\S,1≤|N(v)∩S|≤2.我們稱圖的G的元素最少的[1,2]-集的元素個(gè)數(shù)為[1,2]-支配數(shù),簡(jiǎn)稱[1,2]-數(shù).如果圖的[1,2]-集的導(dǎo)出子圖是連通的,那么稱這個(gè)[1,2]-集是圖G的連通[

3、1,2]-集.
　　首先,我們考慮滿足γ(G)=γ[1,2](G)的圖并給出這樣的一些圖類蜘蛛圖和廣義Petersen圖P(n,1).
　　其次,我們研究了[1,2]-集和連通[1,2]-集之間的關(guān)系.我們研究了滿足連通支配集和連通[1,2]-集相等γc(G)=γc[1,2](G)或連通[1,2]-集等于頂點(diǎn)數(shù)n,即γc[1,2](G)=n的一些圖的結(jié)構(gòu)性質(zhì),并證明了二分圖的最小連通[1,2]-集問題是一個(gè)NPC問題.