On The Exact Wiener Indices Of Some Special Strong Product Graphs

The Wiener index of a simple connected graph of G,is defined as the sum of the distances between all unordered pairs of vertices in the vertex set of the graph and denoted by W（G）.From the perspective of theory and practice,Wiener index is one of the most important graph invariants.The graph parameters closely related to it include average distance,numeration for spanning trees and Szeged index.Strong product is a kind of operation for two or more graphs.By using the strong product method,a large-scale graph can be constructed by several specific small-scale graphs.The large graph constructed by strong product method can not only inherit all the characteristics of small graphs,but also outperform small graphs in all aspects.Therefore,the research of Wiener index of the strong product has theoretical and practical significance.In this thesis,by using the orders of small graphs,the exact Wiener indices of several special strong product graphs are derived.The remainder of this thesis is organized as follows:Chapter Ⅰ introduces the research background and current research status of Wiener index and strong product.Besides,we also give our main contributions.In Chapter Ⅱ,we give a windfall in the research of the special strong product graphs,i.e.,exact Wiener index of the direct product of a path and a wheel graph.In Chapter Ⅲ,by using the transitivity of star graphs and the symmetry of paths,exact Wiener index of the strong product of a path and a star graph is derived.In Chapter Ⅳ,according to the different parity of the order of the two paths,exact Wiener index of the strong product of two paths is derived.In Chapter Ⅴ,firstly,we analyze the network capacity of the strong product network model by using the forwarding index.Secondly,we compare and analyze the reliability and transmission delay of a kind of special strong product network model with cartesian product.Chapter Ⅵ presents the summary and the further research directions of this thesis.