Algebraic Graph Theory Seminar - Katarína Hriňáková (19.10.2018)

Friday 19.10.2018 at 13:30, Lecture room M/XI

---

Katarína Hriňáková (Slovak University of Technology):
On a conjecture about the ratio of Wiener index in iterated line graphs

Abstravt:
Let $G$ be a graph. Denote by $W(G)$ its Wiener index and denote by $L^i(G)$ its $i$-iterated line graph. Dobrynin and Mel'nikov proposed to estimate the extremal values for the ratio $R_k(G) = W(L^k(G))/W(G)$ for $k\ge 1$. Motivated by this we study the ratio for higher~$k$'s. We prove that among all trees on $n$~vertices the path~$P_n$ has the smallest value of this ratio for $k\ge 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.

---