Gromov hyperbolicity in lexicographic product graphs

被引:0
作者
Walter Carballosa
Amauris de la Cruz
José M Rodríguez
机构
[1] Florida International University,Department of Mathematics and Statistics
[2] Miami Dade College,Department of Mathematics
[3] Universidad Carlos III de Madrid,Departamento de Matemáticas
来源
Proceedings - Mathematical Sciences | 2019年 / 129卷
关键词
Lexicographic product graphs; geodesics; Gromov hyperbolicity; infinite graphs; Primary: 05C76; 05C10; Secondary: 05C35; 05C63; 05C12;
D O I
暂无
中图分类号
学科分类号
摘要
If X is a geodesic metric space and x1,x2,x3∈X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_1,x_2,x_3\in X$$\end{document}, a geodesic triangleT={x1,x2,x3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=\{x_1,x_2,x_3\}$$\end{document} is the union of the three geodesics [x1x2]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[x_1x_2]$$\end{document}, [x2x3]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[x_2x_3]$$\end{document} and [x3x1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[x_3x_1]$$\end{document} in X. The space X is δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document}-hyperbolic (in the Gromov sense) if any side of T is contained in a δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document}-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (X)$$\end{document} the sharp hyperbolicity constant of X, i.e. δ(X)=inf{δ≥0:Xisδ-hyperbolic}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (X)=\inf \{\delta \ge 0: \, X \, \text { is }\delta \text {-hyperbolic}\}$$\end{document}. In this paper, we characterize the lexicographic product of two graphs G1∘G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1\circ G_2$$\end{document} which are hyperbolic, in terms of G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} and G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_2$$\end{document}: the lexicographic product graph G1∘G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1\circ G_2$$\end{document} is hyperbolic if and only if G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} is hyperbolic, unless if G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} is a trivial graph (the graph with a single vertex); if G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} is trivial, then G1∘G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1\circ G_2$$\end{document} is hyperbolic if and only if G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_2$$\end{document} is hyperbolic. In particular, we obtain the sharp inequalities δ(G1)≤δ(G1∘G2)≤δ(G1)+3/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G_1)\le \delta (G_1\circ G_2) \le \delta (G_1) + 3/2$$\end{document} if G1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} is not a trivial graph, and we characterize the graphs for which the second inequality is attained.
引用
收藏
相关论文
共 128 条
  • [1] Alvarez V(2006)Gromov hyperbolicity of Denjoy domains Geom. Dedicata 121 221-245
  • [2] Portilla A(2000)Gromov hyperbolicity and the Kobayashi metric on strictly pseudoconvex domains Comm. Math. Helv. 75 504-533
  • [3] Rodríguez JM(2003)Geometric characterizations of Gromov hyperbolicity Invent. Math. 153 261-301
  • [4] Tourís E(2003)Convexes hyperboliques et fonctions quasisymétriques Publ. Math. Inst. Hautes Études Sci. 97 181-237
  • [5] Balogh ZM(2016)Small values of the hyperbolicity constant in graphs Discrete Math. 339 3073-3084
  • [6] Bonk M(2011)Computing the hyperbolicity constant Comput. Math. Appl. 62 4592-4595
  • [7] Balogh ZM(2013)Gromov hyperbolic graphs Discrete Math. 313 1575-1585
  • [8] Buckley SM(2011)Hyperbolicity and complement of graphs Appl. Math. Lett. 24 1882-1887
  • [9] Benoist Y(2001)On the hyperbolicity of chordal graphs Ann. Comb. 5 61-69
  • [10] Bermudo S(2013)Gromov hyperbolicity in strong product graphs Electr. J. Comb. 20 P2-386