Seminár z algebratickej teórie grafov - Katarína Hriňáková (19.10.2018)

v piatok 19.10.2018 o 13:30 hod. v miestnosti M/XI

---

Prednášajúci: Katarína Hriňáková

Názov: On a conjecture about the ratio of Wiener index in iterated line graphs

Termín: 19.10.2018, 13:30 hod., M/XI

Abstrakt:
Abstract: 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.

---