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 条