• 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.

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

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