Disjoint dominating sets with a perfect matching

DOI10.1142/S1793830917500653zbMATH Open1386.05134arXiv1708.09774OpenAlexW2963264506MaRDI QIDQ4595255FDOQ4595255

Authors: William F. Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello 

Publication date: 29 November 2017

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: In this paper, we consider dominating sets $D$ and $D^{\prime }$ such that $D$ and $D^{\prime }$ are disjoint and there exists a perfect matching between them. Let $D{D}_{extrmm}(G)$ denote the cardinality of smallest such sets $D,D^{\prime }$ in $G$ (provided they exist, otherwise $D{D}_{extrmm}(G)=infty$). This concept was introduced in [Klostermeyer et al., Theory and Application of Graphs, 2017] in the context of studying a certain graph protection problem. We characterize the trees $T$ for which $D{D}_{extrmm}(T)$ equals a certain graph protection parameter and for which $D{D}_{extrmm}(T)=alpha(T)$, where $alpha(G)$ is the independence number of $G$. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number.

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

Recommendations

• A note on disjoint dominating sets in graphs
• On graphs with disjoint dominating and 2-dominating sets
• scientific article
• Graphs with disjoint dominating and paired-dominating sets
• A characterization of graphs with disjoint dominating and paired-dominating sets

zbMATH Keywords

matchingdominating setindependence numbergrid graph

Mathematics Subject Classification ID

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?)
• The domination number of grids
• Title not available (Why is that?)
• Remarks about disjoint dominating sets
• Eternal protection in grid graphs
• Eternal domination on \(3 \times n\) grid graphs
• Protecting a graph with mobile guards
• Title not available (Why is that?)
• Disjoint cliques and disjoint maximal independent sets of vertices in graphs
• Dynamic dominating sets: the eviction model for eternal domination
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dominating sets and independent sets in a tree.
• Eternal Independent Sets in Graphs
• Title not available (Why is that?)
• An Eternal Domination Problem in Grids
• A dynamic domination problem in trees

Cited In (2)

• Finding dominators via disjoint set union
• Self-stabilizing algorithm for two disjoint minimal dominating sets

This page was built for publication: Disjoint dominating sets with a perfect matching

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