Seminar of Graph Theory - Katarína Hriňáková (4.4.2019)

Thursday 4.4.2019 at 9:50, Lecture room C

---

Katarína Hriňáková (STU Bratislava):
The structure of graphs with given number of blocks and the maximum Wiener index

Abstract:
The Wiener index (the distance) of a graph is the sum of distances between all pairs of vertices. We study the maximum possible value of this invariant among graphs on $n$ vertices with fixed number of blocks $p$. It is known that among graphs on $n$ vertices that have just one block, the $n$-cycle has the largest Wiener index. And the $n$-path, which has $n-1$ blocks, has the maximum Wiener index in the class of graphs on $n$ vertices. We show that among all graphs on $n$ vertices which have $p\ge 2$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $p=n-1$ for example). Finally, for each $n$ and $p$ we specify the lengths of the cycles in the extremal graph.

This is a joint work with S. Bessy, F. Dross, M. Knor and R. Skrekovski.

 

 

---