2014/11/19 by Sylvain Gravier, Aline Parreau, Gravier, Sylvain +7 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1411.5275
openalex publication_date 2014/11/19 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We consider the problem of computing identifying codes of graphs and its\nfractional relaxation. The ratio between the size of optimal integer and\nfractional solutions is between 1 and 2 ln(|V|)+1 where V is the set of\nvertices of the graph. We focus on vertex-transitive graphs for which we can\ncompute the exact fractional solution. There are known examples of\nvertex-transitive graphs that reach both bounds. We exhibit infinite families\nof vertex-transitive graphs with integer and fractional identifying codes of\norder |V|a with a in 1/4,1/3,2/5. These families are generalized quadrangles\n(strongly regular graphs based on finite geometries). They also provide\nexamples for metric dimension of graphs.\n