Gromov hyperbolicity in the Cartesian sum of graphs Articles uri icon

publication date

  • March 2017

international standard serial number (ISSN)

  • 1017-060X

electronic international standard serial number (EISSN)

  • 1735-8515


  • In this paper we characterize the hyperbolic product graphs for the Cartesian sum G1⊕G2‎: ‎G1⊕G2 is always hyperbolic‎, ‎unless either G1 or G2 is the trivial graph (the graph with a single vertex); if G1 or G2 is the trivial graph‎, ‎then G1⊕G2 is hyperbolic if and only if G2 or G1 is hyperbolic‎, ‎respectively‎. ‎Besides‎, ‎we characterize the Cartesian sums with hyperbolicity constant delta(G1⊕G2)=t for every value of t‎. ‎Furthermore‎, ‎we obtain the sharp inequalities 1≤delta(G1⊕G2)≤3/2 for every non-trivial graphs G1,G2‎. ‎Also‎, ‎we obtain simple formulas for the hyperbolicity constant of the Cartesian sum of many graphs‎. ‎Finally‎, ‎we prove the inequalities 3/2≤delta(G1⊕G2)≤2 for the complement graph of G1⊕G2 for every G1,G2 with min{diamV(G1)‎,‎diamV(G2)}≥3.