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

摘要

设G是有n个点的图，μ（G,x）表示图G的匹配多项式，M₁（G）表示多项式μ（G,x）的最大根，称为匹配最大根。把k条路P_a1+2,P_a2+2,…,P_ak+2的左右2个端点分别黏结成2个点后得到的图称为k-桥图，记为θ_k（a₁,a₂,…,a_k）。有n个点且每一条路上的点数几乎相等的k-桥图记为θ^*_k（n）。证明了：在n个点的k-桥图中匹配最大根取得最小的图是θ^*_k（n）,最大的图是■;在n个点的任意k-桥图中匹配最大根取得最小的图是2-桥图（圈）C_n,最大的图是（n-1）-桥图θ_n-1（0,1,1…,1）。

关键词

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