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...
Saved in:
Published in: | Symmetry (Basel) 2017-08, Vol.9 (8), p.131 |
---|---|
Main Authors: | , , , |
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!
|
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 |