Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2503.07400 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912569844826112 |
|---|---|
| author | Lukoťka, Robert Máčajová, Edita Rajník, Jozef |
| author_facet | Lukoťka, Robert Máčajová, Edita Rajník, Jozef |
| contents | A graph $G$ is cyclically $c$-edge-connected if there is no set of fewer than $c$ edges that disconnects $G$ into at least two cyclic components. We prove that if a $(k, g)$-cage $G$ has at most $2M(k, g) - g^2$ vertices, where $M(k, g)$ is the Moore bound, then $G$ is cyclically $(k - 2)g$-edge-connected, which equals the number of edges separating a $g$-cycle, and every cycle-separating $(k - 2)g$-edge-cut in $G$ separates a cycle of length $g$. In particular, this is true for unknown cages with $(k, g) \in \{(3, 13), (3, 14), (3, 15), (4, 9), (4, 10)$, $(4, 11),$ $(5, 7), (5, 9), (5, 10), (5, 11), (6, 7), (9, 7)\}$ and also the potential missing Moore graph with degree $57$ and diameter $2$.
Keywords: cage, cyclic connectivity, girth, lower bound |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07400 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cages and cyclic connectivity Lukoťka, Robert Máčajová, Edita Rajník, Jozef Combinatorics A graph $G$ is cyclically $c$-edge-connected if there is no set of fewer than $c$ edges that disconnects $G$ into at least two cyclic components. We prove that if a $(k, g)$-cage $G$ has at most $2M(k, g) - g^2$ vertices, where $M(k, g)$ is the Moore bound, then $G$ is cyclically $(k - 2)g$-edge-connected, which equals the number of edges separating a $g$-cycle, and every cycle-separating $(k - 2)g$-edge-cut in $G$ separates a cycle of length $g$. In particular, this is true for unknown cages with $(k, g) \in \{(3, 13), (3, 14), (3, 15), (4, 9), (4, 10)$, $(4, 11),$ $(5, 7), (5, 9), (5, 10), (5, 11), (6, 7), (9, 7)\}$ and also the potential missing Moore graph with degree $57$ and diameter $2$. Keywords: cage, cyclic connectivity, girth, lower bound |
| title | Cages and cyclic connectivity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.07400 |