Gromov hyperbolicity in Mycielskian graphs (Q2333539)

Summary: Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph \(G^M\) is hyperbolic and that \(\delta(G^M)\) is comparable to \(\operatorname{diam}(G^M)\). Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that \(5 / 4 \leq \delta(G^M) \leq 5 / 2\). Graphs \(G\) whose Mycielskian have hyperbolicity constant \(5 / 4\) or \(5 / 2\) are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on \(\delta(G)\) just in terms of \(\delta(G^M)\) is obtained.