EUVIMEDEUVIMED entdecken
Crossref

Identifying Codes in Triangle‐Free Graphs of Bounded Maximum Degree

Dipayan Chakraborty, Florent Foucaud, Michael A. Henning, Tuomo Lehtilä

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →