K₁∪P_m∪P_n的匹配等价图数

The Number of MatchingEquivalent Graphs of K₁∪P_m∪P_n

摘要: 匹配多项式是一种组合计数多项式，与图的特征多项式、色多项式等有许多联系。对于无圈图,它等于特征多项式;对于一般图，它是该图路树的特征多项式的一个因式。每个图都有一个匹配多项式，但一个匹配多项式所确定的图不一定是唯一的，即不同构的图可能共享一个匹配多项式。如果一个图的匹配多项式唯一确定这个图，则称这个图是匹配唯一的。如果两个不同构的图拥有相同的匹配多项式，则称这两个图是匹配等价的。自提出匹配等价的概念以来，虽然已经有了许多研究，但对于给定的图G，想要完全刻画出它的匹配等价图类仍是十分困难的。在前人的研究基础之上，本文通过组合计数的方法计算了K₁∪P_m∪P_n的匹配等价图的个数。

Abstract: The matching polynomial is a kind of combinatorial counting polynomial, which has many relations with the characteristic polynomial and the chromatic polynomial of the graph. For a acyclic graph, it is equal to the characteristic polynomial; for a general graph, it is a factor of the characteristic polynomial of the path tree of the graph. Every graph has a matching polynomial, but the graph determined by a matching polynomial is not necessarily unique, that is, different graphs may share the same matching polynomial. If the matching polynomial of a graph uniquely determines the graph, then the graph is said to be matching unique. If two non isomorphic graphs have the same matching polynomial, then the two graphs are said to be matching equivalent. Since the concept of matching equivalence has been proposed, it is very difficult to characterize the class of matching equivalent graphs for a given graph G. On the basis of previous studies, the number of the matching equivalent graphs of K₁∪P_m∪P_n is calculated by using combination counting in this paper.