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

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2015年 / 22卷 / 04期

关键词：

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 条

[1] ON THE ORDER OF UNIPRIMITIVE PERMUTATION-GROUPS [J].