The crossing number of the generalized Petersen graph \(P[3k,k]\). (English) Zbl 1050.05034

Summary: R. K. Guy and F. Harary [Can. Math. Bull. 10, 493–496 (1967; Zbl 0161.20602)] have shown that, for \(k\geq 3\), the graph \(P[2k,k]\) is homeomorphic to the Möbius ladder \({M_{2k}}\), so that its crossing number is one; it is well known that \(P[2k,2]\) is planar. G. Exoo, F. Harary and J. Kabell [Math. Scand. 48, 184–188 (1981; Zbl 0442.05021)] have shown hat the crossing number of \(P[2k+1,2]\) is three, for \(k\geq 2.\) S. Fiorini [Ann. Discrete Math. 30, 225–241 (1986; Zbl 0595.05030)] and R. B. Richter and G. Salazar [Graphs Comb. 18, 381–394 (2002; Zbl 0999.05022)] have shown that \(P[9,3]\) has crossing number two and that \(P[3k,3]\) has crossing number \(k\), provided \(k\geq 4\). We extend this result by showing that \(P[3k,k]\) also has crossing number \(k\) for all \(k\geq 4\).


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