路并的匹配等价图数

The Number of Graphs of Matching Equivalent to the Union Graphs of Paths

两个图G和H的匹配多项式相等,则称它们匹配等价.用δ(G)表示图G的所有不同构的匹配等价图的个数.计算了一些路的并图的匹配等价图的个数.首先将整数m(≥2)按它所含的最大奇因数分成3-系和2k(k=1.2,…)-系,再按它所含2的方幂分为级.设A是不小于2的整数组成的可重集,B_i(i=1,2,…,t)是同系整数构成的可重集,且A=B_1∪B_2∪…∪B_t,则δ(■P_i)=■δ(■P_i),若x∈B_i,y∈B_j(i≠j),则x与y是互不相同系的整数.设B={m_1^(k_1),m_2^(k_2),…,m_n^(k_n)}是同系整数构成的可重集,其中m_i(≥2)是第i级的,有k_i(≥0)个,则n =1,δ(■P_i)=1;n≥2,δ(■P_i)=sum from i_m-0 to k_n sum from i_(m-1)-0 to k_(n-1)+i_m…sum from i_2-0 to k_2+i_3 1.作为推论,计算了路并补图的匹配等价图的个数.

Two graphs G and H are said to be matching equivalent if they possess the same matching polynomials. 8（G） denotes the number of graphs which matching equivalent to graph G. In this paper, the number of graphs be calculated which graphs matching equivalence to the union graphs of paths. First, the integer m （≥2） is divided into 3-department or 2k （k = 1,2,…）-department by the maximum odd factor of it, then is it divided into grade by the power of factor 2 of it. Let A be a repeated set of integers of greater than or equal 2, and A = B1 ∪ B2… ∪ B1, than δ（∪i∈A Pi）=∏i=1 ^t δ（∪i∈Bi Pi）, where Bi （i= 1,2,…, t） is composed by the same department integers, if x∈Bi,y∈Bj（i≠j）, then the department of x and y is not same each other. Let B={m1^k1,m2^k2,…,mn^kn） be a repeated set of integers of a department （3-or 2k-department） , then δ（∪ i∈B Pi）=1, when n=1; δ（∪ i∈B Pi）=1;n≥2,δ（∪i∈B Pi）=（∑in=0 ^kn ∑i（n-1）=0 ^k（n-1）＋in …∑i2=0 ^k2＋i3） 1, when n≥2. Asacorollary, the number of graphs is also calculated which graphs matching equivalent to the complement of union graphs of paths.