Seminár z teórie grafov - Martin Knor (15.11.2018)

vo štvrtok 15.11.2018 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Martin Knor  (STU Bratislava)

Názov: On the anti-radius of a graph

Termín: 15.11.2018, 9:50 hod., M/213

Abstrakt:
Let $G$ be a graph. By the $k,l$-antiradius of $G$, $p_{k,l}(G)$, we mean the value $$ \max_{K\subseteq V(G)}\{\min_{L\subseteq L}\{d_l(L);\,|L|=l\}; |K|=k\}, $$ where by $d_l(L)$ we mean the sum of distances between all pairs of vertices in $L$.This parameter is in a way dual to radius and we focus on $l=2$, i.e., we consider the $k,2$-anti-radius. We give a tight upper bound for $k,2$-anti-radius over the class of connected graphs on $n$ vertices. Such a bound states, how large the smallest distance among $k$ distinct vertices in an $n$-vertex graph can be. Also, we solve the corresponding problem for 2-connected graphs for $k=3$.

---