On the size of identifying codes in triangle-free graphs
From MaRDI portal
Publication:427898
DOI10.1016/j.dam.2012.02.009zbMath1300.05218arXiv1010.5975OpenAlexW2143470177MaRDI QIDQ427898
Florent Foucaud, Adrian Kosowski, Ralf Klasing, Andre Raspaud
Publication date: 18 June 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.5975
Bounds on codes (94B65) Other types of codes (94B60) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (13)
New results on variants of covering codes in Sierpiński graphs ⋮ Identifying Codes in Line Graphs ⋮ Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes ⋮ Unnamed Item ⋮ Identifying codes and watching systems in Kneser graphs ⋮ Identifying codes in the direct product of a complete graph and some special graphs ⋮ Identifying codes of corona product graphs ⋮ Bounds on the identifying codes in trees ⋮ The identifying code number and Mycielski's construction of graphs ⋮ Unnamed Item ⋮ Strong identification codes for graphs ⋮ Locating-Domination and Identification ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounds for identifying codes in terms of degree parameters
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- Lower bound of the Hadwiger number of graphs by their average degree
- Extremal cardinalities for identifying and locating-dominating codes in graphs
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- Structural properties of twin-free graphs
- Minimal identifying codes in trees and planar graphs with large girth
- On the size of identifying codes in binary hypercubes
- A note on the independence number of triangle-free graphs
- Approximation algorithms for the test cover problem
- Identifying and locating-dominating codes on chains and cycles
- Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
- Extremal graphs for the identifying code problem
- Identifying codes of cycles
- A linear algorithm for minimum 1-identifying codes in oriented trees
- On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
- Complexity results for identifying codes in planar graphs
- Domination and location in acyclic graphs
- Parity Graphs
- On a new class of codes for identifying vertices in graphs
- Two families of optimal identifying codes in binary Hamming spaces
This page was built for publication: On the size of identifying codes in triangle-free graphs
