Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree
Journal of Graph Theory · 2026-07 · 112 (3) · 306-336
DOI: 10.1002/jgt.70025 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 31.03.2026. Verfasst von Dipayan Chakraborty und 3 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben. Gefördert von: University of Johannesburg, Academy of Finland.
Abstract (Originalsprache)
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.
Förderung
- University of Johannesburg
- Academy of Finland
Zitieren
APA
Chakraborty, D., Foucaud, F., Henning, M. A., & Lehtilä, T. (2026). Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree. Journal of Graph Theory, 112(3), 306-336. https://doi.org/10.1002/jgt.70025
Vancouver
Chakraborty D, Foucaud F, Henning MA, Lehtilä T. Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree. Journal of Graph Theory. 2026;112(3):306-336. doi:10.1002/jgt.70025
BibTeX
@article{Chakraborty2026,
author = {Chakraborty, Dipayan and Foucaud, Florent and Henning, Michael A. and Lehtilä, Tuomo},
title = {Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {3},
pages = {306--336},
doi = {10.1002/jgt.70025}
}
EUVIMED