Identifying codes in vertex-transitive graphs and strongly regular graphs

被引:0
作者
Gravier, Sylvain [1 ]
Parreau, Aline [2 ]
Rottey, Sara [3 ,4 ]
Storme, Leo [3 ]
Vandomme, Elise [1 ,5 ]
机构
[1] Univ Grenoble, Inst Fourier, Grenoble, France
[2] Univ Lyon, CNRS, LIRIS, Lyon, France
[3] Univ Ghent, B-9000 Ghent, Belgium
[4] Vrije Univ Brussel, Brussels, Belgium
[5] Univ Liege, Dept Math, Liege, Belgium
关键词
identifying codes; metric dimension; vertex-transitive graphs; strongly regular graphs; finite geometry; generalized quadrangles; METRIC DIMENSION; VERTICES; LOCATION;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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(vertical bar V vertical bar) + 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 vertical bar V vertical bar(alpha) with alpha is an element of{1/4, 1/3, 2/5}These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.
引用
收藏
页数:26
相关论文
共 40 条
  • [31] Kratica J., 2008, P SYMOPIS, P341
  • [32] RATIO OF OPTIMAL INTEGRAL AND FRACTIONAL COVERS
    LOVASZ, L
    [J]. DISCRETE MATHEMATICS, 1975, 13 (04) : 383 - 390
  • [33] On graphs on n vertices having an identifying code of cardinality [log2(n+1)]
    Moncel, Julien
    [J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (14) : 2032 - 2039
  • [34] Payne S. E., 1984, RES NOTES MATH, V110
  • [35] Identifying codes of the direct product of two cliques
    Rall, Douglas F.
    Wash, Kirsti
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 : 159 - 171
  • [36] Slater P.J., 1988, J. Math. Phys. Sci, V22, P445
  • [37] Slater P.J., 1975, Congr. Numer, V14, P549, DOI DOI 10.1002/NET.3230170105
  • [38] DOMINATION AND LOCATION IN ACYCLIC GRAPHS
    SLATER, PJ
    [J]. NETWORKS, 1987, 17 (01) : 55 - 64
  • [39] Ungrangsi R, 2004, LECT NOTES COMPUT SC, V3283, P175
  • [40] Identifying codes of cycles with odd orders
    Xu, Min
    Thulasiraman, Krishnaiyan
    Hu, Xiao-Dong
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (07) : 1717 - 1720