Maximal Wiener index for graphs with prescribed number of blocks

摘要

Wiener index, which is defined as the sum of distances between all unordered pairs of vertices, is one of the oldest and most popular molecular descriptors. It is known that among graphs on n vertices that have just one block, the n-cycle has the biggest Wiener index. In a previous work of the same authors, it was shown that among all graphs on n vertices which have p ≥ 2 blocks, the maximum Wiener index is attained by a graph composed of two cycles Ca and Cb joined by a path of length p−2 (possibly a and b are of size 2). In this paper we elaborate further this result and determine the sizes of a and b in the extremal graphs for each n and p. We distinguish six cases with crucial values being 5p−7 and 5p−8. Roughly speaking, if n bigger than 5p−7, then the extremal graphs is obtained for a=2. i.e. the graph is a path glued to a cycle. For values n=5p−8 and 5p−7, we have more than one extremal graph. And, when n<5p−8, the extremal graphs is again unique with a and b being equal or almost equal depending of the congruence of n−p modulo 4. We also showed unimodal property of a behaviour of Wiener index.