Loading...
Loading...

Go to the content (press return)

Random subgraphs make identification affordable

Author
Foucaud, F.; Perarnau, G.; Serra, O.
Type of activity
Journal article
Journal
Journal of Combinatorics
Date of publication
2017-01-02
Volume
8
Number
1
First page
57
Last page
77
DOI
https://doi.org/10.4310/JOC.2017.v8.n1.a3 Open in new window
Repository
http://hdl.handle.net/2117/112330 Open in new window
https://arxiv.org/pdf/1306.0819.pdf Open in new window
URL
http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0008/0001/a003/index.html Open in new window
Abstract
An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number (the size of a smallest identifying code), which indeed is not even a monotone parameter with respect to graph inclusion. We show that for every large enough ¿¿, every graph GG on nn vertices with maximum degree ¿¿ and minimum degree d=clo...
Citation
Foucaud, F., Perarnau, G., Serra, O. Random subgraphs make identification affordable. "Journal of Combinatorics", 2 Gener 2017, vol. 8, núm. 1, p. 57-77.
Keywords
identifying codes, random subgraphs
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

  • Foucaud, Florent  (author)
  • Perarnau, Guillem  (author)
  • Serra Albo, Oriol  (author)

Attachments