Loading…

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 GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study...

Full description

Saved in:
Bibliographic Details
Published in:Symmetry (Basel) 2017-08, Vol.9 (8), p.131
Main Authors: Granados, Ana, Pestana, Domingo, Portilla, Ana, Rodríguez, José
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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 GM is hyperbolic and that δ(GM) is comparable to diam(GM) . 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≤δ(GM)≤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 δ(GM) is obtained.
ISSN:2073-8994
2073-8994
DOI:10.3390/sym9080131