Bounds and extremal graphs for total dominating identifying codes (Q6133156): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:31, 10 July 2024
scientific article; zbMATH DE number 7729686
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounds and extremal graphs for total dominating identifying codes |
scientific article; zbMATH DE number 7729686 |
Statements
Bounds and extremal graphs for total dominating identifying codes (English)
0 references
18 August 2023
0 references
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.
0 references
identifying codes
0 references
total dominating sets
0 references
total dominating identifying code
0 references
extremal problem
0 references