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

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

2、求它們能花費盡可能小的代價有效地工作,換句話說,不要有太多的冗余設備.
　　在本文中,我們主要研究圖的[1,2]-集和連通[1,2]-集的性質(zhì)和算法.圖G的一個支配集S被稱為[1,2]-集,如果對圖G的任意頂點v,滿足v∈ V(G)\S,1≤|N(v)∩S|≤2.我們稱圖的G的元素最少的[1,2]-集的元素個數(shù)為[1,2]-支配數(shù),簡稱[1,2]-數(shù).如果圖的[1,2]-集的導出子圖是連通的,那么稱這個[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]-集等于頂點數(shù)n,即γc[1,2](G)=n的一些圖的結(jié)構(gòu)性質(zhì),并證明了二分圖的最小連通[1,2]-集問題是一個NPC問題.