Schwenk, Allen J. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs. (English) Zbl 0626.05038 J. Comb. Theory, Ser. B 47, No. 1, 53-59 (1989). 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. Cited in 2 ReviewsCited in 14 Documents MSC: 05C45 Eulerian and Hamiltonian graphs 05C30 Enumeration in graph theory Keywords:generalized Petersen graph; classification; Hamiltonicity; number of Hamiltonian cycles PDFBibTeX XMLCite \textit{A. J. Schwenk}, J. Comb. Theory, Ser. B 47, No. 1, 53--59 (1989; Zbl 0626.05038) Full Text: DOI Online Encyclopedia of Integer Sequences: Number of Hamiltonian cycles in the generalized Petersen Graph P(n,2). References: [1] Alspach, B., The classification of hamiltonian generalized Petersen graphs, J. Combin. Theory Ser. B, 34, 293-312 (1983) · Zbl 0516.05034 [2] Bannai, K., Hamiltonian cycles in generalized Petersen graphs, J. Combin. Theory Ser. B, 24, 181-188 (1978) · Zbl 0376.05034 [3] Bondy, J. A., Variations on the hamiltonian theme, Canad. Math. Bull., 15, 57-62 (1972) · Zbl 0238.05115 [4] Chartrand, G.; Wilson, R. J., The Petersen graph, (Harary, F.; Maybee, J. S., Graphs and Applications (1985), Wiley: Wiley New York), 69-100 [5] Fiorini, S.; Wilson, R. J., Edge colorings of graphs, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press New York/London), 103-126 [6] Greenwell, D.; Kronk, H., Uniquely line-colorable graphs, Canad. Math. Bull., 16, 525-529 (1973) · Zbl 0275.05107 [7] Thomason, A. G., Hamiltonian cycles and uniquely edge colourable graphs, (Bollabás, B., Advances in Graph Theory (1978), North-Holland), 259-268 · Zbl 0382.05039 [8] Thomason, A. G., Cubic graphs with three hamiltonian cycles are not always uniquely edge colorable, J. Graph. Theory, 6, 219-221 (1982) · Zbl 0495.05025 [9] Watkins, M. E., A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, 6, 152-164 (1969) · Zbl 0175.50303 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.