On Wiener index of graphs and their line graphs Cohen, Nathann Dimitrov, Darko Krakovski, Roi Škrekovski, Riste Vukašinović, Vida Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
On Wiener index of graphs and their line graphs
Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 09,03
Wiener index, line graphs
006 Special computer methods 510 Mathematics
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 g_0, 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 and encourages us to conjecture that the answer to a stronger form of their question is affirmative.
If your browser can't open the file, please download the file first and then open it