Cops and robbers on directed and undirected abelian Cayley graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908615215939584 |
|---|---|
| author | Bradshaw, Peter Hosseini, Seyyed Aliasghar Turcotte, Jérémie |
| author_facet | Bradshaw, Peter Hosseini, Seyyed Aliasghar Turcotte, Jérémie |
| contents | We show that the cop number of directed and undirected Cayley graphs on abelian groups has an upper bound of the form of $O(\sqrt{n})$, where $n$ is the number of vertices, by introducing a refined inductive method. With our method, we improve the previous upper bound on cop number for undirected Cayley graphs on abelian groups, and we establish an upper bound on the cop number of directed Cayley graphs on abelian groups. We also use Cayley graphs on abelian groups to construct new \emph{Meyniel extremal families}, which contain graphs of every order $n$ with cop number $Θ(\sqrt{n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_05342 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Cops and robbers on directed and undirected abelian Cayley graphs Bradshaw, Peter Hosseini, Seyyed Aliasghar Turcotte, Jérémie Combinatorics Group Theory 05C57 (Primary) 05C20, 05C25, 05E15 (Secondary) We show that the cop number of directed and undirected Cayley graphs on abelian groups has an upper bound of the form of $O(\sqrt{n})$, where $n$ is the number of vertices, by introducing a refined inductive method. With our method, we improve the previous upper bound on cop number for undirected Cayley graphs on abelian groups, and we establish an upper bound on the cop number of directed Cayley graphs on abelian groups. We also use Cayley graphs on abelian groups to construct new \emph{Meyniel extremal families}, which contain graphs of every order $n$ with cop number $Θ(\sqrt{n})$. |
| title | Cops and robbers on directed and undirected abelian Cayley graphs |
| topic | Combinatorics Group Theory 05C57 (Primary) 05C20, 05C25, 05E15 (Secondary) |
| url | https://arxiv.org/abs/1909.05342 |