An algorithm to find two distance domination parameters in a graph

DOI10.1016/0166-218X(95)00057-XMaRDI QIDQ1917347zbMATH OpenFDO

Authors Michael A. Henning, H. C. Swart, Gerd H. Fricke, Ortrud R. Oellermann

Publication date 6 October 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(95)00057-X

\(n\)-independence number \(n\)-independent set algorithm distance distance domination total \(n\)-dominating set total \(n\)-domination number

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Cites work

Cited in

(5)

This page was built for publication: An algorithm to find two distance domination parameters in a graph

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