Domination parameters with number 2: interrelations and algorithmic consequences
From MaRDI portal
Publication:1682877
DOI10.1016/j.dam.2017.08.017zbMath1375.05193arXiv1511.00410OpenAlexW2963377580MaRDI QIDQ1682877
Luciano N. Grippo, Martín D. Safe, Martin Milanič, Boštjan Brešar, Flavia Bonomo-Braberman
Publication date: 6 December 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.00410
approximation algorithmsplit graphinapproximabilitytotal domination2-dominationrainbow dominationgraph dominationdouble dominationinteger domination
Related Items
A note on the k-tuple domination number of graphs, New bounds on the double domination number of trees, On the 2-domination Number of Cylinders with Small Cycles, Restrained {2}-domination in graphs, Relating the total \(\{2\}\)-domination number with the total domination number of graphs, Vector domination in split-indifference graphs, A note on double domination in graphs, Multiple Domination, Rainbow Domination in Graphs, New bounds on the double total domination number of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Roman domination on strongly chordal graphs
- Algorithmic aspects of \(k\)-tuple total domination in graphs
- Roman domination number of the Cartesian products of paths and cycles
- On rainbow domination numbers of graphs
- \(k\)-tuple total domination in graphs
- Some results on Vizing's conjecture and related problems
- Bounds on weak Roman and 2-rainbow domination numbers
- On integer domination in graphs and Vizing-like problems
- Rainbow domination in graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Rainbow domination on trees
- Note on 2-rainbow domination and Roman domination in graphs
- On the \(\{k\}\)-domination number of Cartesian products of graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- On the total \(\{k\}\)-domination number of Cartesian products of graphs
- Remarks about disjoint dominating sets
- Strong weak domination and domination balance in a graph
- Roman domination in graphs.
- Defending the Roman Empire---a new strategy
- An analysis of the greedy algorithm for the submodular set covering problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Nordhaus-Gaddum inequalities for domination in graphs
- Graph products and integer domination
- On the total \(\{ k\} \)-domination and total \(\{ k\} \)-domatic number of graphs
- On the approximability and exact algorithms for vector domination and related problems in graphs
- Difference between 2-rainbow domination and roman domination in graphs
- Pairs of disjoint dominating sets and the minimum degree of graphs
- Paired versus double domination in \(K_{1,r}\)-free graphs
- Integer domination of Cartesian product graphs
- A note on total domination and 2-rainbow domination in graphs
- Bounds on the \(k\)-domination number of a graph
- Rainbow domination and related problems on strongly chordal graphs
- On \(k\)-domination and \(j\)-independence in graphs
- Rainbow domination in the lexicographic product of graphs
- On the 2-rainbow domination in graphs
- 2-colorings in \(k\)-regular \(k\)-uniform hypergraphs
- Minimum 2-tuple dominating set of permutation graphs
- Degree Sequence Index Strategy
- Roman Domination on 2-Connected Graphs
- Strong Transversals in Hypergraphs and Double Total Domination in Graphs
- A threshold of ln n for approximating set cover
- Maximum-Minimum Sätze über Graphen
- Onk-domination and minimum degree in graphs
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- Hypergraph domination and strong independence
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Split Graphs Having Dilworth Number Two
- Towards a theory of domination in graphs
- Paired-domination in graphs
- On dominating the Cartesian product of a graph and K2
- Total Domination in Graphs
- Analytical approach to parallel repetition
- R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
- Exact double domination in graphs