
Sylvain Gravier

Aline Parreau

Sara Rottey

Leo Storme

Élise Vandomme
Keywords:
Graph theory, identifying codes, metricdimension, vertextransitive graphs, strongly regular graphs, finite geometry, generalized quadrangles
Abstract
We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and $2\ln(V)+1$ where $V$ is the set of vertices of the graph. We focus on vertextransitive graphs for which we can compute the exact fractional solution. There are known examples of vertextransitive graphs that reach both bounds. We exhibit infinite families of vertextransitive graphs with integer and fractional identifying codes of order $V^{\alpha}$ with $\alpha \in \{\frac{1}{4},\frac{1}{3},\frac{2}{5}\}$. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.