树线图的最大匹配数

On the Number of Maximum Matchings in the Line Graph of a Tree

设T是n个顶点的树,令Max(L(T))表示T的线图L(T)最大匹配的数目。当n是奇数时,Max(L(T))就是L(T)的完美匹配数。当n是偶数时,研究线图L(T)的最大匹配,给出其最大匹配所含的边数,得到最大匹配数Max(L(T))的一个一般表达式。作为应用,得到了一些特殊的毛毛虫树和三元树线图最大匹配数的具体表达式。

Let T be a tree with n vertices,and let Max(L(T))denote the number of maximum matchings in the line graph of T.When n is odd,Max(L(T))is the number of perfect matchings of L(T).In this paper,the maximum matchings of L(T)for even n were studied.The number of edges in a maximum matching was firstly determined,and then a general expression for Max(L(T))was given.As applications,for some special caterpillar trees and ternary trees,explicit expressions of Max(L(T))were got.