Identifying codes in triangle-free graphs of bounded maximum degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916332368297984 |
|---|---|
| author | Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. Lehtilä, Tuomo |
| author_facet | Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. Lehtilä, Tuomo |
| contents | An $\textit{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 $\left( \frac{Δ-1}Δ \right) 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 $Δ\ge 3$, $c=1/3$ suffices and there is only a set of 12 trees requiring $c>0$ for $Δ=3$, and when $Δ\ge 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 $\left( \frac{Δ-1}Δ \right) n+1/Δ+4t$ for graphs that can be made triangle-free by the removal of $t$ edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17877 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Identifying codes in triangle-free graphs of bounded maximum degree Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. Lehtilä, Tuomo Combinatorics 05C69, 05C07 An $\textit{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 $\left( \frac{Δ-1}Δ \right) 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 $Δ\ge 3$, $c=1/3$ suffices and there is only a set of 12 trees requiring $c>0$ for $Δ=3$, and when $Δ\ge 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 $\left( \frac{Δ-1}Δ \right) n+1/Δ+4t$ for graphs that can be made triangle-free by the removal of $t$ edges. |
| title | Identifying codes in triangle-free graphs of bounded maximum degree |
| topic | Combinatorics 05C69, 05C07 |
| url | https://arxiv.org/abs/2403.17877 |