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

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

作　　者：贾雁宇 李玉瑛 郝艺方 JIA Yan-yu;LI Yu-ying;HAO Yi-fang(College of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)

机构地区：[1]太原理工大学数学学院,山西太原030024

出　　处：《数学的实践与认识》2022年第1期188-195,共8页Mathematics in Practice and Theory

基　　金：国家自然科学青年基金(11501402)。

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

关 键 词：星型树 度序列 段序列 覆盖成本 反向覆盖成本 

分 类 号：O157.5[理学—数学]