An algorithm to find two distance domination parameters in a graph
type: Item
instance of: scholarly article
title: An algorithm to find two distance domination parameters in a graph
zbMATH Open document ID: 0848.05040
DOI: 10.1016/0166-218X(95)00057-X
author: Michael A. Henning
author: H. C. Swart
author: Gerd H. Fricke
author: Ortrud R. Oellermann
published in: Discrete Applied Mathematics
publication date: 1996-10-06T00:00:00Z
review text: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called total \(n\)-dominating, if for each \(x \in V(G)\) there exists a vertex \(y \in D\) distinct from \(x\) such that the distance between \(x\) and \(y\) is less than or equal to \(n\). A subset \(S\) of \(V(G)\) is called \(n\)-independent, if the distance between any two vertices of \(S\) is at least \(n + 1\). The minimum number of vertices of a total \(n\)-dominating set in \(G\) is the total \(n\)-domination number \(\gamma_n' (G)\), the minimum number of vertices of a maximal (with respect to set inclusion) \(n\)-independent set in \(G\) is the \(n\)-independence number \(i_n (G)\) of \(G\). The paper presents an algorithm for finding a total \(n\)-dominating set and a maximal \(n\)-independent set in a graph \(G\) with \(p \geq 2n + 1\) vertices. For such graphs the inequality \(i_n (G) + n \gamma_n' (G) \leq p\) is proved.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 897434
zbMATH Keywords: distance domination
zbMATH Keywords: total \(n\)-dominating set
zbMATH Keywords: total \(n\)-domination number
zbMATH Keywords: \(n\)-independent set
zbMATH Keywords: \(n\)-independence number
zbMATH Keywords: distance
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: A note on total domination
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: A characterization of graphs without long induced paths
cites work: Q4305538
cites work: A sufficient condition for dominating cycles
cites work: R-domination of block graphs
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Q3818315
cites work: A note on distance-dominating cycles
cites work: Q4865131
cites work: Q4697579
cites work: Q4693367
cites work: The ratio of the distance irredundance and domination numbers of a graph
cites work: Q4029974
cites work: Q4301754
cites work: Q4848783
cites work: Q4405916
cites work: The diversity of domination
cites work: Relations between packing and covering numbers of a tree
cites work: Q3353043
cites work: R -Domination in Graphs
cites work: On packing and covering numbers of graphs
cites work: Efficient parallel algorithms for r-dominating set and p-center problems on trees
description: scientific article; zbMATH DE number 897434