On several extremal problems in graph theory involving gromov hyperbolicity constant

• Autores: Mónica Hernández Martínez
• Directores de la Tesis: José Manuel Rodríguez García (dir. tes.) , Domingo Pestana Galván (codir. tes.)
• Lectura: En la Universidad Carlos III de Madrid ( España ) en 2018
• Idioma: inglés
• Tribunal Calificador de la Tesis: Elena Romera Colmenarejo (presid.) , Ana María Portilla Ferreira (secret.) , José María Sigarreta Almira (voc.)
• Enlaces
  • Tesis en acceso abierto en: e-Archivo
• Resumen

  • 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.