For an ordered subset $S = {s_1, s_2,dots s_k}$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $ r(u|S)=(d_G(v,s_1), d_G(v,s_2),dots,$ $d_G(v,s_k))$, where $d_G(x,y
)$ represents the distance between the vertices $x$ and $y$. The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$, the metric dimension of $G$. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.
A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In
this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $Gamma=(V,E)$, ($psi_{k}^{gd}(Gamma)$) $psi_k^{d}(Gamma)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $psi_k^{d}(Gamma)$ and $psi_{k}^{gd}(Gamma)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Gamma_1times Gamma_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $Gamma_i$ into (global) defensive $k_i$-alliances, $iin {1,2}$.
