若干圖類的全符號(hào)控制數(shù)的研究.pdf

1、圖的符號(hào)控制是圖論的一個(gè)重要的研究方向，不僅僅在實(shí)際生活中有著非常廣泛的應(yīng)用，例如，發(fā)射基站的選址、計(jì)算機(jī)通訊網(wǎng)絡(luò)和群決策等，而且人們也可以在計(jì)算的復(fù)雜性和算法設(shè)計(jì)、優(yōu)化理論、通訊網(wǎng)絡(luò)設(shè)計(jì)與分析等方面應(yīng)用圖的控制理論。我們研究圖的符號(hào)控制尤其是一些特殊圖的符號(hào)控制問題可以為解決一般的NP-困難問題提供重要的借鑒，具有較為重要的意義，圖的控制數(shù)的研究也因此一直受到廣大學(xué)者的關(guān)注。
　　本文主要研究路徑圖Pm與圈圖Cn的交圖的全符號(hào)控

2、制數(shù)。本文考慮的圖G均為有限簡單連通圖，根據(jù)Pm□Cn的點(diǎn)和邊鄰域的特點(diǎn)（在全符號(hào)控制研究中，頂點(diǎn)的鄰域中包含邊，邊的鄰域中也包含頂點(diǎn)），給出圖Pm□Cn的全符號(hào)控制數(shù)較好的上下界。
　　首先，根據(jù)前人的重要結(jié)論，對(duì)于任意圖G，如果圖G頂點(diǎn)的最小度為δ(G)，最大度為△(G)，頂點(diǎn)數(shù)為|V(G)|，邊數(shù)為|E(G)|，那么G的全符號(hào)控制數(shù)為:γ*s(G)≥([)δ(G)-△(G)+1/δ(G)+△(G)+1(|E(G)|+|V(G

3、)|)(])ρ(|E(G)|+|V'(G)|),
　　并且這個(gè)下界是可達(dá)的，其中ρ(s)表示s的奇偶性，即如果s是奇數(shù)時(shí)，則ρ(s)=奇數(shù)，如果s是偶數(shù)時(shí)，則ρ(s)=偶數(shù)。
　　對(duì)于Pm□Cn，根據(jù)上式可以得到γ*s（Pm□Cn）≥0，由于Pm□Cn的點(diǎn)和邊鄰域的特性，我們可知其全符號(hào)控制數(shù)γ*s（Pm□Cm）的下界可以比零更大一些。利用解析法證明Pm□Cn的全符號(hào)控制數(shù)γ*s（Pm□Cn）的下界，該下界比一般圖G的全符號(hào)