Seminar of Graph Theory - Martin Knor (15.11.2018)

Thursday 15.11.2018 at 9:50, Lecture room M/213

---

Martin Knor  (STU Bratislava):
On the anti-radius of a graph

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

---