Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2016
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/1608.02107 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911139125788672 |
|---|---|
| author | Krop, Elliot Wolff, Kimber |
| author_facet | Krop, Elliot Wolff, Kimber |
| contents | For any graph $G$, we define the power $π(G)$ as the minimum of the largest number of neighbors in a $γ$-set of $G$, of any vertex, taken over all $γ$-sets of $G$. We show that $γ(G\square H)\geq \frac{π(G)}{2π(G) -1}γ(G)γ(H)$. Our methods allow us to prove the following statements for any graphs $G$ and $H$, (1) $γ(G\square H)\geq \frac{\lceil \frac{γ(G)}{2}\rceil}{2\lceil \frac{γ(G)}{2}\rceil-1}γ(G)γ(H)$ for odd $γ(G)$, (2) $γ(G\square H)\geq \frac{γ(G)}{2γ(G)-2}γ(G)γ(H)$, for even $γ(G)$, and (3) a short proof of Vizing's conjecture where $γ(G)=3$. Our argument relies on establishing efficient correspondences between dominating vertices and subsets of their neighborhoods and then showing a sufficient number of dominating vertices that horizontally dominate vertically undominated cells. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1608_02107 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | A new bound for Vizing's conjecture Krop, Elliot Wolff, Kimber Combinatorics 05C69 For any graph $G$, we define the power $π(G)$ as the minimum of the largest number of neighbors in a $γ$-set of $G$, of any vertex, taken over all $γ$-sets of $G$. We show that $γ(G\square H)\geq \frac{π(G)}{2π(G) -1}γ(G)γ(H)$. Our methods allow us to prove the following statements for any graphs $G$ and $H$, (1) $γ(G\square H)\geq \frac{\lceil \frac{γ(G)}{2}\rceil}{2\lceil \frac{γ(G)}{2}\rceil-1}γ(G)γ(H)$ for odd $γ(G)$, (2) $γ(G\square H)\geq \frac{γ(G)}{2γ(G)-2}γ(G)γ(H)$, for even $γ(G)$, and (3) a short proof of Vizing's conjecture where $γ(G)=3$. Our argument relies on establishing efficient correspondences between dominating vertices and subsets of their neighborhoods and then showing a sufficient number of dominating vertices that horizontally dominate vertically undominated cells. |
| title | A new bound for Vizing's conjecture |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/1608.02107 |