Unpublished conference/Abstract (Scientific congresses and symposiums)
Identifying codes in vertex-transitive graphs
Gravier, Sylvain; Parreau, Aline; Rottey, Sara et al.
20149th International colloquium on graph theory and combinatorics (ICGT 2014)
 

Files


Full Text
vandomme_ICGT2014.pdf
Publisher postprint (419.11 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
identifying code; graph; generalized quadrangles
Abstract :
[en] We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) 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|^a with a in {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.
Disciplines :
Mathematics
Author, co-author :
Gravier, Sylvain;  Institut Fourier, Université Grenoble 1
Parreau, Aline ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rottey, Sara;  Ghent University and Vrije Universiteit Brussels
Storme, Leo;  Ghent University
Vandomme, Elise ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Identifying codes in vertex-transitive graphs
Publication date :
July 2014
Event name :
9th International colloquium on graph theory and combinatorics (ICGT 2014)
Event place :
Grenoble, France
Event date :
30/06/2014 -- 04/07/2014
Audience :
International
Available on ORBi :
since 09 July 2014

Statistics


Number of views
42 (8 by ULiège)
Number of downloads
66 (4 by ULiège)

Bibliography


Similar publications



Contact ORBi