關(guān)于圖的全無贅數(shù)的討論.pdf

1、由于控制數(shù)理論的研究越來越引起人們的重視,人們對(duì)控制數(shù)有了更深入的了解,提出了不同的控制數(shù),例如全控制數(shù)、小控制數(shù)、負(fù)控制數(shù)、連通控制數(shù)等.這些類型的控制數(shù)的量的關(guān)系在圖的結(jié)構(gòu)中起著重要的作用.在長期的研究中,一些研究者們發(fā)現(xiàn)研究圖的無贅數(shù)可以使人更深入的了解圖的控制數(shù)理論.到目前為止,對(duì)于圖的無贅數(shù)的研究已經(jīng)越來越深入,研究者們也已經(jīng)得到了圖的無贅集的大量的性質(zhì).Cockayne和Mynhardt更是認(rèn)為對(duì)全無贅數(shù)的討論有利于我們更好

2、的了解全控制數(shù).事實(shí)上,Hedetniemi et al.在文[8]中給出了圖的全無贅數(shù)的概念,并討論了一些特殊圖的全無贅數(shù),而Odile favaron et al.在文[9]中進(jìn)一步得到了圖G滿足ir<,t>(G)=0的充分必要條件和滿足ir<,t>(T)=1的樹T的結(jié)構(gòu).該文主要討論的是滿足ir<,t>(G)=1的圖G的某些結(jié)構(gòu)特征及滿足ir(G)=ir<,t>(G)=1的圖G的構(gòu)成.得到的主要結(jié)果如下:(1)圖G=(V,E)是經(jīng)

3、克隆-收縮后得到的圖,v<,0>∈V,以v<,0>為第0層將圖G中的點(diǎn)分層,若層數(shù)k>4,則有ir<,t>(G)≥2;(2)圖G為連通圖,v<,0>∈G,滿足N[v<,0>]=V(G),若G<,1>,G<,2>,…,G<,k>為G-v<,0>的所有的連通分支,則Ξk<,0>∈{1,2,…,k},使得ir<,t>(G<,k0>)=1,ir<,t>(G<,i>)=0,i=1,2,…,k<,0>-1,k<,0>+1,…,k.其中對(duì)ir(G)=