On Wiener index of graphs and their line graphs

Authors

Nathann Cohen,
Darko Dimitrov,
Roi Krakovski, Riste Škrekovski, Vida Vukašinović

Publication

MATCH Communications in Mathematical and in Computer Chemistry, 2010, 64(3): 683-698

Abstract

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 > g0, 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.

BIBTEX copied to Clipboard