Restrained domination in trees
A set \(S\subseteq V\) is a restrained dominating set of the graph \(G= (V,E)\) if every vertex of \(G\) not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V-S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the smallest cardinality of a restrained dominating set of \(G\). \textit{G. S. Domke}, \textit{H. J. Hatting}, \textit{S. T. Hedetniemi}, \textit{R. C. Laskar} and \textit{L. R. Markus} [Discrete Math. 203, No. 1-3, 61-69 (1999)] proved that \(\gamma_r(T)\geq \lceil (n+2)/3\rceil\) when \(T\) is the path of order \(n\). Here this is shown to hold for all trees of order \(n\). A constructive characterization of the extremal trees is given.
- On a conjecture involving a bound for the total restrained domination number of a graph
- On bondage numbers of graphs: a survey with some comments
- Some progress on the restrained Roman domination
- Restrained domination in self-complementary graphs
- The product of the restrained domination numbers of a graph and its complement
- On equality in an upper bound for the restrained and total domination numbers of a graph
- Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
- Trees with equal domination and restrained domination numbers
- Secure restrained domination in graphs
- On weak and restrained domination in trees
- Weighted restrained domination in subclasses of planar graphs
- All graphs with restrained domination number three less than their order
- A general method in the theory of domination in graphs
- Restrained domination excellent trees.
- A lower bound of k-component restrained domination number in trees
- A note on restrained domination in trees.
- scientific article; zbMATH DE number 5138367 (Why is no real title available?)
- Total restrained domination in graphs of diameter 2 or 3
- NP-completeness and APX-completeness of restrained domination in graphs
- Further results on secure restrained domination in graphs
- scientific article; zbMATH DE number 7509363 (Why is no real title available?)
- Restrained Roman domination in graphs
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- Bounds on the total restrained domination number of a graph
- Strong restrained domination number on trees and product of graphs: An algorithmic approach
- A probabilistic algorithm for bounding the total restrained domination number of a \(K_{1 , \ell}\) -free graph
- A note on total co-independent domination in trees
- Global restrained Roman domination in graphs
- Fractional restrained domination
- Restrained domination in cubic graphs
- Analyzing restrained pitchfork domination across path-related graph structures
- Total restrained domination in trees
- Total restrained domination in graphs with minimum degree two
- An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
- Restrained domination in claw-free graphs with minimum degree at least two
- Restrained bondage in graphs
This page was built for publication: Restrained domination in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969775)
