2024/03/26 by Dipayan Chakraborty, Chakraborty, Dipayan, Florent Foucaud +5
Computer Science · Engineering · #05C07 #05C69 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2403.17877
openalex publication_date 2024/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 neighborhood and S. It was conjectured that there exists a constant c such that for every connected closed-twin-free graph G of order n and maximum degree Δ, the graph G admits an identifying code of size at most ( \fracΔ-1Δ ) n+c. In [D. Chakraborty, F. Foucaud, M. A. Henning, and T. Lehtilä. Identifying codes in graphs of given maximum degree: Characterizing trees. arXiv preprint arXiv:2403.13172, 2024], 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 c>0 as for trees: for Δ≥ 3, c=1/3 suffices and there is only a set of 12 trees requiring c>0 for Δ=3, and when Δ≥ 4 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 ( \fracΔ-1Δ ) n+1/Δ+4t for graphs that can be made triangle-free by the removal of t edges.