点圈并图的匹配等价图数

The number of matching equivalent to the union graphs of points and cycles

若两个图G和H的匹配多项式相等,称图G和H匹配等价.用δ(G)表示图G的所有不同构的匹配等价图的个数.设m1<m2<…<mk,且mi≠6,9,15(i=1,2,…,k),则δ(sK1∪t1Cm1∪…∪tkCmk)=∑ri=0δ((s-i)K1∪t1Cm1∪…∪tk-1Cmk-1),r=min{s,tk}.由此推出δ(sK1∪tCm)=min{s,t}+1,δ(sK1∪t1Cm1∪t2Cm3)=∑ri=0min{s-i,t1}+r+1,r=min{s,t2}.对m=6,9或15,给出了δ(sK1∪tCm)的计算公式.

Two graphs G and H are said to be matching equivalent, if they have same matching plynomial. By δ（G） denote the number of graphs of matching equivalent to G. Let m1 〈 m2〈…〈mk, and mi≠6, 9,15（i = 1,2,…,k）,then δ（sK1Ut1Cm1U … UtkCmk ） =∑i=0^＇δ （（s - i ） K1U tiCm1U… Utk-1 Cmk-1 ）, where r =min{ s, tk } ;As an immediate consequence,δ（sKi UtCm） = min{ s, t } ＋ 1,δ（sKiUt1Cm1Ut2Cm3） =∑i=0^＇ min{ s - i, t1} ＋ r ＋ 1, where r = min{ s, t2 }. For m = 6,9 or 15, the calculating formulas of δ（skiUtCm）isalso given in this paper.