×

Enumeration of Hamiltonian cycles in certain generalized Petersen graphs. (English) Zbl 0626.05038

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.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI

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.