Publication:
Gromov Hyperbolicity in Mycielskian Graphs

Loading...
Thumbnail Image
Identifiers
Publication date
2017-07-27
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
MDPI
Impact
Google Scholar
Export
Research Projects
Organizational Units
Journal Issue
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.
Description
Keywords
Extremal problems on graphs, Mycielskian graphs, Geodesics, Gromov hyperbolicity
Bibliographic citation
Granados, A., Pestana, D., Portilla, A., Rodríguez,J. M. (2017). Gromov Hyperbolicity in Mycielskian Graphs. Symmetry, 9(8), 131.