[en] 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 2ln(|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|^α with α∈{14,13,25}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.
Disciplines :
Mathematics
Author, co-author :
Gravier, Sylvain; Université de Grenoble > Institut Fourier
L. Babai, On the complexity of canonical labeling of strongly regular graphs, SIAM J. Computing, 9(1), 212-216 (1980).
L. Babai, On the order of uniprimitive permutation groups, Ann. Math. (2), 113(3), 553-568 (1981).
R. F. Bailey, On the metric dimension of imprimitive distance-regular graphs, Preprint, arXiv: 1312. 4971.
R. F. Bailey, The metric dimension of small distance-regular and strongly regular graphs, Australas. J. Combin., 62(1), 18-34 (2015).
R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc., 43(2), 209-242 (2011).
N. Bertrand, I. Charon, O. Hudry and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European J. Combin., 25(7), 969-987 (2004).
U. Blass, I. Honkala and S. Litsyn, On binary codes for identification, J. Combin. Des., 8(2), 151-156 (2000).
J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, On the Metric Dimension of Cartesian Products of Graphs, SIAM J. Discrete Math., 21(2), 423-441 (2007).
P. J. Cameron, Partial quadrangles, Quart. J. Math. Oxford, 26, 61-73 (1975).
P. J. Cameron, Random strongly regular graphs?, Discrete Math., 273(1-3), 103-114 (2003).
I. Charon, O. Hudry and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci., 290(3), 2109-2120 (2003).
G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Locating vertices using codes, Congr. Numer., 191, 143-159 (2008).
G. Exoo, T. Laihonen and S. Ranto, New bounds on binary identifying codes, Discrete Applied Math., 156(12), 2250-2263 (2008).
M. Feng, M. Xu and K. Wang, Identifying codes in lexicographic product of graphs, Electron. J. Combin., 19(4), #P56 (2012).
G. Fijavz and B. Mohar, Rigidity and separation indices of Paley graphs, Discrete Math., 289(1-3), 157-161 (2004).
F. Foucaud, E. Guerrini, M. Kovśe, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, European J. Combin., 32(4), 628-638 (2011).
W. Goddard and K. Wash, ID codes in Cartesian products of cliques, J. Combin. Math. Combin. Comput., 85, 97-106 (2013).
S. Gravier, S. Janson, T. Laihonen and S. Ranto, Graphs where every k-subset of vertices is an identifying set, Discrete Math. Theor. Comput. Sci., 16(1), 73-88 (2014).
S. Gravier, R. Klasing and J. Moncel, Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs, Algorithmic Oper. Res., 3(1), 43-50 (2008).
S. Gravier and J. Moncel, On graphs having a V n fxg set as an identifying code, Discrete Math., 307(3-5), 432-434 (2007).
S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin., 27(5), 767-776 (2006).
S. Gravier, J. Moncel and A. Semri, Identifying codes of Cartesian product of two cliques of the same size, Electron. J. Combin., 15, #N4 (2008).
R. H. Hammack, W. Imrich and S. Klavźar, Handbook of product graphs, CRC Press, Inc., Boca Raton, FL, USA (2011).
D. G. Higman, Partial Geometries, generalized quadrangles and strongly regular graphs, Atti del Convegno di Geometria Combinatoria e sue Applicazioni 1970 (Pe-rugia), 263-293 (1971).
D. G. Higman, Invariant relations, coherent configurations and generalized polygons, Combinatorics (Proc. Advances Study Inst., Breukelen, 1974), Part 3: Combinatorial group theory, 27-43, M Math. Centre Tracts 57, Math. Centrum, Amsterdam (1974).
J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries. Oxford Science Publications, Oxford (1991).
I. Honkala and A. Lobstein, On identifying codes in binary Hamming spaces, J. Combin. Theory, Ser. A, 99(2), 232-243 (2002).
V. Junnila and T. Laihonen, Optimal identifying codes in cycles and paths, Graphs Combin., 28(4), 469-481 (2012).
M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44(2), 599-611 (1998).
J. Kratica, D. Cvetković, M. Ćangalović, V. Kovaćević-Vujćić and J. Kojić, The met-ric dimension of strongly regular graphs, Proceedings of SYMOPIS 2008 (Belgrade), 341-344 (2008).
L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math., 13(4), 383-390 (1975).
J. Moncel, On graphs on n vertices having an identifying code of cardinality dlog2(n+ 1)e, Discrete Applied Math., 154(14), 2032-2039 (2006).
S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, Research Notes in Mathematics, 110, Pitman, Boston (1984).
D. F. Rall and K. Wash, Identifying codes of the direct product of two cliques, European J. Combin., 36, 159-171 (2014).
P. J. Slater, Leaves of trees, Congr. Numer., 14, 549-559 (1975).
P. J. Slater, Domination and location in acyclic graphs, Networks, 17(1), 55-64 (1987).
P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22(4), 445-455 (1988).
R. Ungrangsi, A. Trachtenberg and D. Starobinski, An implementation of indoor location detection systems based on identifying codes, Proceedings of Intelligence in Communication Systems, INTELLCOMM 2004, LNCS 3283, 175-189 (2004).
M. Xu, K. Thulasiraman and X. Hu, Identifying codes of cycles with odd orders, European J. Combin., 29(7), 1717-1720 (2008).
