2K_(1)∪I_(n)的匹配等价图类

The Class of Matching Equivalent Graphs of 2K_(1)∪I_(n)

匹配多项式是一种组合计数多项式,与图的特征多项式、色多项式等有许多联系.对于无圈图,它等于特征多项式;对于一般图,它是该图路树的特征多项式的一个因式.每个图都有一个匹配多项式,但一个匹配多项式所确定的图不一定是唯一的,即不同构的图可能共享一个匹配多项式.如果一个图的匹配多项式唯一确定这个图,则称这个图是匹配唯一的.如果两个不同构的图拥有相同的匹配多项式,则称这两个图是匹配等价的.自提出匹配等价的概念以来,虽然已经有了许多研究,但对于给定的图G,想要完全刻画出它的匹配等价图类仍是十分困难的.本文在前人的研究基础之上,通过组合计数和数学归纳法计算了2K_(1)∪I_(n)的匹配等价图的个数,并且利用组合分析的方法刻画了2K_(1)∪I_(n)以及它的补图的匹配等价图类.

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 graphs have the same matching polynomial,then the two graphs are said to be matching equivalent.Since the concept of matching equivalence as 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 matching equivalent graphs of 2K_(1)∪I_(n)calculated by using combination counting and mathematical induction,and the classes of matching equivalent graphs of 2K_(1)∪I_(n)and its complement graphs recharacterized by using combination analysis.