圖的控制參數(shù)研究.pdf

1、本文一共五章。第一章介紹一些圖論的基本概念和控制參數(shù)的預(yù)備知識。然后，我們分別對笛卡爾乘積圖的成對控制數(shù)，強(qiáng)全控制邊臨界圖，以及樹的上控制數(shù)這三個問題進(jìn)行研究。最后，我們總結(jié)本文的主要結(jié)果，并提出幾個有待繼續(xù)研究的問題。@2 記γ<,P>(G)和ρ<,P>(G)分別為圖G的成對控制數(shù)和成對packing數(shù)。記G□H為圖G和圖H的笛卡爾乘積。稱圖G為(ρ<,P>，γ<,P>)一圖，如果ρ<,P>(G)=γ<,P>(G)。在第二章，我們證明

2、了，對于任意的不含孤立點(diǎn)的圖G和圖H，其中至少一個是不含三角形的(ρ<,P>，γ<,P>)一圖，有γ<,P>(G)γ<,P>(H)≤2γ<,P>(G□H)。進(jìn)一步在一般情況下，我們證明了，對于任意的不含孤立點(diǎn)的圖G和圖日，有γ<,P>(G)γ<,P>(H)≤7γ<,P>(G□H)。 不含孤立點(diǎn)的圖G，如果它的任意兩個不相鄰頂點(diǎn)u，υ，有γ<,t>(G+uυ)<γ<,t>(G)，則圖G是全控制邊臨界的，簡稱γ<,t>-臨界。γ<,

3、t>-臨界圖G，如果對任意頂點(diǎn)υ∈V(G)存在G的一個基數(shù)為γ<,t>(G)-1的控制集D，使得υ∈D且G[D]除υ外不含孤立點(diǎn)，則圖G是強(qiáng)γ<,t>-臨界的。在第三章，我們研究了竹臨界圖和強(qiáng)γ<,t>-臨界圖的性質(zhì)，并給出了一個構(gòu)造強(qiáng)γ<,t>-臨界圖的方法。 記γ(G)和г(G)分別為圖G的控制數(shù)和上控制數(shù)。在第四章，我們給出了一個確定樹T上控制集的算法，并利用該算法分別刻劃了滿足條件，γ(T)+г(T)=n和γ(T)=г(