NoteAll double generalized Petersen graphs are Hamiltonian

Research paper by XiuyunWang

Indexed on: 09 Nov '17Published on: 01 Dec '17Published in: Discrete Mathematics

Abstract

The double generalized Petersen graph DP(n,t)<math class="math"><mi is="true">D</mi><mi is="true">P</mi><mrow is="true"><mo is="true">(</mo><mi is="true">n</mi><mo is="true">,</mo><mi is="true">t</mi><mo is="true">)</mo></mrow>[/itex], n≥3<math class="math"><mi is="true">n</mi><mo is="true">≥</mo><mn is="true">3</mn>[/itex] and t∈Zn∖{0}<math class="math"><mi is="true">t</mi><mo is="true">∈</mo><msub is="true"><mrow is="true"><mi mathvariant="double-struck" is="true">Z</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">∖</mo><mrow is="true"><mo is="true">{</mo><mn is="true">0</mn><mo is="true">}</mo></mrow>[/itex], 2≤2t<n<math class="math"><mn is="true">2</mn><mo is="true">≤</mo><mn is="true">2</mn><mi is="true">t</mi><mo is="true">&lt;</mo><mi is="true">n</mi>[/itex], has vertex-set {xi,yi,ui,vi∣i∈Zn}<math class="math"><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">y</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">u</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">v</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">∣</mo><mi is="true">i</mi><mo is="true">∈</mo><msub is="true"><mrow is="true"><mi mathvariant="double-struck" is="true">Z</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">}</mo></mrow>[/itex], edge-set {{xi,xi+1},{yi,yi+1},{ui,vi+t},{vi,ui+t},{xi,ui},{yi,vi}∣i∈Zn}<math class="math"><mrow is="true"><mo is="true">{</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mi is="true">i</mi><mo is="true">+</mo><mn is="true">1</mn></mrow></msub><mo is="true">}</mo></mrow><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">y</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">y</mi></mrow><mrow is="true"><mi is="true">i</mi><mo is="true">+</mo><mn is="true">1</mn></mrow></msub><mo is="true">}</mo></mrow><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">u</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">v</mi></mrow><mrow is="true"><mi is="true">i</mi><mo is="true">+</mo><mi is="true">t</mi></mrow></msub><mo is="true">}</mo></mrow><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">v</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">u</mi></mrow><mrow is="true"><mi is="true">i</mi><mo is="true">+</mo><mi is="true">t</mi></mrow></msub><mo is="true">}</mo></mrow><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">u</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">}</mo></mrow><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">y</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">v</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">}</mo></mrow><mo is="true">∣</mo><mi is="true">i</mi><mo is="true">∈</mo><msub is="true"><mrow is="true"><mi mathvariant="double-struck" is="true">Z</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">}</mo></mrow>[/itex]. These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of DP(n,t)<math class="math"><mi is="true">D</mi><mi is="true">P</mi><mrow is="true"><mo is="true">(</mo><mi is="true">n</mi><mo is="true">,</mo><mi is="true">t</mi><mo is="true">)</mo></mrow>[/itex], and conjectured that all DP(n,t)<math class="math"><mi is="true">D</mi><mi is="true">P</mi><mrow is="true"><mo is="true">(</mo><mi is="true">n</mi><mo is="true">,</mo><mi is="true">t</mi><mo is="true">)</mo></mrow>[/itex] are Hamiltonian. In this paper, we prove this conjecture.