% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{color}
\usepackage{graphicx}
\DeclareGraphicsRule{.JPG}{eps}{*}{`jpeg2ps #1}


 \newtheorem{remark}{Remark}
 \newtheorem{definition}{Definition}
 \newtheorem{assumption}[remark]{Assumption}
 \newtheorem{lemma}[remark]{Lemma}
 \newtheorem{theorem}[remark]{Theorem}
 \newtheorem{proposition}[remark]{Proposition}
 \newtheorem{corollary}[remark]{Corollary}
  \newtheorem{conjecture}[remark]{Conjecture}

\begin{document}
\setcounter{page}{61}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{On the partition dimension of Cartesian product graphs}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}


\author[label1]{Ismael G. Yero}, \ead{ismael.gonzalez\@@urv.cat}
\author[label1]{Juan A.
Rodr\'{\i}guez-Vel\'{a}zquez} and
\author[label2]{Magdalena Lema\'{n}ska}

\address[label1]{Department of Computer Engineering and Mathematics
Rovira i Virgili University,  Av. Pa\"{\i}sos Catalans 26, 43007
Tarragona, Spain}
\address[label2]{Department of Technical Physics and Applied Mathematics
Gdansk University of Technology, ul. Narutowicza 11/12 80-233
Gdansk, Poland}

\begin{abstract}
Let $G=(V,E)$ be a connected graph. The distance between two
vertices $u,v\in V$, denoted by $d(u, v)$, is the length of a
shortest $u-v$ path in $G$. The distance between a vertex $v\in V$
and a subset $P\subset V$ is defined as $min\{d(v, x): x \in P\}$,
and it is denoted by $d(v, P)$.
  An ordered partition $\{P_1,P_2, ...,P_t\}$ of vertices of a
graph $G$, is a \emph{resolving partition }of $G$, if all the
distance vectors $(d(v,P_1),d(v,P_2),...,d(v,P_t))$ are different.
The \emph{partition dimension} of $G$, denoted by $pd(G)$, is the
minimum number of sets in any resolving partition of $G$. In this
article we show that for all pair of connected graphs $G, H$,
$pd(G\times H)\le pd(G)+pd(H)$ and $pd(G\times H)\le pd(G)+dim(H).$
Consequently, we show that $pd(G\times H)\le dim(G)+dim(H)+1.$
\end{abstract}

\begin{keyword}
Resolving sets, resolving partition, partition dimension, Cartesian
product.
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

\vspace{-1.2cm}
% main text
\section{Introduction}
\label{}

\vspace{-0,8cm}
 The concepts of resolvability and location in graphs were described
independently by Harary and Melter \cite{harary} and Slater
\cite{leaves-trees}, to define the same structure in a graph. After
these papers were published several authors developed diverse
theoretical works about this topic
\cite{pelayo1,pelayo2,chappell,chartrand,chartrand1,chartrand2,fehr,landmarks}.
Also, Slater described the usefulness of these ideas into long range
aids to navigation \cite{leaves-trees}. Recently, these concepts
were used by a pharmacy company while attempting to develop a
capability of large datasets of chemical graphs
\cite{pharmacy1,pharmacy2}. Other applications of this concept to
navigation of robots in networks and other areas appear in
\cite{chartrand,robots,landmarks}. Some variations on resolvability
or location have been appearing in the literature, like those about
conditional resolvability \cite{survey}, locating domination
\cite{haynes}, resolving domination \cite{brigham} and resolving
partitions \cite{chappell,chartrand2,fehr}.

Given a graph $G=(V,E)$ and a set of vertices
$S=\{v_1,v_2,...,v_k\}$ of $G$, the {\it metric representation} of a
vertex $v\in V$ with respect to $S$ is the vector
$r(v|S)=(d(v,v_1),d(v,v_2),...,d(v,v_k))$, where $d(v,v_i)$, with
$1\leq i\leq k$, denotes the distance between the vertices $v$ and
$v_i$. We say that $S$ is a {\it resolving set} of $G$ if for every
pair of vertices $u,v\in V$, $r(u|S)\ne r(v|S)$. The {\it metric
dimension}\footnote{Also called locating number.} of $G$ is the
minimum cardinality of any resolving set of $G$, and it is denoted
by $dim(G)$. The metric dimension of graphs is studied in
\cite{pelayo1,pelayo2,chappell,chartrand,chartrand1,tomescu}. Given
an ordered partition $\Pi =\{P_1,P_2, ...,P_t\}$ of the vertices of
$G$, the {\it partition representation} of a vertex $v\in V$ with
respect to the partition $\Pi$ is the vector
$r(v|\Pi)=(d(v,P_1),d(v,P_2),...,d(v,P_t))$, where $d(v,P_i)$, with
$1\leq i\leq t$, represents the distance between the vertex $v$ and
the set $P_i$, that is $d(v,P_i)=\min_{u\in P_i}\{d(v,u)\}$. We say
that $\Pi$ is a {\it resolving partition} of $G$ if for every pair
of vertices $u,v\in V$, $r(u|\Pi)\ne r(v|\Pi)$. The {\it partition
dimension} of $G$ is the minimum number of sets in any resolving
partition of $G$ and it is denoted by $pd(G)$. The partition
dimension of graphs is studied in
\cite{chappell,chartrand2,fehr,tomescu}. It is natural to think that
the partition dimension and metric dimension are related; in
\cite{chartrand2} it was shown that for any nontrivial connected
graph $G$ we have
\begin{equation}\label{partition-dimension}pd(G)\le  dim(G) + 1.\end{equation}

\vspace{-0,6cm}
 The study of relationships between invariants of
Cartesian product graphs and invariants of its factors appears
frequently in research about graph theory. In the case of
resolvability,  the relationships between the metric dimension of
the Cartesian product graphs and the metric dimension of its factors
was studied in \cite{pelayo1,pelayo2}. An open problem on the
dimension of Cartesian product graphs is to prove (or finding a
counterexample) that for all pair of graphs $G, H$; $dim(G\times
H)\le dim(G)+dim(H)$. In the present paper we study the case of
resolving partition in Cartesian product graphs, by giving some
relationships between the partition dimension of  Cartesian product
graphs and the partition dimension of its factors. More precisely,
we show that for all pair of connected graphs $G, H$; $pd(G\times
H)\le pd(G)+pd(H)$ and $pd(G\times H)\le pd(G)+dim(H).$
Consequently, we show that $pd(G\times H)\le dim(G)+dim(H)+1.$


% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\vspace{-1.0cm}
\section{Results}

\vspace{-0,6cm}
\begin{theorem}\label{sumapd}
For any connected graphs $G_1$ and $G_2$,
$$pd(G_1\times G_2)\leq pd(G_1)+pd(G_2).$$
\end{theorem}

\vspace{-0,6cm}
 By (\ref{partition-dimension}) we obtain the
following direct consequence of Theorem \ref{sumapd}.
\begin{corollary}
For any connected graphs $G_1$ and $G_2$,
$$pd(G_1\times G_2)\leq pd(G_1)+dim(G_2)+1.$$
\end{corollary}

\vspace{-0,6cm} As we can see below, the above relationship can be
improved.

\begin{theorem}\label{THpartDimension}
For any connected graphs $G_1$ and $G_2$, $$pd(G_1\times G_2)\le
pd(G_1)+dim(G_2).$$
\end{theorem}

\vspace{-0,6cm} We note that there are graphs for which Theorem
\ref{sumapd} estimates $pd(G_1\times G_2)$ better than Theorem
\ref{THpartDimension} and vice versa. For example Theorem
\ref{sumapd} leads to $pd(K_n\times P_n)\le n+2$ while Theorem
\ref{THpartDimension} gives $pd(K_n\times P_n)\le n+1$. On the
contrary, if $G$ denotes the graph in Figure \ref{grafo-triangulo},
Theorem \ref{sumapd} leads to $pd(G\times G)\le 8$ while Theorem
\ref{THpartDimension} gives $pd(G\times G)\le 13$.

\begin{figure}[h]
\centering
  \includegraphics[width=0.3\textwidth]{triangulo-4hojas}
 \caption{
$\{\{1,4,8,12\},\{2,5,9,13\},\{3,6,10,14\},\{7,11,15\}\}$ is
a resolving partition of $G$ and $\{4,5,6,8,9,10,12,13,14\}$ is a
resolving set of $G$.}\label{grafo-triangulo}
\end{figure}

 As a direct consequence of above theorem and
(\ref{partition-dimension}) we deduce the following interesting
result.

\begin{corollary}\label{sumadimen}
For any connected graphs $G_1$ and $G_2$, $$pd(G_1\times G_2)\le
dim(G_1)+dim(G_2)+1.$$
\end{corollary}

\vspace{-0,6cm} One example of graphs for which the equality holds
in Corollary \ref{sumadimen} (and also in Corollary
\ref{particulares} (ii)) are the graphs belonging to the family of
grid graphs: $pd(P_r\times P_t)=3$.

\begin{corollary}\label{particulares}For any connected graph $G$,
\begin{itemize}
\item[{\rm (i)}] $pd(G\times K_n)\le pd(G)+n-1$.
\item[{\rm (ii)}] $pd(G\times P_n)\le pd(G)+1$.
\item[{\rm (iii)}]  $pd(G\times C_n)\le pd(G)+2$.
\item[{\rm (iv)}]  $pd(G\times K_{1,n})\le pd(G)+n-1$.
\end{itemize}
\end{corollary}

\noindent{\bf Acknowledgments:} This work was partly supported by
the Spanish Ministry of Science and Innovation through projects
TSI2007-65406-C03-01 ``E-AEGIS", CONSOLIDER INGENIO 2010
CSD2007-0004 ``ARES".

\vspace{-0,6cm}
\begin{thebibliography}{00}
\vspace{-0,6cm}

\bibitem{brigham} R. C. Brigham, G. Chartrand, R. D. Dutton, P.
Zhang, Resolving domination in graphs, {\it Mathematica Bohemica}
{\bf 128} (1) (2003) 25--36.

\bibitem{pelayo1} J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood,
On the metric dimension of Cartesian product of graphs, {\it SIAM
Journal of Discrete Mathematics} {\bf 21} (2) (2007) 273--302.


\bibitem{pelayo2} J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, On the
metric dimension of some families of graphs, {\it Electronic Notes
in Discrete Mathematics} {\bf 22} (2005) 129--133.

\bibitem{chappell} G. Chappell, J. Gimbel, C. Hartman, Bounds on
the metric and partition dimensions of a graph, {\it Ars Combinatoria} {\bf 88} (2008) 349--366.

\bibitem{chartrand} G. Chartrand, L. Eroh, M. A. Jhonson, O. R.
Oellermann, Resolvabiblity in graphs ans the metric dimension of a
graph, {\it Discrete Applied Mathematics} {\bf 105} (2000) 99--113.

\bibitem{chartrand1} G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper
dimension of graphs, {\it Computer and Mathematics with Appplications} {\bf 39}
(2000) 19--28.

\bibitem{chartrand2} G. Chartrand, E. Salehi, P. Zhang, The partition dimension of
a graph, {\it Aequationes Mathematicae} {\bf 59} (2000)
45--54.

\bibitem{fehr} M. Fehr, S. Gosselin, O. R. Oellermann, The
partition dimension of Cayley digraphs {\it Aequationes
Mathematicae} {\bf 71} (2006) 1--18.

\bibitem{harary} F. Harary, R. A. Melter, On the metric dimension of a graph, {\it Ars Combinatoria} {\bf 2} (1976)
191--195.

\bibitem{haynes} T. W. Haynes, M. Henning, J. Howard, Locating
and total dominating sets in trees, {\it Discrete Applied
Mathematics} {\bf 154} (2006) 1293--1300.

\bibitem{robots} B. L. Hulme, A. W. Shiver, P. J. Slater, A Boolean algebraic analysis of fire protection,
{\it Algebraic and Combinatorial Methods in Operations Research}
{\bf 95} (1984) 215--227.

\bibitem{pharmacy1} M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug
design, {\it Journal of Biopharmaceutical Statististics} {\bf 3} (1993) 203--236.

\bibitem{pharmacy2} M. A. Johnson, Browsable structure-activity datasets, {\it Advances in Molecular
Similarity} (R. Carbó--Dorca and P. Mezey, eds.) JAI Press
Connecticut (1998) 153--170.

\bibitem{landmarks} S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in
graphs, {\it Discrete Applied Mathematics} {\bf 70} (1996) 217--229.

\bibitem{survey} V. Saenpholphat, P. Zhang, Conditional resolvability in graphs: a
survey, {\it International Journal of Mathematics and Mathematical
Sciences} {\bf 38} (2004) 1997--2017.

\bibitem{leaves-trees} P. J. Slater, Leaves of trees, Proc. 6th Southeastern Conference on Combinatorics, Graph
Theory, and Computing, {\it Congressus Numerantium} {\bf 14} (1975)
549--559.

\bibitem{tomescu} I. Tomescu, Discrepancies between metric and
partition dimension of a connected graph, {\it Discrete Mathematics}
{\bf 308} (2008) 5026--5031.

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\end{thebibliography}

\end{document}
