On Wiener index of graphs and their line graphs

Description

The Wiener index of a graph $G$, denoted by $W(G)$, is the sum of distances between all pairs of vertices in $G$. In this paper, we consider the relation between the Wiener index of a graph, $G$, and its line graph, $L(G)$. We show that if $G$ is of minimum degree at least two, then $W(G) ≤ W(L(G))$. We prove that for every non-negative integer g0, there exists $g > g_0$, such that there are infinitely many graphs $G$ of girth $g$, satisfying $W(G) = W(L(G))$. This partially answers a question raised by Dobrynin and Mel'nikov [8] and encourages us to conjecture that the answer to a stronger form of their question is affirmative.

Abstract

International audience

Additional details