Gromov Hyperbolicity in Mycielskian Graphs

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 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 <= delta(G(M)) <= 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 d (G) just in terms of d (GM) is obtained.We would like to thank the referees for their valuable comments, which have improved the paper. This work was supported in part by two grants from Ministerio de Economía y Competititvidad (MTM2013-46374-P and MTM2015-69323-REDT), Spain