Resumen de On several extremal problems in graph theory involving gromov hyperbolicity constant
Mónica Hernández Martínez
To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph.
Given a graph $G$, we denote the hyperbolicity constant by $\delta(G)$.
Let $\mathcal{G}(n,m)$ be the family of graphs $G$ of order $n$ and size $m$. Let us define $ A(n,m):=\min\{\delta(G)\mid G \in \mathcal{G}(n,m) \},$ $ B(n,m):=\max\{\delta(G)\mid G \in \mathcal{G}(n,m) \}.$ Let $\mathcal{H}(n,\delta_{0})$ be the family of graphs $G$ of order $n$ and minimum degree $\delta_{0}$. Let us define $ a(n,\delta_{0}):=\min\{\delta(G)\mid G \in \mathcal{H}(n,\delta_{0}) \},$ $ b(n,\delta_{0}):=\max\{\delta(G)\mid G \in \mathcal{H}(n,\delta_{0}) \}.$ Let $\mathcal{J}(n,\Delta)$ be the family of graphs $G$ of order $n$ and maximum degree $\Delta$. Let us define $ \alpha(n,\Delta):=\min\{\delta(G)\mid G \in \mathcal{J}(n,\Delta) \}, $ $ \beta(n,\Delta):=\max\{\delta(G)\mid G \in \mathcal{J}(n,\Delta) \}.$ Let $\mathcal{M}(g,c,n)$ be the family of graphs $G$ of girth $g$, circumference $c$, and order $n$. Let us define $ \mathcal{A}(g,c,n):=\min\{\delta(G)\mid G \in \mathcal{M}(g,c,n) \},$ $ \mathcal{B}(g,c,n):=\max\{\delta(G)\mid G \in \mathcal{M}(g,c,n) \}.$ Let $\mathcal{N}(g,c,m)$ be the family of graphs $G$ of girth $g$, circumference $c$, and size $m$. Let us define $ \mathfrak{A}(g,c,m):=\min\{\delta(G)\mid G \in \\ \mathcal{N}(g,c,m) \},$ $ \mathfrak{B}(g,c,m):=\max\{\delta(G)\mid G \in \mathcal{N}(g,c,m) \}.$ Our aim in this work is to estimate $ A(n,m)$, $B(n,m)$, $a(n,\delta_{0})$, $b(n,\delta_{0})$, $\alpha(n,\Delta),$ $ \beta(n,\Delta)$, $\mathcal{A}(g,c,n)$, $\mathcal{B}(g,c,n)$, $\mathfrak{A}(g,c,m)$ and $\mathfrak{B}(g,c,m)$, i.e., to study the extremal problems of maximazing and minimazing $\delta(G)$ on the sets $\mathcal{G}(n,m)$, $\mathcal{H}(n,\delta_{0})$, $\mathcal{J}(n,\Delta)$, $\mathcal{M}(g,c,n)$ and $\mathcal{N}(g,c,m)$. In this way, we find bounds for the hyperbolicity constant in terms of important parameters of the graph.
