A new bound for Vizing's conjecture
| Autor: | Krop, Elliot |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For any graph $G$, we define the power $\pi(G)$ as the minimum of the largest number of neighbors in a $\gamma$-set of $G$, of any vertex, taken over all $\gamma$-sets of $G$. We show that $\gamma(G\square H)\geq \frac{\pi(G)}{2\pi(G) -1}\gamma(G)\gamma(H)$. This implies that for any graphs $G$ and $H$, $\gamma(G\square H)\geq \frac{\gamma(G)}{2\gamma(G)-1}\gamma(G)\gamma(H)$, and if $G$ is claw-free or $P_4$-free, $\gamma(G\square H)\geq \frac{2}{3}\gamma(G)\gamma(H)$, where $\gamma(G)$ is the domination number of $G$. Comment: 7 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|