Upper bounds for inverse domination in graphs
In any graph $G$, the domination number $\gamma(G)$ is at most the independence number $\alpha(G)$. The \emph{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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Georgia Southern University
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/a781f4f3bd8947448ccf77849beb240d |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| id |
oai:doaj.org-article:a781f4f3bd8947448ccf77849beb240d |
|---|---|
| record_format |
dspace |
| spelling |
oai:doaj.org-article:a781f4f3bd8947448ccf77849beb240d2021-11-16T16:59:16ZUpper bounds for inverse domination in graphs2470-985910.20429/tag.2021.080205https://doaj.org/article/a781f4f3bd8947448ccf77849beb240d2021-08-01T00:00:00Zhttps://digitalcommons.georgiasouthern.edu/tag/vol8/iss2/5https://doaj.org/toc/2470-9859In any graph $G$, the domination number $\gamma(G)$ is at most the independence number $\alpha(G)$. The \emph{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$.Elliot KropJessica McDonaldGregory PuleoGeorgia Southern Universityarticleinverse dominationkulli-sigarkantiMathematicsQA1-939ENTheory and Applications of Graphs, Vol 8, Iss 2 (2021) |
| institution |
DOAJ |
| collection |
DOAJ |
| language |
EN |
| topic |
inverse domination kulli-sigarkanti Mathematics QA1-939 |
| spellingShingle |
inverse domination kulli-sigarkanti Mathematics QA1-939 Elliot Krop Jessica McDonald Gregory Puleo Upper bounds for inverse domination in graphs |
| description |
In any graph $G$, the domination number $\gamma(G)$ is at most the independence number $\alpha(G)$. The \emph{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$. |
| format |
article |
| author |
Elliot Krop Jessica McDonald Gregory Puleo |
| author_facet |
Elliot Krop Jessica McDonald Gregory Puleo |
| author_sort |
Elliot Krop |
| title |
Upper bounds for inverse domination in graphs |
| title_short |
Upper bounds for inverse domination in graphs |
| title_full |
Upper bounds for inverse domination in graphs |
| title_fullStr |
Upper bounds for inverse domination in graphs |
| title_full_unstemmed |
Upper bounds for inverse domination in graphs |
| title_sort |
upper bounds for inverse domination in graphs |
| publisher |
Georgia Southern University |
| publishDate |
2021 |
| url |
https://doaj.org/article/a781f4f3bd8947448ccf77849beb240d |
| work_keys_str_mv |
AT elliotkrop upperboundsforinversedominationingraphs AT jessicamcdonald upperboundsforinversedominationingraphs AT gregorypuleo upperboundsforinversedominationingraphs |
| _version_ |
1718426319783460864 |