An upper bound on the Wiener Index of a k-connected graph

2018/11/06 by Zhongyuan Che, Che, Zhongyuan, Karen L. Collins +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Drug Discovery Methods #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1811.02664

openalex publication_date 2018/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a k-connected graph G of order n for integers n-1>k ≥ 1: W(G) ≤ (1)/(4) n \lfloor (n+k-2)/(k) \rfloor (2n+k-2-k\lfloor (n+k-2)/(k) \rfloor). Moreover, we show that this upper bound is sharp when k ≥ 2 is even, and can be obtained by the Wiener index of Harary graph H_k,n.

Citations

• Structural Determination of Paraffin Boiling Points

Related

• Wiener index of graphs with fixed number of pendant or cut vertices
• Distance Sequences to bound the Harary Index and other Wiener-type Indices of a Graph
• Selected topics on Wiener index
• Some results on the Wiener index related to the Šoltés problem of graphs
• Wiener index and graphs, almost half of whose vertices satisfy Šoltés property