<p>A bicirculant is a regular graph that admits a semi-regular automorphism with two vertex orbits of the same size. By <i>m</i>, we denote the size of vertex orbits and by <i>d</i> the valence of a bicirculant. Furthermore, we denote by <i>s</i> the valence of the bipartite graph joining the two vertex orbits. In 1983, Brian Alspach proved that the only non-Hamiltonian generalized Petersen graphs are <i>G</i>(<i>m</i>,&#xa0;2) with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(m \equiv 5 \pmod 6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≡</mo> <mn>5</mn> <mspace width="4.44443pt" /> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mn>6</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. In a recent paper, we conjectured that this is the only exception among regular, connected bicirculants of degree <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(d &gt; 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>&gt;</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and we have verified the conjecture for the quartic bicirculants with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(s=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, also known as the generalized rose window graphs. In this paper, we develop tools and apply them for a partial verification of the conjecture. We show that the conjecture holds for all bicirculants with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(s \le 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>≤</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. As a consequence, we obtain that every connected bicirculant with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(s \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> is Hamiltonian if <i>m</i> is a product of at most three prime powers. In particular, every connected bicirculant with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(s \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> is Hamiltonian for even <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(m&lt;210\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>&lt;</mo> <mn>210</mn> </mrow> </math></EquationSource> </InlineEquation> and odd <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(m &lt; 1155\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>&lt;</mo> <mn>1155</mn> </mrow> </math></EquationSource> </InlineEquation>. Our results imply that many other families of bicirculants are Hamiltonian. For example, all bicirculants with <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(d-s\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>-</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> odd are Hamiltonian.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Hamiltonian Bicirculants

  • Simona Bonvicini,
  • Tomaž Pisanski,
  • Arjana Žitnik

摘要

A bicirculant is a regular graph that admits a semi-regular automorphism with two vertex orbits of the same size. By m, we denote the size of vertex orbits and by d the valence of a bicirculant. Furthermore, we denote by s the valence of the bipartite graph joining the two vertex orbits. In 1983, Brian Alspach proved that the only non-Hamiltonian generalized Petersen graphs are G(m, 2) with \(m \equiv 5 \pmod 6\) m 5 ( mod 6 ) . In a recent paper, we conjectured that this is the only exception among regular, connected bicirculants of degree \(d > 1\) d > 1 and we have verified the conjecture for the quartic bicirculants with \(s=2\) s = 2 , also known as the generalized rose window graphs. In this paper, we develop tools and apply them for a partial verification of the conjecture. We show that the conjecture holds for all bicirculants with \(s \le 2\) s 2 . As a consequence, we obtain that every connected bicirculant with \(s \ge 3\) s 3 is Hamiltonian if m is a product of at most three prime powers. In particular, every connected bicirculant with \(s \ge 3\) s 3 is Hamiltonian for even \(m<210\) m < 210 and odd \(m < 1155\) m < 1155 . Our results imply that many other families of bicirculants are Hamiltonian. For example, all bicirculants with \(d-s\) d - s odd are Hamiltonian.