k-桥图匹配最大根的极值
Extremum of the matching maximum root of k-bridge graphs
马海成 1攸晓杰1
作者信息
- 1. 青海民族大学数学与统计学院,青海西宁 810007
- 折叠
摘要
设G是有n个点的图,μ(G,x)表示图G的匹配多项式,M1(G)表示多项式μ(G,x)的最大根,称为匹配最大根.把k条路Pa1+2,Pa2+2,…,Pak+2的左右2个端点分别黏结成2个点后得到的图称为k-桥图,记为θk(a1,a2,…,ak).有n个点且每一条路上的点数几乎相等的k-桥图记为θ*k(n).证明了:在n个点的k-桥图中匹配最大根取得最小的图是θ*k(n),最大的图是θk(0,1,1…,k-2 1,n-k);在n个点的任意k-桥图中匹配最大根取得最小的图是2-桥图(圈)Cn,最大的图是(n-1)-桥图θn-1(0,1,1…,1).
Abstract
Let G be a graph with n vertices,and μ(G,x)denote the matching polynomial of graph G,M1(G)denote the maximum root of the polynomial μ(G,x),which is called the matching maximum root.By identifying the first vertices and the last vertices of k paths Pa1+2,Pa2+2,…,Pak+2,respectively,the resulting graph is called the k-bridge graphs,denoted by θk(a1,a2,ak).A k-bridge graph with n vertices and nearly equal number of vertices on each paths is denoted asθk(n).The following conclusions are proved.In all k-bridge graphs with n vertices,the matching maximum root to get the smallest graph is θk*(n),and the biggest graph is θk(0,1,1,…,k-2 1,n-k).In any k-bridge graphs with n vertices,the graph that the matching maximum root to get the smallest is 2-bridge graphs Cn(cycle),and the biggest one is(n-l)-bridge graph θn-1(0,1,1…,1).
关键词
匹配多项式/匹配最大根/k-桥图Key words
matching polynomial/matching maximum root/k-bridge graph引用本文复制引用
基金项目
国家自然科学基金资助项目(11561056)
青海省自然科学基金资助项目(2022-ZJ-924)
出版年
2024
NETL
NSTL
万方数据