Refereed article in conference proceedings (A4)

Identifying codes in bipartite graphs of given maximum degree

List of AuthorsChakraborty Dipayan, Foucaud Florent, Lehtilä Tuomo

EditorsCristina Fernandes, Sergio Rajsbaum

Conference nameLatin-American Algorithms, Graphs and Optimization Symposium

Publication year2023

JournalProcedia Computer Science

Book title *XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023)

Title of seriesProcedia Computer Science

Volume number223

Start page157

End page165




Self-archived copy’s web address


An identifying code of a closed-twin-free graph G is a set S of vertices of G such that any two vertices in G have a distinct intersection between their closed neighborhoods and S. It was conjectured in [F. Foucaud, R. Klasing, A. Kosowski, A. Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics, 2012] that there exists an absolute constant c such that for every connected graph G of order n and maximum degree G admits an identifying code of size at most ∆-1/∆n + c. We provide significant support for this conjecture by proving it for the class of all bipartite graphs that do not contain any pairs of open-twins of degree at least 2. In particular, this class of bipartite graphs contains all trees and more generally, all bipartite graphs without 4-cycles. Moreover, our proof allows us to precisely determine the constant c for the considered class, and the list of graphs needing c ≥ 0. For ∆ = 2 (the graph is a path or a cycle), it is long known that c = 3/2 suffices. For connected graphs in the considered graph class, for each  ≥ 3, we show that c = 1/∆ ≤ 1/3 suffices and that c is required to be positive only for a finite number of trees. In particular, for ∆ = 3, there are 12 trees with diameter at most 6 with a positive constant c and, for each  ≥ 4, the only tree with positive constant c is the ∆-star. Our proof is based on induction and utilizes recent results from [F. Foucaud, T. Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022].

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2023-27-09 at 13:03