Identifying codes in vertex-transitive graphs and strongly regular graphs (Q888612)

Summary: 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 vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive 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.