Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

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

vo štvrtok 4.4.2019 o 9:50 hod. v posluchárni C

01. 04. 2019 14.42 hod.
Od: Martin Škoviera

Prednášajúci: Katarína Hriňáková (STU Bratislava)

Názov: The structure of graphs with given number of blocks and the maximum Wiener index

Termín: 4.4.2019, 9:50 hod., poslucháreň C

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.