From the identification of vertices in a graph to non-identification: a short story

Ismael Gonzalez Yero
University of Cadiz



Content: Graph structures may be used to model computer networks. Each vertex in a graph is a possible location for an intruder (fault in a computer network, spoiled device). So, a correct surveillance of each vertex of the graph to control such a possible intruder would be worthwhile. In this sense, Slater (1975) brought in the notion of locating sets in graphs. Also, Harary and Melter (1976) introduced independently the same concept, but using the name of resolving sets. Moreover, the terminology of metric generators was recently introduced. A metric generator is an ordered subset $S$ of vertices in a graph $G$, such that every vertex of $G$ is uniquely determined by its vector of distances to the vertices in $S$. The cardinality of a minimum metric generator for $G$ is called the metric dimension of $G$. A generalization of this concept to $k$-metric generators is due to Estrada-Moreno et al. (2013). Let $G=(V,E)$ be a simple and connected graph. A set $S\subseteq V$ is said to be a \emph{$k$-metric generator} for $G$ if any pair of vertices of $G$ is distinguished by at least $k$ elements of $S$. The minimum cardinality of any $k$-metric generator is the $k$-\emph{metric dimension} of $G$. At this point of the story we are able to propose a new problem in Graph Theory: the $k$-metric antidimension, that resembles to the aforementioned $k$-metric dimension. The fact is that not always is desirable to uniquely recognize each vertex of the graph, instead, it is very frequently desirable to have some privacy features. In this sense, a principal motivation of the new concept arises from a connection with some privacy preserving problem lying along the borderline between computer science and social sciences. Let $d_G(u, v)$ be the length of the shortest path between the vertices $u$ and $v$ in $G$. For an ordered set $S =\{u_1,\cdots, u_{t}\}$ of vertices in $V$ and a vertex $v$, we call $r(v|S) = (d_G(v, u_1), \dots, d_G(v, u_{t}))$ the \emph{metric representation} of $v$ with respect to $S$. The set $S$ is a $k$-\emph{antiresolving set} for $G$, if $k$ is the largest positive integer such that for every $v \in V-S$ there exist at least $k-1$ different vertices $v_1, \dots, v_{k-1} \in V-S$ with $r(v|S) = r(v_1|S) = \cdots = r(v_{k-1}|S)$. The $k$-\emph{metric antidimension} of a simple connected graph $G = (V, E)$ is the minimum cardinality of any $k$-antiresolving set in $G$. Intuitively, if $S$ is a $k$-antiresolving set, then it cannot uniquely re-identify other nodes in the network with probability higher than $1/k$. However, it might exist other subset of vertices in $G$ that forms a $k'$-antiresolving set where $k' < k$. This is, indeed, considered in the next privacy measure. It is said that a graph $G$ meets $(k, \ell)$-\emph{anonymity} with respect to active attacks if $k$ is the smallest positive integer such that the $k$-metric antidimension of $G$ is lower or equal than $\ell$. According to the facts above, in this talk the ``evolution'' of the metric dimension in graphs is described, beginning at its primary usefulness as a model of navigation of robots in networks and finishing as a privacy measure for social graphs.

Back to all abstracts