Gromov hyperbolicity in Mycielskian graphs Articles uri icon

publication date

  • August 2017

issue

  • 8

volume

  • 9

International Standard Serial Number (ISSN)

  • 2073-8994

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 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.

subjects

  • Mathematics

keywords

  • extremal problems on graphs; mycielskian graphs; geodesics; gromov hyperbolicity