Gromov hyperbolicity in Mycielskian graphs (Q2333539)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gromov hyperbolicity in Mycielskian graphs |
scientific article |
Statements
Gromov hyperbolicity in Mycielskian graphs (English)
0 references
13 November 2019
0 references
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 \(G^M\) is hyperbolic and that \(\delta(G^M)\) is comparable to \(\operatorname{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 \leq \delta(G^M) \leq 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 \(\delta(G)\) just in terms of \(\delta(G^M)\) is obtained.
0 references
extremal problems on graphs
0 references
Mycielskian graphs
0 references
geodesics
0 references
Gromov hyperbolicity
0 references
0 references
0 references
0 references