Revisiting and improving upper bounds for identifying codes

DOI10.1137/22M148999XMaRDI QIDQ5048300zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Tuomo Lehtilä

Publication date 15 November 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphsidentifying codestreesupper bound

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: An identifying code $C$ of a graph $G$ is a dominating set of $G$ such that any two distinct vertices of $G$ have distinct closed neighbourhoods within $C$. These codes have been widely studied for over two decades. We give an improvement over all the best known upper bounds, some of which have stood for over 20 years, for identifying codes in trees, proving the upper bound of $(n+ell)/2$, where $n$ is the order and $ell$ is the number of leaves (pendant vertices) of the graph. In addition to being an improvement in size, the new upper bound is also an improvement in generality, as it actually holds for bipartite graphs having no twins (pairs of vertices with the same closed or open neighbourhood) of degree 2 or greater. We also show that the bound is tight for an infinite class of graphs and that there are several structurally different families of trees attaining the bound. We then use our bound to derive a tight upper bound of $2n/3$ for twin-free bipartite graphs of order $n$, and characterize the extremal examples, as $2$-corona graphs of bipartite graphs. This is best possible, as there exist twin-free graphs, and trees with twins, that need $n-1$ vertices in any of their identifying codes. We also generalize the existing upper bound of $5n/7$ for graphs of order $n$ and girth at least 5 when there are no leaves, to the upper bound $frac5n+2ell7$ when leaves are allowed. This is tight for the $7$-cycle $C_7$ and for all stars.

Recommendations

• Bounds on the identifying codes in trees
• Maximum difference about the size of optimal identifying codes in graphs differing by one vertex
• Bounds for identifying codes in terms of degree parameters
• Extremal graphs for the identifying code problem
• Identifying codes in line graphs

Cites work

• Bounds for identifying codes in terms of degree parameters
• Bounds on the differentiating-total domination number of a tree
• Bounds on the identifying codes in trees
• Bounds on the locating-domination number and differentiating-total domination number in trees
• Bounds on the locating-total domination number of a tree
• Domination and location in acyclic graphs
• Extremal graphs for the identifying code problem
• scientific article; zbMATH DE number 1735664 (Why is no real title available?)
• scientific article; zbMATH DE number 2147927 (Why is no real title available?)
• Identifying and locating-dominating codes on chains and cycles
• Identifying codes in hereditary classes of graphs and VC-dimension
• Induced subsets
• Locating and total dominating sets in trees
• Locating-dominating sets and identifying codes in graphs of girth at least 5
• Locating-dominating sets in twin-free graphs
• Locating-dominating sets: from graphs to oriented graphs
• Locating-domination and identifying codes in trees
• Locating-total dominating sets in twin-free graphs: a conjecture
• Minimal identifying codes in trees and planar graphs with large girth
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On separating systems
• On the parameterized complexity of red-blue points separation
• The difference between the metric dimension and the determining number of a graph
• Total domination in graphs

Cited in

(12)

• Improved identification schemes based on error-correcting codes
• A class of I.P.P. codes with efficient identification
• Bounds on the identifying codes in trees
• On robust and dynamic identifying codes
• Huge Size Codes for Identification Via a Multiple Access Channel Under a Word-Length Constraint
• On three domination-based identification problems in block graphs
• Bounds and extremal graphs for total dominating identifying codes
• The \textsc{Red-Blue Separation} problem on graphs
• On three domination-based identification problems in block graphs
• Identifying codes in graphs of given maximum degree: characterizing trees
• Identifying codes in triangle-free graphs of bounded maximum degree
• New bounds on binary identifying codes

This page was built for publication: Revisiting and improving upper bounds for identifying codes

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