dc.contributor.author
Cohen, Nathann
dc.contributor.author
Dimitrov, Darko
dc.contributor.author
Krakovski, Roi
dc.contributor.author
Škrekovski, Riste
dc.contributor.author
Vukašinović, Vida
dc.date.accessioned
2018-06-08T08:05:15Z
dc.date.available
2010-03-04T12:12:58.789Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/19333
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-22989
dc.description.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 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.
de
dc.relation.ispartofseries
urn:nbn:de:kobv:188-fudocsseries000000000021-2
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::006 Spezielle Computerverfahren
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
dc.title
On Wiener index of graphs and their line graphs
refubium.affiliation
Mathematik und Informatik
de
refubium.affiliation.other
Institut für Informatik
refubium.mycore.fudocsId
FUDOCS_document_000000004954
refubium.resourceType.isindependentpub
no
refubium.series.name
Freie Universität Berlin, Fachbereich Mathematik und Informatik
refubium.series.reportNumber
09-3
refubium.mycore.derivateId
FUDOCS_derivate_000000000888
dcterms.accessRights.openaire
open access
