ISSN 2590-9770
The Art of Discrete and Applied Mathematics 1 (2018) #P1.09
https://doi.org/10.26493/2590-9770.1257.dda
(Also available at http://adam-journal.eu)
On a conjecture about the ratio of Wiener index
in iterated line graphs∗
Katarína Hriňáková , Martin Knor
Faculty of Civil Engineering, Slovak University of Technology,
Radlinského 11, 810 05, Bratislava, Slovakia
Riste Škrekovski
FMF, University of Ljubljana, 1000 Ljubljana and
Faculty of Information Studies, 8000 Novo Mesto and
FAMNIT, University of Primorska, 6000 Koper, Slovenia
Received 9 January 2017, accepted 30 May 2018, published online 23 July 2018
Abstract
Let G be a graph. Denote by W (G) its Wiener index and denote by Li(G) its i-
iterated line graph. Dobrynin and Mel’nikov proposed to estimate the extremal values for
the ratio Rk(G) = W (Lk(G))/W (G) for k ≥ 1. Motivated by this we study the ratio for
higher k’s. We prove that among all trees on n vertices the path Pn has the smallest value
of this ratio for k ≥ 3. We conjecture that this holds also for k = 2, and even more, for
the class of all connected graphs on n vertices. Moreover, we conjecture that the maximum
value of the ratio is obtained for the complete graph.
Keywords: Wiener index, line graph, tree, iterated line graph.
Math. Subj. Class.: 05C12, 05C05, 05C76
∗The first and second author acknowledge partial support by Slovak research grants VEGA 1/0007/14, VEGA
1/0026/16, VEGA 1/0142/17, APVV-0136-12 and APVV-15-0220. The research was partially supported by
Slovenian research agency ARRS, program no. P1-0383.
E-mail addresses: hrinakova@math.sk (Katarína Hriňáková), knor@math.sk (Martin Knor),
skrekovski@gmail.com (Riste Škrekovski)
cb This work is licensed under https://creativecommons.org/licenses/by/3.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 1 (2018) #P1.09
https://doi.org/10.26493/2590-9770.1257.dda
(Dostopno tudi na http://adam-journal.eu)
O domnevi v zvezi z razmerjem Wienerjevega
indeksa v iteriranih povezavnih grafih∗
Katarína Hriňáková , Martin Knor
Faculty of Civil Engineering, Slovak University of Technology,
Radlinského 11, 810 05, Bratislava, Slovakia
Riste Škrekovski
FMF, University of Ljubljana, 1000 Ljubljana and
Faculty of Information Studies, 8000 Novo Mesto and
FAMNIT, University of Primorska, 6000 Koper, Slovenia
Prejeto 9. januarja 2017, sprejeto 30. maja 2018, objavljeno na spletu 23. julija 2018
Povzetek
Naj bo G graf. Označimo z W (G) njegov Wienerjev indeks, z Li(G) pa njegov i-
iterirani povezavni graf. Dobrynin in Mel’nikov sta predlagala, da se oceni ekstremno
vrednost razmerja Rk(G) = W (Lk(G))/W (G) za k ≥ 1. Motivirani s tem raziskujemo
razmerje za višje k-je. Dokažemo, da ima med vsemi drevesi na n vozliščih pot Pn naj-
manjšo vrednost tega razmerja za k ≥ 3. Domnevamo, da to velja tudi za k = 2, in še
več, za razred vseh povezanih grafov na n vozliščih. Poleg tega domnevamo, da je največja
vrednost tega razmerja dosežena pri polnem grafu.
Ključne besede: Wienerjev indeks, povezavni graf, drevo, iterirani povezavni graf.
Math. Subj. Class.: 05C12, 05C05, 05C76
∗Prvi in drugi avtor priznavata delno podporo s strani Slovak research grants VEGA 1/0007/14, VEGA
1/0026/16, VEGA 1/0142/17, APVV-0136-12 in APVV-15-0220. Raziskavo je delno podprla Javna agencija
za raziskovalno dejavnost Republike Slovenije ARRS, program št. P1-0383.
E-poštni naslovi: hrinakova@math.sk (Katarína Hriňáková), knor@math.sk (Martin Knor),
skrekovski@gmail.com (Riste Škrekovski)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/3.0/