Gromov Hyperbolicity in Mycielskian Graphs

Abstract

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 δ ( 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 ≤ δ ( 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 δ ( G ) just in terms of δ ( G M ) is obtained.

Keywords

• extremal problems on graphs
• Mycielskian graphs
• geodesics
• Gromov hyperbolicity