不含三角形的图的独立数和匹配数关系

Independence and Matching Numbers in Triangle Free Graphs

摘要:

设α(G), β(G) 和n(G)分别表示图G的独立数、匹配数和阶数.图的独立数和匹配数是图的两个较重要的参数.证明了对于不含三角形且最大度不超过5的图，独立数、匹配数和阶数之间存在两个最优的数量关系.

Abstract:

Let α(G), β(G) and n(G) be the independence number, the matching number and the order of a graph G, respectively, the independence number and the matching number are two more important parameters for a graph. In this paper, it is proved that there exist two optimal numerical relationships between them for the graphs which are K3free and the maximum degree is 5 at most.