Refereed article in conference proceedings (A4)

Identifying codes in bipartite graphs of given maximum degree

List of Authors: Chakraborty Dipayan, Foucaud Florent, Lehtilä Tuomo

Editors: Cristina Fernandes, Sergio Rajsbaum

Conference name: Latin-American Algorithms, Graphs and Optimization Symposium

Publication year: 2023

Journal: Procedia Computer Science

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

Title of series: Procedia Computer Science

Volume number: 223

Start page: 157

End page: 165

eISSN: 1877-0509

DOI: http://dx.doi.org/10.1016/j.procs.2023.08.225

URL: https://doi.org/10.1016/j.procs.2023.08.225

Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/181101943

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