给定最大度单圈图的最小维纳指数
The Minimum Wiener Index of Unicyclic Graphs with Giving Maximum Degree
DOI: 10.12677/PM.2023.136165, PDF,    国家自然科学基金支持
作者: 张 珊：浙江理工大学计算机科学与技术学院，浙江 杭州
关键词: 单圈图；维纳指数；T-单圈图；悬挂树；Unicyclic Graph； Wiener Index； T-Unicyclic-Graph； Hanging-Tree
摘要: 近年来，随着结构图理论和拓扑图理论在计算机网络、图像处理等领域的应用，越来越多的图论分支理论被研究拓展，各种应用瓶颈也催生出更实际更严格的定理结论。在基站分布拓扑网络、社会关系网络等布局设计领域，代价作为衡量效率的重要指标被多方面深入研究。维纳指数是拓扑结构中最经典应用最广泛的指标之一，反应了图中任意节点对平均距离，通过降低图的维纳指数可极大减少网络布局消耗。本文定义了一类给定阶n和最大度Δ的围长为3的单圈图，并刻画了具有最小维纳指数的单圈图结构。
Abstract: 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.
文章引用：张珊. 给定最大度单圈图的最小维纳指数[J]. 理论数学, 2023, 13(6): 1619-1629. https://doi.org/10.12677/PM.2023.136165

参考文献

[1] Gao, X.R. and Yang, N. (2017) Establishment of the Index System for Paper Evaluation by Social Network Analysis. Information Science, 35, 97-102, 144.
[2] Gupta, S., Sunil, M. and Madan, A. (2002) Application of Graph Theory: Relationship of Eccentric Connectivity Index and Wiener’s Index with Anti-Inflammatory Activity. Journal of Math-ematical Analysis and Applications, 266, 259-268. [Google Scholar] [CrossRef] 
[3] Yang, N. and Yang, L. (2012) QSPR Study for a New Index Defined Based on the Wiener and Physicochemical Properties of Organic Ketones. Journal of Southwest University, 34, 62-66.
[4] Zhou, X.N. (2017) Application of Graph Theory in Channel Routing and Research of Wiener Index. Master’s Thesis, Anhui University of Science and Technology, Huai-nan.
[5] Casablanca, R.M. and Dankelmann, P. (2018) Distance and Eccentric Sequences to Bound the Wiener Index, Hosoya Polynomial and the Average Eccentricity in the Strong Products of Graphs. Discrete Applied Mathematics, 263, 105-117. [Google Scholar] [CrossRef] 
[6] Entringer, R.C., Jackson, D.E. and Snyder, D.A. (1976) Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296. [Google Scholar] [CrossRef] 
[7] Lin, H. (2014) Extremal Wiener Index of Trees with Given Number of Vertices of Even Degree Sequence. Match-Communications In Mathematical and In Computer Chemistry, 72, 311-320.
[8] Plesník, J. (1984) On the Sum of All Distances in a Graph or Digraph. Journal of Graph Theory, 8, 1-21. [Google Scholar] [CrossRef] 
[9] Soltés, L. (1991) Transmission in Graphs: A Bound and Vertex Re-moving. Mathematica Slovaca, 41, 11-16.
[10] Zhang, X.D. (2008) The Laplacian Spectral Radii of Trees with Degree Sequences. Discrete Mathematics, 308, 3143-3150. [Google Scholar] [CrossRef] 
[11] Luo, P., Zhang, C.Q. and Zhang, X.D. (2020) Wiener Index of Unicycle Graphs with Given Number of even Degree Vertices, Discrete Mathematics. Algorithms and Applications, 12, Article ID: 2050054. [Google Scholar] [CrossRef] 
[12] Chen, Y.H. and Zhang, X.D. (2012) The Wiener Index of Unicyclic Graphs with Girth and the Matching Number. Ars Combinatoria, 106, 115-128.
[13] Du, Z. and Bo, Z. (2010) Minimum on Wiener Indices of Trees and Unicyclic Graphs of the Given Matching Number. Match-Communications In Mathematical and In Computer Chemistry, 63, 101-112.
[14] Yu, G.H. and Feng, L.H. (2010) On the Wiener Index of Unicyclic Graphs with Given Girth. Ars Combinatoria, 94, 361-369.
[15] Du, Z.B. and Zhou, B. (2009) On the Reverse Wiener Indices of Unicyclic Graphs. Acta Applicandae Mathematicae, 106, 293-306. [Google Scholar] [CrossRef] 
[16] Ren, C.R. and Shi, J.S. (2018) On the Wiener Index of Unicyclic Graphs with Fixed Diameter. Journal of East China University of Science and Technology, 6, 768-772.
[17] Tan, S.W. (2018) The Minimum Wiener Index of Unicyclic Graphs with a Fixed Diameter. Journal of Applied Mathematics and Computing, 56, 93-114. [Google Scholar] [CrossRef] 
[18] Hong, Y., Liu, H.Q. and Wu, X.Y. (2011) On the Wiener Index of Unicyclic Graphs. Hacettepe Journal of Mathematics and Statistics, 2, 63-68.
[19] Wu, Y. (2019) The Minimum Wiener Index of Unicyclic Graph with Given Pendant Vertices. Advances in Computational Science and Computing, 877, 21-27. [Google Scholar] [CrossRef] 
[20] Fischermanna, M., Hoffmannb, A. and Rautenbach, D. (2002) Wiener Index Versus Maximum Degree in Trees. Discrete Applied Mathematics, 122, 127-137. [Google Scholar] [CrossRef] 

为你推荐