2019/05/07 by Stéphane Bessy, François Dross, Bessy, Stéphane +7
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1905.02633
arxiv created 2019/05/07 · openalex publication_date 2019/05/07 · arxiv updated 2019/05/08 · openalex created_date 2022/07/23 · openalex updated_date 2026/07/28
The Wiener index (the distance) of a connected graph is the sum of distances between all pairs of vertices. In this paper, we study the maximum possible value of this invariant among graphs on n vertices with fixed number of blocks p. It is known that among graphs on n vertices that have just one block, the n-cycle has the largest Wiener index. And the n-path, which has n-1 blocks, has the maximum Wiener index in the class of graphs on n vertices. We show 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 joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case p=n-1 for example).