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

Main titleOn Wiener index of graphs and their line graphs
AuthorCohen, Nathann
AuthorDimitrov, Darko
AuthorKrakovski, Roi
AuthorŠkrekovski, Riste
AuthorVukašinović, Vida
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages11 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]09,03
KeywordsWiener index, line graphs
Classification (DDC)006 Special computer methods
510 Mathematics
AbstractThe 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
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2009
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2010-03-04 : 12:12:58
Last changed2015-03-03 : 01:43:34
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004954