ABSTRACT An identifying code of a closed‐twin‐free graph is a set of vertices of such that any two vertices in have a distinct, nonempty intersection between their closed neighborhood and . It was conjectured that there exists a constant such that for every connected closed‐twin‐free graph of order and maximum degree , the graph admits an identifying code of size at most . In D. Chakraborty, F. Foucaud, M. A. Henning, and T. Lehtilä. Identifying codes in graphs of given maximum degree: Characterizing trees. Discrete Mathematics 349(2), 114826, 2026, we proved the conjecture for all trees. In this article, we show that the conjecture holds for all triangle‐free graphs, with the same list of exceptional graphs needing as for trees: for suffices and there is only a set of 12 trees requiring for , and when this set is reduced to the ‐star only. Our proof is by induction, whose starting point is the above result for trees. Along the way, we prove a generalized version of Bondy's theorem on induced subsets J. A. Bondy. Induced subsets. Journal of Combinatorial Theory, Series B, 1972 that we use as a tool in our proofs. We also use our main result for triangle‐free graphs to prove the upper bound for graphs that can be made triangle‐free by the removal of edges.
Chakraborty et al. (Tue,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: