Algorithmic results on locating-total domination in graphs

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

A dominating set (DS) of \(G\) is a set \(D\subseteq V\) such that each vertex in \(V\setminus D\) is adjacent to at least one vertex in \(D\). A total dominating set (TDS) of \(G\) is a set \(D\subseteq V\) with the property that each vertex in \(V\) is adjacent to at least one vertex in \(D\). A locating-dominating set (LDS) of \(G\) is a subset \(D\subseteq V\) such that \(D\) is a DS of \(G\) and \(N(u) \cap D\neq N(v)\cap D\) for each pair of distinct vertices \(u\) and \(v\) in \(V\setminus D\). A locating-total dominating set (LTDS) of \(G\) is a subset \(D\subseteq V\) such that \(D\) is both TDS and LDS of \(G\). The smallest size of an LTDS of \(G\) between all LTDSs of \(G\) is called the locating-total domination number of \(G\), denoted by \(\gamma_L^t(G)\). The Locating-Total Dominating Set problem is the problem of computing an LTDS \(D\) of a given graph \(G\) with \(|D|=\gamma_L^t(G)\). The authors prove that the decision version of the Locating-Total Dominating Set problem is NP-complete for circle graphs, undirected path graphs, and graphs of separability at most 2. Also, they give a \((2 \ln|V|+1.7)\)-approximation algorithm for computing a minimum LTDS of a given graph \(G\) and prove that the problem of computing a minimum locating-total dominating set is APX-complete for graphs of degree at most 4. Finally, they propose a linear algorithm for computing the locating-total domination number of trees.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Algorithmic results on locating-total domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157416)