Enumeration of Hamiltonian cycles in certain generalized Petersen graphs
type: Item
instance of: scholarly article
title: Enumeration of Hamiltonian cycles in certain generalized Petersen graphs
zbMATH Open document ID: 0626.05038
DOI: 10.1016/0095-8956(89)90064-6
author: Allen J. Schwenk
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: The generalized Petersen graph P(n,k) has vertex set \(V=\{u_ 0,u_ 1,...,u_{n-1}\), \(v_ 0,v_ 1,...,v_{n-1}\}\) and edge set \(E=\{u_ iu_{i+1},u_ iv_ i,v_ iv_{i+k}|\) for \(0\leq i\leq n-1\) with indices taken modulo \(n\}\). The classification of the Hamiltonicity of generalized Petersen graphs was begun by Watkins, continued by Bondy and Bannai, and completed by Alspach. We now determine the precise number of Hamiltonian cycles present in each of the graphs P(n,2). This more detailed information allows us to identify an infinite family of counterexamples to a conjecture of Greenwell and Kronk who had suggested a relation between uniquely 3-edge-colorable cubic graphs and the number of Hamiltonian cycles present.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 4016943
zbMATH Keywords: generalized Petersen graph
zbMATH Keywords: classification
zbMATH Keywords: Hamiltonicity
zbMATH Keywords: number of Hamiltonian cycles
Wikidata QID: Q55869274
MaRDI profile type: Publication
full work available at URL: 0095-8956(89)90064-6
OpenAlex ID: W2080276486
cites work: The classification of Hamiltonian generalized Petersen graphs
cites work: Hamiltonian cycles in generalized Petersen graphs
cites work: Variations on the Hamiltonian Theme
cites work: Q3216702
cites work: Q3874228
cites work: Uniquely Line Colorable Graphs
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
cites work: Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
cites work: A theorem on tait colorings with an application to the generalized Petersen graphs
description: scientific article; zbMATH DE number 4016943