Bounds for identifying codes in terms of degree parameters (Q426794): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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\). | |||
Property / 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\). / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60B99 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94B60 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94C12 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6045656 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
size of the minimum identifying code of random \(d\)-regular graphs | |||
Property / zbMATH Keywords: size of the minimum identifying code of random \(d\)-regular graphs / rank | |||
Normal rank |
Revision as of 22:57, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounds for identifying codes in terms of degree parameters |
scientific article |
Statements
Bounds for identifying codes in terms of degree parameters (English)
0 references
12 June 2012
0 references
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\).
0 references
size of the minimum identifying code of random \(d\)-regular graphs
0 references