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).
matching polynomialmatching maximum rootk-bridge graph
NETL
NSTL
万方数据
