Identifying open codes in trees and 4-cycle-free graphs of given maximum degree
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910526551883776 |
|---|---|
| author | Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. |
| author_facet | Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. |
| contents | An identifying open code of a graph $G$ is a set $S$ of vertices that is both a separating open code (that is, $N_G(u) \cap S \ne N_G(v) \cap S$ for all distinct vertices $u$ and $v$ in $G$) and a total dominating set (that is, $N(v) \cap S \ne \emptyset$ for all vertices~$v$ in $G$). Such a set exists if and only if the graph $G$ is open twin-free and isolate-free; and the minimum cardinality of an identifying open code in an open twin-free and isolate-free graph $G$ is denoted by $γ^{\rm {\small IOC}}(G)$.
We study the smallest size of an identifying open code of a graph, in relation with its order and its maximum degree. For $Δ$ a fixed integer at least $3$, if $G$ is a connected graph of order $n \ge 5$ that contains no $4$-cycle and is open twin-free with maximum degree bounded above by $Δ$, then we show that $γ^{\rm {\small IOC}}(G) \le \left( \frac{2Δ- 1}Δ \right) n$, unless $G$ is obtained from a star $K_{1,Δ}$ by subdividing every edge exactly once.
Moreover, we show that the bound is best possible by constructing graphs that reach the bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09692 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Identifying open codes in trees and 4-cycle-free graphs of given maximum degree Chakraborty, Dipayan Foucaud, Florent Henning, Michael A. Combinatorics An identifying open code of a graph $G$ is a set $S$ of vertices that is both a separating open code (that is, $N_G(u) \cap S \ne N_G(v) \cap S$ for all distinct vertices $u$ and $v$ in $G$) and a total dominating set (that is, $N(v) \cap S \ne \emptyset$ for all vertices~$v$ in $G$). Such a set exists if and only if the graph $G$ is open twin-free and isolate-free; and the minimum cardinality of an identifying open code in an open twin-free and isolate-free graph $G$ is denoted by $γ^{\rm {\small IOC}}(G)$. We study the smallest size of an identifying open code of a graph, in relation with its order and its maximum degree. For $Δ$ a fixed integer at least $3$, if $G$ is a connected graph of order $n \ge 5$ that contains no $4$-cycle and is open twin-free with maximum degree bounded above by $Δ$, then we show that $γ^{\rm {\small IOC}}(G) \le \left( \frac{2Δ- 1}Δ \right) n$, unless $G$ is obtained from a star $K_{1,Δ}$ by subdividing every edge exactly once. Moreover, we show that the bound is best possible by constructing graphs that reach the bound. |
| title | Identifying open codes in trees and 4-cycle-free graphs of given maximum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.09692 |