Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Martin Knor (11.10.2018)

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


09. 10. 2018 09.08 hod.
By: Martin Škoviera

Martin Knor (STU Bratislava):
Trees with the maximal value of Graovac-Pisanski index


Abstract:
Let $G$ be a graph. Its Graovac-Pisanski index is defined as $GP(G)=\frac{|V(G)|}{2|Aut(G)|}\sum_{u\in V(G)}\sum_{\apha\in Aut(G)}d_G(u,\alpha(u))$, where $Aut(G)$ is the group of automorphisms of $G$. It is easy to see that $G$ has the smallest Graovac-Pisanski index if its group of automorphisms is trivial, in which case $GP(G)=0$. The question is to find graphs with the largest value of Graovac-Pisanski index. We found graphs with the maximum value of Graovac-Pisanski index in the class of trees and in the class of unicyclic graphs.