Identifying codes in graphs (one-vertex perturbations)

M2 research project to study the following article:

• Charon, I., Honkala, I., Hudry, O., & Lobstein, A. (2012). Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex (https://hal.science/hal-00731811/document). (Provided as OH2.pdf in this repo.)

Motivation and objective of the article

Identifying codes formalize the idea of locating faults/sensors in a network from local observations: we place a set of "sensors" (a code) on vertices so that every vertex has a unique signature given by the sensors in its neighborhood. This comes up in fault diagnosis, monitoring, and routing, where we want robust identification with as few sensors as possible.

This project focuses on stability under a small graph modification: how much can the minimum identifying-code size change when a graph is modified by adding or removing a single vertex. Concretely, we compare the identifying-code number of a graph $G$ with that of a closely related graph $G^*$ that differs from $G$ by exactly one vertex.

Core definitions

Let $G=(V,E)$ be a simple, undirected graph with vertex set $V$ and edge set $E$. The order of a graph is its number of vertices $|V|$.

Distance and neighborhoods

• Distance: For any two vertices $x, y \in V$, the distance $d_G(x,y)$ is the length of a shortest path between $x$ and $y$ (or $+\infty$ if no path exists).
• Ball of radius $r$: For any vertex $v \in V$ and integer $r \geq 1$, the ball of radius $r$ and centre $v$ is: $$B_{G,r}(v) = {x \in V : d_G(v,x) \leq r}.$$ This is the set of all vertices within distance $r$ from $v$.

Twins and twin-free graphs

• $(G,r)$-twins: Two vertices $x$ and $y$ such that $B_{G,r}(x) = B_{G,r}(y)$ are called $(G,r)$-twins.
• $r$-twin-free: A graph $G$ is $r$-twin-free if it has no $(G,r)$-twins, i.e., if for all distinct vertices $x, y \in V$, we have $B_{G,r}(x) \neq B_{G,r}(y)$.

Covering and separation

• $r$-cover: When two vertices $x$ and $y$ are within distance $r$ from each other in $G$, i.e., $x \in B_{G,r}(y)$ and $y \in B_{G,r}(x)$, we say that $x$ and $y$ $r$-cover each other.
• $r$-separate: When three vertices $x, y, z$ are such that $x \in B_{G,r}(z)$ and $y \notin B_{G,r}(z)$, we say that $z$ $r$-separates $x$ and $y$ in $G$. A set $r$-separates $x$ and $y$ if it contains at least one vertex that $r$-separates them.

Identifying codes

• Code: A code $\mathcal{C}$ is simply a subset of $V$; its elements are called codewords.
• $r$-identifying set: For each vertex $v \in V$ and a code $\mathcal{C} \subseteq V$, the $r$-identifying set of $v$ (with respect to $\mathcal{C}$) is the set of codewords that $r$-cover $v$: $$I_{G,\mathcal{C},r}(v) = B_{G,r}(v) \cap \mathcal{C}.$$
• $r$-identifying code: A code $\mathcal{C} \subseteq V$ is an $r$-identifying code if:
  1. All sets $I_{G,\mathcal{C},r}(v)$, $v \in V$, are nonempty (every vertex is $r$-covered by at least one codeword), and
  2. All sets $I_{G,\mathcal{C},r}(v)$, $v \in V$, are distinct (every pair of vertices is $r$-separated by at least one codeword).
• $r$-identifiable: A graph $G$ admits an $r$-identifying code if and only if $G$ is $r$-twin-free. For this reason, $r$-twin-free graphs are also called $r$-identifiable.
• $\gamma_r(G)$: When $G$ is $r$-twin-free, we denote by $\gamma_r(G)$ the cardinality of a smallest $r$-identifying code in $G$.

Problem statement

Given an $r$-twin-free graph $G$ and a graph $G^$ obtained from $G$ by adding or deleting one vertex, if $G^$ is still $r$-twin-free, we study:

• The difference: $\gamma_r(G) - \gamma_r(G^*)$
• The ratio: $\frac{\gamma_r(G)}{\gamma_r(G^)}$ (or $\frac{\gamma_r(G^)}{\gamma_r(G)}$)

as functions of the order $n$ of the graph and the radius $r$.