给定度序列图的覆盖成本和反向覆盖成本的研究

具有n个顶点且度序列为(m,2,…,2,1,…,1)(1的重数为m)的连通图不止一个(这些图均为树),而每个树对应唯一一个段序列(l₁,l₂,…,l_m).通过对任意一树移动最长段的悬挂点到最短段悬挂点的方式得到另一树,比较前后两树的覆盖成本和反向覆盖成本,给出了具有最小覆盖成本和反向覆盖成本的极树,并且进一步给出了取得最小覆盖成本和反向覆盖成本的顶点.

Study on the Cover Cost and Reverse Cover Cost of Graphs with Given Degree Sequence

There is more than one connected graph with the degree sequence(m,2,…,2,1,…,1)(the multiplicity of 1 is m)of order n(these graphs are all trees),and each tree corresponds to a unique segment sequence(l₁,l₂,…,l_m).In this paper,we get another tree by moving pendent vertex of the longest segment to pendent vertex of the shortest segment for any tree.By comparing the cover cost and the reverse cover cost of the former tree and the latter tree,a extremal tree with the minimum cover cost and the reverse cover cost is determined,and the vertex of the minimum cover cost and reverse cover cost is also given.