%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  VERSION LATEX de HIPERBOLICIDAD DE PRODUCTO FUERTE DE GRAFOS

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  The Electronic Journal of Combinatorics

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2}{20(3)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\allowdisplaybreaks
\usepackage[utf8]{inputenc}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\cotan}{cotan}
\DeclareMathOperator{\cotanh}{cotanh}
\DeclareMathOperator{\sech}{sech}
\DeclareMathOperator{\Arcsinh}{Arcsinh}
\DeclareMathOperator{\Arccosh}{Arccosh}
\DeclareMathOperator{\Arctanh}{Arctanh}

%%%%%%%%%%%%%%%%%%%
% Letras griegas  %
%%%%%%%%%%%%%%%%%%%
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\e}{\varepsilon}
\renewcommand{\d}{\delta}
\newcommand{\g}{\gamma}
\newcommand{\G}{\Gamma}
\renewcommand{\th}{\theta}
%\renewcommand{\l}{\lambda}
\renewcommand{\O}{\Omega}
\newcommand{\s}{\sigma}
%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Gromov hyperbolicity \\ in strong product graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Walter Carballosa\\
\small Departamento de Matem\'aticas\\[-0.8ex]
\small Universidad Carlos III de Madrid\\[-0.8ex]
\small Av. de la Universidad 30, 28911 Legan\'es, Madrid, Spain\\
\small\tt wcarball@math.uc3m.es\\
\and
Roc\'io M. Casablanca\\
\small Departamento de Matem\'atica Aplicada I\\[-0.8ex]
\small Universidad de Sevilla\\[-0.8ex]
\small Av. Reina Mercedes 2, 41012 Sevilla, Spain\\
\small\tt rociomc@us.es\\
\and
Amauris de la Cruz \qquad Jos\'e M. Rodr{\'\i}guez\\
\small Departamento de Matem\'aticas\\[-0.8ex]
\small Universidad Carlos III de Madrid\\[-0.8ex]
\small Av. de la Universidad 30, 28911 Legan\'es, Madrid, Spain\\
\small\tt alcruz@econ-est.uc3m.es, jomaro@math.uc3m.es
}

%
%
%\author{Walter Carballosa \qquad Amauris de la Cruz\\
%\small Departamento de Matem\'aticas\\[-0.8ex]
%\small Universidad Carlos III de Madrid\\[-0.8ex]
%\small Av. de la Universidad 30, 28911 Legan\'es, Madrid, Spain\\
%\small\tt wcarball@math.uc3m.es, alcruz@econ-est.uc3m.es\\
%\and
%Roc\'io M. Casablanca\\
%\small Departamento de Matem\'atica Aplicada I\\[-0.8ex]
%\small Universidad de Sevilla\\[-0.8ex]
%\small Av. Reina Mercedes 2, 41012 Sevilla, Spain\\
%\small\tt rociomc@us.es\\
%\and
%Jos\'e M. Rodr{\'\i}guez\\
%\small Departamento de Matem\'aticas\\[-0.8ex]
%\small Universidad Carlos III de Madrid\\[-0.8ex]
%\small Av. de la Universidad 30, 28911 Legan\'es, Madrid, Spain\\
%\small\tt jomaro@math.uc3m.es
%}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{April 6, 2013}{June 28, 2013}{Jul 19, 2013}\\
\small Mathematics Subject Classifications: 05C69;  05A20; 05C50}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\vspace*{-2ex}
\begin{abstract}
  If X is a geodesic metric space and $x_1,x_2,x_3\in X$, a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and $[x_3x_1]$ in $X$. The space $X$ is $\d$-\emph{hyperbolic} $($in the Gromov sense$)$ if any side of $T$ is contained in a $\d$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. If $X$ is hyperbolic, we denote by $\d(X)$ the sharp hyperbolicity constant of $X$, i.e. $\d(X)=\inf\{\d\ge 0: \, X \, \text{ is $\d$-hyperbolic}\,\}\,.$ In this paper we characterize the strong product of two graphs $G_1\boxtimes G_2$ which are hyperbolic, in terms of $G_1$ and $G_2$: the strong product graph $G_1\boxtimes G_2$ is hyperbolic if and only if one of the factors is hyperbolic and the other one is bounded. 
  We also prove some sharp relations between $\d(G_1\boxtimes G_2)$, $\d(G_1)$, $\d(G_2)$ and the diameters of $G_1$ and $G_2$ (and we find families of graphs for which the inequalities are attained). 
  Furthermore, we obtain the exact values of the hyperbolicity constant for many strong product graphs.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Strong Product Graphs;  Geodesics; Gromov Hyperbolicity;  Infinite Graphs
\end{abstract}




%--------------------------- Introduction ----------------------------

\section{Introduction}


The study of mathematical properties of Gromov hyperbolic spaces
and its applications is a topic of recent and increasing interest in
graph theory; see, for instance, \cite{BRST,BRSV,BHB1,CGPR1,CGPR2,CPeRS,CPoRS,CRS,CRSV,CDEHV,K50,K27,
K21,K22,K23,K24,K56,MRSV,MRSV2,PRSV,PRT1,RSVV,RT1,RT3,Si,T}.
It is well known that most networks can be modeled by a graph $G=(V,E)$, where $V$ is the set of mainly elements and $E$ is the set of communication links between them in the network. Different methods have been proposed for configuration processing and data generation. Some of them are structural models which can be seen as the product graph of two given graphs, known as factors or generators. Many properties of structural models can be obtained by considering the properties of their generators. The different kinds of products of graphs are an important research topic in Graph Theory. In particular, the strong product graph operation has been extensively investigated in relation to a wide range of subjects \cite{ACDG13,CHMPP10,KK08,S10}. A fundamental principle for network design is extenda\-bility. That is to say, the possibility of building larger versions of a network preserving certain desirable properties. For designing large-scale interconnection networks, the strong p
 roduct is a useful method to obtain large graphs from smaller ones whose invariants can be easily calculated \cite{CHMPP10,KK08,S10}.

The theory of Gromov hyperbolic spaces was used initially for the study of
finitely generated groups, where it was demonstrated to have an
enormous practical importance. This theory was applied principally
to the study of automatic groups (see \cite{O}), which plays an
important role in sciences of the computation. Another important
application of these spaces is the secure transmission of information by
internet. In particular, the hyperbolicity plays an important role in the spread of viruses through the
network (see \cite {K21,K22}).
The hyperbolicity is also useful in the study of DNA data (see \cite{BHB1}).

Last years several researchers have been interested in showing
that metrics used in geometric function theory are Gromov
hyperbolic. For instance, the Gehring-Osgood $j$-metric
is Gromov hyperbolic; and the Vuorinen $j$-metric is not Gromov
hyperbolic except in the punctured space (see \cite{Ha}).
The study of Gromov hyperbolicity of the quasihyperbolic and the
Poincar\'e metrics is the subject of
\cite{APRT,BB,BHK,HLPRT,HPRT,HPRT2,HPRT3,PRT1,PT,RT1,RT2,RT3,T}.
In particular, the equivalence of the hyperbolicity of Riemannian manifolds and the hyperbolicity
of a simple graph was proved in \cite{PRT1,RT1,RT3,T}, hence, it is useful to know hyperbolicity criteria for graphs.

Notations and terminology not explicitly given here can be found in \cite{GH}.
We present now some basic facts about Gromov's spaces.
Let $(X,d)$ be a metric space and let $\g:[a,b]\longrightarrow X$ be a continuous function.
We define the \emph{length} of $\g$ as
\[
L(\g):=\sup\Big\{ \sum_{i=1}^n d(\g(t_{i-1}),\g(t_{i})):\,
a=t_0<t_1<\cdots <t_n=b\Big\}\,.
\]
We say that $\g$ is a
\emph{geodesic} if it is an isometry, i.e.
$d(\g(t),\g(s))=s-t$ for every $t<s$. We
say that $X$ is a \emph{geodesic metric space} if for every $x,y\in
X$ there exists a geodesic joining $x$ and $y$; we denote by $[xy]$
any of such geodesics (since we do not require uniqueness of
geodesics, this notation is ambiguous, but it is convenient). It is
clear that every geodesic metric space is path-connected. If $X$ is
a graph, we use the notation $[u,v]$ for the edge joining the vertices $u$ and $v$; in what follows, by $u\sim v$ we mean that $[u,v]\in E(X)$.

In order to consider a graph $G$ as a geodesic metric space, we must identify
(by an isometry) any edge $[u,v]\in E(G)$
with a real interval with length $l:=L([u,v])$; therefore, an inner point
of the edge $[u,v]$ is a point of $G$.
A connected graph $G$ is naturally equipped with a distance defined on its points, induced by taking shortest
paths in $G$.
Then, $G$ can be seen as a metric graph.


Throughout this paper we just consider non-oriented (finite or infinite) connected graphs
with edges of length $1$.
These conditions guarantee that the graphs are geodesic metric spaces.
We also consider simple graphs, that is without loops or multiple edges, which is not a restriction [6, Theorems 6 and 8].
%We do not allow loops and multiple edges in the graphs (i.e., they are simple graphs); this is not a restriction by \cite[Theorems 6 and 8]{BRSV}.


If $X$ is a geodesic metric space and $J=\{J_1,J_2,\dots,J_n\}$ is a polygon
with sides $J_j\subseteq X$, we say that $J$ is $\d$-{\it thin} if for
every $x\in J_i$ we have that $d(x,\cup_{j\neq i}J_{j})\le \d$. We
denote by $\d(J)$ the sharp thin constant of $J$, i.e., $
\d(J):=\inf\{\d\ge 0: \, J \, \text{ is $\d$-thin}\,\}\,. $ If
$x_1,x_2,x_3\in X$, a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is
the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and
$[x_3x_1]$ (sometimes we write $T=\{[x_1x_2],[x_2x_3],[x_3x_1]\}$).
The space $X$ is $\d$-\emph{hyperbolic} $($or satisfies
the {\it Rips condition} with constant $\d)$ if every geodesic
triangle in $X$ is $\d$-thin. We denote by $\d(X)$ the sharp
hyperbolicity constant of $X$, i.e., $\d(X):=\sup\{\d(T): \, T \,
\text{ is a geodesic triangle in }\,X\,\}.$ We say that $X$ is
\emph{hyperbolic} if $X$ is $\d$-hyperbolic for some $\d \ge 0$. If
$X$ is hyperbolic, then $ \d(X)=\inf\{\d\ge 0: \, X \, \text{ is
$\d$-hyperbolic}\,\}$.
A geodesic \emph{bigon} is a geodesic triangle $\{x_1,x_2,x_3\}$ with $x_2=x_3$.
Therefore, every bigon in a $\d$-hyperbolic geodesic metric space is $\d$-thin.




There are several definitions of Gromov hyperbolicity.
These different definitions are equivalent in the sense
that if $X$ is $\d$-hyperbolic with respect to the definition $A$,
then it is $\d'$-hyperbolic with respect to the definition $B$
for some $\d'$ (see, e.g., \cite{BHB,GH}).
We have chosen this definition since
it has a deep geometric meaning (see, e.g., \cite{GH}).



The following remarks are interesting examples of hyperbolic spaces.
The real line $\mathbb{R}$ is $0$-hyperbolic due to any point of a geodesic
triangle in the real line belongs to two sides of the triangle
simultaneously.
The Euclidean plane $\mathbb{R}^2$ is not hyperbolic since the
equilateral triangles can be drawn with arbitrarily large diameter.
This argument can be generalized in a similar way to
higher dimensions: a normed vector space $E$ is hyperbolic if and
only if $\dim\ E=1$. Every arbitrary length metric tree is
$0$-hyperbolic due to all points of a geodesic triangle in a tree
belong simultaneously to two sides of the triangle. Every bounded
metric space $X$ is $((\diam X)/2)$-hyperbolic. Every simply connected
complete Riemannian manifold with sectional curvature verifying
$K\leq -k^2$, for some positive constant $k$, is hyperbolic. We
refer to \cite{BHB,GH} for more background and further results.


Notice that the main examples of hyperbolic graphs are the trees.
In fact, the hyperbolicity constant of a geodesic metric space can be viewed as a measure of
how ``tree-like'' the space is, since those spaces $X$ with $\delta(X) = 0$ are precisely the metric trees.
This is an interesting subject since, in many applications, one finds that the borderline between tractable and intractable cases may be the tree-like degree of the structure to be dealt with
(see, e.g., \cite{CYY}).


If $D$ is a closed connected subset of $X$, we always consider in $D$ the
\emph{inner metric} obtained by the restriction of the metric in
$X$, that is
$$
d_{D}(z,w):= \inf\big\{ L_{X}(\g) : \, \g\subset D \text{ is a
continuous curve joining $z$ and $w$} \big\}\ge d_{X}(z,w)\,. $$
Consequently, $L_{D}(\g) =  L_{X}(\g)$ for every curve $\g\subset D$.




Given a Cayley graph (of a presentation with solvable word problem)
there is an algorithm which allows to decide if it is hyperbolic.
However, the problem of deciding whether a general geodesic metric space is
hyperbolic or not is usually very difficult.
Note that, first of all, we have to consider an arbitrary geodesic triangle $T$, and
calculate the minimum distance from an arbitrary point $P$ of $T$ to
the union of the other two sides of the triangle to which $P$ does
not belong to.
Finally we have to take supremum over all the
possible choices for $P$ and over all the possible choices for $T$.
Without disregarding the difficulty to solve this
minimax problem, notice that in general the main obstacle is that we do not
know the location of geodesics in the space.
Therefore, it is interesting to obtain inequalities involving the hyperbolicity
constant and to study the hyperbolicity of a particular class of graphs.

The papers \cite{BRST,BHB1,CRSV,MRSV2,PeRSV,R,Si} study the hyperbolicity of, respectively, complement of graphs, chordal graphs, line graphs, Cartesian product graphs, cubic graphs, short graphs and median graphs, respectively.
Our aim in this work is to obtain interesting results about the hyperbolicity constant of strong product graphs.

The structure of this paper is as follows. First, in Section 2, we study several inequalities involving the distance in the strong product of graphs and we obtain the exact value of its diameter.
Furthermore, we also study the relations between the geodesics of $G_1\boxtimes G_2$ and geodesics in $G_1$ and $G_2$;
it is not a trivial issue as Example \ref{ex:projSP} will show.

In Section 3, we prove several lower and upper bounds for the hyperbolicity
constant of $G_1\boxtimes G_2$,
involving $\d(G_1)$, $\d(G_2)$ and the diameters of $G_1$ and $G_2$.
One of the main results of this work is Theorem \ref{th:equivSP}, which characterizes the hyperbolic strong product graphs $G_1\boxtimes G_2$ in terms of $G_1$ and $G_2$.
The graph $G_1\boxtimes G_2$ is hyperbolic if and only if one of its factors is hyperbolic
and the other one is bounded.
We also find families of graphs for which many of the inequalities of this section are
attained. Another main result in this paper is Theorem \ref{th:boundSP2mM} which provides the precise value of $\d(G_1\boxtimes G_2)$ for a large class of graphs $G_1,G_2$; this kind of result is not usual at all in the theory of hyperbolic graphs.

We conclude this paper with Section 4 where the exact values of the hyperbolicity constant for
many strong product graphs are calculated.






\section{The distance in strong product graphs}

In order to estimate the hyperbolicity constant of the strong product of two graphs $G_1$ and $G_2$, we must obtain lower and upper bound on the distances between any two arbitrary points in $G_1\boxtimes G_2$. The lemmas of this section provide these estimations. We will use the strong product definition given by Sabidussi in \cite{S60}.

\begin{definition}\label{def:strongprod}
Let $G_1=(V(G_1),E(G_1))$ and $G_2=(V(G_2),E(G_2))$ two graphs. The strong product $G_1\boxtimes G_2$ of $G_1$ and $G_2$ has $V(G_1) \times V(G_2)$ as vertex set, so that two distinct vertices $(u_1;v_1)$ and $(u_2;v_2)$ of $G_1\boxtimes G_2$ are adjacent if either $u_1=u_2$ and $[v_1,v_2]\in E(G_2)$, or $[u_1,u_2]\in E(G_1)$ and $v_1=v_2$, or $[u_1,u_2]\in E(G_1)$ and $[v_1,v_2]\in E(G_2)$.
\end{definition}

Note that the strong product of two graphs is commutative. We use the notation $(u;v)$ instead of $(u,v)$ to the points of the graph $G_1\boxtimes G_2$.
We consider that every edge of $G_1\boxtimes G_2$ has length $1$.

\medskip

Next, we will bound the distances between any two different pair of points in the strong product graph. For this aim we must distinguish some cases depending on the situation of the considered points. Let $p \in G_1$ and $q \in G_2$ be two points of $G_1$ and $G_2$ respectively.
The pair $(p;q)$ is an \emph{inner point} in $G_1 \boxtimes G_2$, if $p \in G_1\setminus V(G_1)$ and $q \in V(G_2)$ or $p \in V(G_1)$ and $q \in G_2\setminus V(G_2)$ or $p \in G_1\setminus V(G_1)$ and $q \in G_2\setminus V(G_2)$ (i.e., $(p;q) \in G_1 \boxtimes G_2\setminus V(G_1 \boxtimes G_2)$).
Notice that the first and second cases of the inner points in $G_1 \boxtimes G_2$ are contained in the Cartesian product graph $G_1 \Box G_2 \subset G_1 \boxtimes G_2$; so the first and second cases are the inner points of the Cartesian edges properly.
In order to represent the inner points of the non Cartesian edges in $G_1 \boxtimes G_2$ we will consider the following assumptions. Let $[A_1,A_2] \in E(G_1)$ and $[B_1,B_2] \in E(G_2)$ be edges in $G_1$ and $G_2$, respectively. Let $p \in [A_1,A_2]$ and $q \in [B_1,B_2] $ be inner points of theses fixed edges; we have $(p;q) \in G_1 \boxtimes G_2 \setminus G_1 \Box G_2$ if $L([pA_1])=L([qB_1])$ or $L([pA_1])=L([qB_2])$.



Notice that there are different points on $G_1 \boxtimes G_2$ with the same representation: the midpoints of $[(A_1;B_1),(A_2;B_2)]$ and $[(A_1;B_2),(A_2;B_1)]$. Then, this notation is ambiguous, but it is convenient.

\medskip

The following lemmas provide bounds on the distance between any two pair of points in the strong product graph $(p_1; q_1), (p_2; q_2) \in G_1 \boxtimes G_2$.


The first one is a well known property about distances between vertices in the strong product of graphs proved in \cite{IK00}.

\begin{lemma}[Lemma 5.1 in \cite{IK00}]\label{l:vertices}
Let $G_1$, $G_2$ be any graphs. If  $p_1,p_2 \in V(G_1)$ and $q_1,q_2 \in V(G_2)$, then
$$d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) = \max \{ d_{G_1}(p_1,p_2) , d_{G_2}(q_1,q_2)\}.$$
\end{lemma}

Next, a lower bound on the distance between any two points in the strong product graph.

\begin{proposition}\label{prop:lowboundDist}
Let $G_1$, $G_2$ be any graphs. For every $(p_1;q_1),(p_2;q_2) \in G_1 \boxtimes G_2$ we have

   \begin{equation}\label{eq:lowboundDist}
      d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) \geq \max \{d_{G_1}(p_1 , p_2) , d_{G_2}(q_1 , q_2) \}.
   \end{equation}
\end{proposition}

\medskip

\begin{proof}
   By symmetry, it suffices to prove $d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) \geq d_{G_1}(p_1 , p_2)$. Seeking for a contradiction, assume that $d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) < d_{G_1}(p_1 , p_2)$.

   \bigskip

   Hence, there exist a geodesic $\G$ joining $(p_1;q_1)$ and $(p_2;q_2)$ in $G_1\boxtimes G_2$ with $L(\G) < d_{G_1}(p_1 , p_2)$.
   Denote by $(A_{1} ; B_{1}),\ldots,(A_{k} ; B_{k})$ the vertices of $G_1\boxtimes G_2$ in $\G$; without loss of generality we can assume that $\G$ meets $(A_{1} ; B_{1}),\ldots,(A_{k} ; B_{k})$ in this order. Then, we have

   $$\G:= [(p_1;q_1) (A_{1} ; B_{1})] \bigcup \left\{ \bigcup_{j=1}^{k-1} [(A_{j} ; B_{j}),(A_{j+1} ; B_{j+1})]\right\} \bigcup [(A_{k} ; B_{k})  (p_2;q_2)].$$


   By Definition \ref{def:strongprod}, we obtain that

   $$\g:= [p_1 A_{1}] \bigcup \left\{ \bigcup_{j=1}^{k-1} [A_{j} A_{j+1}]\right\} \bigcup [A_{k} p_2]$$
   is a path joining $p_1$ and $p_2$ such that $L(\g) \leq L(\G) < d_{G_1}(p_1 , p_2)$.
   This is the contradiction we were looking for.
\end{proof}

The following result provides an upper bound for the distance between a vertex and an inner point, as well as between two inner points in $G_1\boxtimes G_2$.




\begin{proposition}\label{prop:upperboundDist}
Let $G_1$, $G_2$  be any graphs.
\begin{itemize}
  \item[(i)] {If  $(u;v) \in V(G_1 \boxtimes G_2)$ and $(p;q) \in G_1 \boxtimes G_2 \setminus V(G_1 \boxtimes G_2 )$, then
      \begin{equation}\label{eq:pv}
      d_{G_1 \boxtimes G_2}((u;v),(p;q))\leq \max \{d_{G_1}(u, p), d_{G_2}(v,q)\}+1.
      \end{equation}

      }

  \item[(ii)] {If   $(p_1;q_1), (p_2;q_2) \in G_1\boxtimes G_2\setminus V(G_1\boxtimes G_2)$, then
      \begin{equation}\label{eq:pp}
      d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) \leq \max \{ d_{G_1}(p_1 , p_2) , d_{G_2}(q_1 , q_2)\} + 2.
      \end{equation}

      }
\end{itemize}
\end{proposition}


\begin{proof}
In order to prove (i), let us consider $[(u_1;v_1),(u_2;v_2)]\in E(G_1\boxtimes G_2)$ such that $(p;q)\in[(u_1;v_1),(u_2;v_2)]$. Let $\g$ be a geodesic in $G_1\boxtimes G_2$ joining $(u;v)$ and $(p;q)$. Without loss of generality we can assume that $(u_1;v_1)\in\g$.
Define $\e:=d_{G_1\boxtimes G_2}((u_1;v_1),(p;q))$.
By Lemma \ref{l:vertices}, we have
\[
\begin{aligned}
d_{G_1\boxtimes G_2}((u;v),(p;q)) & = \max\{ d_{G_1}(u,u_1), d_{G_2}(v,v_1) \} + \e \\
& \le \max\{ d_{G_1}(u,p) + d_{G_1}(p,u_1), d_{G_2}(v,q) + d_{G_2}(q,v_1)\} + \e \\
& \le \max\{ d_{G_1}(u,p), d_{G_2}(v,q) \} + 2\e.
\end{aligned}
\]
If $\e\le 1/2$, then we have \eqref{eq:pv}.
If $\e> 1/2$, then we have $\max\{ d_{G_1}(u,u_2), d_{G_2}(v,v_2) \}$ $= \max\{ d_{G_1}(u,u_1), d_{G_2}(v,v_1) \} + 1$; thus, $d_{G_1\boxtimes G_2}\big((u;v), (p;q)\big) = \max\{ d_{G_1}(u,p),d_{G_2}(v,q) \}$.

\smallskip

In order to proof (ii), notice that if $(p_1;q_1),(p_2;q_2)$ belong to the same edge of $G_1\boxtimes G_2$, then we have the result since $d_{G_1\boxtimes G_2}((p_1;q_1) , (p_2;q_2)) < 1$.
Assume now that $(p_1;q_1),(p_2;q_2)$ belong to different edges of $G_1\boxtimes G_2$.
Let us consider $(u_1;v_1),(u_2;v_2),(u_3;v_3),(u_4;v_4)\in V(G_1\boxtimes G_2)$ such that $(p_1;q_1)\in[(u_1;v_1),(u_2;v_2)]$ and $(p_2;q_2)\in[(u_3;v_3),(u_4;v_4)]$.
Let $\g^*$ be a geodesic in $G_1\boxtimes G_2$ joining $(p_1;q_1)$ and $(p_2;q_2)$. Without loss of generality we can assume that $(u_2;v_2),(u_3;v_3)\in\g^*$. Define $\e_1:=d_{G_1\boxtimes G_2}((u_2;v_2),(p_1;q_1))$ and $\e_2:=d_{G_1\boxtimes G_2}((u_3;v_3),(p_2;q_2))$.
Then, we have

\[
\begin{aligned}
d_{G_1\boxtimes G_2}((p_1;q_1),(p_2;q_2)) & = \e_1 + \max\{ d_{G_1}(u_2,u_3), d_{G_2}(v_2,v_3) \} + \e_2 \\
& \le 2 \e_1 + \max\{ d_{G_1}(p_1,p_2) , d_{G_2}(q_1,q_2)\} + 2 \e_2.
\end{aligned}
\]
Notice that if $\e_1,\e_2\le 1/2$, then \eqref{eq:pp} holds directly.
If $\e_1> 1/2$ (the case $\e_2> 1/2$ is analogous), then $\max\{ d_{G_1}(u_1,u_3), d_{G_2}(v_1,v_3) \} =$ $\max\{ d_{G_1}(u_2,u_3),d_{G_2}(v_2,v_3) \} + 1$; thus, $d_{G_1\boxtimes G_2}\big((p_1;q_1), (u_3;v_3)\big) = \max\{ d_{G_1}(p_1,u_3), d_{G_2}(q_1,v_3) \}$. Hence, we have

\[
\begin{aligned}
d_{G_1\boxtimes G_2}\big( (p_1;q_1),(p_2;q_2) \big) & = \max\{ d_{G_1}(p_1,u_3), d_{G_2}(q_1,v_3) \} + \e_2 \\
& \le \max\{ d_{G_1}(p_1,p_2) + d_{G_1}(p_2,u_3) , d_{G_2}(q_1,q_2) + d_{G_2}(q_2,v_3)\} + \e_2 \\
& \le \max\{ d_{G_1}(p_1,p_2), d_{G_2}(q_1,q_2) \} + 2 \e_2.
\end{aligned}
\]
This finishes the proof.
\end{proof}

The previous lemmas let us announce the following general result on the distances in the strong product
of two graphs.

\begin{theorem}\label{th:DistStrongP}
For all graphs $G_1, G_2$ we have:
\begin{itemize}%{enumerate}[(a)]
\item[a$)$]  {$d_{G_1\boxtimes G_2}((p_1;q_1),(p_2;q_2))=\max\{d_{G_1}(p_1,p_2),d_{G_2}(q_1,q_2)\}$, for every $(p_1;q_1),(p_2;q_2)\in V(G_1\boxtimes G_2)$,}

\medskip

\item[b$)$]  {$\max\{d_{G_1}(p_1,p_2),d_{G_2}(q_1,q_2)\}\leq d_{G_1\boxtimes G_2}((p_1;q_1),(p_2;q_2)) \leq \max\{d_{G_1}(p_1,p_2),d_{G_2}(q_1,q_2)\}$ $+1$, for every  $(p_1;q_1) \in V(G_1 \boxtimes G_2)$ and $(p_2;q_2) \in G_1 \boxtimes G_2$,}

\medskip

\item[c$)$]  {$\max\{d_{G_1}(p_1,p_2),d_{G_2}(q_1,q_2)\}\leq d_{G_1\boxtimes G_2}((p_1;q_1),(p_2;q_2)) \leq \max\{d_{G_1}(p_1,p_2),d_{G_2}(q_1,q_2)\}$ $+2$, for every $(p_1;q_1), (p_2;q_2) \in G_1\boxtimes G_2$.}
\end{itemize}
\end{theorem}



\medskip

Let us consider the projection $P_k:G_1\boxtimes G_2\longrightarrow G_k$ for $k\in\{1,2\}$.



\begin{corollary}\label{cor:Rsimetric}
   Let $\{i,j\}$ be a permutation of $\{1,2\}$. Then, for every $x,y$ in $G_1\boxtimes G_2$,

   \begin{equation}\label{eq:Rsimetric}
      d_{G_i}(P_i(x) , P_i(y)) \le d_{G_1\boxtimes G_2}(x,y) \le d_{G_i}(P_i(x) , P_i(y)) + \diam G_j + 2.
   \end{equation}
\end{corollary}


These results provide information about the geodesics in $G_1\boxtimes G_2$.
Notice that, if $\g$ is a geodesic joining $x$ and $y$ in $G_1\boxtimes G_2$, then it is possible that $P_j(\g)$ does not contain a geodesic joining $P_j(x)$ and $P_j(y)$ in $G_j$, as the following example shows.





\begin{example}\label{ex:projSP}
Consider a cycle graph $G_1$ with vertices $\{v_1,\ldots,v_n\}$ such that $v_i\sim v_{i+1}$ for every $i\in\{1,\ldots,n-1\}$ and a path graph $G_2$ with vertices $\{w_1,\ldots,w_n\}$ such that $w_i\sim w_{i+1}$ for every $i\in\{1,\ldots,n-1\}$.
By Lemma \ref{l:vertices}, we have that $\g:=\cup_{i=1}^{n-1}[(v_i;w_i),(v_{i+1};w_{i+1})]$ is a geodesic joining $(v_1;w_1)$ and $(v_n;w_n)$ in $G_1\boxtimes G_2$, but $P_1(\g)=\cup_{i=1}^{n-1}[v_i,v_{i+1}]$ does not contain the geodesic joining $v_1$ and $v_n$ in $G_1$ (the edge $[v_1,v_n]$).
\end{example}










The following result allows to compute the diameter of the strong product of two graphs. We denote by $E_1$ the graph with just a single vertex.



\begin{theorem}\label{th:diamSP}
Let $G_1, G_2$ be any graphs. Then we have

\[  \diam G_1\boxtimes G_2=\left\{
\begin{array}{ll}
\max\{\diam G_1,\diam G_2\},\quad \quad \mbox{if } G_1 \text{ or } G_2 \text{ is an isomorphic graph to } E_1,\\

\\

\max\{\diam V(G_1),\diam V(G_2)\} + 1,\quad \quad \mbox{otherwise}.
\end{array}
\right.
\]

 \end{theorem}

 \medskip

\begin{proof}
Since for any graph $G$, $E_1 \boxtimes G$ is isomorphic to $G$ we have the first equality.
By Lemma \ref{l:vertices}, we have $\diam V(G_1\boxtimes G_2)=\max\{\diam V(G_1),\diam V(G_2)\}$; hence,

$$\max\{\diam V(G_1),\diam V(G_2)\} \leq \diam G_1\boxtimes G_2 \leq \max\{\diam V(G_1),\diam V(G_2)\} + 1.$$

\smallskip

\noindent Without loss of generality we can assume that $\diam V(G_1) \leq \diam V(G_2)$.
If $\diam  V(G_2)$ $= \infty$, then the inequality holds.
Hence, we can assume that $G_1$ and $G_2$ are bounded.
Let $B_1,B_2$ be vertices of $G_2$ such that $d_{G_2} (B_1,B_2) = \diam V(G_2)$, and let $A_1,A_2$ be two adjacent vertices of $G_1$.
Let $M_1$ (respectively, $M_2$) be the midpoint of $[(A_1;B_1),(A_2;B_1)]$ (respectively, $[(A_1;B_2),(A_2;B_2)]$).
One can check that $d_{G_1\boxtimes G_2} (M_1 , M_2) = \diam V(G_2) + 1$.

This finish the proof.
\end{proof}




Note that, in particular, $\diam G_1\boxtimes G_2 = \diam V(G_1\boxtimes G_2) + 1$ if $G_1$ and $G_2$ are not isomorphic to $E_1$.



We say that a subgraph  $\G$ of $G$ is \emph{isometric} if
$d_{\G}(x,y)=d_{G}(x,y)$ for every $x,y\in \G$.

We can deduce several results from Theorem \ref{th:diamSP}.
The first one says that $\max\{\diam G_1$, $\diam G_2\}$ is a good approximation of the
diameter of $G_1\boxtimes G_2$.


\begin{corollary}\label{cor:diameterboundSP}
For all graphs $G_1, G_2$ we have
\[
\max\{ \diam G_1 , \diam G_2 \} \leq \diam G_1\boxtimes G_2\leq \max\{ \diam G_1 , \diam G_2 \} + 1.
\]
\end{corollary}

\begin{proof}
If $V$ is a vertex of $G_1$ (respectively, $G_2$), then, by Proposition \ref{prop:lowboundDist}, we have that $\{V\}\boxtimes G_2$ (respectively, $G_1\boxtimes\{V\}$) is an isometric subgraph of $G_1\boxtimes G_2$. Hence, we obtain the first inequality.
The second one is a consequence of Theorem \ref{th:diamSP} and the inequality $\diam V(G) \leq \diam G$.
\end{proof}

Furthermore, we characterize the graphs with $\diam G_1\boxtimes G_2 = \max\{ \diam  G_1 , \diam G_2 \}$.


\begin{corollary}\label{cor:diamSP}
The equality
$\diam G_1\boxtimes G_2 = \max \{ \diam G_1 , \diam G_2 \}$ holds
if and only if $G_1$ or $G_2$ is isomorphic to $E_1$, or $\diam G = \diam V(G) + 1$ for $G \in \{G_1,G_2\}$ with $\diam G = \max\{ \diam G_1 , \diam G_2 \}$.
\end{corollary}


\

\section{Bounds for the hyperbolicity constant.}

Some bounds for the hyperbolicity constant of the strong product of two graphs are studied in this section.
These bounds allow to prove Theorem \ref{th:equivSP}, which characterizes the hyperbolic strong product graphs.
The next well-known result will be useful.

\begin{theorem}[Theorem 8 in \cite{RSVV}]
\label{t:diameter1} In any graph $G$ the inequality $\d(G)\le\frac12\,\diam G$ holds and
it is sharp.
\end{theorem}

Thanks to the Theorems \ref{th:diamSP} and \ref{t:diameter1} we obtain the following consequence.

\begin{corollary}\label{cor:SP}
For all graphs $G_1,G_2$, we have $$\d(G_1\boxtimes G_2)\leq\frac{\max\{\diam V(G_1),\diam V(G_2)\} + 1}{2},$$
and the inequality is sharp.
\end{corollary}


Theorems \ref{th:TSPT}, \ref{th:CnSPCm} and \ref{th:PnSPCm} are families of examples for which the equality in the previous corollary is attained.

\medskip





Taking into account that $E_1\boxtimes G$ is an isomorphic graph to $G$, we have the following result.


\begin{corollary}\label{cor:Isometric}
For every graph $G$ we have
$$\d(G\boxtimes E_1)=\d(E_1\boxtimes G)=\d(G).$$
\end{corollary}


\medskip

The next result will be useful.

\begin{lemma}[Lemma 5 in \cite{RSVV}]
\label{l:subgraph} If $\G$ is an isometric subgraph of $G$, then
$\d(\G) \le \d(G)$.
\end{lemma}









All the previous results allow us to present the following theorem which provides some lower bounds for $\d(G_1\boxtimes G_2)$.

\begin{theorem}\label{th:infSP}
For all graphs $G_1,G_2$ we have:
\begin{itemize}
\item [(a)]{$\d(G_1\boxtimes G_2)\geq \max\{\d(G_1),\d(G_2)\},$}

\item [(b)]{$\d(G_1\boxtimes G_2)\geq \frac12 \, \min\{\diam V(G_1),\diam V(G_2)\},$}

\item [(c)]{$\d(G_1\boxtimes G_2)\geq \frac12 \, \big(\diam V(G_1)+1\big),$ if \ $0<\diam V(G_1)<\diam V(G_2),$}

\item [(d)]{$\d(G_1\boxtimes G_2)\geq\frac{1}{4} \min\{\diam V(G_1) + 2 \d(G_2) , \diam V(G_2) + 2 \d(G_1)\}.$}
\end{itemize}
\end{theorem}


\begin{proof}
Part $(a)$ is immediate due to $G_1\boxtimes\{v\}$ and $\{u\}\boxtimes G_2$
are isometric subgraphs of $G_1\boxtimes G_2$ for every $(u;v)\in V(G_1\boxtimes G_2)$.
Then Lemma \ref{l:subgraph} gives that
$\d(G_1\boxtimes G_2)\geq\d(G_1\boxtimes\{v\})=\d(G_1)$ and $\d(G_1\boxtimes
G_2)\geq\d(\{u\}\boxtimes G_2)=\d(G_2)$.
Hence, we obtain $\d(G_1\boxtimes G_2)\geq \max\{\d(G_1),\d(G_2)\}$.

\smallskip
Let $D:=\min\{\diam V(G_1),\diam V(G_2)\}$.

Let us prove $(b)$.  If $D=0$, then $(b)$ holds; so, we just consider $D>0$.
If $D<\infty$, let us consider a geodesic square $K:=\{\g_1,\g_2,\g_3,\g_4\}$ in
$G_1\Box G_2 \subset G_1\boxtimes G_2$ with sides of length $D$;
then $T:=\{\g_1,\g_2,\g\}$ is a geodesic triangle in $G_1\boxtimes G_2$, where $\g$ is a ``diagonal'' geodesic joining the endpoints of $\g_1\cup\g_2$.
It is clear that the midpoint $p$ of $\g$ satisfies $d_{G_1\boxtimes G_2}(p,\g_1\cup\g_2)=D/2$;
therefore $\d(T)\geq D/2$ and, consequently, $\d(G_1\boxtimes G_2)\geq D/2$.
If $D=\infty$, we can repeat the same argument for any integer $N$ instead of $D$,
and we obtain $\d(G_1\boxtimes G_2)\geq N/2$, for every $N$: hence, $\d(G_1\boxtimes G_2)=\infty=D/2$.

\smallskip

In order to prove $(c)$, note that $D<\infty$.
Let us consider a geodesic rectangle $R:=\{\s_1,\s_2,\s_3,\s_4\}$ in $G_1\Box G_2 \subset G_1\boxtimes G_2$ with $L(\s_1)=L(\s_3)=\diam V(G_1)$ and $L(\s_2)=L(\s_4)=\diam V(G_1)+1$.
Denote by $\g$ a geodesic in $G_1\boxtimes G_2$ joining the endpoints of $\s_1\cup\s_2$ which contains the edge in $\s_4$ incident to $\s_1\cap\s_4$; we may choose $\g$ such that it contains a diagonal of a geodesic square in $G_1\boxtimes G_2$.
Then $B:=\{\s_1,\s_2,\g\}$ is a geodesic triangle in $G_1\boxtimes G_2$. If $p$ is the midpoint of $\g$, then

\[
d_{G_1\boxtimes G_2}(p,\s_1\cup\s_2)=\frac{\diam V(G_1) + 1}2.
\]

Consequently, $\d(G_1\boxtimes G_2)\geq\d(B)\geq (\diam V(G_1) + 1)/2$.

\smallskip

Finally, $(d)$. Let $E:=\max\{\d(G_1),\d(G_2)\}$. Then from parts $(a)$ and $(b)$, we have
\begin{align*}
\d(G_1\boxtimes G_2) & \geq \max\left\{ \frac{D}2 , E \right\} \geq \frac{1}{2} \left(\frac{D}2 + E\right) \\
&= \frac{1}{4} \min\{\diam V(G_1)+2E,\diam V(G_2)+2E\}\\
&\geq\frac{1}{4}\min\{\diam V(G_1) + 2 \d(G_2) , \diam V(G_2) + 2 \d(G_1)\}.
\end{align*}
\end{proof}

Theorems \ref{th:CnSPCm} and \ref{th:PnSPCm} provide a family of examples for which the equality in Theorem \ref{th:infSP} (a) is attained.

\smallskip

Corollary \ref{cor:SP} and Theorem \ref{th:infSP} provide lower and upper bounds for $\d(G_1\boxtimes G_2)$ just in terms of distances in $G_1$ and
$G_2$.

\begin{corollary}
For all graphs $G_1,G_2$, we have
\[
\frac12\min\{\diam V(G_1),\diam V(G_2)\}\leq\d(G_1\boxtimes G_2)\leq\frac{1}{2}\big(\max\{\diam V(G_1),\diam V(G_2)\}+1\big).
\]
\end{corollary}


\smallskip

From Theorem \ref{th:infSP} we have obtained several interesting consequences. The following one is a qualitative result about the hyperbolicity of $G_1\boxtimes G_2$.


\begin{theorem}\label{th:SPinfty}
If $G_1$ and $G_2$ are infinite graphs, then $G_1\boxtimes G_2$ is not hyperbolic.
\end{theorem}






\begin{theorem}\label{th:inf2SP}
Let $G_1, G_2$ be graphs with at least two vertices. Let $m$ and $M$ be the minimum and the maximum between $\diam V(G_1)$ and $\diam V(G_2)$, respectively. Then we have
\begin{equation}\label{eq:inf1SP}
   \d(G_1\boxtimes G_2) \geq \min\left\{ m + \frac12, \frac{M}2 \right\}.
\end{equation}
\end{theorem}



\begin{proof}
First of all, we prove
\begin{equation}\label{eq:inf2SP}
\d(G_1\boxtimes G_2) \geq \min\left\{ m, \frac{M}2 \right\}.
\end{equation}

In order to prove this inequality, assume first that $2m \leq M$.
If $m<\infty$, then let us consider a geodesic rectangle $R:=\g_1\cup\g_2\cup\g_3\cup\g_4$ in $G_1\Box G_2 \subset G_1\boxtimes G_2$ with $L(\g_1)=L(\g_3)= 2m$ and $L(\g_2)=L(\g_4)= m$, and consider a geodesic $\g$ joining the endpoints of $\g_1$ and containing the midpoint of $\g_3$;
then $B:=\{\g_1,\g\}$ is a geodesic bigon in $G_1\boxtimes G_2$.
If $p$ is the midpoint of $\g_3$, then $d_{G_1\boxtimes G_2}(p,\g_1)=m$;
therefore $\d(B)\geq m$, and consequently $\d(G_1\boxtimes G_2)\geq m$.
If $m=\infty$, then we can repeat the same argument for any integer $N$ instead of $m$,
and we obtain $\d(G_1\boxtimes G_2)\geq N$, for every $N$; hence, $\d(G_1\boxtimes G_2)=\infty=m$.

If $2m > M$, then $M<\infty$ and
we can repeat the previous argument with $\lfloor M/2\rfloor$ instead of $m$, and we obtain the result when $M$ is even.
If $M$ is odd, let us consider a geodesic rectangle $R:=\g_1\cup\g_2\cup\g_3\cup\g_4$ in $G_1\Box G_2 \subset G_1\boxtimes G_2$ with $L(\g_1)=L(\g_3)= 2\lfloor M/2\rfloor+1=M$ and $L(\g_2)=L(\g_4)= \lfloor M/2\rfloor$; let $p_1,p_2$ be points on $\g_3$ such that $d_{G_1\boxtimes G_2}(p_1, \g_4) = \lfloor M/2\rfloor$ and $d_{G_1\boxtimes G_2}(p_2, \g_2) = \lfloor M/2\rfloor$;
consider a geodesic $\g$ joining the endpoints of $\g_1$ and containing $p_1$ and $p_2$;
then $B:=\{\g_1,\g\}$ is a geodesic bigon in $G_1\boxtimes G_2$.
Denote by $p$ the midpoint of $[p_1 p_2] \subset \g_3$; so, $d_{G_1\boxtimes G_2}(p,\g_1) = M/2$;
therefore, $\d(G_1\boxtimes G_2)\geq\d(B)\geq M/2$.


Since we have proved \eqref{eq:inf2SP}, in order to obtain \eqref{eq:inf1SP}, we can assume that $0 < 2m < M$; then we have $m<\infty$.
If we replace $\lfloor M/2\rfloor$ by $m$ in the previous argument, we obtain $\d(G_1\boxtimes G_2)\geq m + 1/2$.
\end{proof}

Corollary \ref{th:PnSPPm} and Theorems \ref{th:CnSPCm} and \ref{th:PnSPCm} show that the inequality in Theorem \ref{th:inf2SP} is sharp.





\medskip

\begin{theorem}\label{th:boundSP2mM}
Let $G_1,G_2$ be any graphs. Let $m$ and $M$ be the minimum and the maximum between $\diam V(G_1)$ and $\diam V(G_2)$, respectively. If $\ 2m \geq M$, then

\begin{equation}\label{eq:boundSP2mM1}
   \frac{M}2 \leq \d(G_1\boxtimes G_2) \leq \frac{M+1}2.
\end{equation}

Furthermore, if $\ 2m > M>0$, then

\begin{equation}\label{eq:boundSP2mM2}
   \d(G_1\boxtimes G_2) = \frac{M+1}2.
\end{equation}
\end{theorem}

\begin{proof}

If $M=0$, then $\d(G_1\boxtimes G_2)=0$  and (\ref {eq:boundSP2mM1}) holds. If $M>0$, then, by Corollary \ref{cor:SP} and Theorem \ref{th:inf2SP}, the inequalities in \eqref{eq:boundSP2mM1} hold directly.

\smallskip

In order to prove \eqref{eq:boundSP2mM2}, without loss of generality we can assume that $\diam V(G_1) = m$ and $\diam V(G_2)=M$.
Assume first that $M$ is an even number. Since $m>M/2$, let us consider $A_0,A_1,\ldots,A_{M/2+1} \in V(G_1)$ and $B_0,B_1,\ldots,B_{M} \in V(G_2)$ with $\g_1:=A_0 A_1\ldots A_{M/2+1}$ is a geodesic in $G_1$ and $\g_2:=B_0 B_1 \ldots B_{M}$ is a geodesic in $G_2$.
Denote by $X$ (respectively, $Y$) the midpoint of $[(A_0;B_0),(A_1;B_0)]$ (respectively, $[(A_0;B_M),(A_1;B_M)]$).
Let us consider

\[
\G^*:= [X (A_0;B_0)]\bigcup\left\{\bigcup_{i=1}^{M} [(A_0;B_{i-1}),(A_0;B_i)] \right\}\bigcup[(A_0;B_M) Y]
\]
and

\[
\begin{aligned}
\G^\prime:= & [X (A_1;B_0)] \bigcup \left\{\bigcup_{i=1}^{M/2} [(A_i;B_{i-1}),(A_{i+1};B_i)] \right\}\bigcup \\
&\bigcup \left\{\bigcup_{j=M/2+1}^{M} [(A_{M+2-j};B_{j-1}),(A_{M+1-j};B_j)] \right\}\bigcup[(A_1;B_M) Y].
\end{aligned}
\]
Then $B:=\{\G^*,\G^\prime\}$ is a geodesic bigon in $G_1\boxtimes G_2$.
If $p$ is the midpoint of $\G^\prime$, then $d_{G_1\boxtimes G_2}(p,\G^*) = (M + 1)/2$;
therefore, $\d(G_1\boxtimes G_2)\geq \d(B)\geq (M + 1)/2$.
Then, Corollary \ref{cor:SP} gives the equality.

\medskip

Assume now that $M$ is an odd number. Since $m\ge (M+1)/2$, let us consider $A_0,A_1,\ldots,A_{(M+1)/2} \in V(G_1)$ and $B_0,B_1,\ldots,B_{M} \in V(G_2)$ with $\g_1:=A_0 A_1\ldots A_{(M+1)/2}$ is a geodesic in $G_1$ and $\g_2:=B_0 B_1 \ldots B_{M}$ is a geodesic in $G_2$.
Denote by $X$ (respectively, $Y$) the midpoint of $[(A_0;B_0),(A_1;B_0)]$ (respectively, $[(A_0;B_M),(A_1;B_M)]$).
Let us consider

\[
\G^*:= [X (A_0;B_0)]\bigcup\left\{\bigcup_{i=1}^{M} [(A_0;B_{i-1}),(A_0;B_i)] \right\}\bigcup[(A_0;B_M) Y]
\]
and

\[
\begin{aligned}
\G^\prime:= & [X (A_1;B_0)] \bigcup \left\{\bigcup_{i=1}^{(M-1)/2} [(A_i;B_{i-1}),(A_{i+1};B_i)] \right\}\bigcup \\
&\bigcup [(A_{(M+1)/2};B_{(M-1)/2}),(A_{(M+1)/2};B_{(M+1)/2})] \bigcup \\
& \bigcup\left\{\bigcup_{j=(M+1)/2}^{M} [(A_{M+1-j};B_{j-1}),(A_{M-j};B_j)] \right\}\bigcup[(A_1;B_M) Y].
\end{aligned}
\]
Then $B:=\{\G^*,\G^\prime\}$ is a geodesic bigon in $G_1\boxtimes G_2$.
If $p$ is the midpoint of $\G^\prime$, then $d_{G_1\boxtimes G_2}(p,\G^*) = (M + 1)/2$;
therefore, $\d(G_1\boxtimes G_2)\geq \d(B)\geq (M + 1)/2$.
Finally, Corollary \ref{cor:SP} gives the equality.
\end{proof}


Theorems \ref{th:CnSPCm} and \ref{th:PnSPCm} show that the first inequality in Theorem \ref{th:boundSP2mM} is attained.




\medskip


Let $X$ be a metric space, $Y$ a non-empty subset of $X$ and $\varepsilon$ a positive number.
We call $\varepsilon$-\emph{neighborhood}
of $Y$ in $X$, denoted by $V_{\varepsilon}(Y)$ to the set $\{x\in X: d_X(x,Y)\leq\varepsilon\}$.


The next result will be useful in order to prove the upper bound for $\d(G_1\boxtimes G_2)$ in Theorem \ref{th:supSP} below.

\begin{theorem}[Theorem 2.9 in \cite{R}]
\label{t:stablight}
Let $X$ be a $\d$-hyperbolic geodesic metric space, $u,v\in X,$
$b$ a non-negative constant,
$h$ a curve joining $u$ and $v$
with $L(h) \le d(u,v)+b$, and $g=[uv]$.
Then,
$$
h \subseteq V_{8\d+b/2}(g) , \qquad g \subseteq V_{16\d+b}(h).
$$
\end{theorem}

\smallskip

\begin{theorem}\label{th:supSP}
Let $G_1,G_2$ be any graphs. Then, we have
\begin{equation}\label{eq:deltasupSP}
\d(G_1\boxtimes G_2)\leq
\frac52 \diam G_1 + 25 \d(G_2) + 5.
\end{equation}

\end{theorem}

\begin{proof}
It suffices to prove \eqref{eq:deltasupSP} if $G_1$ is bounded and $G_2$ is hyperbolic, since otherwise the inequality $\d(G_1\boxtimes G_2)\leq\infty$ holds.
Let us consider any fixed geodesic triangle $T=\{x,y,z\}$ in $G_1\boxtimes G_2$ and $\a\in T$. In order to bound $\d(T)$, without loss of generality we can assume that $\a\in[xy]$.
Consider the projection $P_2:G_1\boxtimes G_2\longrightarrow G_2$ and any geodesic $\g:=[uv]$ in $G_1\boxtimes G_2$.
By Corollary \ref{cor:Rsimetric}, we obtain
\begin{equation*}
L\big(P_2(\g)\big) \le L(\g) = d_{G_1\boxtimes G_2}(u,v) \leq d_{G_2}\big(P_2(v), P_2(v)\big) + b, \quad \text{ with } b=\diam G_1 + 2.
\end{equation*}

Then, by Theorem \ref{t:stablight}, there is $\a^\prime\in [P_2(x)P_2(y)]$ such that

\begin{equation}\label{eq:supSP2}
d_{G_2}(P_2(\a),\a^\prime) \leq 8 \d(G_2) + \frac{b}2.
\end{equation}

Since $G_2$ is hyperbolic, there is $\b^\prime\in [P_2(y)P_2(z)]\cup[P_2(z)P_2(x)]$ such that

\begin{equation}\label{eq:supSP3}
d_{G_2}(\a^\prime,\b^\prime) \leq \d(G_2).
\end{equation}

By Theorem \ref{t:stablight}, there is $\b^{\prime\prime}\in P_2([yz]\cup[zx])$ such that

\begin{equation}\label{eq:supSP4}
d_{G_2}(\b^\prime, \b^{\prime\prime}) \leq 16 \d(G_2) + b.
\end{equation}
Consequently, by \eqref{eq:supSP2}, \eqref{eq:supSP3} and \eqref{eq:supSP4} we obtain

\begin{equation}\label{eq:supSP5}
d_{G_2}( P_2(\a) , P_2([yz]\cup[zx]) ) \le d_{G_2}(P_2(\a) , \b^{\prime\prime}) \leq 25 \d(G_2) + \frac{3b}2.
\end{equation}

Finally, by Corollary \ref{cor:Rsimetric} and \eqref{eq:supSP5} we obtain

\[
d_{G_1\boxtimes G_2}(\a, [yz]\cup[zx]) \le d_{G_2}( P_2(\a) , P_2([yz]\cup[zx]) ) + b \leq 25 \d(G_2) + \frac{5b}2.
\]
This finishes the proof.
\end{proof}




Theorems \ref{th:infSP} and \ref{th:supSP} provide lower and upper bounds of $\d(G_1\boxtimes G_2)$ in terms of linear combinations of hyperbolicity constants and diameters of its generator graphs, as the following result shows.

\begin{corollary}\label{cor:infsupSP}
For all graphs $G_1,G_2$, we have
\[\frac{1}{4}\min\{2\d(G_1)+\diam V(G_2),2\d(G_2)+\diam V(G_1)\} \leq\d(G_1\boxtimes G_2)\]
\[\leq
\frac52 \min\left\{\diam G_1 + 10 \d(G_2),\diam G_2 + 10 \d(G_1)\right\} + 5.
\]
\end{corollary}



Corollary \ref{cor:infsupSP} allows to obtain the main result of this work:
the characterization of the hyperbolic graphs $G_1\boxtimes G_2$.


\begin{theorem}\label{th:equivSP}
For all graphs $G_1,G_2$ we have that $G_1\boxtimes G_2$ is hyperbolic if and only if $G_1$ is hyperbolic and $G_2$ is bounded or $G_2$ is hyperbolic and $G_1$ is bounded.
\end{theorem}






Many parameters $\g$ of graphs satisfy the inequality
$\g(G_1 \boxtimes G_2) \ge \g(G_1) + \g(G_2)$. Therefore,
one could think that the inequality $\d(G_1\boxtimes G_2)\geq\d(G_1)+\d(G_2)$ holds for
all graphs $G_1,G_2$. However, this is false, as the following example shows:

\begin{example}
$\d(P\boxtimes C_4)<\d(P)+\d(C_4)$, where $P$ is the Petersen graph.
\end{example}


We have that $\diam V(P)=2$, $\diam V(C_4)=2$. Besides,
Theorem 11 in \cite{RSVV} gives that $\d(P)=3/2$ and $\d(C_4)=1$.
By Theorem \ref{th:boundSP2mM}, we obtain $\d(P\boxtimes C_4)= 3/2<3/2+1=\d(P)+\d(C_4)$.


The inequality
$\d(G_1 \boxtimes G_2) \le \d(G_1) + \d(G_2)$ is also false, since $\d(P_2\boxtimes P_2) = \d(K_4)=1 > 2\d(P_2) = 0$.


\


\section{Computation of the hyperbolicity constant for some product graphs}

This last section present the value of the hyperbolicity constant for many product of graphs.

The following results in \cite{BRS} will be useful.
Denote by $J(G)$ the set of vertices and midpoints of edges in $G$.
As usual, by \emph{cycle} we mean a simple closed curve, i.e., a path with different vertices,
unless the last one, which is equal to the first vertex.

\smallskip

First, remark some previous results of \cite{BRS} which will be useful.

\begin{theorem}[Theorem 2.6 in \cite{BRS}]
\label{t:multk/4}
For every hyperbolic graph $G$, $\d(G)$ is a multiple of $1/4$.
\end{theorem}

\begin{theorem}[Theorem 2.7 in \cite{BRS}]
\label{t:TrianVMp}
For any hyperbolic graph $G$, there exists
a geodesic triangle $T = \{x, y, z\}$ that is a cycle with $x, y, z \in J(G)$ and $\d(T) = \d(G)$.
\end{theorem}

\begin{remark}
\label{r:TrianVMp}
By Theorems \ref{t:multk/4} and \ref{t:TrianVMp}, in order to compute the hyperbolicity constant of a graph $G$
it suffices to consider $d_G(p,[xz]\cup [yz])$ where $T = \{x, y, z\}$ is a geodesic triangle that is a cycle with $x, y, z \in J(G)$ and $p\in [x y]$ satisfies $d_G(p,V(G)) \in \{0,1/4,1/2\}$.
\end{remark}


The following results characterize the hyperbolicity constant of the strong product of trees and certain graphs.
These results are interesting by themselves and, furthermore, they will be useful in order to prove the last theorems of this paper.


\begin{theorem}\label{th:GSPT>}
Let $T$ be any tree and $G$ any graph with \ $0< \diam V(G) < \diam T /2$. Then, we have
\[
\d(G\boxtimes T)=\diam V(G) + \frac12.
\]
\end{theorem}

\begin{proof}
On the one hand, Theorem \ref{th:inf2SP} gives $\d(G\boxtimes T) \geq \diam V(G) + 1/2$.
On the other hand, by Theorem \ref{t:TrianVMp} it suffices to consider geodesic triangles $\triangle=\{x,y,z\}$ in $G\boxtimes T$ which are cycles with $x,y,z\in J(G\boxtimes T)$.
Let $(v;w)$ be a vertex in $[xy]$.
If $d_{G\boxtimes T}( (v;w), \{x,y\} ) \le \diam V(G)$, then $d_{G\boxtimes T}( (v;w) , [yz]\cup[zx] ) \le \diam V(G)$.
Assume that $d_{G\boxtimes T}( (v;w), \{x,y\} ) > \diam V(G)$.
Let $V_x$ (respectively, $V_y$) be the closest vertex to $x$ (respectively, $y$) in $[xy]$.
Note that $d_{G\boxtimes T}( V_x,V_y) = d_{G\boxtimes T}( V_x , (v;w) ) + d_{G\boxtimes T}( (v;w) , V_y ) \ge 2\diam V(G)$. Consider the projection $P_{T}$ on $T$.
By Lemma \ref{l:vertices} we have $d_{G\boxtimes T}( V_x,V_y) = d_{T}( P_{T}(V_x) , P_{T}(V_y) )$.
Due to $d_{T}( P_{T}(V_x) , P_{T}(V_y) ) \le d_{T}( P_{T}(V_x) , w ) + d_{T}( w , P_{T}(V_y) )$, we have $d_{G\boxtimes T}( V_x, (v;w) ) = d_{T}( P_{T}(V_x) , w )$ and $d_{G\boxtimes T}( (v;w) , V_y)$ $=d_{T}( w , P_{T}(V_y) )$.
Then, $w\in[P_{T}(x)P_{T}(y)]=P_T([xy])$.
Since $T$ is a tree, $w\in P_T\big( [yz]\cup[zx] \big)$.
Then, $([yz]\cup[zx]) \cap (G\boxtimes\{w\}) \neq \emptyset$ and $d_{G\boxtimes T}( (v;w) , [yz]\cup[zx]) \leq \diam V(G)$.
So, we have $d_{G\boxtimes T}( (v;w) , [yz]\cup[zx]) \leq \diam V(G)$ for every vertex $(v;w)$ in $[xy]$. Since $x,y\in J(G\boxtimes T)$, $d_{G\boxtimes T}( p , [yz]\cup[zx]) \leq \diam V(G) + 1/2$ for every $p\in[xy]$. Hence, $\d(\triangle) \leq \diam V(G) + 1/2$, and we obtain $\d(G\boxtimes T) \leq \diam V(G) + 1/2$.
\end{proof}


\begin{theorem}\label{th:GSPT=}
Let $T$ be any tree and $G$ any graph with \ $0< \diam V(G) = \diam T /2$. Then, we have
\[
\d(G\boxtimes T)=\diam V(G) + \frac14.
\]
\end{theorem}

\begin{proof}
By Theorem \ref{th:boundSP2mM}, we have that $\diam V(G) \leq \d(G\boxtimes T)\leq \diam V(G) + 1/2$.

Now we show a geodesic bigon $B$ in $G\boxtimes T$ with $\d(B)= \diam V(G) + 1/4$.
Define by $n:=\diam V(G)$ and consider $v_1,\ldots,v_{n+1}\in V(G)$ with $v_i\sim v_{i+1}$ for $i=1,\ldots,n$ and $d_{G}(v_1,v_{n+1})=n$.
Also, consider $w_1,\ldots,w_{2n+1}\in V(T)$ with $w_i\sim w_{i+1}$ for $i=1,\ldots,2n$ and $d_{T}(w_1,w_{2n+1})=\diam T=2n$.
Denote by $a$ (respectively, $b$) the midpoint of $[(v_1;w_1),(v_2;w_1)]$ (respectively, $[(v_1;w_{2n+1}),(v_2;w_{2n+1})]$).
Let us consider

\[
\g^*:= [a (v_1;w_1)]\bigcup\left\{\bigcup_{i=1}^{2n} [(v_1;w_{i}),(v_1;w_{i+1})]\right\} \bigcup[(v_1;w_{2n+1}) b]
\]
and

\[
\begin{aligned}
\g^\prime:= & [a (v_2;w_1)] \bigcup \left\{\bigcup_{i=1}^{n-1} [(v_{i+1};w_{i}),(v_{i+2};w_{i+1})] \right\}\bigcup [(v_{n+1};w_{n}),(v_{n+1};w_{n+1})] \bigcup  \\
& \bigcup [(v_{n+1};w_{n+1}),(v_{n+1};w_{n+2})] \bigcup\left\{\bigcup_{j=1}^{n-1} [(v_{n+2-j};w_{n+1+j}),(v_{n+1-j};w_{n+2+j})] \right\}\bigcup\\
&\bigcup[(v_2;w_{2n+1}) b].
\end{aligned}
\]
Consider the geodesic bigon $B:=\{\g^*,\g^\prime\}$ in $G\boxtimes T$. Let $p$ be the midpoint of $\g'$ and let $p_0$ be a point in $\g'$ with $d_{G\boxtimes T}(p_0,p)=1/4$; then $d_{G\boxtimes T}(p_0,\g^*)=n+1/4$ and $\d(G\boxtimes T)\ge \d(B) \ge  n+1/4$.


Hence, by Theorem \ref{t:multk/4} we have $\d(G\boxtimes T)\in \{ n + 1/4 \ , \ n + 1/2\}$.
Seeking for a contradiction assume that $\d(G\boxtimes T) = n + 1/2$.
Then there are a geodesic triangle $\triangle=\{x,y,z\}$ in $G\boxtimes T$ and $p\in[xy]$ with $d_{G\boxtimes T}(p, [yz]\cup[zx]) = n + 1/2$.
By Theorem \ref{t:TrianVMp} we can assume that $\triangle$ is a cycle with $x,y,z \in J(G\boxtimes T)$.
By Theorem \ref{th:diamSP}, $\diam(G\boxtimes T)= 2n + 1$ and we conclude that $L([xy])=2n+1$ and $p$ is the midpoint of $[xy]$.
Since $\diam V(G\boxtimes T) = 2n$, we have that $x,y$ are midpoints of edges in $G\boxtimes T$, and so, $p$ is a vertex of $G\boxtimes T$.
We can write $[xy]\cap V(G\boxtimes T) = \{(a_1;b_1),(a_2;b_2),\ldots,(a_{2n+1};b_{2n+1})\}$ with $a_1,\ldots,a_{2n+1} \in V(G)$, $(a_i;b_i)\sim(a_{i+1};b_{i+1})$ for $i=1,\ldots,2n$ and $d_T(b_1,b_{2n+1})=2n$.
Thus, $p=(a_{n+1};b_{n+1})$ and $p\in V(G\boxtimes\{b_{n+1}\})$.
Since $T$ is a tree we have that $([yz]\cup[zx]) \cap (G\boxtimes\{b_{n+1}\}) \neq \emptyset$; in particular, $d_{G\boxtimes T}(p, [yz]\cup[zx]) \leq \diam V(G)$.
This is the contradiction we were looking for, and then $\d(G\boxtimes T)= \diam V(G) + 1/4$.
\end{proof}



\medskip

The following lemma will be useful.

\begin{lemma}\label{l:ProjCm}
 Let $C_m$ be a cycle graph and $G$ any graph with $\diam V(G)<\diam V(C_m)$.
 Let  $\g=[xy]$ be a geodesic in $G \boxtimes C_m$ such that  $x, y\in J(G \boxtimes C_m)$. Then, $L(P_{C_m}(\g)) \leq m/2$ where $P_{C_m}$ is the projection on $C_m$.
\end{lemma}

\begin{proof}
 If $\diam V(G)=0$, it is a trivial case. Assume now that $\diam V(G)>0$.

 If $L(\g) \leq m/2$, then  we have the result since $L(P_{C_m}(\g)) \leq L(\g)$.
 Assume that $L(\g) > m/2$.
 Seeking for a contradiction, assume that $L(P_{C_m}(\g)) > m/2$.

 Assume that $m$ is even (the case $m$ odd is similar).
 Since $x,y\in J(G\boxtimes C_m)$ and $L(P_{C_m}(\g)) > m/2$, there are $x^\prime,y^\prime \in \g\cap J(G\boxtimes C_m)$ such that $d_{C_m}(P_{C_m}(x^\prime),P_{C_m}(y^\prime ))=(m+1)/2$.
 Without loss of generality we can assume that $x^\prime \in V(G\boxtimes C_m) $
 and  $y^\prime \notin V(G\boxtimes C_m) $.
 Let  $A,A_1,A_2 \in V(G)$ and  $B,B_1,B_2 \in V(C_m)$ such that $x^\prime=(A;B)$ and $y^\prime \in [(A_1;B_1),(A_2;B_2)] $.
 Since $d_{C_m}(P_{C_m}(x^\prime),P_{C_m}(y^\prime ))=(m+1)/2$, without loss of generality we can assume that $d_{C_m}(B,B_1)+1=d_{C_m}(B,B_2)=m/2$.
 Since $\diam V(C_m)> \diam V(G)$, by Lemma \ref{l:vertices}  we have $d_{G \boxtimes C_m}((A;B),(A_1;B_1))=m/2-1$; thus, $d_{G \boxtimes C_m}(x^\prime,y^\prime)$ $\leq (m-1)/2$. This is the contradiction  we were looking for.
\end{proof}


The following theorem provides the exact value of the hyperbolicity constant of the strong product of a cycle $C_m$  and any graph $G$ with $\diam V(G) \le \diam V(C_m) /2$.
This result is interesting by itself and, furthermore, it will be useful in order to prove the last theorems of this paper.


\begin{theorem}\label{th:GSPCm}
Let $C_m$ be a cycle graph and $G$ any graph with $\diam V(G) \le \diam V(C_m) /2$. Then, we have
\begin{equation}\label{eq:GSPCm}
\d(G\boxtimes C_m)=\left\{
                   \begin{array}{ll}
                     \lfloor m/2\rfloor / 2 + 1/4,\quad &\mbox{if }\ \diam V(G) = \diam V(C_m) /2,\\
                     m/4,\quad &\mbox{if }\ \diam V(G) < \diam V(C_m) /2.
                   \end{array}
                   \right.
\end{equation}
\end{theorem}


\begin{proof}
If $\diam V(G)=0$, then the equality is trivial. Assume now that $\diam V(G)> 0$.
Let $V(C_m)=\{w_1,\ldots,w_m\}$ where $w_i\sim w_{i+1}$ for $i=1,\ldots,m-1$.
Let $P_{C_m}$ be the projection on $C_m$.

\smallskip


First, we prove that $\d(G\boxtimes C_m) < (\lfloor m/2\rfloor + 1)/2$.
Seeking for a contradiction, assume that there are a geodesic triangle $T=\{x,y,z\}$ in $G\boxtimes C_m$ and a point $p\in\g:=[xy]$ with $d_{G\boxtimes C_m}(p,[yz]\cup[zx])=(\lfloor m/2\rfloor + 1)/2 = \diam(G\boxtimes C_m)/2$.
Then $L(\g)=\diam(G\boxtimes C_m)$ and $d_{G\boxtimes C_m}(p, [yz]\cup[zx]) = \diam(G\boxtimes C_m)/2$, and we conclude that $p$ is the midpoint of $\g$.
By Theorem \ref{t:TrianVMp}, we can assume that $T$ is a cycle with $x,y,z \in J(G\boxtimes C_m)$.
Since $\diam V(G\boxtimes C_m) = \diam(G\boxtimes C_m)-1$, by Theorem \ref{th:diamSP} we have that $x,y$ are midpoints of edges in $G\boxtimes C_m$.
Let $V_x$ (respectively, $V_y$) be the closest vertex to $x$ (respectively, $y$) in $\g$.
Let $V'_x$ (respectively, $V'_y$) be the closest vertex to $x$ (respectively, $y$) in $[xz]$ (respectively, $[yz]$).
By Lemma \ref{l:vertices}, we have $d_{G\boxtimes C_m}(V_x,V_y)=d_{C_m}(P_{C_m}(V_x) , P_{C_m}(V_y))=\lfloor m/2\rfloor$.
Therefore, since $\diam V(G) \le \diam V(C_m) /2$ we have $d_{C_m}(P_{C_m}(V_x) , P_{C_m}(p))=d_{C_m}(P_{C_m}(p) , P_{C_m}(V_y))=\lfloor m/2\rfloor / 2$.
By Lemma \ref{l:ProjCm} we have $L(P_{C_m}(\g))\le m/2$; since $2 \big( \lfloor m/2\rfloor/2 + 1/2 \big) > m/2$ we have either $P_{C_m}(V_x)=P_{C_m}(x)=P_{C_m}(V'_x)$ or $P_{C_m}(V_y)=P_{C_m}(y)=P_{C_m}(V'_y)$.
So, we have
$$d_{G\boxtimes C_m}(p,[xz]\cup[yz]) \leq d_{G\boxtimes C_m}(p,\{V'_x,V'_y\}) \le \lfloor m/2\rfloor/2 \leq m/4.$$
This is the contradiction we were looking for, and we have $\d(G\boxtimes C_m) < (\lfloor m/2\rfloor + 1)/2$.
So, by Theorem \ref{t:multk/4} we have $\d(G\boxtimes C_m) \leq \lfloor m/2\rfloor/2 + 1/4$.

\smallskip

Assume now that $\lfloor m/2\rfloor = 2 \diam V(G)$.
If $m$ is odd (i.e., $m=4k+1$), then Theorem \ref{th:infSP} (a) gives $\d(G\boxtimes C_m)\ge m/4=\lfloor m/2\rfloor/2 + 1/4$. So, \eqref{eq:GSPCm} holds.
Assume that $m$ in even (i.e., $m=4k$).
Now we show a geodesic bigon $B$ in $G\boxtimes C_m$ with $\d(B)= \lfloor m/2\rfloor/2 + 1/4= k + 1/4$.
Note that $k=\diam V(G)$ and consider $v_1,\ldots,v_{k+1}\in V(G)$ with $v_i\sim v_{i+1}$ for $i=1,\ldots,k$ and $d_{G}(v_1,v_{k+1})=k$.
Denote by $a$ (respectively, $b$) the midpoint of $[(v_1;w_1),(v_2;w_1)]$ (respectively, $[(v_1;w_{2k+1}),(v_2;w_{2k+1})]$).
Let us consider

\[
\g^*:= [a (v_1;w_1)]\bigcup\left\{\bigcup_{i=1}^{2k} [(v_1;w_{i}),(v_1;w_{i+1})]\right\}\bigcup[(v_1;w_{2k+1}) b]
\]
and

\[
\begin{aligned}
\g^\prime:= & [a (v_2;w_1)] \bigcup \left\{\bigcup_{i=1}^{k-1} [(v_{i+1};w_{i}),(v_{i+2};w_{i+1})] \right\} \bigcup [(v_{k+1};w_{k}),(v_{k+1};w_{k+1})] \bigcup \\
& \bigcup[(v_{k+1};w_{k+1}),(v_{k+1};w_{k+2})] \bigcup\left\{\bigcup_{j=1}^{k-1} [(v_{k+2-j};w_{k+1+j}),(v_{k+1-j};w_{k+2+j})] \right\}\bigcup\\
&\bigcup[(v_2;w_{2k+1}) b].
\end{aligned}
\]
Then $B:=\{\g^*,\g^\prime\}$ is a geodesic bigon in $G\boxtimes C_m$ with $\d(B) = k + 1/4 = \lfloor m/2\rfloor/2 + 1/4$.

\medskip

Finally, assume that $\lfloor m/2\rfloor > 2\diam V(G)$. By Theorem \ref{th:infSP} (a) it suffices to prove $\d(G\boxtimes C_m)\le m/4$.
If $m$ is odd, then $\lfloor m/2\rfloor / 2 + 1/4 = m/4$ and \eqref{eq:GSPCm} holds.

Assume that $m$ is even, then $\diam V(G)\le m/4-1/2$.
Fix any geodesic triangle $T=\{x,y,z\}$ in $G\boxtimes C_m$ and $p\in[xy]$. By Remark \ref{r:TrianVMp}, we can assume that $T$ is a cycle, $x,y,z\in J(G\boxtimes C_m)$ and $p$ satisfies $d_G(p,V(G)) \in \{0,1/4,1/2\}$.
If $d_{G\boxtimes C_m}(p,\{x,y\})\le m/4$, then $d_{G\boxtimes C_m}(p,[yz]\cup[zx])\le m/4$.
Assume that $d_{G\boxtimes C_m}(p,\{x,y\})> m/4$;
since $x,y \in J(G\boxtimes C_m)$ and $d_G(p,V(G)) \in \{0,1/4,1/2\}$, we have $d_{G\boxtimes C_m}(p,\{x,y\})\ge m/4+1/4$.
We have $L([xy])> m/2$.
Let $V_x$ (respectively, $V_y$) be the closest vertex to $x$ (respectively, $y$) in $[xy]$; then
$d_{G\boxtimes C_m}(p,\{V_x,V_y\})\ge m/4-1/4$.
Let $V'_x$ (respectively, $V'_y$) be the closest vertex to $x$ (respectively, $y$) in $[xz]$ (respectively, $[yz]$).
Since $m$ is even and $x,y\in J(G\boxtimes C_m)$ we have $d_{G\boxtimes C_m}(V_x,V_y)\ge m/2$ and we conclude $d_{G\boxtimes C_m}(V_x,V_y)= m/2$.
By Lemma \ref{l:vertices} we have $d_{G\boxtimes C_m}(V_x,V_y)=d_{C_m}(P_{C_m}(V_x) , P_{C_m}(V_y))= m/2$;
by Lemma \ref{l:ProjCm} we conclude $L\big(P_{C_m}([xy])\big)=m/2$.
Since $m/2=\lfloor m/2\rfloor > \diam V(G)$, we have $P_{C_m}(V_x)=P_{C_m}(x)=P_{C_m}(V_x')$ and $P_{C_m}(V_y)=P_{C_m}(y)=P_{C_m}(V_y')$.
Since $d_{G\boxtimes C_m}(p,\{V_x,V_y\}) \leq d_{G\boxtimes C_m}(V_x,V_y)/2 = m/4$,
without loss of generality we can assume that $d_{G\boxtimes C_m}(p,\{V_x,V_y\})$ $= d_{G\boxtimes C_m}(p,V_x) \le m/4$.
Let $V_p$ be the closest vertex to $p$ in $[xp]$.
Since $d_{G\boxtimes C_m}(p,V_x) \ge m/4-1/4 > m/4-1/2 \ge \diam V(G)$, we have
$\diam V(G) \ge d_{G\boxtimes C_m}(V_p,V_x) = d_{C_m}(P_{C_m}(V_p),$ $P_{C_m}(V_x)) = d_{C_m}(P_{C_m}(V_p),P_{C_m}(V_x'))$
and we conclude $d_{G\boxtimes C_m}(V_p,V_x) = d_{G\boxtimes C_m}(V_p,V_x')$ and
$d_{G\boxtimes C_m}(p,[xz]\cup[yz]) \leq d_{G\boxtimes C_m}(p,V_x') \le d_{G\boxtimes C_m}(p,V_x) \le m/4$.
Then $\d(G\boxtimes C_m)\le m/4$.
\end{proof}


As a consequence of Theorems \ref{th:boundSP2mM}, \ref{th:GSPT>}, \ref{th:GSPT=} and \ref{th:GSPCm} we obtain the precise values of the hyperbolicity constants of the following families of graphs.

\begin{theorem}\label{th:TSPT}
Let $T_1,T_2$ be two trees with $ \diam T_1\leq \diam T_2$. Then
  \[\d(T_1\boxtimes T_2)=\left\{
\begin{array}{ll}
0, \quad &\mbox{if }\ \diam T_1 = 0,\\

\diam T_1 + 1/2,\quad &\mbox{if }\ 0 < \diam T_1 < (\diam T_2)/2,\\

\diam T_1 + 1/4,\quad &\mbox{if }\ 0 < \diam T_1 = (\diam T_2)/2,\\

(\diam T_2 + 1)/2,\quad &\mbox{if }\  \diam T_1 > (\diam T_2)/2.
\end{array}
\right.
\]
\end{theorem}



\begin{corollary}\label{th:PnSPPm}
Let $P_n,P_m$ be two path graphs with $2\leq n\leq m$. Then
  \[\d(P_n\boxtimes P_m)=\left\{
\begin{array}{ll}
m/2,\quad &\mbox{if }\ m-1 < 2(n-1),\\

n-3/4,\quad &\mbox{if }\ m-1=2(n-1),\\

n - 1/2,\quad &\mbox{if }\ m-1 > 2(n-1).
\end{array}
\right.
\]
\end{corollary}


\begin{theorem}\label{th:CnSPCm}
Let $C_n,C_m$ be two cycle graphs with $3\leq n\leq m$. Then

  \[\d(C_n\boxtimes C_m)=\left\{
\begin{array}{ll}
\lfloor m/2 \rfloor/2 + 1/2,\quad &\mbox{if }\ \lfloor m/2\rfloor < 2\lfloor n/2\rfloor,\\

\lfloor m/2\rfloor /2 + 1/4,\quad &\mbox{if }\ \lfloor m/2\rfloor = 2\lfloor n/2\rfloor,\\

m/4,\quad &\mbox{if }\ \lfloor m/2\rfloor > 2\lfloor n/2\rfloor.
\end{array}
\right.
\]
\end{theorem}




\begin{theorem}\label{th:PnSPCm}
For every $m\geq 2,n\geq 3$,

  \[\d(C_n\boxtimes P_m)=\left\{
\begin{array}{ll}
\lfloor n/2 \rfloor + 1/2,\quad &\mbox{if }\ \lfloor n/2\rfloor < (m-1)/2,\\
\lfloor n/2\rfloor + 1/4,\quad &\mbox{if }\ \lfloor n/2\rfloor = (m-1)/2,\\
m/2,\quad &\mbox{if }\ (m-1)/2 < \lfloor n/2\rfloor \leq (m-1),\\
\big(\lfloor n/2\rfloor + 1\big)/2,\quad &\mbox{if }\ m-1 < \lfloor n/2\rfloor < 2(m-1),\\
\lfloor n/2\rfloor /2 + 1/4,\quad &\mbox{if }\ \lfloor n/2\rfloor = 2(m-1),\\
n/4,\quad &\mbox{if }\ \lfloor n/2\rfloor > 2(m-1).
\end{array}
\right.
\]
\end{theorem}






\section*{Acknowledgements}
We would like to thank the referee for a careful reading of the manuscript
and for some helpful suggestions.

This work was partly supported by the Spanish Ministry of Science
and Innovation through projects MTM2008-02829-E, MTM2009-07800, MTM2011-28800-C02-02; under the
Catalonian Government project 1298 SGR2009 and a grant from CONACYT
(CONACYT-UAG I0110/62/10), M\'exico.



\begin{thebibliography}{10}

\bibitem{APRT}
Alvarez, V., Portilla, A., Rodr{\'\i}guez, J. M. and Tour{\'\i}s,
E., Gromov hyperbolicity of Denjoy domains, {\it Geom.
Dedicata}~{\bf 121} (2006), 221-245.

\bibitem{ACDG13} Abajo, E., Casablanca, R. M., Di\'anez, A., Garc{\'\i}a-V\'azquez, P.
The Menger number of the strong product of graphs, {\it Discrete Math} {\bf 313} (2013), 1490-1495.

\bibitem{BB} Balogh, Z. M. and Buckley, S. M.,
Geometric characterizations of Gromov hyperbolicity, {\it Invent.
Math.}~{\bf 153} (2003), 261-301.

\bibitem{BRS} Bermudo, S., Rodr\'{\i}guez, J. M. and Sigarreta, J. M., Computing the hyperbolicity constant,
{\it Comp. Math. Appl.} {\bf 62} (2011), 4592-4595.

\bibitem{BRST} Bermudo, S., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Tour{\'\i}s, E.,
Hyperbolicity and complement of graphs,
{\it Appl. Math. Letters} {\bf 24} (2011), 1882-1887.

\bibitem{BRSV} Bermudo, S., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Vilaire, J.-M.,
Gromov hyperbolic graphs, {\it Discrete Math.} {\bf 313} (2013), 1575-1585.

\bibitem{BHK} Bonk, M., Heinonen, J. and Koskela, P.,
\emph{Uniformizing Gromov hyperbolic spaces}. Ast\'erisque {\bf 270}
(2001).

\bibitem{BHB} Bowditch, B. H., Notes on Gromov's hyperobolicity criterion for path-metric spaces. Group theory from a geometrical viewpoint, Trieste, 1990 (ed. E. Ghys, A. Haefliger and A. Verjovsky; World Scientific, River
Edge, NJ, 1991), 64-167.

\bibitem{BHB1} Brinkmann, G., Koolen J. and Moulton, V., On the hyperbolicity of chordal
graphs, {\it Ann. Comb.} {\bf 5} (2001), 61-69.

\bibitem{CHMPP10} C\'aceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., On the geodetic and the hull numbers in strong product graphs,
{\it Comput. Math. Appl.} {\bf 60} (2010), 3020-3031.

\bibitem{CGPR1} Cant\'on, A., Granados, A., Pestana, D., Rodr\'{\i}guez, J. M.,
Gromov hyperbolicity of periodic planar graphs, to appear in {\it Acta Math. Sinica}.

\bibitem{CGPR2} Cant\'on, A., Granados, A., Pestana, D., Rodr\'{\i}guez, J. M.,
Gromov hyperbolicity of planar graphs, to appear in {\it Central Europ. J. Math.}

\bibitem{CPeRS} Carballosa, W., Pestana, D., Rodr\'{\i}guez, J. M. and Sigarreta, J. M.,
Distortion of the hyperbolicity constant of a graph,
{\it Electr. J. Comb.} {\bf 19} (2012), \#P67.

\bibitem{CPoRS} Carballosa, W., Portilla, A., Rodr\'{\i}guez, J. M. and Sigarreta, J. M.,
Gromov hyperbolicity of planar graphs and CW complexes.
Submitted.

\bibitem{CRS} Carballosa, W., Rodr\'{\i}guez, J. M. and Sigarreta, J. M.,
New inequalities on the hyperbolity constant of line graphs,
to appear in {\it Ars Combinatoria.}

\bibitem{CRSV} Carballosa, W., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Villeta, M.,
On the Hyperbolicity Constant of Line Graphs, %Gromov hyperbolicity of line graphs,
{\it Electr. J. Comb.} {\bf 18} (2011), \#P210.

\bibitem{CYY} Chen, B., Yau, S.-T. and Yeh, Y.-N., Graph homotopy and Graham homotopy,
{\it Discrete Math.} {\bf 241} (2001), 153-170.

\bibitem{CDEHV}
Chepoi, V., Dragan, F. F., Estellon, B., Habib, M. and Vaxes Y.,
Notes on diameters, centers, and approximating trees of $\d$-hyperbolic geodesic spaces and graphs,
{\it Electr. Notes Discrete Math.} {\bf 31} (2008), 231-234.

\bibitem{K50} Frigerio, R. and Sisto, A., Characterizing hyperbolic spaces and real trees, {\it Geom. Dedicata} {\bf 142} (2009), 139-149.

\bibitem{GH} Ghys, E. and de la Harpe, P., Sur les Groupes Hyperboliques d'apr\`es Mikhael Gromov. Progress
in Mathematics 83, Birkh\"auser Boston Inc., Boston, MA, 1990.

\bibitem{Ha} H\"ast\"o, P. A.,
Gromov hyperbolicity of the $j_G$ and $\tilde{\jmath}_G$ metrics,
{\it Proc. Amer. Math. Soc.}~{\bf 134} (2006), 1137-1142.

\bibitem{HLPRT} H\"ast\"o, P. A., Lind\'en, H., Portilla, A., Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics,
{\it J. Math. Soc. Japan} {\bf 64} (2012), 247-261.

\bibitem{HPRT} H\"ast\"o, P. A., Portilla, A., Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic
metrics in Denjoy domains, {\it Bull. London Math. Soc.} {\bf 42} (2010), 282-294.

\bibitem{HPRT2} H\"ast\"o, P. A., Portilla, A., Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Comparative Gromov hyperbolicity results for the hyperbolic and quasihyperbolic metrics, {\it Complex Var. Ellip. Eq.} {\bf 55} (2010), 127-135.

\bibitem{HPRT3} H\"ast\"o, P. A., Portilla, A., Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Uniformly separated sets and Gromov hyperbolicity of domains with the quasihyperbolic metric, {\it Medit. J. Math.} {\bf 8} (2011), 47-65.

\bibitem{IK00} Imrich, W. and Klav\v{z}ar, S., Product Graphs: Structure and Recognition, {\em Wiley Series in Discrete Mathematics and Optimization}, (2000).

\bibitem{K27} Jonckheere, E. and Lohsoonthorn, P., A hyperbolic geometry approach to
multipath routing, Proceedings of the 10th Mediterranean Conference on Control and Automation (MED 2002), Lisbon, Portugal, July 2002. FA5-1.

\bibitem{K21} Jonckheere, E. A., Controle du trafic sur les reseaux a
geometrie hyperbolique--Une approche mathematique a la securite de
l'acheminement de l'information, {\it J. Europ. de Syst.
Autom.} {\bf 37} (2003), 145-159.

\bibitem{K22} Jonckheere, E. A. and Lohsoonthorn, P., Geometry of network security,
{\it American Control Conference} {\bf ACC} (2004), 111-151.

\bibitem{K23} Jonckheere, E. A., Lohsoonthorn, P. and Ariaesi, F, Upper bound on scaled
Gromov-hyperbolic delta, {\it Applied Mathematics and Computation} {\bf 192} (2007), 191-204.

\bibitem{K24} Jonckheere, E. A., Lohsoonthorn, P. and Bonahon, F., Scaled Gromov
hyperbolic graphs, {\it J. Graph Theory} {\bf 2} (2007), 157-180.

\bibitem{KK08} Kaveh, A., Koohestani, K., Graph products for configuration processing of space structures,
{\it Comput. Struct.} {\bf 86} (2008), 1219-1231.

\bibitem{K56} Koolen, J. H. and Moulton, V., Hyperbolic Bridged
Graphs, {\it Europ. J. Comb.} {\bf 23} (2002), 683-699.

\bibitem{MRSV} Michel, J., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Villeta, M.,
Hyperbolicity and parameters of graphs, {\it Ars Combinatoria} {\bf 100} (2011), 43-63.

\bibitem{MRSV2} Michel, J., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Villeta, M.,
Gromov hyperbolicity in Cartesian product graphs,
{\it Proc. Indian Acad. Sci. Math. Sci.} {\bf 120} (2010), 1-17.

\bibitem{O} Oshika, K., Discrete groups, AMS Bookstore, 2002.

\bibitem{PeRSV} Pestana, D., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Villeta, M.,
Gromov hyperbolic cubic graphs, {\it Central Europ. J. Math.} {\bf 10(3)} (2012), 1141-1151.

\bibitem{PRSV} Portilla, A., Rodr\'{\i}guez, J. M., Sigarreta, J. M. and Vilaire, J.-M.,
Gromov hyperbolic tessellation graphs, to appear in {\it Utilitas Math.}

\bibitem{PRT1} Portilla, A., Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Gromov hyperbolicity through decomposition of metric spaces II, {\it
J. Geom. Anal.}~{\bf 14} (2004), 123-149.

\bibitem{PT} Portilla, A. and Tour{\'\i}s, E.,
A characterization of Gromov hyperbolicity of surfaces with variable
negative curvature, {\it Publ. Mat.} {\bf 53} (2009), 83-110.

\bibitem{R} Rodr\'{\i}guez, J. M.,
Characterization of Gromov hyperbolic short graphs, to appear in {\it Acta Math. Sinica}.

\bibitem{RSVV} Rodr\'{\i}guez, J. M., Sigarreta, J. M., Vilaire, J.-M.
and Villeta, M., On the hyperbolicity constant in graphs,
{\it Discrete Math.} {\bf 311} (2011), 211-219.

\bibitem{RT1} Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Gromov hyperbolicity through decomposition of metric spaces, {\it
Acta Math. Hung.} {\bf 103} (2004), 53-84.

\bibitem{RT2} Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
A new characterization of Gromov hyperbolicity for Riemann surfaces,
{\it Publ. Mat.}~{\bf 50} (2006), 249-278.

\bibitem{RT3} Rodr\'{\i}guez, J. M. and Tour{\'\i}s, E.,
Gromov hyperbolicity of Riemann surfaces, {\it Acta Math.
Sinica}~{\bf 23} (2007), 209-228.

\bibitem{S60} Sabidussi, G., Graph multiplication, {\it Math. Z.} {\bf 72} (1960), 446-457.

\bibitem{S10} \v{S}pacapan, S., Connectivity of Strong Products of Graphs, {\it Graphs Combin.} {\bf 26} (2010), 457-467.

\bibitem{Si} Sigarreta, J. M. Hyperbolicity in median graphs, to appear in
{\it Proc. Indian Acad. Sci. Math. Sci.}

\bibitem{T} Tour{\'\i}s, E.,
Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces.
{\it J. Math. Anal. Appl.} {\bf 380} (2011), 865-881.


\end{thebibliography}

\end{document}