On The Sum Of All Distances In Bipartite Graphs

The transmission of a connected graph G is the sum of all distances between all pairs of vertices in G, it is also called the Wiener index of G. In this paper, sharp bounds on the transmission are determined for several classes of connected bipartite graphs. For example, in the class of all connected n-vertex bipartite graphs with a given matching number q, the minimum transmission is realized only by the graph Kq,n-q; in the class of all connected n-vertex bipartite graphs of diameter d, the extremal graphs with the minimal transmission are characterized. Moreover, all the extremal graphs having the minimal transmission in the class of all connected n-vertex bipartite graphs with a given vertex connectivity (resp. edge-connectivity) are also identified. The concrete content is in the following.· In chapter1, we introduce the background and significance of the research, in-cluding the development of a representative at home and abroad regarding this aspect. Based on this research background and profound discussion, by using deep-going analysis, it fully shows the main work’s necessity and innovation.· In chapter2, we give the graph with minimum sum of all distances among (?)d/n.· In chapter3, we determine the graph with minimum sum of all distances among (?)d/n.· In chapter4, we order the extremal graphs according to their vertex connec-tivity and their edge connectivity.