Upper bounds for inverse domination in graphs
| Autor: | Krop, Elliot, McDonald, Jessica, Puleo, Gregory J. |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Theory and Applications of Graphs, 8(2): Article 5, (2021) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.20429/tag.2021.080205 |
| Popis: | In any graph $G$, the domination number $\gamma(G)$ is at most the independence number $\alpha(G)$. The Inverse Domination Conjecture says that, in any isolate-free $G$, there exists pair of vertex-disjoint dominating sets $D, D'$ with $|D|=\gamma(G)$ and $|D'| \leq \alpha(G)$. Here we prove that this statement is true if the upper bound $\alpha(G)$ is replaced by $\frac{3}{2}\alpha(G) - 1$ (and $G$ is not a clique). We also prove that the conjecture holds whenever $\gamma(G)\leq 5$ or $|V(G)|\leq 16$. Comment: 9 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|