导出匹配可扩图的韧度  

Toughness of Induced Matching Extendable Graphs

作　　者：周素静[1] 王峥[1] 李静[1] 

机构地区：[1]郑州铁路职业技术学院,河南郑州450052

出　　处：《天中学刊》2010年第2期1-3,共3页Journal of Tianzhong

摘　　要：如果图G的每一个导出匹配都包含在图G的一个完美匹配中,则称图G是导出匹配可扩的.用T(G)表示图G的韧度,文章的主要结论是:设G是有2n(n≥3)个顶点的非完全图,如果G是导出匹配可扩的,则2/(n-1)≤T(G)≤n-1;对于任意满足2/(n-1)≤p/q≤n-1,p+q≤2n,1≤q≤n-1的数p/q,都有韧度为p/q的导出匹配可扩图.Suppose every induced matching of G is included in a perfect matching of G,then G is induced matching extendable,shortly for IM-extendable.T（G） is used to denote the toughness of graph G.The main results are as follows：（1） Suppose that a graph G with 2n vertices is not complete（n ≥ 3）,and G is IM-extendable,then 2/（n - 1） ≤ T（G） ≤ n - 1.（2） For any rational number p/q with 2/（n - 1） ≤ p/q ≤ n - 1,p ＋ q ≤ 2n and 1 ≤ q ≤ n - 1,there is an IM-extendable graph with toughness p/q.

关 键 词：完美匹配 导出匹配 导出匹配可扩图韧度 

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