Bounds for identifying codes in terms of degree parameters
type: Item
instance of: scholarly article
title: Bounds for identifying codes in terms of degree parameters
zbMATH Open document ID: 1243.05184
author: Florent Foucaud
author: Guillem Perarnau
published in: The Electronic Journal of Combinatorics
publication date: 2012-06-12T00:00:00Z
full work available at URL: v19i1p32
review text: Summary: An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If \(\gamma^{\text{ID}}(G)\) denotes the minimum size of an identifying code of a graph \(G\), it was conjectured by \textit{F. Foucaud}, \textit{R. Klasing}, \textit{A. Kosowski} and \textit{A. Raspaud} [``On the size of identifying codes in triange-free graphs'' (submitted to publication)] that there exists a constant \(c\) such that if a connected graph \(G\) with \(n\) vertices and maximum degree \(d\) admits an identifying code, then \(\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{d}+c\). We use probabilistic tools to show that for any \(d\geq 3, \gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d)}\) holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove \(\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d^{3})}\). In a second part, we prove that in any graph \(G\) of minimum degree \(\delta\) and girth at least 5, \(\gamma^{\text{ID}}(G)\leq(1+o_\delta(1))\tfrac{3\log\delta}{2\delta}n\). Using the former result, we give sharp estimates for the size of the minimum identifying code of random \(d\)-regular graphs, which is about \(\tfrac{\log d}{d}n\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60B99
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94C12
zbMATH DE Number: 6045656
zbMATH Keywords: size of the minimum identifying code of random \(d\)-regular graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6045656