Disjoint dominating and 2-dominating sets in graphs

DOI10.1016/J.DISOPT.2019.100553zbMATH Open1506.05161arXiv1903.06129OpenAlexW2969695232MaRDI QIDQ2299982FDOQ2299982

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

Publication date: 24 February 2020

Published in: Discrete Optimization (Search for Journal in Brave)

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.

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths, Trees, and Flowers
• Planar 3DM is NP-complete
• Total Domination in Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Computational Complexity of Combinatorial Problems
• Remarks about disjoint dominating sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Disjoint dominating and total dominating sets in graphs
• Inverse domination in graphs
• Trees with two disjoint minimum independent dominating sets
• Parallel Processing and Applied Mathematics
• A characterization of graphs with disjoint dominating and paired-dominating sets
• Pairs of disjoint dominating sets and the minimum degree of graphs
• Partitioning a graph into a dominating set, a total dominating set, and something else
• A Characterization of Graphs with Disjoint Dominating and Total Dominating Sets
• An independent dominating set in the complement of a minimum dominating set of a tree
• Dominating and total dominating partitions in cubic graphs
• Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitioning the vertices of a cubic graph into two total dominating sets
• Partitioning the Vertices of a Graph into Two Total Dominating Sets
• On graphs with disjoint dominating and 2-dominating sets
• Graphs with equal domination and certified domination numbers

Cited In (8)

• Cutting Barnette graphs perfectly is hard
• Graphs with disjoint 2-dominating sets
• A characterization of graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
• Pairs of disjoint dominating sets and the minimum degree of graphs
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• Minimal graphs with disjoint dominating and paired-dominating sets
• Spanning trees with disjoint dominating and 2-dominating sets
• Title not available (Why is that?)

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)