All generalized rose window graphs are hamiltonian
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912555840045056 |
|---|---|
| author | Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana |
| author_facet | Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana |
| contents | A bicirculant is a regular, $d$-valent graph that admits a semiregular automorphism of order $m$ having two vertex-orbits of size $m$. The vertices of each orbit induce a circulant graph of order $m$ and the remaining edges span a regular bipartite graph of valence, say $s$, $1 \leq s \leq d$, connecting the two vertex-orbits. Generalized Petersen graphs constitute a prominent family of bicirculants, with $d = 3$ and $s = 1$. In 1983, Brian Alspach proved that all generalized Petersen graphs are hamiltonian, except for the family $G(m, 2)$ with $m\equiv 5\pmod 6$. In this paper we conjecture that among all connected bicirculants of valence at least 2, there are no other exceptions. It follows from various sources that the conjecture is true for all cubic bicirculants. In this paper we prove the conjecture for quartic bicirulants with $s = 2$, also known as the generalized rose window graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16205 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | All generalized rose window graphs are hamiltonian Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana Combinatorics 05C45, 05C76, 05C70, 05C25, 05E18 A bicirculant is a regular, $d$-valent graph that admits a semiregular automorphism of order $m$ having two vertex-orbits of size $m$. The vertices of each orbit induce a circulant graph of order $m$ and the remaining edges span a regular bipartite graph of valence, say $s$, $1 \leq s \leq d$, connecting the two vertex-orbits. Generalized Petersen graphs constitute a prominent family of bicirculants, with $d = 3$ and $s = 1$. In 1983, Brian Alspach proved that all generalized Petersen graphs are hamiltonian, except for the family $G(m, 2)$ with $m\equiv 5\pmod 6$. In this paper we conjecture that among all connected bicirculants of valence at least 2, there are no other exceptions. It follows from various sources that the conjecture is true for all cubic bicirculants. In this paper we prove the conjecture for quartic bicirulants with $s = 2$, also known as the generalized rose window graphs. |
| title | All generalized rose window graphs are hamiltonian |
| topic | Combinatorics 05C45, 05C76, 05C70, 05C25, 05E18 |
| url | https://arxiv.org/abs/2504.16205 |