On the cop number and the weak Meyniel conjecture for algebraic graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910919528808448 |
|---|---|
| author | Biswas, Arindam Saha, Jyoti Prakash |
| author_facet | Biswas, Arindam Saha, Jyoti Prakash |
| contents | We show that the cop number of the Cayley sum graph of a finite group $G$ with respect to a symmetric subset $S$ is at most twice its degree when the graph is connected, undirected. We also prove that a similar bound holds for the cop number of generalised Cayley graphs and twisted Cayley sum graphs under some conditions. These extend a result of Frankl to such graphs. Using the above bounds and a result of Bollobás--Janson--Riordan, we show that the weak Meyniel conjecture holds for these algebraic graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_05381 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the cop number and the weak Meyniel conjecture for algebraic graphs Biswas, Arindam Saha, Jyoti Prakash Combinatorics 05C57, 91A24, 91A43 We show that the cop number of the Cayley sum graph of a finite group $G$ with respect to a symmetric subset $S$ is at most twice its degree when the graph is connected, undirected. We also prove that a similar bound holds for the cop number of generalised Cayley graphs and twisted Cayley sum graphs under some conditions. These extend a result of Frankl to such graphs. Using the above bounds and a result of Bollobás--Janson--Riordan, we show that the weak Meyniel conjecture holds for these algebraic graphs. |
| title | On the cop number and the weak Meyniel conjecture for algebraic graphs |
| topic | Combinatorics 05C57, 91A24, 91A43 |
| url | https://arxiv.org/abs/2303.05381 |