On the domination number of the cartesian product of the path graph and any pair of graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911743963299840 |
|---|---|
| author | Tout, Omar |
| author_facet | Tout, Omar |
| contents | It is known that for any graph $G,$ $γ(G\square P_2)\geq γ(G)$ where $γ$ stands for the domination number, $\square$ for the cartesian product and $P_2$ is the path graph on two vertices. In an attempt to prove Vizing's conjecture, Clark and Suen proved in $2000$ that $γ(X\square Y)\geq \frac{1}{2}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ Combining these two inequalities, we have $γ(X\square Y\square P_2)\geq \frac{1}{2}γ(X)γ(Y).$ In this paper, we use space projections to improve this lower bound and show that $γ(X\square Y\square P_2)\geq \frac{2}{3}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ In addition, we prove that $γ(X\square Y\square P_{n})\geq c_nγ(X)γ(Y)γ(P_{n}),$ where $c_n$ is almost $\frac{3}{4}$ when $n$ is big enough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_09208 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the domination number of the cartesian product of the path graph and any pair of graphs Tout, Omar Combinatorics 05C69, 05C76 It is known that for any graph $G,$ $γ(G\square P_2)\geq γ(G)$ where $γ$ stands for the domination number, $\square$ for the cartesian product and $P_2$ is the path graph on two vertices. In an attempt to prove Vizing's conjecture, Clark and Suen proved in $2000$ that $γ(X\square Y)\geq \frac{1}{2}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ Combining these two inequalities, we have $γ(X\square Y\square P_2)\geq \frac{1}{2}γ(X)γ(Y).$ In this paper, we use space projections to improve this lower bound and show that $γ(X\square Y\square P_2)\geq \frac{2}{3}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ In addition, we prove that $γ(X\square Y\square P_{n})\geq c_nγ(X)γ(Y)γ(P_{n}),$ where $c_n$ is almost $\frac{3}{4}$ when $n$ is big enough. |
| title | On the domination number of the cartesian product of the path graph and any pair of graphs |
| topic | Combinatorics 05C69, 05C76 |
| url | https://arxiv.org/abs/2312.09208 |