Hyperbolicity in the corona and join of graphs

DOI10.1007/S00010-014-0324-0zbMATH Open1321.05170arXiv1410.2938OpenAlexW2036017360MaRDI QIDQ499645FDOQ499645

Authors: Walter Carballosa, José M. Rodríguez, Jose M. Sigarreta 

Publication date: 30 September 2015

Published in: Aequationes Mathematicae (Search for Journal in Brave)

Abstract: If X is a geodesic metric space and $x_1,x_2,x_{3}inX$, a {it geodesic triangle} $T=x_1,x_2,x_3$ is the union of the three geodesics $[x_1{x}_2]$, $[x_2{x}_3]$ and $[x_3{x}_1]$ in $X$. The space $X$ is $delta$-emph{hyperbolic} $($in the Gromov sense$)$ if any side of $T$ is contained in a $delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. If $X$ is hyperbolic, we denote by $delta(X)$ the sharp hyperbolicity constant of $X$, i.e. $$delta$$ Some previous works characterize the hyperbolic product graphs (for the Cartesian product, strong product and lexicographic product) in terms of properties of the factor graphs. In this paper we characterize the hyperbolic product graphs for graph join $G_{1}uplus{G}_2$ and the corona $G_{1}diamond{G}_2$: $G_{1}uplus{G}_2$ is always hyperbolic, and $G_{1}diamond{G}_2$ is hyperbolic if and only if $G_1$ is hyperbolic. Furthermore, we obtain simple formulae for the hyperbolicity constant of the graph join $G_{1}uplus{G}_2$ and the corona $G_{1}diamond{G}_2$.

Full work available at URL: https://arxiv.org/abs/1410.2938

Recommendations

• Gromov hyperbolicity in Cartesian product graphs
• Gromov hyperbolicity in lexicographic product graphs
• Characterization of the hyperbolicity in the lexicographic product
• Gromov hyperbolicity in strong product graphs
• Results on hyperbolicity in graphs: a survey

zbMATH Keywords

Gromov hyperbolicityinfinite graphcorona graphgraph join

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Infinite graphs (05C63) Combinatorial inequalities (05A20)

Cites Work

• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• On the corona of two graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gromov hyperbolicity in lexicographic product graphs
• On the strong metric dimension of corona product graphs and join graphs
• Hyperbolicity in median graphs
• Computing the hyperbolicity constant
• Characterization of Gromov hyperbolic short graphs
• Discrete groups. Transl. from the Japanese by Ken'ichi Ohshika
• Gromov hyperbolic tessellation graphs
• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
• Hyperbolicity and parameters of graphs.
• Gromov hyperbolicity in Cartesian product graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Gromov hyperbolic graphs
• Gromov hyperbolicity in strong product graphs
• Gromov hyperbolic cubic graphs
• On the hyperbolicity of chordal graphs
• Graph homotopy and Graham homotopy
• On the hyperbolicity constant in graphs
• On the hyperbolicity constant of line graphs
• Hyperbolicity and complement of graphs
• Small values of the hyperbolicity constant in graphs
• Artin groups of finite type are biautomatic
• Coloring, location and domination of corona graphs
• Algorithms and Computation
• The Join of Graphs and Crossing Numbers
• On the join of graphs and chromatic uniqueness

Cited In (12)

• On the hyperbolicity constant in graph minors
• Gromov hyperbolicity in Mycielskian graphs
• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• Mathematical properties of the hyperbolicity of circulant networks
• Characterization of the hyperbolicity in the lexicographic product
• Gromov hyperbolicity in Cartesian product graphs
• Gromov hyperbolicity in the Cartesian sum of graphs
• On a classical theorem on the diameter and minimum degree of a graph
• Geometric and topological properties of the complementary prism networks
• Gromov hyperbolicity in lexicographic product graphs
• Bounds on Gromov hyperbolicity constant
• Results on hyperbolicity in graphs: a survey

This page was built for publication: Hyperbolicity in the corona and join of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499645)