Minimal graphs with disjoint dominating and paired-dominating sets
| Autor: | Henning, Michael A., Topp, Jerzy |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Discussiones Mathematicae Graph Theory 41 (2021) 827-847 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.7151/dmgt.2328 |
| Popis: | A subset $D\subseteq V_G$ is a dominating set of $G$ if every vertex in $V_G-D$ has a~neighbor in $D$, while $D$ is a paired-dominating set of $G$ if $D$ is a~dominating set and the subgraph induced by $D$ contains a perfect matching. A graph $G$ is a $D\!P\!D\!P$-graph if it has a pair $(D,P)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $P$ is a paired-dominating set of $G$. The study of the $D\!P\!D\!P$-graphs was initiated by Southey and Henning (Cent. Eur. J. Math. 8 (2010) 459--467; J. Comb. Optim. 22 (2011) 217--234). In this paper, we provide conditions which ensure that a graph is a $D\!P\!D\!P$-graph. In particular, we characterize the minimal $D\!P\!D\!P$-graphs. Comment: 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|