Vertaisarvioitu artikkeli konferenssijulkaisussa (A4)

Identifying codes in bipartite graphs of given maximum degree

Julkaisun tekijätChakraborty Dipayan, Foucaud Florent, Lehtilä Tuomo

ToimittajaCristina Fernandes, Sergio Rajsbaum

Konferenssin vakiintunut nimiLatin-American Algorithms, Graphs and Optimization Symposium


JournalProcedia Computer Science

Kirjan nimi *XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023)

Sarjan nimiProcedia Computer Science



Lopetussivun numero165




Rinnakkaistallenteen osoite


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].

Ladattava julkaisu

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