Algorithmic aspect of \(k\)-tuple domination in graphs.
type: Item
instance of: scholarly article
title: Algorithmic aspect of \(k\)-tuple domination in graphs.
zbMATH Open document ID: 1047.05032
author: Chung-Shou Liao
author: Gerard Jennhwa Chang
published in: Taiwanese Journal of Mathematics
publication date: 2002-01-01T00:00:00Z
review text: A dominating set of a graph \(G=(V,E)\) is defined as a set of vertices \(D\) such that each vertex from \(V\) is adjacent to to some vertex from \(D\) or it belongs to \(D\). One possible generalization of a dominating set is an \(M\)-dominating set. Let each vertex \(v\) be associated with a label \(M(v)=(t(v),k(v))\), where \(t(v)\) is one of the symbols in \(\{B,R\}\) and \(k(v)\) is a nonnegative integer. We say that a set of vertices \(D\) is \(M\)-dominating if it satisfies the following conditions for all vertices: (M1) If \(t(v)=R\), then \(v\in D.\) (M2) \(\left| N_{G}[v]\cap D\right| \) \(\geq k(v)\) where \(N_{G}[v]\) is the closed neighborhood of vertex \(v\). The authors present a linear-time algorithm to find a minimal \(M\)-dominating set in a tree with given labelling \(M\). In the case when \(t(v)=B\) and \(k(v)=2\) for all vertices in \(V\), the \(M\)-dominating set is called \(2\)-tuple dominating set or double dominating set. In a graph each vertex is dominated by at least two vertices from a \(2\)-tuple dominating set. In the case \( k(v)=1\) the \(M\)-dominating set is the usual dominating set.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1876796
zbMATH Keywords: domination
zbMATH Keywords: \(k\)-tuple domination
zbMATH Keywords: linear algorithm
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.11650/twjm/1500558307
OpenAlex ID: W4248071256
DOI: 10.11650/TWJM/1500558307
Recommended article: Algorithmic aspects of \(k\)-tuple total domination in graphs
Recommended article: Algorithmic aspects of the \(k\)-domination problem in graphs
Recommended article: On the algorithmic complexity of \(k\)-tuple total domination
Recommended article: \(k\)-tuple domination in graphs
Recommended article: Q4247463
Recommended article: On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs
Recommended article: Algorithmic Aspects of Some Variants of Domination in Graphs
Recommended article: \(k\)-tuple total domination in graphs
Recommended article: Q5004748
Recommended article: Algorithmic aspects of total k-subdomination in graphs
description: scientific article; zbMATH DE number 1876796