The crossing number of the generalized Petersen graph \(P(10,4)\) is four. (English) Zbl 1053.05507

Summary: For \(n \geq 3\) and \(k \in \mathbb Z_n - \{0\}\) the generalized Petersen graph \(P(n,k)\) is defined on the set of vertices \(\{x_i, y_i\:i \in \mathbb Z_n\}\) with edges \(x_i x_{i+1}, x_i y_i\), and \(y_i y_{i+k}\). The crossing number of a graph is the least number of crossings of edges among all drawings of the graph in the plane.
In the note it is proved that the crossing number of the generalized Petersen graph \(P(10,4)\) is four. The author presents the drawing of \(P(10,4)\) with 4 crossings and proves that 4 crossings are needed using the fact that the crossing number of the Petersen graph \(P(5,2)\) is 2.


05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML


[1] FIORINI S.: On the crossing number of generalized Petersen graphs. Ann. Discrete Math. 30 (1986), 225-241. · Zbl 0595.05030
[2] McQUILLAN D.-RICHTER R. B.: On the crossing numbers of certain generalized Petersen graphs. Discrete Math. 104 (1992), 311-320. · Zbl 0756.05048 · doi:10.1016/0012-365X(92)90453-M
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.