论文部分内容阅读
图的控制数γ(G)，独立控制数i(G)，(上)全无赘数(IRt(G))irt(G)和(上)无赘数(IR(G))ir(G)是重要的图结构参数，对它们的研究已经有了很长一段历史。关于控制数γ(G)和独立控制数i(G)，D.P.Sumner和P.Blitich在文[10]中提出如下猜想：如果G为3-γ-临界图，则有γ(G)=i(G)。迄今为止，该猜想尚未得到证明。王春香等在文[19]中给出该猜想成立的一个充分条件，同时猜想在3-(γ，d)-临界图中有γ(G)=i(G)。本论文第一部分利用不含给定的禁用子图条件给出上述第一个猜想成立的一个新的充分条件，同时给出第二个猜想在d=2时成立的一个充分条件。
文[30]证明了：确定任意一个图的(上)全无赘数(IRt(G))irt(G)是一个NP-困难问题。2002年OdileFavaron在[31]中研究了全无赘集理论方面的问题。他们刻画了满足irt(G)=IRt(G)=0的图；研究了irt(G)≥1的树；刻画了满足irt(G)=1的树，同时他们提出了这样一个问题：如何用图的最小度δ来刻画IRt(G)和irt(G)的界?本论文第二部分主要回答这个问题，给出了两个用图的最小度δ表示的IRt(G)和irt(G)的上界，即IRt(G)≤(n-1)(△-1)/△+δ-1和IRt(G)n/19+(△+1)δ/(△-1)△，并且我们证明了这两个上界是可达的，进一步，给出上界可达的必要条件。本论文第三部分研究了上无赘数IR(G)的稳定数SN(G)-满足IR(G-E′)=IR(G)的图的最大可去边数E，本文证明了：(1)对于n(n≥2)阶非空连通图G，有SN(G)≤n-2。(2)当IR(G)≥2时，有SN(G)≤(IR(G)-1)△(G)-1。