Secure total domination number in maximal outerplanar graphs
A subset \(S\) of vertices in a graph \(G\) is a secure total dominating set of \(G\) if \(S\) is a total dominating set of \(G\) and, for each vertex \(u \in S\), there is a vertex \(v \in S\) such that \(uv\) is an edge and \((S\setminus \{v\})\cup \{u\}\) is also a total dominating set of \(G\). The minimum cardinality of a secure total dominating set, denoted by \(\gamma_{st}(G)\), is called the secure total domination number of \(G\).\N\NA graph \(G\) is outerplanar if it has a crossing-free embedding in the plane such that all vertices belong to the boundary of its outer face (the unbounded face). A maximal outerplanar graph is an outerplanar graph such that the addition of a single edge results in a graph that is not outerplanar.\N\NThe authors of this paper under review, prove that for any maximal outerplanar graph \(G\) of \(n \geq 3\), \(\lceil \frac{n+2}{3}\rceil \leq \gamma_{st}(G) \leq \lfloor \frac{2n}{3}\rfloor\). They also show that these bounds are sharp.
scientific article; zbMATH DE number 7855812
scientific article