Advanced search
1 file | 388.96 KB

Identifying codes in vertex-transitive graphs and strongly regular graphs

Author
Organization
Abstract
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.
Keywords
metric dimension, identifying codes, vertex-transitive graphs, strongly regular graphs, finite geometry, generalized quadrangles, METRIC DIMENSION, VERTICES, CYCLES, LOCATION, SET

Downloads

  • 5256-15256-2-PB.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 388.96 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Gravier, Sylvain, Aline Parreau, Sara Rottey, Leo Storme, and Élise Vandomme. 2015. “Identifying Codes in Vertex-transitive Graphs and Strongly Regular Graphs.” Electronic Journal of Combinatorics 22 (4).
APA
Gravier, S., Parreau, A., Rottey, S., Storme, L., & Vandomme, É. (2015). Identifying codes in vertex-transitive graphs and strongly regular graphs. ELECTRONIC JOURNAL OF COMBINATORICS, 22(4).
Vancouver
1.
Gravier S, Parreau A, Rottey S, Storme L, Vandomme É. Identifying codes in vertex-transitive graphs and strongly regular graphs. ELECTRONIC JOURNAL OF COMBINATORICS. 2015;22(4).
MLA
Gravier, Sylvain et al. “Identifying Codes in Vertex-transitive Graphs and Strongly Regular Graphs.” ELECTRONIC JOURNAL OF COMBINATORICS 22.4 (2015): n. pag. Print.
@article{8028374,
  abstract     = {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.},
  articleno    = {P4.6},
  author       = {Gravier, Sylvain and Parreau, Aline and Rottey, Sara and Storme, Leo and Vandomme, Élise},
  issn         = {1077-8926},
  journal      = {ELECTRONIC JOURNAL OF COMBINATORICS},
  keywords     = {metric dimension,identifying codes,vertex-transitive graphs,strongly regular graphs,finite geometry,generalized quadrangles,METRIC DIMENSION,VERTICES,CYCLES,LOCATION,SET},
  language     = {eng},
  number       = {4},
  pages        = {26},
  title        = {Identifying codes in vertex-transitive graphs and strongly regular graphs},
  url          = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p6/0},
  volume       = {22},
  year         = {2015},
}

Web of Science
Times cited: