All generalized rose window graphs are hamiltonian

Bonvicini, Simona (author), Pisanski, Tomaž (author), Žitnik, Arjana (author)

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 \le s \le 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$ $(\mod 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.

• Language: English
• Keywords: Hamilton cycle, generalized rose window graphs, bicirculants, generalized Petersen graphs, Lovász conjecture
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.04.2026
• Year: 2026
• Number of pages: 20 str.
• Numbering: Vol. 42, iss. 2, article no. 27
• PID: 20.500.12556/RUL-179843
• UDC: 519.17
• ISSN on article: 0911-0119
• DOI: 10.1007/s00373-026-03016-w
• COBISS.SI-ID: 269644547
• Publication date in RUL: 25.02.2026

Record is a part of a journal

• Title: Graphs and combinatorics
• Shortened title: Graphs comb.
• Publisher: Springer Nature
• ISSN: 0911-0119
• COBISS.SI-ID: 25536512

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: Hamiltonov cikel, posplošeni rozetni grafi, bicirkulanti, posplošeni Petersenovi grafi, Lovászova domneva