Secure total domination number in maximal outerplanar graphs
type: Item
instance of: scholarly article
title: Secure total domination number in maximal outerplanar graphs
zbMATH Open document ID: 1545.05161
author: Yasufumi Aita
author: Toru Araki
published in: Discrete Applied Mathematics
publication date: 2024-05-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 7855812
zbMATH Keywords: secure total domination
zbMATH Keywords: total domination
zbMATH Keywords: maximal outerplanar graphs
zbMATH Keywords: upper bound
zbMATH Keywords: lower bound
MaRDI profile type: Publication
cites work: Secure domination in proper interval graphs
cites work: Secure domination in cographs
cites work: On the secure domination numbers of maximal outerplanar graphs
cites work: Q5503336
cites work: A linear algorithm for secure domination in trees
cites work: On minimum secure dominating sets of graphs
cites work: Vertex Covers and Secure Domination in Graphs
cites work: On dominating sets of maximal outerplanar graphs
cites work: Q3065457
cites work: Q5461685
cites work: Total domination in maximal outerplanar graphs. II.
cites work: Secure total domination in graphs: bounds and complexity
cites work: The secure domination problem in cographs
cites work: Secure domination and secure total domination in graphs
cites work: Total dominating sets in maximal outerplanar graphs
cites work: On secure domination in trees
cites work: On dominating sets of maximal outerplanar and planar graphs
cites work: Dominating sets in planar graphs
cites work: On secure domination in graphs
cites work: Q3799261
cites work: On computing a minimum secure dominating set in block graphs
cites work: Dominating sets of maximal outerplanar graphs
cites work: A simple algorithm for secure domination in proper interval graphs
DOI: 10.1016/J.DAM.2024.04.007
description: scientific article; zbMATH DE number 7855812