圖的控制參數(shù)和一類極值問題.pdf

1、圖的某些參數(shù),如圖的控制參數(shù),因為其在圖論的研究以及現(xiàn)實世界的各種應用中固有的重要性,而得到廣泛的研究和發(fā)展.圖的控制集定義為圖中的一個點的集合,使得圖中其它任何一個點都與該點集中的某個點鄰接.確定圖的控制集問題在網(wǎng)絡的目標、安全裝置和便利設施等的定位的方面有很大用處.在過去的30多年里,對圖的各種控制參數(shù)的研究已經(jīng)成為圖論研究的一個重要領域,迄今為止關于圖的控制參數(shù)問題的研究已有上千篇文章,現(xiàn)在已有近百種類型的控制形式得到研究.該文主

2、要工作包括以下幾個方面:(1)簡單介紹了幾種常見的控制參數(shù)的概念和應用,以及它們的上下界和相互關系;(2)討論了連通圖G的連通k-控制數(shù)γ<'c><,k>(G)的上下界,并證明了不等式γ<'c><,k>(G)≤(2k+k+1/2)ir<,k>(G-2K);(3)給出在樹和單圈圖中,2-控制數(shù)和連通2-控制數(shù)相等的充分必要條件,并加以證明;(4)討論了給定連數(shù)和頂點數(shù)的圖的一類極值問題.對于所有給定邊數(shù)和頂點數(shù)的圖,我們將刻畫出其所有頂點