On minimizing the Wiener index of unicyclic graphs with fixed girth and given degree sequence

2024/10/07 by Alewyn P. Burger, Burger, Alewyn P., Valisoa R. M. Rakotonarivo +1 · 1 citation
Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2410.04903

openalex publication_date 2024/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Wiener index of a graph is the sum of all the distances between any pair of vertices. We aim to describe graphs which minimize the Wiener index among all unicyclic graphs with fixed girth and given degree sequence. Depending on where the centroid of the graph is, we will present three candidates for the minimization, namely the greedy unicyclic graph, the cycle-centered graph and the out-greedy unicyclic graph.

Cited by

• Efficient generation of networks with minimal average shortest-path distance

Related

• The Wiener Index of Unicyclic Graphs with Girth and the Matching Number
• Wiener index of graphs with fixed number of pendant or cut vertices
• Wiener index of unicycle graphs with given number of even degree vertices
• Maximum Wiener index of unicyclic graphs with given bipartition
• Wiener index and graphs, almost half of whose vertices satisfy Šoltés property