Identifying codes in graphs of given maximum degree: characterizing trees

DOI10.1016/J.DISC.2025.114826MaRDI QIDQ6884364zbMATH OpenFDO

Authors Dipayan Chakraborty, Florent Foucaud, Michael A. Henning, Tuomo Lehtilä

Publication date 15 December 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114826

Trees (05C05) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Theory of error-correcting codes and error-detecting codes (94B99)

Cites work

scientific article; zbMATH DE number 3161569 (Why is no real title available?)
scientific article; zbMATH DE number 1735664 (Why is no real title available?)
scientific article; zbMATH DE number 2147927 (Why is no real title available?)
An upper bound on the domination number of \(n\)-vertex connected cubic graphs
Bounds for identifying codes in terms of degree parameters
Bounds on the identifying codes in trees
Domination in Graphs: Core Concepts
Extremal graphs for the identifying code problem
ID codes in Cartesian products of cliques
Identifying and locating-dominating codes on chains and cycles
Identifying codes in bipartite graphs of given maximum degree
Identifying codes in line graphs
Identifying codes of cycles
Identifying codes of the direct product of two cliques
Independent domination in cubic graphs
Independent domination of graphs with bounded maximum degree
Induced subsets
Locating and total dominating sets in trees
Locating-dominating sets and identifying codes in graphs of girth at least 5
Locating-domination and identification
Locating-domination and identifying codes in trees
Minimal identifying codes in trees and planar graphs with large girth
New results on variants of covering codes in Sierpiński graphs
On a conjecture regarding identification in Hamming graphs
On a new class of codes for identifying vertices in graphs
On graphs having a \(V\setminus \{x\}\) set as an identifying code
On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
On independent domination of regular graphs
On the Complexity of Canonical Labeling of Strongly Regular Graphs
On the independent domination number of regular graphs
On the size of identifying codes in triangle-free graphs
Paths, Stars and the Number Three
Revisiting and improving upper bounds for identifying codes
Some remarks on domination
The first order definability of graphs: Upper bounds for quantifier depth
Total domination in graphs
Total domination of graphs and small transversals of hypergraphs

Cited in

(3)

Identifying open codes in trees and 4-cycle-free graphs of given maximum degree
A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
Identifying codes in triangle-free graphs of bounded maximum degree

This page was built for publication: Identifying codes in graphs of given maximum degree: characterizing trees

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