图的全控制数和匹配数的可比较性  

Comparability on matching and total domination numbers in graphs

作　　者：孙天川[1] 康丽英[2] 

机构地区：[1]湖州师范学院数学系,浙江湖州313000 [2]上海大学数学系,上海200436

出　　处：《高校应用数学学报（A辑）》2006年第2期231-237,共7页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10101010;10571117);上海市重点学科建设资助项目;上海市教委发展基金(05AZ04);青年科学基金(01QN6262)

摘　　要：设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G)+1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.Let α（G） and γt（G） denote the matching and total domination numbers of a graph G, respectively. It is showed that （1）γt（G）≤α（G）＋1 for a generalized θ-graph G, and （2） γt（G）≤α（G） for a k-regular claw-free graph G,k≥3. In particular,the result in （2） deduces that Favaron＇s conjecture holds for k-regular claw-free graphs i. e. γt（G）≤1/2｜V（G）｜ for a graph G with minimum degree no less than 3. In addition, It is showed that α（G） and γt（G） are not comparable for graphs with minimum degree at most 2.

关 键 词：全控制集 匹配 K-正则图 无爪图 

分 类 号：O157.5[理学—数学]