Identifying codes in bipartite graphs of given maximum degree

Abstract

<p>An <em>identifying code</em> of a closed-twin-free graph <em>G</em> is a set <em>S</em> of vertices of <em>G</em> such that any two vertices in <em>G</em> have a distinct intersection between their closed neighborhoods and <em>S</em>. 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 <em>c</em> such that for every connected graph <em>G</em> of order <em>n</em> and maximum degree <strong>∆</strong>, <em>G</em> admits an identifying code of size at most ∆-1/∆<em>n</em> <strong>+</strong> <em>c.</em> 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 <em>c</em> for the considered class, and the list of graphs needing <em>c</em> ≥ 0. For <strong>∆ =</strong> 2 (the graph is a path or a cycle), it is long known that <em>c</em> <em><strong>=</strong></em> 3/2 suffices. For connected graphs in the considered graph class, for each <strong>∆</strong> ≥ 3, we show that <em>c</em> <em><strong>=</strong></em> 1<strong>/∆</strong> ≤ 1/3 suffices and that <em>c</em> is required to be positive only for a finite number of trees. In particular, for <strong>∆ =</strong> 3, there are 12 trees with diameter at most 6 with a positive constant <em>c</em> and, for each <strong>∆</strong> ≥ 4, the only tree with positive constant <em>c</em> 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].<br></p>