Geodesic
Identifying codes in vertex-transitive graphs and strongly regular graphs
Sylvain Gravier1 ; Aline Parreau2 ; Sara Rottey3 ; Leo Storme4 ; Élise Vandomme5
1Institut Fourier, University of Grenoble
2LIRIS, University of Lyon, CNRS
3Ghent University and Vrije Universiteit Brussel
4Ghent University
5Department of Mathematics, University of Liege, and Institut Fourier, University of Grenoble
The electronic journal of combinatorics, Tome 22 (2015) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $2\ln(|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|^{\alpha}$ with $\alpha \in \{\frac{1}{4},\frac{1}{3},\frac{2}{5}\}$. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.
DOI : 10.37236/5256
Classification : 05E30, 05B25, 05C69, 94B99
Mots-clés : identifying codes, metric dimension, vertex-transitive graphs, strongly regular graphs, finite geometry, generalized quadrangles

Sylvain Gravier  1   ; Aline Parreau  2   ; Sara Rottey  3   ; Leo Storme  4   ; Élise Vandomme  5

1 Institut Fourier, University of Grenoble
2 LIRIS, University of Lyon, CNRS
3 Ghent University and Vrije Universiteit Brussel
4 Ghent University
5 Department of Mathematics, University of Liege, and Institut Fourier, University of Grenoble 
@article{10_37236_5256,
     author = {Sylvain Gravier and Aline Parreau and Sara Rottey and Leo Storme and \'Elise Vandomme},
     title = {Identifying codes in vertex-transitive graphs and strongly regular graphs},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {4},
     doi = {10.37236/5256},
     zbl = {1323.05141},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5256/}
}
TY  - JOUR
AU  - Sylvain Gravier
AU  - Aline Parreau
AU  - Sara Rottey
AU  - Leo Storme
AU  - Élise Vandomme
TI  - Identifying codes in vertex-transitive graphs and strongly regular graphs
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5256/
DO  - 10.37236/5256
ID  - 10_37236_5256
ER  - 
%0 Journal Article
%A Sylvain Gravier
%A Aline Parreau
%A Sara Rottey
%A Leo Storme
%A Élise Vandomme
%T Identifying codes in vertex-transitive graphs and strongly regular graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5256/
%R 10.37236/5256
%F 10_37236_5256
Sylvain Gravier; Aline Parreau; Sara Rottey; Leo Storme; Élise Vandomme. Identifying codes in vertex-transitive graphs and strongly regular graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/5256

Cité par Sources :