Bounds and extremal graphs for total dominating identifying codes (Q6133156): Difference between revisions

Let \(G=(V,E)\) be a graph. The open neighborhood of a vertex \(v\) is the set \(N(v)= \{u \in V\mid uv \in E\}\) and the closed neighborhood of \(v\) is the set \(N[v]= N(v) \cup \{v\}\). For a set \(C\) of vertices and a vertex \(v\), the intersection between \(N[v]\) and \(C\) is called the \(I\)-set of \(v\), \(I(v) = N[v]\cap C\). A dominating set \(C \subseteq V (G)\) is called an identifying code of \(G\) if for each pair of distinct vertices \(u, v \in V(G)\), their \(I\)-sets are distinct, that is, \(I(u)\neq I(v)\). When every vertex of \(G\) also has a neighbour in \(C\), it is said to be a total dominating identifying code of \(G\). The smallest size of a total dominating identifying code of \(G\) is denoted \(\gamma_t^{\mathrm{ID}}(G)\). In this paper, the authors first characterize all graphs \(G\) of order \(n\) with \(\gamma_t^{\mathrm{ID}}(G)\in \{n,n-1\}\), and then they show that every connected twin-free graph \(G\) of girth at least 5 on \(n\ge 3\) vertices, satisfies \(\gamma_t^{\mathrm{ID}}(G)\le \frac{3n}{4}\). Finally, they study the ratio between parameter \(\gamma_t^{\mathrm{ID}}\) and related parameters such as locating domination number and locating-total domination number.