2024/03/06 by Aita, Yasufumi, Araki, Toru
#05C10 #05C69 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2403.03404
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 \not∈ S, there is a vertex v ∈ S such that uv is an edge and (S ∖ \v\) ∪ \u\ is also a total dominating set of G. We show that if G is a maximal outerplanar graph of order n, then G has a total secure dominating set of size at most \lfloor 2n/3 \rfloor. Moreover, if an outerplanar graph G of order n, then each secure total dominating set has at least \lceil (n+2)/3 \rceil vertices. We show that these bounds are best possible.