给定最大度单圈图的最小维纳指数

The Minimum Wiener Index of Unicyclic Graphs with Giving Maximum Degree

近年来,随着结构图理论和拓扑图理论在计算机网络、图像处理等领域的应用,越来越多的图论分支理论被研究拓展,各种应用瓶颈也催生出更实际更严格的定理结论。在基站分布拓扑网络、社会关系网络等布局设计领域,代价作为衡量效率的重要指标被多方面深入研究。维纳指数是拓扑结构中最经典应用最广泛的指标之一,反应了图中任意节点对平均距离,通过降低图的维纳指数可极大减少网络布局消耗。本文定义了一类给定阶n和最大度Δ的围长为3的单圈图,并刻画了具有最小维纳指数的单圈图结构。

In recent years, with the application of structure graph theory and topological graph theory in com-puter network, image processing and other fields, more and more branch theories of graph theory have been studied and expanded, and the bottlenecks of various application also give rise to more practical and rigorous theorem conclusions. In the field of layout design such as base station distri-bution topology network and social relationship network, cost has been in-depth studied as an important indicator to measure efficiency. Wiener index is one of the most classic and widely used indicators in topology, reflecting the average distance of any node pair in the graph, and greatly reducing the network layout consumption by reducing the Wiener index of the graph. This paper defines a class of unicyclic graphs with a girth of 3 for a given order n and the maximum degree Δ, and characterizes the structure of the unicyclic graph with the smallest Wiener index.