Disjoint dominating sets with a perfect matching

DOI10.1142/S1793830917500653MaRDI QIDQ4595255zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

matchingdominating setindependence numbergrid graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5531984 (Why is no real title available?)
• scientific article; zbMATH DE number 3902703 (Why is no real title available?)
• scientific article; zbMATH DE number 1124600 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2174620 (Why is no real title available?)
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• A dynamic domination problem in trees
• An Eternal Domination Problem in Grids
• Closing the gap: eternal domination on \(3 \times n\) grids
• Disjoint cliques and disjoint maximal independent sets of vertices in graphs
• Dominating sets and independent sets in a tree.
• Dynamic dominating sets: the eviction model for eternal domination
• Eternal Independent Sets in Graphs
• Eternal domination on \(3 \times n\) grid graphs
• Eternal protection in grid graphs
• Protecting a graph with mobile guards
• Remarks about disjoint dominating sets
• The domination number of grids

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)