Disjoint dominating and 2-dominating sets in graphs

DOI10.1016/J.DISOPT.2019.100553MaRDI QIDQ2299982zbMATHOpenAlexFDO

Authors Mateusz Miotk, Jerzy Topp, Paweł Żyliński

Publication date 24 February 2020

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.06129

zbMATH Keywords

2-dominationdominationNP-hardnesscertified domination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A graph $G$ is a $D!D_2$-graph if it has a pair $(D,D_2)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $D_2$ is a 2-dominating set of $G$. We provide several characterizations and hardness results concerning $D!D_2$-graphs.

Recommendations

• On graphs with disjoint dominating and 2-dominating sets
• Graphs with disjoint \(2\)-dominating sets
• scientific article; zbMATH DE number 5531984
• Domination versus disjunctive domination in graphs
• Algorithmic aspects of disjunctive domination in graphs

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 5531984 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 2109321 (Why is no real title available?)
• A Characterization of Graphs with Disjoint Dominating and Total Dominating Sets
• A characterization of graphs with disjoint dominating and paired-dominating sets
• A note on disjoint dominating sets in graphs
• A note on graphs with disjoint dominating and total dominating sets
• An independent dominating set in the complement of a minimum dominating set of a tree
• Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
• Disjoint dominating and total dominating sets in graphs
• Dominating and total dominating partitions in cubic graphs
• Graphs with equal domination and certified domination numbers
• Inverse domination in graphs
• On graphs with disjoint dominating and 2-dominating sets
• On the Computational Complexity of Combinatorial Problems
• Pairs of disjoint dominating sets and the minimum degree of graphs
• Parallel Processing and Applied Mathematics
• Partitioning a graph into a dominating set, a total dominating set, and something else
• Partitioning the vertices of a cubic graph into two total dominating sets
• Partitioning the vertices of a graph into two total dominating sets
• Paths, Trees, and Flowers
• Planar 3DM is NP-complete
• Remarks about disjoint dominating sets
• Semitotal domination in graphs: partition and algorithmic results
• Total domination in graphs
• Trees with two disjoint minimum independent dominating sets

Cited in

(11)

• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• On graphs with disjoint dominating and 2-dominating sets
• A characterization of graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
• Spanning trees with disjoint dominating and 2-dominating sets
• Some results for the two disjoint connected dominating sets problem
• Cutting Barnette graphs perfectly is hard
• Pairs of disjoint dominating sets and the minimum degree of graphs
• Graphs with disjoint \(2\)-dominating sets
• scientific article; zbMATH DE number 5531984 (Why is no real title available?)
• Minimal graphs with disjoint dominating and paired-dominating sets
• Algorithmic aspects of disjunctive domination in graphs

This page was built for publication: Disjoint dominating and 2-dominating sets in graphs

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