Random subgraphs make identification affordable

DOI10.4310/JOC.2017.V8.N1.A3zbMATH Open1352.05167arXiv1306.0819MaRDI QIDQ501982FDOQ501982

Guillem Perarnau, Oriol Serra, Florent Foucaud

Publication date: 10 January 2017

Published in: Journal of Combinatorics (Search for Journal in Brave)

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 every graph $G$ with $n$ vertices, maximum degree $Delta=omega(1)$ and minimum degree $deltageqclogDelta$, for some constant $c>0$, contains a large spanning subgraph which admits an identifying code with size $Oleft(fracnlogDeltadeltaight)$. In particular, if $delta=Theta(n)$, then $G$ has a dense spanning subgraph with identifying code $Oleft(lognight)$, namely, of asymptotically optimal size. The subgraph we build is created using a probabilistic approach, and we use an interplay of various random methods to analyze it. Moreover we show that the result is essentially best possible, both in terms of the number of deleted edges and the size of the identifying code.

Full work available at URL: https://arxiv.org/abs/1306.0819

Recommendations

• On the complexity of the identifiable subgraph problem
• On the complexity of the identifiable subgraph problem, revisited
• scientific article; zbMATH DE number 3906536
• Fast canonical labeling of random subgraphs
• Random Subgraphs in Sparse Graphs
• The cost of distinguishing graphs
• Subgraphs of Random Graphs
• The anonymous subgraph problem
• Subgraphs of random match-graphs

zbMATH Keywords

identifying codesidentifying code of a graphrandom subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (1)

• Locating-Domination and Identification

This page was built for publication: Random subgraphs make identification affordable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501982)