k-桥图匹配最大根的极值

作者：马海成; 攸晓杰

来源：山东大学学报(理学版), 2023, 1-6.

• 匹配多项式
• 匹配最大根
• k-桥图

设G是有n个点的图,μ(G,x)表示图G的匹配多项式,M1(G)表示多项式μ(G,x)的最大根,称为匹配最大根。把k条路Pa1+2,Pa2+2,…,和Pak+2的左右两个端点分别黏结成2个点后得到的图称为k-桥图,记为θk(a1,a2,…,ak)。有n个点且每一条路上的点数几乎相等的k-桥图记为θk*(n)。本文证明了在n个点的k-桥图中匹配最大根取得最小的图是θk*(n),最大的图是θk(0,1,1...,1,n-k)(k-2)。在n个点的任意k-桥图中匹配最大根取得最小的图是2-桥图(圈)Cn,最大的图是(n-1)-桥图θn-1(0,1,1…,1)。

• 出版日期2023
• 单位青海民族大学