【作者】 华洪波；

【导师】 邓汉元；

【作者基本信息】 湖南师范大学 ， 基础数学， 2004， 硕士

【摘要】 图的控制数γ(G),独立控制数i(G),(上)全无赘数(IR_t(G))ir_t(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]证明了:确定任意一个图的(上)全无赘数(IR_t(G))ir_t(G)是一个NP-困难问题。2002年Odile Favaron在[31]中研究了全无赘集理论方面的问题。他们刻画了满足ir_t(G)=IR_t(G)=0的图;研究了ir_t(G)≥1的树;刻画了满足ir_t(G)=1的树,同时他们提出了这样一个问题:如何用图的最小度δ来刻画IR_t(G)和ir_t(G)的界?本论文第二部分主要回答这个问题,给出了两个用图的最小度δ表示的IR_t(G)和ir_t(G)的上界,即IR_t(G)≤((n-1)(△-1))/(△+δ-1)和IR_t(G)≤n/(1+(((△+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。 从而填补了在图的无赘集的性质方面研究的空白。更多还原

【Abstract】 Domination number γ(G) , independant domination number i{G) , the (upper) total irredunance number (IR_t(G))ir_t(G) and the (upper) irredunadance number (IR(G))ir(G)a.re all important graphic structural parameters and has been studied for a long history.D.P.Sumner and P.Blitich conjectured in [10] that if G is a 3 - γ-critical graph ,then γ(G) = i(G).But this conjecture hasn’t been proved till now.In [19] , Wang chunxiang et al gave a sufficient condition on which the above conjecture holds and raised a new conjecture that if G is a 3 - (γ, d)- critical graph ,then γ(G) = i(G) . In the first part of my master dissertation , I gave a new sufficient condition on which the first conjecture holds and a sufficient condition on which the second one holds when d = 2.In [30],S.M.Hedetniemi et al showed that it’s a NP-hard problem to determine the (upper)total irredundance number for any given graph . In 2002 Odile Favaron et al studied the total irredundant set in theory. They’ve characterized the graph satisfying the equality ir_t{G) = IR_t(G) = 0 and the tree with ir_t(G) - 1. They also investigated the regular graph satisfying ir_t(G) > 1 at the same time. In the end, they questioned whether the bound of the (up-per)total irredundance number can be phrased in terms of the minimum degree S(G) ?In the second one of my paper , I mainly dealt with this question by giving two upper bounds for the (upper)total irredundance number in terms ofthe minimum degree 8(G) ,I showed that these two bounds are reachable and gave the necessary condition on which the bounds are attainable .In the third part of my paper , I investigated the stability number SN(G) of the upper irredundance IR(G)-the maximum edges E whose removal will result in IR{G - E’) = IR(G) . I showed that(l)For any nonempty connected graph G with order n greater than or equal to 2 ,SN(G) ≤ n - 2.(2)SN(G) ≤ (IR{G) - l)△(G) - 1 holds if IR{G) ≥ 2.更多还原