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